src/toolbox/tree.c

   1 /************************** toolbox/tree.c *************************************
   2
   3         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
   4
   5         See file COPYRIGHT for information on usage and disclaimer of warranties
   6
   7         Not documented, see tree.h.
   8
   9         Authors: Reinhard Grafl      EMAIL: cacao@complang.tuwien.ac.at
  10
  11         Last Change: 1996/10/03
  12
  13 *******************************************************************************/
  14
  15 #include <stdio.h>
  16 #include <assert.h>
  17
  18 #include "memory.h"
  19 #include "tree.h"
  20
  21
  22 tree *tree_new (treeelementcomperator comperator)
  23 {
  24         tree *t = NEW (tree);
  25
  26         t -> usedump = 0;
  27         t -> comperator = comperator;
  28         t -> top = NULL;
  29         t -> active = NULL;
  30
  31         return t;
  32 }
  33
  34 tree *tree_dnew (treeelementcomperator comperator)
  35 {
  36         tree *t = DNEW (tree);
  37
  38         t -> usedump = 1;
  39         t -> comperator = comperator;
  40         t -> top = NULL;
  41         t -> active = NULL;
  42
  43         return t;
  44 }
  45
  46
  47 static void tree_nodefree (treenode *tn)
  48 {
  49         if (!tn) return;
  50         tree_nodefree (tn -> left);
  51         tree_nodefree (tn -> right);
  52         FREE (tn, treenode);
  53 }
  54
  55 void tree_free (tree *t)
  56 {
  57         assert (! t -> usedump);
  58
  59         tree_nodefree ( t -> top );
  60         FREE (t, tree);
  61 }
  62
  63
  64 static treenode *tree_nodeadd
  65     (tree *t, treenode *par, treenode *n, void *element, void *key)
  66 {
  67         if (!n) {
  68                 if ( t-> usedump )  n = DNEW (treenode);
  69                 else                n = NEW (treenode);
  70
  71                 n -> left = NULL;
  72                 n -> right = NULL;
  73                 n -> parent = par;
  74                 n -> element = element;
  75                 }
  76         else {
  77                 if ( t->comperator (key, n -> element) < 0 ) {
  78                         n -> left = tree_nodeadd (t, n, n -> left, element, key);
  79                         }
  80                 else {
  81                         n -> right = tree_nodeadd (t, n, n -> right, element, key);
  82                         }
  83                 }
  84
  85         return n;
  86 }
  87
  88 void tree_add (tree *t, void *element, void *key)
  89 {
  90         t -> top = tree_nodeadd (t, NULL, t -> top, element, key);
  91         t -> active = t -> top;
  92 }
  93
  94
  95 static treenode *tree_nodefind (tree *t, treenode *n, void *key)
  96 {
  97         int way;
  98
  99         if (!n) return NULL;
 100
 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);
 105 }
 106
 107
 108 void *tree_find (tree *t, void *key)
 109 {
 110         treenode *tn = tree_nodefind (t, t -> top, key);
 111         if (!tn) return NULL;
 112
 113         t -> active = tn;
 114         return tn -> element;
 115 }
 116
 117
 118
 119 void *tree_this (tree *t)
 120 {
 121         if (! t->active) return NULL;
 122         return t->active->element;
 123 }
 124
 125
 126 static treenode *leftmostnode(treenode *t)
 127 {
 128         while (t->left) t=t->left;
 129         return t;
 130 }
 131
 132 void *tree_first (tree *t)
 133 {
 134         treenode *a = t->top;
 135         if (!a) return NULL;
 136
 137         a = leftmostnode (a);
 138         t->active = a;
 139         return a->element;
 140 }
 141
 142 void *tree_next (tree *t)
 143 {
 144         treenode *a = t->active;
 145         treenode *comefrom = NULL;
 146
 147         while (a) {
 148                 if (!a) return NULL;
 149
 150                 if (a->left && (a->left == comefrom)) {
 151                         t -> active = a;
 152                         return a->element;
 153                         }
 154
 155                 if (a->right && (a->right != comefrom) ) {
 156                         a = leftmostnode(a->right);
 157                         t -> active = a;
 158                         return a->element;
 159                         }
 160
 161                 comefrom=a;
 162                 a=a->parent;
 163                 }
 164         t->active = NULL;
 165         return NULL;
 166 }