soak (Level.__init__): Trim newline from the tree listing.

[xyla] / rbtree.h

#ifndef XYLA_RBTREE_H
#define XYLA_RBTREE_H

#include <limits.h>

#include "bstree.h"

struct rbnode {
  struct bstnode _bst;
  unsigned f;
#define RBF_RED 1u
};

/* The maximum possible height %$H_n$% for a red-black tree containing %$n$%
 * nodes is surprisingly hard to pin down.  The best way to start is to
 * reverse the question and find the smallest number %$N_h$% of nodes which
 * can force the tree to have height %$h$%.
 *
 * A red-black tree has the same number -- the tree's `black-height' -- of
 * black nodes on every path from root to leaf, and this will be the primary
 * limitation on the structure of our trees.  It's pretty obvious that the
 * complete binary tree %$B_h$% containing %$2^h - 1$% nodes is the lightest
 * red-black tree with black-height %$h$%.
 *
 * This is going to involve a recurrence.  The base cases are the rather
 * unsurprising observation that %$N_0 = 0$% and %$N_1 = 1$%.
 *
 * Because of the asymmetry between red and black nodes, the minimal tree
 * structures will differ according to whether %$h$% is odd or even.  Let's
 * tackle the even case first.
 *
 * I claim that a minimal structure for a red-black tree with even height
 * %$h \ge 2$% is %$S_h$%, which looks like this.
 *
 *                                     t
 *                                      (*)
 *                               l    /     \ r
 *                                ( )     B_{h/2-1}
 *                            s /    \ b
 *                        S_{h-2}   B_{h/2-1}
 *
 * Firstly, it has height %$h = (h - 2) + 2$%, node count %$2^{h/2+1} - 2$%,
 * and black-height %$h/2$%; all of these are clear from induction.
 *
 * Secondly, this is a valid red-black tree.  Inductively, %$S_{h-2}$% is a
 * red-black tree, and therefore its root is black.
 *
 * And, thirdly, the node count and black-height are minimal for a tree of
 * this height.  That the black-height is minimal is immediate from the
 * height, since a red node can only have black children.  If a tree has
 * height %$h$%, one of the root's grandchildren, %$s$% say, must be the
 * root of a subtree with height %$h - 2$%.  Let %$n$% and %$h'$% be
 * respectively the node count and black-height of %$s$%; clearly
 * %$h' \ge h/2 - 1$%.  Let %$l$% be the parent of %$s$%, with %$b$% its
 * sibling; let %$r$% be the sibling of %$l$%, and %$t$% be the tree root.
 * The node %$b$% must have black-height %$h'$%, and hence at least
 * %$2^{h'} - 1$% nodes.  If %$l$% is red, then %$r$% must also have
 * black-height %$h'$%; otherwise it has black-height %$h' + 1$%, and an
 * additional %$2^{h'}$% nodes.  These node counts are all minimized if %$s$%
 * has minimal black-height and %$l$% is black.  Furthermore, if %$s$% has
 * more than %$2^{h/2} - 2$% nodes, then it can be replaced by a copy of
 * %$S_{h-2}$% to reduce the overall node count.
 *
 * This proves that a red-black tree with even height %$h$% has at least
 * %$2^{h/2+1} - 2$% nodes.
 *
 * We now turn to the case where %$h$% is odd.  I claim that a minimal
 * structure for a red-black tree with odd height %$h \ge 3$% is %$S_h$%,
 * which looks like this.
 *
 *                                     t
 *                                      (*)
 *                                  s /     \ b
 *                              S_{h-1}   B_{(h-1)/2}
 *
 * Firstly, it has height %$h = (h - 1) + 1$%, node count
 * %$3 \cdot 2^{(h-1)/2} - 2$%, and black-height %$(h + 1)/2$%; all of these
 * are immediate from the above, since %$h - 1$% is even.
 *
 * Secondly, this is a valid red-black tree.  This is clear because the
 * additional structure contains no red nodes, and the black-height is
 * consistent.
 *
 * And, thirdly, the node count and black-height are minimal for a tree of
 * this height.  That the black-height is minimal is again immediate from the
 * height.  Let %$t$% be the root.  One of %$t$%'s children, %$s$% say, must
 * have height %$h - 1$%; let %$b$% be the sibling of %$s$%.  The black-
 * height of %$s$% must be at least %$(h - 1)/2$%, and therefore %$b$% must
 * have at least %$2^{(h-1)/2}$% nodes.  Suppose for a moment that the node
 * %$s$% is red.  Then, %$s$% has two children; one has height %$h - 2$%, and
 * both have black-height %$(h - 1)/2$%.  Inductively, these will have node
 * counts of at least %$3 \cdot 2^{(h-3)/2} - 2$% and %$2^{(h-1)/2} - 1$%
 * respectively, giving a total of %$5 \cdot 2^{(h-3)/2} - 3$%, so
 * %$5 \cdot 2^{h-3}/2} - 2$% including %$s$% itself.  On the other hand, if
 * %$s$% is black, then its subtree has only %$2^{(h-1)/2+1} - 2$% nodes,
 * which is fewer by %$2^{(h-3)/2}$%.
 *
 * This proves that a red-black tree with odd height %$h$% has at least
 * %$3 \cdot 2^{(h-1)/2} - 2$% nodes.
 *
 * Having two different expressions is annoying.  We'll take the smaller of
 * the two.  Notice that
 *
 *      %$3 \cdot 2^{(h-1)/2} - 2 = 3/\sqrt{2} \cdot 2^{h/2} - 2$%,
 *
 * and
 *
 *      %$2^{h/2+1} - 2 = 2 \cdot 2^{h/2} - 2$%.
 *
 * Both %$3/\sqrt{2}$% and %$2$% are nonnegative, so squaring them will
 * preserve their relative order; %$(3/\sqrt{2})^2 = 9/4$%, while
 * %$2^2 = 4 = 8/4$%, so the former is larger.  We therefore conclude that
 * a red-black tree with height %$h$% must have at least %$2^{h/2+1} - 2$%
 * nodes.
 *
 * Where were we?  Oh, yes.  What we actually wanted to know was the maximum
 * possible height %$H_n$% for a red-black tree with %$n$% nodes.  Suppose,
 * then, that, for some %$h$%, the tree has %$n \ge N_h \ge 2^{h/2+1} - 2$%
 * nodes.  Then %$n + 2 \ge 2^{h/2+1}$%.  Taking (binary) logs gives
 * %$h/2 + 1 \le \lg (n + 2)$%, so
 *
 *      %$h \le 2 \lg (n + 2) - 2$%.
 *
 * Our %$n$% of interest is the largest value that can fit in @size_t@, which
 * is an unsigned type; therefore %$n = 2^k - 1$% for some %$k$%, and
 * %$\floor{\lg (n + 2)} = k$%.  Alas, C doesn't give us %$k$% directly, but
 * it can certainly be no more than @CHAR_BIT*sizeof(size_t)@; since padding
 * bits in integers are extremely rare, this is usually the exact value.
 *
 * On conventional 32-bit targets, this is 62; on 64-bit targets, it's 126.
 */
