1 /************************** toolbox/tree.c *************************************
3 Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
5 See file COPYRIGHT for information on usage and disclaimer of warranties
7 Not documented, see tree.h.
9 Authors: Reinhard Grafl EMAIL: cacao@complang.tuwien.ac.at
11 Last Change: 1996/10/03
13 *******************************************************************************/
22 tree *tree_new (treeelementcomperator comperator)
27 t -> comperator = comperator;
34 tree *tree_dnew (treeelementcomperator comperator)
36 tree *t = DNEW (tree);
39 t -> comperator = comperator;
47 static void tree_nodefree (treenode *tn)
50 tree_nodefree (tn -> left);
51 tree_nodefree (tn -> right);
55 void tree_free (tree *t)
57 assert (! t -> usedump);
59 tree_nodefree ( t -> top );
64 static treenode *tree_nodeadd
65 (tree *t, treenode *par, treenode *n, void *element, void *key)
68 if ( t-> usedump ) n = DNEW (treenode);
69 else n = NEW (treenode);
74 n -> element = element;
77 if ( t->comperator (key, n -> element) < 0 ) {
78 n -> left = tree_nodeadd (t, n, n -> left, element, key);
81 n -> right = tree_nodeadd (t, n, n -> right, element, key);
88 void tree_add (tree *t, void *element, void *key)
90 t -> top = tree_nodeadd (t, NULL, t -> top, element, key);
91 t -> active = t -> top;
95 static treenode *tree_nodefind (tree *t, treenode *n, void *key)
101 way = t -> comperator (key, n->element);
102 if (way==0) return n;
103 if (way<0) return tree_nodefind (t, n -> left, key);
104 else return tree_nodefind (t, n -> right, key);
108 void *tree_find (tree *t, void *key)
110 treenode *tn = tree_nodefind (t, t -> top, key);
111 if (!tn) return NULL;
114 return tn -> element;
119 void *tree_this (tree *t)
121 if (! t->active) return NULL;
122 return t->active->element;
126 static treenode *leftmostnode(treenode *t)
128 while (t->left) t=t->left;
132 void *tree_first (tree *t)
134 treenode *a = t->top;
137 a = leftmostnode (a);
142 void *tree_next (tree *t)
144 treenode *a = t->active;
145 treenode *comefrom = NULL;
150 if (a->left && (a->left == comefrom)) {
155 if (a->right && (a->right != comefrom) ) {
156 a = leftmostnode(a->right);