/cvmfs/atlas.cern.ch/repo/sw/ASG/AnalysisBase/2.4.31/CxxUtils/CxxUtils/libcalg/avl-tree.h
Go to the documentation of this file.00001 /* 00002 00003 Copyright (c) 2005-2008, Simon Howard 00004 00005 Permission to use, copy, modify, and/or distribute this software 00006 for any purpose with or without fee is hereby granted, provided 00007 that the above copyright notice and this permission notice appear 00008 in all copies. 00009 00010 THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL 00011 WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED 00012 WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE 00013 AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR 00014 CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 00015 LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 00016 NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 00017 CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 00018 00019 */ 00020 00054 #ifndef ALGORITHM_AVLTREE_H 00055 #define ALGORITHM_AVLTREE_H 00056 00057 #ifdef __cplusplus 00058 extern "C" { 00059 #endif 00060 00067 typedef struct _AVLTree AVLTree; 00068 00073 typedef void *AVLTreeKey; 00074 00079 typedef void *AVLTreeValue; 00080 00085 #define AVL_TREE_NULL ((void *) 0) 00086 00097 typedef struct _AVLTreeNode AVLTreeNode; 00098 00103 typedef enum { 00104 AVL_TREE_NODE_LEFT = 0, 00105 AVL_TREE_NODE_RIGHT = 1 00106 } AVLTreeNodeSide; 00107 00119 typedef int (*AVLTreeCompareFunc)(AVLTreeValue value1, AVLTreeValue value2); 00120 00129 AVLTree *avl_tree_new(AVLTreeCompareFunc compare_func); 00130 00137 void avl_tree_free(AVLTree *tree); 00138 00150 AVLTreeNode *avl_tree_insert(AVLTree *tree, AVLTreeKey key, AVLTreeValue value); 00151 00159 void avl_tree_remove_node(AVLTree *tree, AVLTreeNode *node); 00160 00172 int avl_tree_remove(AVLTree *tree, AVLTreeKey key); 00173 00184 AVLTreeNode *avl_tree_lookup_node(AVLTree *tree, AVLTreeKey key); 00185 00199 AVLTreeValue avl_tree_lookup(AVLTree *tree, AVLTreeKey key); 00200 00209 AVLTreeNode *avl_tree_root_node(AVLTree *tree); 00210 00218 AVLTreeKey avl_tree_node_key(AVLTreeNode *node); 00219 00227 AVLTreeValue avl_tree_node_value(AVLTreeNode *node); 00228 00238 AVLTreeNode *avl_tree_node_child(AVLTreeNode *node, AVLTreeNodeSide side); 00239 00248 AVLTreeNode *avl_tree_node_parent(AVLTreeNode *node); 00249 00257 int avl_tree_subtree_height(AVLTreeNode *node); 00258 00270 AVLTreeValue *avl_tree_to_array(AVLTree *tree); 00271 00279 int avl_tree_num_entries(AVLTree *tree); 00280 00281 #ifdef __cplusplus 00282 } 00283 #endif 00284 00285 #endif /* #ifndef ALGORITHM_AVLTREE_H */ 00286