#define RBTREE_PATHMAX (2*CHAR_BIT*sizeof(size_t) - 2)

struct rbpath {
  int k;
  struct bstnode **p[RBTREE_PATHMAX];
};

struct rbiter {
  int sp;
  struct bstnode *stack[RBTREE_PATHMAX];
};

/* --- @rbtree_check@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct rbnode *const *root@ = root pointer that we're
 *                      checking
 *              @int blkht@ = expected black-height for tree, or %$-1$% if
 *                      unknown
 *              @void *arg@ = argument to pass to check function
 *
 * Returns:     Zero if everything was OK, %$-1$% if problems were found and
 *              reported.
 *
 * Use:         Recursively examine a red-black tree, checking that it
 *              satisfies all of the necessary invariants.
 */

extern int rbtree_check(struct bstree_nodecls */*cls*/,
                        struct bstnode *const */*root*/, int /*blkht*/,
                        void */*arg*/);

/* --- @rbtree_height@ --- *
 *
 * Arguments:   @const struct rbnode *node@ = pointer to a tree node
 *
 * Returns:     The `black height' for the (sub)tree rooted at @node@.  This
 *              is primarily useful as input to @rbtree_join@ and
 *              @rbtree_split@.
 */

extern int rbtree_height(const struct rbnode */*node*/);

/* --- @rbtree_lookup@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode *root@ = pointer to root node
 *              @void *arg@ = argument to the navigation function
 *
 * Returns:     Pointer to the matching node, or null if it couldn't be
 *              found.
 *
 * Use:         Search for a node within the tree according to the navigation
 *              function.
 */

extern void *rbtree_lookup(struct bstree_nodecls */*cls*/,
                           struct bstnode */*root*/, void */*arg*/);

/* --- @rbtree_probe@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode **root@ = pointer to root link
 *              @const void *search_key@ = the key to search for
 *              @struct rbpath *path@ = path to fill in
 *
 * Returns:     Pointer to the matching node, or null if it couldn't be
 *              found.
 *
 * Use:         Search for a node within the tree according to the navigation
 *              function, recording the search path  This can be used later,
 *              e.g., by @rbtree_insert@ to insert a new node if none was
 *              found, or by @rbtree_remove@ to remove the node that was
 *              found.
 */

