/*
 * frost_tree.h
 *
 *  Created on: Jul 3, 2012
 *      Author: ergino
 */

#ifndef FROST_TREE_H_
#define FROST_TREE_H_
#include "frost_common.h"
#include "frost/frost_basictypes.h"
#include "frost_node.h"

typedef struct _FROST_Tree  FROST_Tree;


typedef frost_bool (*FROSTTraverseFunc) (frost_pointer  key,
                                   frost_pointer  value,
                                   frost_pointer  data);

#ifdef __cplusplus
extern "C"
{
#endif

/* Balanced binary trees
 */
FROST_Tree*   frost_tree_new             (FROSTCompareFunc      key_compare_func);
FROST_Tree*   frost_tree_new_with_data   (FROSTCompareDataFunc  key_compare_func,
                                 frost_pointer          key_compare_data);
FROST_Tree*   frost_tree_new_full        (FROSTCompareDataFunc  key_compare_func,
                                 frost_pointer          key_compare_data,
                                 FROSTDestroyNotify    key_destroy_func,
                                 FROSTDestroyNotify    value_destroy_func);
FROST_Tree*   frost_tree_ref             (FROST_Tree            *tree);
void     frost_tree_unref           (FROST_Tree            *tree);
void     frost_tree_destroy         (FROST_Tree            *tree);
void     frost_tree_insert          (FROST_Tree            *tree, frost_pointer          key, frost_pointer          value);
void     frost_tree_replace         (FROST_Tree            *tree, frost_pointer          key, frost_pointer          value);
frost_bool frost_tree_remove          (FROST_Tree            *tree, frost_constpointer     key);
frost_bool frost_tree_steal           (FROST_Tree            *tree, frost_constpointer     key);
frost_pointer frost_tree_lookup          (FROST_Tree            *tree, frost_constpointer     key);
frost_bool frost_tree_lookup_extended (FROST_Tree            *tree,
                                 frost_constpointer     lookup_key,
                                 frost_pointer         *orig_key,
                                 frost_pointer         *value);
void     frost_tree_foreach         (FROST_Tree            *tree,
                                 FROSTTraverseFunc     func,
                                 frost_pointer      user_data);

void     frost_tree_traverse        (FROST_Tree            *tree,
                                 FROSTTraverseFunc     traverse_func,
                                 FROSTTraverseType     traverse_type,
                                 frost_pointer          user_data);

frost_pointer frost_tree_search          (FROST_Tree            *tree,
                                 FROSTCompareFunc      search_func,
                                 frost_constpointer     user_data);
frost_int     frost_tree_height          (FROST_Tree            *tree);
frost_int     frost_tree_nnodes          (FROST_Tree            *tree);

#ifdef __cplusplus
}
#endif

#endif /* FROST_TREE_H_ */
