lib/gl_anytree_oset.h

   1 /* Ordered set data type implemented by a binary tree.
   2    Copyright (C) 2006-2007 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c.  */
  19
  20 /* An item on the stack used for iterating across the elements.  */
  21 typedef struct
  22 {
  23   gl_oset_node_t node;
  24   bool rightp;
  25 } iterstack_item_t;
  26
  27 /* A stack used for iterating across the elements.  */
  28 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
  29
  30 static gl_oset_t
  31 gl_tree_create_empty (gl_oset_implementation_t implementation,
  32                       gl_setelement_compar_fn compar_fn,
  33                       gl_setelement_dispose_fn dispose_fn)
  34 {
  35   struct gl_oset_impl *set = XMALLOC (struct gl_oset_impl);
  36
  37   set->base.vtable = implementation;
  38   set->base.compar_fn = compar_fn;
  39   set->base.dispose_fn = dispose_fn;
  40   set->root = NULL;
  41   set->count = 0;
  42
  43   return set;
  44 }
  45
  46 static size_t
  47 gl_tree_size (gl_oset_t set)
  48 {
  49   return set->count;
  50 }
  51
  52 static bool
  53 gl_tree_search (gl_oset_t set, const void *elt)
  54 {
  55   gl_setelement_compar_fn compar = set->base.compar_fn;
  56   gl_oset_node_t node;
  57
  58   for (node = set->root; node != NULL; )
  59     {
  60       int cmp = (compar != NULL
  61                  ? compar (node->value, elt)
  62                  : (node->value > elt ? 1 :
  63                     node->value < elt ? -1 : 0));
  64
  65       if (cmp < 0)
  66         node = node->right;
  67       else if (cmp > 0)
  68         node = node->left;
  69       else /* cmp == 0 */
  70         /* We have an element equal to ELT.  */
  71         return true;
  72     }
  73   return false;
  74 }
  75
  76 static bool
  77 gl_tree_search_atleast (gl_oset_t set,
  78                         gl_setelement_threshold_fn threshold_fn,
  79                         const void *threshold,
  80                         const void **eltp)
  81 {
  82   gl_oset_node_t node;
  83
  84   for (node = set->root; node != NULL; )
  85     {
  86       if (! threshold_fn (node->value, threshold))
  87         node = node->right;
  88       else
  89         {
  90           /* We have an element >= VALUE.  But we need the leftmost such
  91              element.  */
  92           gl_oset_node_t found = node;
  93           node = node->left;
  94           for (; node != NULL; )
  95             {
  96               if (! threshold_fn (node->value, threshold))
  97                 node = node->right;
  98               else
  99                 {
 100                   found = node;
 101                   node = node->left;
 102                 }
 103             }
 104           *eltp = found->value;
 105           return true;
 106         }
 107     }
 108   return false;
 109 }
 110
 111 static gl_oset_node_t
 112 gl_tree_search_node (gl_oset_t set, const void *elt)
 113 {
 114   gl_setelement_compar_fn compar = set->base.compar_fn;
 115   gl_oset_node_t node;
 116
 117   for (node = set->root; node != NULL; )
 118     {
 119       int cmp = (compar != NULL
 120                  ? compar (node->value, elt)
 121                  : (node->value > elt ? 1 :
 122                     node->value < elt ? -1 : 0));
 123
 124       if (cmp < 0)
 125         node = node->right;
 126       else if (cmp > 0)
 127         node = node->left;
 128       else /* cmp == 0 */
 129         /* We have an element equal to ELT.  */
 130         return node;
 131     }
 132   return NULL;
 133 }
 134
 135 static bool
 136 gl_tree_add (gl_oset_t set, const void *elt)
 137 {
 138   gl_setelement_compar_fn compar;
 139   gl_oset_node_t node = set->root;
 140
 141   if (node == NULL)
 142     {
 143       gl_tree_add_first (set, elt);
 144       return true;
 145     }
 146
 147   compar = set->base.compar_fn;
 148
 149   for (;;)
 150     {
 151       int cmp = (compar != NULL
 152                  ? compar (node->value, elt)
 153                  : (node->value > elt ? 1 :
 154                     node->value < elt ? -1 : 0));
 155
 156       if (cmp < 0)
 157         {
 158           if (node->right == NULL)
 159             {
 160               gl_tree_add_after (set, node, elt);
 161               return true;
 162             }
 163           node = node->right;
 164         }
 165       else if (cmp > 0)
 166         {
 167           if (node->left == NULL)
 168             {
 169               gl_tree_add_before (set, node, elt);
 170               return true;
 171             }
 172           node = node->left;
 173         }
 174       else /* cmp == 0 */
 175         return false;
 176     }
 177 }
 178
 179 static bool
 180 gl_tree_remove (gl_oset_t set, const void *elt)
 181 {
 182   gl_oset_node_t node = gl_tree_search_node (set, elt);
 183
 184   if (node != NULL)
 185     return gl_tree_remove_node (set, node);
 186   else
 187     return false;
 188 }
 189
 190 static void
 191 gl_tree_oset_free (gl_oset_t set)
 192 {
 193   /* Iterate across all elements in post-order.  */
 194   gl_oset_node_t node = set->root;
 195   iterstack_t stack;
 196   iterstack_item_t *stack_ptr = &stack[0];
 197
 198   for (;;)
 199     {
 200       /* Descend on left branch.  */
 201       for (;;)
 202         {
 203           if (node == NULL)
 204             break;
 205           stack_ptr->node = node;
 206           stack_ptr->rightp = false;
 207           node = node->left;
 208           stack_ptr++;
 209         }
 210       /* Climb up again.  */
 211       for (;;)
 212         {
 213           if (stack_ptr == &stack[0])
 214             goto done_iterate;
 215           stack_ptr--;
 216           node = stack_ptr->node;
 217           if (!stack_ptr->rightp)
 218             break;
 219           /* Free the current node.  */
 220           if (set->base.dispose_fn != NULL)
 221             set->base.dispose_fn (node->value);
 222           free (node);
 223         }
 224       /* Descend on right branch.  */
 225       stack_ptr->rightp = true;
 226       node = node->right;
 227       stack_ptr++;
 228     }
 229  done_iterate:
 230   free (set);
 231 }
 232
 233 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 234
 235 static gl_oset_iterator_t
 236 gl_tree_iterator (gl_oset_t set)
 237 {
 238   gl_oset_iterator_t result;
 239   gl_oset_node_t node;
 240
 241   result.vtable = set->base.vtable;
 242   result.set = set;
 243   /* Start node is the leftmost node.  */
 244   node = set->root;
 245   if (node != NULL)
 246     while (node->left != NULL)
 247       node = node->left;
 248   result.p = node;
 249   /* End point is past the rightmost node.  */
 250   result.q = NULL;
 251 #ifdef lint
 252   result.i = 0;
 253   result.j = 0;
 254   result.count = 0;
 255 #endif
 256
 257   return result;
 258 }
 259
 260 static bool
 261 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 262 {
 263   if (iterator->p != iterator->q)
 264     {
 265       gl_oset_node_t node = (gl_oset_node_t) iterator->p;
 266       *eltp = node->value;
 267       /* Advance to the next node.  */
 268       if (node->right != NULL)
 269         {
 270           node = node->right;
 271           while (node->left != NULL)
 272             node = node->left;
 273         }
 274       else
 275         {
 276           while (node->parent != NULL && node->parent->right == node)
 277             node = node->parent;
 278           node = node->parent;
 279         }
 280       iterator->p = node;
 281       return true;
 282     }
 283   else
 284     return false;
 285 }
 286
 287 static void
 288 gl_tree_iterator_free (gl_oset_iterator_t *iterator)
 289 {
 290 }