extern void *rbtree_probe(struct bstree_nodecls */*cls*/,
                          struct bstnode **/*root*/, void */*arg*/,
                          struct rbpath */*path*/);

/* --- @rbtree_inititer@ --- *
 *
 * Arguments:   @struct bstnode *root@ = pointer to the tree header
 *              @struct rbiter *it@ = pointer to iterator to initialize
 *
 * Returns:     ---
 *
 * Use:         Initialize an iterator.
 */

extern void rbtree_inititer(struct bstnode */*root*/, struct rbiter */*it*/);

/* --- @rbtree_next@ --- *
 *
 * Arguments:   @struct rbiter *it@ = pointer to iterator
 *
 * Returns:     A pointer to the next node in ascending order, or null
 *              if no more nodes remain.
 *
 * Use:         Advances a tree iterator.  Inserting or removing elements
 *              invalidates the iterator.  As a special exception, it is
 *              permitted to free all of the nodes by iterating over the tree
 *              in the obvious manner:
 *
 *                      @rbtree_inititer(tree, &it);@
 *                      @for (;;) {@
 *                        @node = rbtree_next(&it); if (!node) break;@
 *                        @free(node);@
 *                      @}@
 *
 *              At this point, the tree header structure is left in an
 *              invalid state, and must not be used; it is, however, safe to
 *              discard, since it holds no resources.
 */

extern void *rbtree_next(struct rbiter */*it*/);

/* --- @rbtree_firstpath@, @rbtree_lastpath@ --- *
 *
 * Arguments:   @struct bstnode **root@ = address of the tree root link
 *              @struct rbpath *path@ = path to fill in
 *
 * Returns:     Pointer to the requested node, or null if the tree is empty.
 *
 * Use:         Return the first or last node in the tree, as ordered by
 *              their keys, together with a path to the requested node, which
 *              can be used to remove them, or to navigate to other nodes in
 *              the tree.
 */

extern void *rbtree_firstpath(struct bstnode **/*root*/,
                              struct rbpath */*path*/);
extern void *rbtree_lastpath(struct bstnode **/*root*/,
                             struct rbpath */*path*/);

/* --- @rbtree_nextpath@, @rbtree_prevpath@ --- *
 *
 * Arguments:   @struct rbpath *path@ = path to update
 *
 * Returns:     Pointer to the requested node, or null if the tree is empty
 *              or the path is already positioned at the relevant extreme.
 *
 * Use:         Return the next or previous node in the tree, as ordered by
 *              their keys, together with a path to the requested node, which
 *              can be used to remove them, or to navigate to other nodes in
 *              the tree.
 *
 *              If the path is full, i.e., refers to an existing node, then
 *              the functions return that node's successor or predecessor.
 *              If the path is empty, i.e., refers to a space between nodes
 *              where a new node can be inserted, then the functions return
 *              the node at the upper or lower end of the gap, unless the
 *              `gap' is actually at an extreme of the tree and no such node
 *              exists.  In the latter case, a null pointer is returned.
 *              The path is modified to refer to the new node, if any, or to
 *              the gap at the appropriate extreme of the tree.
 */

extern void *rbtree_nextpath(struct rbpath */*path*/);
extern void *rbtree_prevpath(struct rbpath */*path*/);

/* --- @rbtree_beforepath@, @rbtree_afterpath@ --- *
 *
 * Arguments:   @struct rbpath *path@ = path to update
 *
 * Returns:     ---
 *
 * Use:         Advance the path to just before or after the current node.
 *              The path thereby becomes empty, suitable to insert an element
 *              or split the tree just before or after the previously
 *              selected node.
 */

extern void rbtree_afterpath(struct rbpath */*path*/);
extern void rbtree_beforepath(struct rbpath */*path*/);

/* --- @rbtree_replace@ --- *
 *
 * Arguments:   @struct rbpath *path@ = pointer to a full path
 *              @struct rbnode *node@ = pointer to replacement node
 *
 * Returns:     ---
 *
 * Use:         Replace the node identified by the @path@ with the given
 *              @node@.  The replacement @node@ should have the same (equal,
 *              according to the node-class comparison function) key as the
 *              node it replaces, and %%\emph{must}%% be strictly between the
 *              keys of the old node's predecessor and successor.  The node's
 *              links need not be initialized.  Paths and iterators are not
 *              invalidated.
 */

extern void rbtree_replace(struct rbpath */*path*/, struct rbnode */*node*/);

