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 =
  36     (struct gl_oset_impl *) xmalloc (sizeof (struct gl_oset_impl));
  37
  38   set->base.vtable = implementation;
  39   set->base.compar_fn = compar_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 gl_oset_node_t
  77 gl_tree_search_node (gl_oset_t set, const void *elt)
  78 {
  79   gl_setelement_compar_fn compar = set->base.compar_fn;
  80   gl_oset_node_t node;
  81
  82   for (node = set->root; node != NULL; )
  83     {
  84       int cmp = (compar != NULL
  85                  ? compar (node->value, elt)
  86                  : (node->value > elt ? 1 :
  87                     node->value < elt ? -1 : 0));
  88
  89       if (cmp < 0)
  90         node = node->right;
  91       else if (cmp > 0)
  92         node = node->left;
  93       else /* cmp == 0 */
  94         /* We have an element equal to ELT.  */
  95         return node;
  96     }
  97   return NULL;
  98 }
  99
 100 static bool
 101 gl_tree_add (gl_oset_t set, const void *elt)
 102 {
 103   gl_setelement_compar_fn compar;
 104   gl_oset_node_t node = set->root;
 105
 106   if (node == NULL)
 107     {
 108       gl_tree_add_first (set, elt);
 109       return true;
 110     }
 111
 112   compar = set->base.compar_fn;
 113
 114   for (;;)
 115     {
 116       int cmp = (compar != NULL
 117                  ? compar (node->value, elt)
 118                  : (node->value > elt ? 1 :
 119                     node->value < elt ? -1 : 0));
 120
 121       if (cmp < 0)
 122         {
 123           if (node->right == NULL)
 124             {
 125               gl_tree_add_after (set, node, elt);
 126               return true;
 127             }
 128           node = node->right;
 129         }
 130       else if (cmp > 0)
 131         {
 132           if (node->left == NULL)
 133             {
 134               gl_tree_add_before (set, node, elt);
 135               return true;
 136             }
 137           node = node->left;
 138         }
 139       else /* cmp == 0 */
 140         return false;
 141     }
 142 }
 143
 144 static bool
 145 gl_tree_remove (gl_oset_t set, const void *elt)
 146 {
 147   gl_oset_node_t node = gl_tree_search_node (set, elt);
 148
 149   if (node != NULL)
 150     return gl_tree_remove_node (set, node);
 151   else
 152     return false;
 153 }
 154
 155 static void
 156 gl_tree_oset_free (gl_oset_t set)
 157 {
 158   /* Iterate across all elements in post-order.  */
 159   gl_oset_node_t node = set->root;
 160   iterstack_t stack;
 161   iterstack_item_t *stack_ptr = &stack[0];
 162
 163   for (;;)
 164     {
 165       /* Descend on left branch.  */
 166       for (;;)
 167         {
 168           if (node == NULL)
 169             break;
 170           stack_ptr->node = node;
 171           stack_ptr->rightp = false;
 172           node = node->left;
 173           stack_ptr++;
 174         }
 175       /* Climb up again.  */
 176       for (;;)
 177         {
 178           if (stack_ptr == &stack[0])
 179             goto done_iterate;
 180           stack_ptr--;
 181           node = stack_ptr->node;
 182           if (!stack_ptr->rightp)
 183             break;
 184           /* Free the current node.  */
 185           free (node);
 186         }
 187       /* Descend on right branch.  */
 188       stack_ptr->rightp = true;
 189       node = node->right;
 190       stack_ptr++;
 191     }
 192  done_iterate:
 193   free (set);
 194 }
 195
 196 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 197
 198 static gl_oset_iterator_t
 199 gl_tree_iterator (gl_oset_t set)
 200 {
 201   gl_oset_iterator_t result;
 202   gl_oset_node_t node;
 203
 204   result.vtable = set->base.vtable;
 205   result.set = set;
 206   /* Start node is the leftmost node.  */
 207   node = set->root;
 208   if (node != NULL)
 209     while (node->left != NULL)
 210       node = node->left;
 211   result.p = node;
 212   /* End point is past the rightmost node.  */
 213   result.q = NULL;
 214
 215   return result;
 216 }
 217
 218 static bool
 219 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 220 {
 221   if (iterator->p != iterator->q)
 222     {
 223       gl_oset_node_t node = (gl_oset_node_t) iterator->p;
 224       *eltp = node->value;
 225       /* Advance to the next node.  */
 226       if (node->right != NULL)
 227         {
 228           node = node->right;
 229           while (node->left != NULL)
 230             node = node->left;
 231         }
 232       else
 233         {
 234           while (node->parent != NULL && node->parent->right == node)
 235             node = node->parent;
 236           node = node->parent;
 237         }
 238       iterator->p = node;
 239       return true;
 240     }
 241   else
 242     return false;
 243 }
 244
 245 static void
 246 gl_tree_iterator_free (gl_oset_iterator_t *iterator)
 247 {
 248 }