/* Copyright 2006 Garrett Rooney.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef _TREE_H
#define _TREE_H

#include <stdbool.h>

#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */

/* a vtable containing callbacks that allow a binary tree node to
 * compare the contents of two nodes (thus determining ordering) and
 * clean up the contents of a node.
 */
typedef struct {
  int (*compare)(void *a, void *b);
  void (*cleanup)(void *content, void *baton);
} etl_tree_vtbl_t;

/* a node in the tree.  holds a pointer to the tree's vtable, the
 * actual data stored in the node, and pointers to the left and right
 * children, if there are any.
 */
typedef struct etl_tree_node_t {
  etl_tree_vtbl_t *vtbl;

  void *content;

  struct etl_tree_node_t *left;

  struct etl_tree_node_t *right;

  struct etl_tree_node_t *parent;
} etl_tree_node_t;

/* return the node in this tree that contains value, or NULL if it
 * doesn't exist.
 */
etl_tree_node_t *
etl_tree_find(etl_tree_node_t *root, void *value);

/* insert value into the tree, returning true if it is added
 * successfully or false if it was already there.
 */
bool
etl_tree_insert(etl_tree_node_t *root, void *value);

/* create a new node, holding value and using vtbl for ordering and
 * cleanup.
 */
etl_tree_node_t *
etl_tree_create(void *value, etl_tree_vtbl_t *vtbl);

/* destroy a tree, deallocating all memory in it using its cleanup
 * function.  the baton will be passed to the cleanup function.
 */
void
etl_tree_destroy(etl_tree_node_t *root, void *baton);

/* iterate over the nodes in a tree, calling callback and passing it
 * baton for each node.
 */
void
etl_tree_traverse(etl_tree_node_t *root,
                  void (*callback)(etl_tree_node_t *, void *),
                  void *baton);

#ifdef __cplusplus
}
#endif /* __cplusplus */

#endif /* _TREE_H */