/* --- @rbtree_insert@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct rbpath *path@ = pointer to an empty path
 *              @struct rbnode *node@ = the new node to add
 *
 * Returns:     Adjustment (%$0$% or %$+1$%) to the tree black-height.
 *
 * Use:         Add a new node to the tree, in the place determined by the
 *              empty path.  The @new_node@'s key must be equal to the key
 *              passed to @rbtree_probe@ when it produced the path.
 *
 *              The new node is not copied, and its storage must remain valid
 *              until the node is removed or the tree is discarded.
 */

extern int rbtree_insert(struct bstree_nodecls */*cls*/,
                         struct rbpath */*path*/, struct rbnode */*node*/);

/* --- @rbtree_remove@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct rbpath *path@ = pointer to a full path
 *
 * Returns:     Adjustment (%$0$% or %$-1$%) to the tree black-height.
 *
 * Use:         Removes the node identified by the path.  The node was
 *              allocated by the caller, and should be freed by the caller in
 *              whatever way is appropriate.
 */

extern int rbtree_remove(struct bstree_nodecls */*cls*/,
                         struct rbpath */*path*/);

/* --- @rbtree_join@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode **root_out@ = address to store the link to
 *                      the root of the combined tree
 *              @struct bstnode **left@ = address containing the current
 *                      root of the left tree
 *              @int lht@ = black-height of the left tree, or %$-1$% if
 *                      unknown
 *              @struct bstnode *mid@ = pointer to middle node, or null
 *              @struct bstnode **right@ = address containing the current
 *                      root of the right tree
 *              @int rht@ = black-height of the right tree, or %$-1$% if
 *                      unknown
 *
 * Returns:     The black-height of the combined tree.
 *
 * Use:         Concatenate two trees.
 *
 *              Every node in the left tree must have a key strictly less
 *              than any node of the right tree.  If a middle node is
 *              provided, then its key must be greater than that of any node
 *              in the left tree, and less than that of any node in the right
 *              tree.
 *
 *              The output is a single tree containing every node in the left
 *              and right input trees, together with the middle node, if that
 *              is not null.
 *
 *              The @root_out@ pointer may equal either @left@ or @right@
 *              (or, indeed, both, only if both are empty).  If @left@ is
 *              distinct from @root_out@ then @*left@ set null on exit;
 *              similarly, if @right@ is distinct from @root_out@, then
 *              @*right@ is set null on exit.
 */

extern int rbtree_join(struct bstree_nodecls */*cls*/,
                       struct bstnode **/*root_out*/,
                       struct bstnode **/*left*/, int /*lht*/,
                       struct bstnode */*mid*/,
                       struct bstnode **/*right*/, int /*rht*/);

/* --- @rbtree_split@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode *left_out@ = where to leave the root of the
 *                      resulting left tree
 *              @int *lht_out@ = where to leave the black-height of the left
 *                      tree, or null to discard this information
 *              @int *mht_out@ = where to leave the black-height of the
 *                      middle node (either zero or one), or null to discard
 *                      this information
 *              @struct bstnode *rirght_out@ = where to leave the root of the
 *                      resulting right tree
 *              @int *rht_out@ = where to leave the black-height of the right
 *                      tree, or null to discard this information
 *              @struct rbpath *path@ = full or empty path at which to split
 *                      the tree
 *
 * Returns:     A pointer to the resulting middle node, or null.
 *
 * Use:         Split a tree into two at an indicated place.
 *
 *              The splitting operation produces two trees, a `left tree'
 *              containing every node preceding the given path, and a `right
 *              tree' containing every node following the path.  If the path
 *              is full, i.e., it denotes a node in the input tree, then that
 *              becomes the `middle node', which does not appear in either
 *              tree, and is returned separately.
 */

extern void *rbtree_split(struct bstree_nodecls */*cls*/,
                          struct bstnode **/*left_out*/, int */*lht_out*/,
                          int */*mht_out*/,
                          struct bstnode **/*right_out*/, int */*rht_out*/,
                          struct rbpath */*path*/);

/* --- @rbtree_splitat@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode *left_out@ = where to leave the root of the
 *                      resulting left tree
 *              @int *lht_out@ = where to leave the black-height of the left
 *                      tree, or null to discard this information
 *              @int *mht_out@ = where to leave the black-height of the
 *                      middle node (either zero or one), or null to discard
 *                      this information
 *              @struct bstnode *right_out@ = where to leave the root of the
 *                      resulting right tree
 *              @int *rht_out@ = where to leave the black-height of the right
 *                      tree, or null to discard this information
 *              @struct bstnode **root@ = address of the root link of the
 *                      input tree
 *              @const void *key@ = key at which to split the tree.
 *
 * Returns:     A pointer to the matching middle node, or null.
 *
 * Use:         Split a tree into two at an indicated key.
 *
 *              The splitting operation produces two trees, a `left tree'
 *              containing every node whose key is less than @key@, and a
 *              `right tree' containing every node whose key is greater than
 *              @key@.  If a node matching the @key@ exists in the input
 *              tree, then that becomes the `middle node', which does not
 *              appear in either tree, and is returned separately.
 */

