lib/gl_anytree_oset.h

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