LibRCG  3.1.1
treemap.h
Go to the documentation of this file.
1 
30 #ifndef _TREEMAP_H_
31 #define _TREEMAP_H_
32 
33 #include "iterator.h"
34 
38 typedef enum eBFactor{L,E,R}BFactor;
39 
43 typedef struct sTreeNode
44 {
46  void* key;
48  void* value;
52  struct sTreeNode* super;
54  struct sTreeNode* left;
56  struct sTreeNode* right;
57 }STreeNode;
58 
63 
67 typedef struct sTreeMap
68 {
70  int(*keyComp)(void*,void*);
72  int size;
75 }STreeMap;
76 
80 typedef STreeMap* TreeMap;
81 
82 //==============================================================================
83 
94 TreeMap newTree(int(*keyComp)(void*,void*));
95 
106 int treeSetKComp(TreeMap tree,int(*keyComp)(void*,void*));
107 
117 void treeDelete(TreeMap tree);
118 
136 int treeInsert(TreeMap tree,void* key,void* value,int replace);
137 
159 int treeRemove(TreeMap tree,void* key,void** value,void(*del)(void*));
160 
181 int treeGet(TreeMap tree,void* key,void** value);
182 
196 int treeIsBalanced(TreeMap tree);
197 
206 int treeHeight(TreeMap tree);
207 
216 int treeSize(TreeMap tree);
217 
230 int treeInOrder(TreeMap tree,void(*fun)(void*,void*));
231 
244 int treePreOrder(TreeMap tree,void(*fun)(void*,void*));
245 
258 int treePostOrder(TreeMap tree,void(*fun)(void*,void*));
259 
272 
285 
286 #endif
int treeRemove(TreeMap tree, void *key, void **value, void(*del)(void *))
Removes the mapping for a key from a tree.
Definition: treemap.c:539
int treeInOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (inorder traversal).
Definition: treemap.c:654
int treeInsert(TreeMap tree, void *key, void *value, int replace)
Associates a value to a key in a tree.
Definition: treemap.c:413
BFactor
Type that defines the balance factor of a tree.
Definition: treemap.h:38
void * key
Node's key.
Definition: treemap.h:46
void treeDelete(TreeMap tree)
Deletes a tree.
Definition: treemap.c:318
Iterator treeValues(TreeMap tree)
Creates an iterator from the values of a tree.
Definition: treemap.c:783
struct sTreeNode * super
Node's parent.
Definition: treemap.h:52
struct sTreeNode * left
Node's left subtree.
Definition: treemap.h:54
Iterator treeKeys(TreeMap tree)
Creates an iterator from the keys of a tree.
Definition: treemap.c:745
Iterator structure.
Definition: iterator.h:17
void * value
Node's value.
Definition: treemap.h:48
int treePostOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (postorder traversal).
Definition: treemap.c:711
TreeMap newTree(int(*keyComp)(void *, void *))
Creates a tree.
Definition: treemap.c:273
int treeGet(TreeMap tree, void *key, void **value)
Provides the mapping for a key from a tree.
Definition: treemap.c:550
BFactor bf
Node's balance factor.
Definition: treemap.h:50
int treeIsBalanced(TreeMap tree)
Checks if a tree is balanced.
Definition: treemap.c:593
int size
Number of elements of this tree.
Definition: treemap.h:72
int treeSetKComp(TreeMap tree, int(*keyComp)(void *, void *))
Sets the comparison function of this tree.
Definition: treemap.c:291
STreeMap * TreeMap
Tree definition.
Definition: treemap.h:80
int treeSize(TreeMap tree)
Returns the number of elements present in a tree.
Definition: treemap.c:629
Tree structure.
Definition: treemap.h:67
Tree node structure.
Definition: treemap.h:43
int treeHeight(TreeMap tree)
Returns the height of a tree.
Definition: treemap.c:622
int treePreOrder(TreeMap tree, void(*fun)(void *, void *))
Applies a function to the elements of an tree (preorder traversal).
Definition: treemap.c:683
struct sTreeNode * right
Node's right subtree.
Definition: treemap.h:56
Implementation of an iterator.
STreeNode * TreeNode
Tree node definition.
Definition: treemap.h:62
TreeNode root
Root node of this tree.
Definition: treemap.h:74

LibRCG © 2004-2015   Rui Carlos Gonçalves