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 "global.h"
  19 #include "memory.h"
  20 #include "tree.h"
  21
  22
  23 tree *tree_new (treeelementcomperator comperator)
  24 {
  25         tree *t = NEW (tree);
  26
  27         t -> usedump = 0;
  28         t -> comperator = comperator;
  29         t -> top = NULL;
  30         t -> active = NULL;
  31
  32         return t;
  33 }
  34
  35 tree *tree_dnew (treeelementcomperator comperator)
  36 {
  37         tree *t = DNEW (tree);
  38
  39         t -> usedump = 1;
  40         t -> comperator = comperator;
  41         t -> top = NULL;
  42         t -> active = NULL;
  43
  44         return t;
  45 }
  46
  47
  48 static void tree_nodefree (treenode *tn)
  49 {
  50         if (!tn) return;
  51         tree_nodefree (tn -> left);
  52         tree_nodefree (tn -> right);
  53         FREE (tn, treenode);
  54 }
  55
  56 void tree_free (tree *t)
  57 {
  58         assert (! t -> usedump);
  59
  60         tree_nodefree ( t -> top );
  61         FREE (t, tree);
  62 }
  63
  64
  65 static treenode *tree_nodeadd
  66     (tree *t, treenode *par, treenode *n, void *element, void *key)
  67 {
  68         if (!n) {
  69                 if ( t-> usedump )  n = DNEW (treenode);
  70                 else                n = NEW (treenode);
  71
  72                 n -> left = NULL;
  73                 n -> right = NULL;
  74                 n -> parent = par;
  75                 n -> element = element;
  76                 }
  77         else {
  78                 if ( t->comperator (key, n -> element) < 0 ) {
  79                         n -> left = tree_nodeadd (t, n, n -> left, element, key);
  80                         }
  81                 else {
  82                         n -> right = tree_nodeadd (t, n, n -> right, element, key);
  83                         }
  84                 }
  85
  86         return n;
  87 }
  88
  89 void tree_add (tree *t, void *element, void *key)
  90 {
  91         t -> top = tree_nodeadd (t, NULL, t -> top, element, key);
  92         t -> active = t -> top;
  93 }
  94
  95
  96 static treenode *tree_nodefind (tree *t, treenode *n, void *key)
  97 {
  98         int way;
  99
 100         if (!n) return NULL;
 101
 102         way = t -> comperator (key, n->element);
 103         if (way==0) return n;
 104         if (way<0) return tree_nodefind (t, n -> left, key);
 105         else       return tree_nodefind (t, n -> right, key);
 106 }
 107
 108
 109 void *tree_find (tree *t, void *key)
 110 {
 111         treenode *tn = tree_nodefind (t, t -> top, key);
 112         if (!tn) return NULL;
 113
 114         t -> active = tn;
 115         return tn -> element;
 116 }
 117
 118
 119
 120 void *tree_this (tree *t)
 121 {
 122         if (! t->active) return NULL;
 123         return t->active->element;
 124 }
 125
 126
 127 static treenode *leftmostnode(treenode *t)
 128 {
 129         while (t->left) t=t->left;
 130         return t;
 131 }
 132
 133 void *tree_first (tree *t)
 134 {
 135         treenode *a = t->top;
 136         if (!a) return NULL;
 137
 138         a = leftmostnode (a);
 139         t->active = a;
 140         return a->element;
 141 }
 142
 143 void *tree_next (tree *t)
 144 {
 145         treenode *a = t->active;
 146         treenode *comefrom = NULL;
 147
 148         while (a) {
 149                 if (!a) return NULL;
 150
 151                 if (a->left && (a->left == comefrom)) {
 152                         t -> active = a;
 153                         return a->element;
 154                         }
 155
 156                 if (a->right && (a->right != comefrom) ) {
 157                         a = leftmostnode(a->right);
 158                         t -> active = a;
 159                         return a->element;
 160                         }
 161
 162                 comefrom=a;
 163                 a=a->parent;
 164                 }
 165         t->active = NULL;
 166         return NULL;
 167 }