/*
- * Red-black trees
+ * UCW Library -- Red-black trees
*
- * (c) 2002, Robert Spalek <robert@ucw.cz>
+ * (c) 2002--2005, Robert Spalek <robert@ucw.cz>
*
* Skeleton based on hash-tables by:
*
* Implies TREE_DUPLICATES.
* TREE_WANT_SEARCH node *search(key) -- find the node with the specified
* or, if it does not exist, the nearest one.
+ * TREE_WANT_BOUNDARY node *boundary(uns direction) -- finds smallest
+ * (direction==0) or largest (direction==1) node.
* TREE_WANT_ADJACENT node *adjacent(node *, uns direction) -- finds next
* (direction==1) or previous (direction==0) node.
* TREE_WANT_NEW node *new(key) -- create new node with given key.
}
#endif
+#ifdef TREE_WANT_BOUNDARY
+STATIC P(node) * P(boundary) (T *t, uns direction)
+{
+ P(bucket) *n = t->root, *ns;
+ if (!n)
+ return NULL;
+ else
+ {
+ uns son = !!direction;
+ while ((ns = P(tree_son) (n, son)))
+ n = ns;
+ return &n->n;
+ }
+}
+#endif
+
#ifdef TREE_STORE_PARENT
STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
{
#define TREE_FOR_ALL(t_px, t_ptr, t_var) \
do \
{ \
- TREE_GLUE(t_px,node) *t_var = TREE_GLUE(t_px,first_node)(t_ptr, 0); \
- for (; t_var; t_var = TREE_GLUE(t_px,adjacent)(t_var, 1)) \
+ GLUE_(t_px,node) *t_var = GLUE_(t_px,first_node)(t_ptr, 0); \
+ for (; t_var; t_var = GLUE_(t_px,adjacent)(t_var, 1)) \
{
#define TREE_END_FOR } } while(0)
#define TREE_BREAK break
#define TREE_CONTINUE continue
-#define TREE_GLUE(x,y) x##_##y
#endif
#endif
#undef TREE_WANT_FIND
#undef TREE_WANT_FIND_NEXT
#undef TREE_WANT_SEARCH
+#undef TREE_WANT_BOUNDARY
#undef TREE_WANT_ADJACENT
#undef TREE_WANT_NEW
#undef TREE_WANT_LOOKUP