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