src/toolbox/tree.c

   1 /* toolbox/tree.h - binary tree management
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    Institut f. Computersprachen, TU Wien
   5    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
   6    S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
   7    J. Wenninger
   8
   9    This file is part of CACAO.
  10
  11    This program is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU General Public License as
  13    published by the Free Software Foundation; either version 2, or (at
  14    your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful, but
  17    WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  24    02111-1307, USA.
  25
  26    Contact: cacao@complang.tuwien.ac.at
  27
  28    Authors: Reinhard Grafl
  29
  30    $Id: tree.c 684 2003-12-02 16:50:17Z twisti $
  31
  32 */
  33
  34
  35 #include <stdio.h>
  36 #include <assert.h>
  37
  38 #include "global.h"
  39 #include "memory.h"
  40 #include "tree.h"
  41
  42
  43 tree *tree_new(treeelementcomperator comperator)
  44 {
  45         tree *t = NEW(tree);
  46
  47         t->usedump = 0;
  48         t->comperator = comperator;
  49         t->top = NULL;
  50         t->active = NULL;
  51
  52         return t;
  53 }
  54
  55
  56 tree *tree_dnew(treeelementcomperator comperator)
  57 {
  58         tree *t = DNEW(tree);
  59
  60         t->usedump = 1;
  61         t->comperator = comperator;
  62         t->top = NULL;
  63         t->active = NULL;
  64
  65         return t;
  66 }
  67
  68
  69 static void tree_nodefree(treenode *tn)
  70 {
  71         if (!tn)
  72                 return;
  73
  74         tree_nodefree(tn->left);
  75         tree_nodefree(tn->right);
  76         FREE(tn, treenode);
  77 }
  78
  79
  80 void tree_free(tree *t)
  81 {
  82         assert(!t->usedump);
  83
  84         tree_nodefree(t->top);
  85         FREE(t, tree);
  86 }
  87
  88
  89 static treenode *tree_nodeadd(tree *t, treenode *par, treenode *n,
  90                                                           void *element, void *key)
  91 {
  92         if (!n) {
  93                 if (t->usedump) {
  94                         n = DNEW(treenode);
  95
  96                 } else {
  97                         n = NEW(treenode);
  98                 }
  99
 100                 n->left = NULL;
 101                 n->right = NULL;
 102                 n->parent = par;
 103                 n->element = element;
 104
 105         } else {
 106                 if (t->comperator(key, n->element) < 0) {
 107                         n->left = tree_nodeadd(t, n, n->left, element, key);
 108
 109                 } else {
 110                         n->right = tree_nodeadd(t, n, n->right, element, key);
 111                 }
 112         }
 113
 114         return n;
 115 }
 116
 117
 118 void tree_add(tree *t, void *element, void *key)
 119 {
 120         t->top = tree_nodeadd(t, NULL, t->top, element, key);
 121         t->active = t->top;
 122 }
 123
 124
 125 static treenode *tree_nodefind(tree *t, treenode *n, void *key)
 126 {
 127         int way;
 128
 129         if (!n)
 130                 return NULL;
 131
 132         way = t->comperator(key, n->element);
 133         if (way == 0)
 134                 return n;
 135
 136         if (way < 0) {
 137                 return tree_nodefind(t, n->left, key);
 138
 139         } else {
 140                 return tree_nodefind (t, n -> right, key);
 141         }
 142 }
 143
 144
 145 void *tree_find(tree *t, void *key)
 146 {
 147         treenode *tn = tree_nodefind(t, t->top, key);
 148
 149         if (!tn)
 150                 return NULL;
 151
 152         t->active = tn;
 153
 154         return tn->element;
 155 }
 156
 157
 158
 159 void *tree_this(tree *t)
 160 {
 161         if (!t->active)
 162                 return NULL;
 163
 164         return t->active->element;
 165 }
 166
 167
 168 static treenode *leftmostnode(treenode *t)
 169 {
 170         while (t->left) {
 171                 t = t->left;
 172         }
 173
 174         return t;
 175 }
 176
 177
 178 void *tree_first(tree *t)
 179 {
 180         treenode *a = t->top;
 181
 182         if (!a)
 183                 return NULL;
 184
 185         a = leftmostnode(a);
 186         t->active = a;
 187
 188         return a->element;
 189 }
 190
 191
 192 void *tree_next (tree *t)
 193 {
 194         treenode *a = t->active;
 195         treenode *comefrom = NULL;
 196
 197         while (a) {
 198                 if (!a)
 199                         return NULL;
 200
 201                 if (a->left && (a->left == comefrom)) {
 202                         t -> active = a;
 203                         return a->element;
 204                 }
 205
 206                 if (a->right && (a->right != comefrom)) {
 207                         a = leftmostnode(a->right);
 208                         t -> active = a;
 209                         return a->element;
 210                 }
 211
 212                 comefrom = a;
 213                 a = a->parent;
 214         }
 215
 216         t->active = NULL;
 217
 218         return NULL;
 219 }
 220
 221
 222 /*
 223  * These are local overrides for various environment variables in Emacs.
 224  * Please do not remove this and leave it at the end of the file, where
 225  * Emacs will automagically detect them.
 226  * ---------------------------------------------------------------------
 227  * Local variables:
 228  * mode: c
 229  * indent-tabs-mode: t
 230  * c-basic-offset: 4
 231  * tab-width: 4
 232  * End:
 233  */