extern void *rbtree_splitat(struct bstree_nodecls */*cls*/,
                            struct bstnode **/*left_out*/, int */*lht_out*/,
                            int */*mht_out*/,
                            struct bstnode **/*right_out*/, int */*rht_out*/,
                            struct bstnode **/*root*/, const void */*key*/);

/* --- @rbtree_splitroot@ --- *
 *
 * Arguments:   @struct bstnode *left_out@ = where to leave the root of the
 *                      resulting left tree
 *              @int *lht_out@ = where to leave the black-height of the left
 *                      tree, or null to discard this information
 *              @int *mht_out@ = where to leave the black-height of the
 *                      middle node (either zero or one), or null to discard
 *                      this information
 *              @struct bstnode *right_out@ = where to leave the root of the
 *                      resulting right tree
 *              @int *rht_out@ = where to leave the black-height of the right
 *                      tree, or null to discard this information
 *              @struct bstnode **root@ = tree root node, or null
 *              @int blkht@ = black-height of the tree, or %$-1$% if unknown
 *
 * Returns:     A pointer to the resulting middle node, or null.
 *
 * Use:         Split a tree into two at its root.
 *
 *              The splitting operation produces two trees, a `left tree'
 *              containing every node preceding the root, and a `right
 *              tree' containing every node following the root, together with
 *              the root.  If the root is null, then the left and right trees
 *              are also null.
 */

extern void *rbtree_splitroot(struct bstnode **/*left_out*/,
                                int */*lht_out*/,
                              int */*mht_out*/,
                              struct bstnode **/*right_out*/,
                                int */*rht_out*/,
                              struct bstnode **/*root*/, int /*blkht*/);

/* --- @rbtree_unisect@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode **uni_out@ = where to write the union root
 *              @int *uniht_out@ = where to put the union height (or null)
 *              @struct bstnode **isect_out@ = where to write the
 *                      intersection root
 *              @int *isectht_out@ = where to put the intersection height (or
 *                      null)
 *              @struct bstnode *a@ = pointer to first operand root node
 *              @int aht@ = first operand height, or %$-1$%
 *              @struct bstnode *b@ = pointer to second operand root node
 *              @int bht@ = second operand height, or %$-1$%
 *
 * Returns:     ---
 *
 * Use:         Compute the union and intersection of the two operand trees.
 *
 *              The original trees are destroyed.  Each node in the original
 *              operands trees ends up in exactly one of the result trees.
 */

extern void rbtree_unisect(struct bstree_nodecls */*cls*/,
                           struct bstnode **/*uni_out*/,
                             int */*uniht_out*/,
                           struct bstnode **/*isect_out*/,
                             int */*isectht_out*/,
                           struct bstnode **/*aroot*/, int /*aht*/,
                           struct bstnode **/*broot*/, int /*bht*/);

/* --- @rbtree_diffsect@ --- *
 *
 * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 *              @struct bstnode **diff_out@ = where to write the difference
 *                      root
 *              @int *diffht_out@ = where to put the difference height (or
 *                      null)
 *              @struct bstnode **isect_out@ = where to write the
 *                      intersection root
 *              @int *isectht_out@ = where to put the intersection height (or
 *                      null)
 *              @struct bstnode *a@ = pointer to first operand root node
 *              @int aht@ = first operand height, or %$-1$%
 *              @struct bstnode *b@ = pointer to second operand root node
 *
 * Returns:     ---
 *
 * Use:         Compute the difference -- i.e., those nodes in %$a$% without
 *              matching nodes in %$b$% -- and intersection of the two
 *              operand trees.
 *
 *              The original tree %$a$% is destroyed.  Each node in the
 *              original operands tree ends up in exactly one of the result
 *              trees.  The input tree %$b$% is unchanged.
 */

extern void rbtree_diffsect(struct bstree_nodecls */*cls*/,
                            struct bstnode **/*diff_out*/, int */*diffht_out*/,
                            struct bstnode **/*isect_out*/,
                              int */*isectht_out*/,
                            struct bstnode **/*aroot*/, int /*aht*/,
                            struct bstnode **/*broot*/);

#endif