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.
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)
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.
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. */
19 /* Common code of gl_avltree_oset.c and gl_rbtree_oset.c. */
21 /* An item on the stack used for iterating across the elements. */
28 /* A stack used for iterating across the elements. */
29 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
32 gl_tree_create_empty (gl_oset_implementation_t implementation,
33 gl_setelement_compar_fn compar_fn,
34 gl_setelement_dispose_fn dispose_fn)
36 struct gl_oset_impl *set = XMALLOC (struct gl_oset_impl);
38 set->base.vtable = implementation;
39 set->base.compar_fn = compar_fn;
40 set->base.dispose_fn = dispose_fn;
48 gl_tree_size (gl_oset_t set)
54 gl_tree_search (gl_oset_t set, const void *elt)
56 gl_setelement_compar_fn compar = set->base.compar_fn;
59 for (node = set->root; node != NULL; )
61 int cmp = (compar != NULL
62 ? compar (node->value, elt)
63 : (node->value > elt ? 1 :
64 node->value < elt ? -1 : 0));
71 /* We have an element equal to ELT. */
78 gl_tree_search_atleast (gl_oset_t set,
79 gl_setelement_threshold_fn threshold_fn,
80 const void *threshold,
85 for (node = set->root; node != NULL; )
87 if (! threshold_fn (node->value, threshold))
91 /* We have an element >= VALUE. But we need the leftmost such
93 gl_oset_node_t found = node;
95 for (; node != NULL; )
97 if (! threshold_fn (node->value, threshold))
105 *eltp = found->value;
112 static gl_oset_node_t
113 gl_tree_search_node (gl_oset_t set, const void *elt)
115 gl_setelement_compar_fn compar = set->base.compar_fn;
118 for (node = set->root; node != NULL; )
120 int cmp = (compar != NULL
121 ? compar (node->value, elt)
122 : (node->value > elt ? 1 :
123 node->value < elt ? -1 : 0));
130 /* We have an element equal to ELT. */
137 gl_tree_add (gl_oset_t set, const void *elt)
139 gl_setelement_compar_fn compar;
140 gl_oset_node_t node = set->root;
144 gl_tree_add_first (set, elt);
148 compar = set->base.compar_fn;
152 int cmp = (compar != NULL
153 ? compar (node->value, elt)
154 : (node->value > elt ? 1 :
155 node->value < elt ? -1 : 0));
159 if (node->right == NULL)
161 gl_tree_add_after (set, node, elt);
168 if (node->left == NULL)
170 gl_tree_add_before (set, node, elt);
181 gl_tree_remove (gl_oset_t set, const void *elt)
183 gl_oset_node_t node = gl_tree_search_node (set, elt);
186 return gl_tree_remove_node (set, node);
192 gl_tree_oset_free (gl_oset_t set)
194 /* Iterate across all elements in post-order. */
195 gl_oset_node_t node = set->root;
197 iterstack_item_t *stack_ptr = &stack[0];
201 /* Descend on left branch. */
206 stack_ptr->node = node;
207 stack_ptr->rightp = false;
211 /* Climb up again. */
214 if (stack_ptr == &stack[0])
217 node = stack_ptr->node;
218 if (!stack_ptr->rightp)
220 /* Free the current node. */
221 if (set->base.dispose_fn != NULL)
222 set->base.dispose_fn (node->value);
225 /* Descend on right branch. */
226 stack_ptr->rightp = true;
234 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
236 static gl_oset_iterator_t
237 gl_tree_iterator (gl_oset_t set)
239 gl_oset_iterator_t result;
242 result.vtable = set->base.vtable;
244 /* Start node is the leftmost node. */
247 while (node->left != NULL)
250 /* End point is past the rightmost node. */
262 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
264 if (iterator->p != iterator->q)
266 gl_oset_node_t node = (gl_oset_node_t) iterator->p;
268 /* Advance to the next node. */
269 if (node->right != NULL)
272 while (node->left != NULL)
277 while (node->parent != NULL && node->parent->right == node)
289 gl_tree_iterator_free (gl_oset_iterator_t *iterator)