chiark - git - mdw - xyla/blob - bst.c

   1 #include <assert.h>
   2
   3 #include "bst.h"
   4
   5 /* --- @bstree_chkorder@ --- *
   6  *
   7  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
   8  *              @struct bstnode *const *root@ = pointer to root link
   9  *              @const struct bstnode *parent@ = pointer to parent, or null
  10  *              @const struct bstnode *lbound, *rbound@ = most recent
  11  *                      ancestors on the left and right, or null
  12  *              @const struct bstnode *node@ = node under consideration
  13  *              @unsigned ord@ = ordering pass
  14  *              @void *arg@ = ignored
  15  *
  16  * Returns:     Zero if everything was OK, %$-1$% if problems were found and
  17  *              reported.
  18  *
  19  * Use:         Check that the node satisfies the binary search tree ordering
  20  *              invariants.
  21  */
  22
  23 int bstree_chkorder(struct bstree_nodecls *cls,
  24                     struct bstnode *const *root,
  25                     const struct bstnode *parent,
  26                     const struct bstnode *lbound,
  27                     const struct bstnode *rbound,
  28                     const struct bstnode *node, unsigned ord,
  29                     void *arg)
  30 {
  31   bstree_idfn *idfn = cls->ops->id;
  32   const void *key;
  33   int rc = 0;
  34
  35   if (ord != BSTCHK_BEFORE) return (0);
  36   if (lbound) {
  37     key = cls->ops->key(cls, lbound);
  38     if (cls->ops->nav(cls, node, (/*unconst*/ void *)key) >= 0) {
  39       fprintf(stderr, "BSTREE %p BUG: node ", (void *)root);
  40       if (idfn) idfn(cls, node, stderr);
  41       else fprintf(stderr, "%p", (void*)node);
  42       fputs(" key not above lower bound\n", stderr);
  43       rc = -1;
  44     }
  45   }
  46   if (rbound) {
  47     key = cls->ops->key(cls, rbound);
  48     if (cls->ops->nav(cls, node, (/*unconst*/ void *)key) <= 0) {
  49       fprintf(stderr, "BSTREE %p BUG: node ", (void *)root);
  50       if (idfn) idfn(cls, node, stderr);
  51       else fprintf(stderr, "%p", (void*)node);
  52       fputs(" key not below upper bound\n", stderr);
  53       rc = -1;
  54     }
  55   }
  56   return (rc);
  57 }
  58
  59 /* Details on iterators.
  60  *
  61  * The structure holds a stack for the natural iterative conversion of the
  62  * recursive in-order traversal algorithm.
  63  *
  64  * Consider an arbitrary node %$n$% in a binary search tree.  The next nodes
  65  * to visit are those in %$n$%'s right subtree.  Then, if %$n$% is a left
  66  * child, we must visit %$n$%'s parent, followed by the subtree headed by
  67  * %$n$%'s sibling.
  68  *
  69  * The invariant that we maintain is as follows.
  70  *
  71  *   * If the stack is empty, then all nodes have been visited.
  72  *
  73  *   * If the stack is nonempty, then the topmost entry in the stack is the
  74  *     least node which has not yet been visited -- and therefore is the next
  75  *     node to visit.
  76  *
  77  *   * The lower entries in the stack are, in top-to-bottom order, those of
  78  *     the topmost stack node's ancestors, from parent to root, which have
  79  *     not yet been visited.  In other words, a node appears in the stack if
  80  *     and only if some node in its left subtree is nearer to the top of the
  81  *     stack.
  82  *
  83  * The stack is initialized by pushing the root, the root's left child, its
  84  * leftmost grandchild, and so on.  This establishes the invariants above:
  85  * the leftmost leaf is the first node to be visited, and its entire ancestry
  86  * is on the stack since none of these nodes has yet been visited.  If the
  87  * tree is empty, the root is null, so we have done nothing and left the
  88  * stack empty.
  89  *
  90  * When we come to actually visit a node, we pop the topmost node from the
  91  * stack.  We don't return it yet: we must restore the invariant.
  92  *
  93  *   * If the node to visit has a right subtree, then the next node to visit
  94  *     is the leftmost node in that subtree.  All of the nodes on the stack
  95  *     are unvisited ancestors of the current node, and therefore of every
  96  *     node in its right subtree.  We're just about to visit the current
  97  *     node, so that should indeed indeed have been removed.  The right
  98  *     subtree contains descendants of the current node, so they are not yet
  99  *     on the stack, but they have not yet been visited.  We therefore push
 100  *     the current node's right child, its left child, leftmost grandchild,
 101  *     and so on.
 102  *
 103  *   * Otherwise, we have just finished traversing a subtree.  Either we are
 104  *     now done, or we have just finished traversing the left subtree of the
 105  *     enxt topmost node on the stack.  This must therefore be the next node
 106  *     to visit, and the remainder of the stack is already correct.
 107  */
 108
 109 /* --- @bstree_inititer@ --- *
 110  *
 111  * Arguments:   @struct bstnode *root@ = pointer to the tree header
 112  *              @struct bstnode *stack@ = pointer to stack to initialize
 113  *              @int *sp_out@ = where to leave the initial stack pointer
 114  *
 115  * Returns:     ---
 116  *
 117  * Use:         Initialize an iterator for binary search trees with
 118  *              %%\emph{a priori}%% bounded height.  This function does not
 119  *              need to know the bound: the caller should simply allocate
 120  *              enough entries in the stack vector.
 121  */
 122
 123 void bstree_inititer(struct bstnode *root,
 124                      struct bstnode **stack, int *sp_out)
 125 {
 126   struct bstnode *node;
 127   int sp;
 128
 129   /* Push the root of each successive left subtree onto the stack.  The top
 130    * of the stack ends up holding the first item in the tree.
 131    */
 132   for (node = root, sp = 0; node; node = node->left) stack[sp++] = node;
 133   *sp_out = sp;
 134 }
 135
 136 /* --- @bstree_next@ --- *
 137  *
 138  * Arguments:   @struct bstnode *stack@ = pointer to iterator stack
 139  *              @int *sp_inout@ = stack pointer, updated
 140  *
 141  * Returns:     A pointer to the next node in ascending order, or null
 142  *              if no more nodes remain.
 143  *
 144  * Use:         Advances a tree iterator.  Inserting or removing elements
 145  *              invalidates the iterator.
 146  */
 147
 148 void *bstree_next(struct bstnode **stack, int *sp_inout)
 149 {
 150   struct bstnode *node, *next;
 151   int sp = *sp_inout;
 152
 153   if (!sp) {
 154     /* The stack is empty.  There are no more nodes to return. */
 155
 156     node = 0;
 157   } else {
 158     /* The topmost node on the stack is the next node to return.  Before
 159      * that, push the roots of each successive left subtree in the node's
 160      * right subtree onto the stack so that we can continue.
 161      */
 162
 163     node = stack[--sp];
 164     for (next = node->right; next; next = next->left)
 165       stack[sp++] = next;
 166     *sp_inout = sp;
 167   }
 168   return (node);
 169 }
 170
 171 /* Details on paths.
 172  *
 173  * The structure describes a path from the root to a node, or to a null link
 174  * denoting a place to insert a node, by indicating the links that are
 175  * followed.  A path which ends with a link to a node is a `full' path, while
 176  * one that ends with a null link is an `empty' path.
 177  *
 178  * The first link followed is always the root link in the tree header, so
 179  * @path[0]@ is always the address of the tree root link.  After that, each
 180  * step involves following a left or right pointer from a node to one of its
 181  * children, so, for %$0 \le i < k$%, we have
 182  *
 183  *   @path[i + 1] == &(*path[i])->left || path[i + 1] == &(*path[i])->right@.
 184  *
 185  * For reasons of internal convenience, @k@ is not the length of the path,
 186  * but one less than this, so @*path[k]@ is the node or null link which
 187  * terminates the path.
 188  */
 189
 190 /* --- @bstree_lookup@ --- *
 191  *
 192  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 193  *              @struct bstnode *root@ = pointer to root node
 194  *              @void *arg@ = argument to the navigation function
 195  *
 196  * Returns:     Pointer to the matching node, or null if it couldn't be
 197  *              found.
 198  *
 199  * Use:         Search for a node within the tree according to the navigation
 200  *              function.
 201  */
 202
 203 void *bstree_lookup(struct bstree_nodecls *cls,
 204                     struct bstnode *root, void *arg)
 205 {
 206   struct bstnode *node;
 207   bstree_navfn *navfn = cls->ops->nav;
 208   int dir;
 209
 210   /* Unsurprisingly, start at the root. */
 211   node = root;
 212
 213   /* Descend the tree. */
 214   for (;;) {
 215
 216     /* If we've reached the end, then give up. */
 217     if (!node) return (0);
 218
 219     /* Consult the navigation function to decide where to go next. */
 220     dir = navfn(cls, node, arg);
 221     if (dir < 0) node = node->left;
 222     else if (dir > 0) node = node->right;
 223     else return (node);
 224   }
 225 }
 226
 227 /* --- @bstree_probe@ --- *
 228  *
 229  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 230  *              @struct bstnode **root@ = pointer to root link
 231  *              @void *arg@ = the argument to the navigation function
 232  *              @struct bstnode ***path@ = path to fill in
 233  *              @int *k_out@ = length of path
 234  *
 235  * Returns:     Pointer to the matching node, or null if it couldn't be
 236  *              found.
 237  *
 238  * Use:         Search for a node within the tree according to the navigation
 239  *              function, recording the search path.
 240  *
 241  *              The tree must have bounded height.  The bound is implicit:
 242  *              the caller is simply expected to have allocated enough space
 243  *              in the path vector.
 244  */
 245
 246 void *bstree_probe(struct bstree_nodecls *cls,
 247                    struct bstnode **root, void *arg,
 248                    struct bstnode ***path, int *k_out)
 249 {
 250   struct bstnode *node, **link;
 251   bstree_navfn *navfn = cls->ops->nav;
 252   int k, dir;
 253
 254   /* This is the same as @bstree_lookup@ above, except that it also fills in
 255    * the path structure, as described above.
 256    */
 257
 258   /* Unsurprisingly, start at the root. */
 259   path[0] = root; k = 0; node = *root;
 260
 261   /* Descend the tree. */
 262   for (;;) {
 263
 264     /* If we've reached the end, then give up. */
 265     if (!node) break;
 266
 267     /* Consult the navigation function to decide where to go next. */
 268     dir = navfn(cls, node, arg);
 269     if (dir < 0) link = &node->left;
 270     else if (dir > 0) link = &node->right;
 271     else break;
 272
 273     /* Append the link to the path and continue. */
 274     path[++k] = link; node = *link;
 275   }
 276   *k_out = k; return (node);
 277 }
 278
 279 /* --- @bstree_firstpath@, @bstree_lastpath@ --- *
 280  *
 281  * Arguments:   @struct bstnode **root@ = address of the tree root link
 282  *              @struct bstnode ***path@ = path to fill in
 283  *              @int *k_out@ = length of path
 284  *
 285  * Returns:     Pointer to the requested node, or null if the tree is empty.
 286  *
 287  * Use:         Return the first or last node in the tree, as ordered by
 288  *              their keys, together with a path to the requested node, which
 289  *              can be used to remove them, or to navigate to other nodes in
 290  *              the tree.
 291  *
 292  *              The tree must have bounded height.  The bound is implicit:
 293  *              the caller is simply expected to have allocated enough space
 294  *              in the path vector.
 295  */
 296
 297 #define DEF_INITPATH(name, dir)                                         \
 298   struct bstnode *bstree_##name(struct bstnode **root,                  \
 299                                 struct bstnode ***path, int *k_out)     \
 300   {                                                                     \
 301     struct bstnode *node, *next;                                        \
 302     int k;                                                              \
 303                                                                         \
 304     /* A path always begins with the root link. */                      \
 305     k = 0; path[0] = root;                                              \
 306                                                                         \
 307     /* If there are elements then we can trace out a full path to one   \
 308      * end of the tree.  There's a slight inconsistency here because    \
 309      * the root link will be present regardless of whether the path is  \
 310      * full or empty.                                                   \
 311      */                                                                 \
 312     node = *root;                                                       \
 313     if (node)                                                           \
 314       for (;;) {                                                        \
 315         next = node->dir; if (!next) break;                             \
 316         path[++k] = &node->dir; node = next;                            \
 317       }                                                                 \
 318                                                                         \
 319     /* Done. */                                                         \
 320     *k_out = k; return (node);                                          \
 321   }
 322
 323 DEF_INITPATH(firstpath, left)
 324 DEF_INITPATH(lastpath, right)
 325
 326 #undef DEF_INITPATH
 327
 328 /* --- @bstree_nextpath@, @bstree_prevpath@ --- *
 329  *
 330  * Arguments:   @struct bstnode ***path@ = path to update
 331  *              @int *k_inout@ = length of path
 332  *
 333  * Returns:     Pointer to the requested node, or null if the tree is empty
 334  *              or the path is already positioned at the relevant extreme.
 335  *
 336  * Use:         Return the next or previous node in the tree, as ordered by
 337  *              their keys, together with a path to the requested node, which
 338  *              can be used to remove them, or to navigate to other nodes in
 339  *              the tree.
 340  *
 341  *              If the path is full, i.e., refers to an existing node, then
 342  *              the functions return that node's successor or predecessor.
 343  *              If the path is empty, i.e., refers to a space between nodes
 344  *              where a new node can be inserted, then the functions return
 345  *              the node at the upper or lower end of the gap, unless the
 346  *              `gap' is actually at an extreme of the tree and no such node
 347  *              exists.  In the latter case, a null pointer is returned.
 348  *              The path is modified to refer to the new node, if any, or to
 349  *              the gap at the appropriate extreme of the tree.
 350  *
 351  *              The tree must have bounded height.  The bound is implicit:
 352  *              the caller is simply expected to have allocated enough space
 353  *              in the path vector.
 354  */
 355
 356 #define DEF_STEPPATH(name, dir, opp)                                    \
 357   struct bstnode *bstree_##name(struct bstnode ***path, int *k_inout)   \
 358   {                                                                     \
 359     struct bstnode **link, **parent, *start, *node, *next;              \
 360     int k = *k_inout;                                                   \
 361                                                                         \
 362     /* Find the designated node, and the link address. */               \
 363     link = path[k]; start = *link;                                      \
 364                                                                         \
 365     /* If there's a node, then we might be able to explore its subtree  \
 366      * on the required side.                                            \
 367      */                                                                 \
 368     if (start) {                                                        \
 369       next = start->dir;                                                \
 370       if (next) {                                                       \
 371         /* There is indeed a subtree on the relevant side.  We need to  \
 372          * chase links in the opposite direction to find the next node. \
 373          */                                                             \
 374                                                                         \
 375         /* Descend into the subtree. */                                 \
 376         path[++k] = &start->dir; node = next;                           \
 377                                                                         \
 378         /* And chase links back. */                                     \
 379         for (;;) {                                                      \
 380           next = node->opp; if (!next) break;                           \
 381           path[++k] = &node->opp; node = next;                          \
 382         }                                                               \
 383                                                                         \
 384         /* The last item in the path is the link to the chosen node. */ \
 385         *k_inout = k; return (node);                                    \
 386       }                                                                 \
 387     }                                                                   \
 388                                                                         \
 389     /* Otherwise, we must ascend the tree, searching for the most       \
 390      * recent ancestor in the required direction.                       \
 391      */                                                                 \
 392     for (;;) {                                                          \
 393                                                                         \
 394       /* If there's no more tree to ascend, set the path to refer to a  \
 395        * nonexistent node beyond the initial node and return.           \
 396        */                                                               \
 397       if (!k) {                                                         \
 398         if (start)                                                      \
 399           { k = *k_inout; path[k] = &start->dir; *k_inout = k + 1; }    \
 400         return (0);                                                     \
 401       }                                                                 \
 402                                                                         \
 403       /* Ascend the tree. */                                            \
 404       parent = path[--k]; node = *parent;                               \
 405                                                                         \
 406       /* If the ancestor's link to its child in the path is in the      \
 407        * opposite direction to the one we require, then this ancestor   \
 408        * is indeed the node we seek.                                    \
 409        */                                                               \
 410       if (link == &node->opp) { *k_inout = k; return (node); }          \
 411                                                                         \
 412       /* Otherwise continue the search up the tree. */                  \
 413       link = parent;                                                    \
 414     }                                                                   \
 415   }
 416
 417 DEF_STEPPATH(nextpath, right, left)
 418 DEF_STEPPATH(prevpath, left, right)
 419
 420 #undef DEF_STEPPATH
 421
 422 /* --- @bstree_beforepath@, @bstree_afterpath@ --- *
 423  *
 424  * Arguments:   @struct bstnode ***path@ = (full) path to update
 425  *              @int *k_inout@ = length of path, updated
 426  *
 427  * Returns:     ---
 428  *
 429  * Use:         Advance the path to just before or after the current node.
 430  *              The path thereby becomes empty, suitable to insert an element
 431  *              or split the tree just before or after the previously
 432  *              selected node.
 433  */
 434
 435 #define DEF_MISSPATH(name, dir, opp)                                    \
 436   void bstree_##name(struct bstnode ***path, int *k_inout)              \
 437   {                                                                     \
 438     struct bstnode *node;                                               \
 439     int k;                                                              \
 440                                                                         \
 441     k = *k_inout; node = *path[k]; assert(node);                        \
 442     path[++k] = &node->dir; node = node->dir;                           \
 443     while (node) { path[++k] = &node->opp; node = node->opp; }          \
 444   }
 445
 446 DEF_MISSPATH(beforepath, left, right)
 447 DEF_MISSPATH(afterpath, right, left)
 448
 449 #undef DEF_MISSPATH
 450
 451 /* --- @bstree_remove@ --- *
 452  *
 453  * Arguments:   @struct bstnode **del_out@ = pointer to deleted node
 454  *              @struct bstnode **subst_out@ = pointer to substituted node
 455  *              @struct bstnode **replace_out@ = pointer to replacement node
 456  *              @struct bstnode ***path@ = (full) path to consult and update
 457  *              @int *k_inout@ = length of path, updated
 458  *
 459  * Returns:     ---
 460  *
 461  * Use:         Remove a node from a binary search tree.
 462  *
 463  *              The path must be full, i.e., it must refer to a node present
 464  *              in the tree.  That node is returned as @*del_out@.
 465  *
 466  *              If the deleted node has two children, then it can't easily be
 467  *              disentangled from the tree.  Instead, the node is swapped
 468  *              with its immediate successor, which must exist because the
 469  *              node has two children and therefore a right child.  On the
 470  *              other hand, the immediate successor is the leftmost node in
 471  *              the deleted node's right subtree, and therefore has no left
 472  *              child.  In this case, @*subst_node@ is set to the successor
 473  *              node, which may require some further fixing up (e.g., to
 474  *              maintain balance state).  The path is extended to refer to
 475  *              the place at which the successor node was linked.  If the
 476  *              deleted node doesn't have both children, none of this is
 477  *              necessary: @*subst_node@ is set to null, and the path is left
 478  *              unchanged.
 479  *
 480  *              The node (after substitution) is replaced with its child, if
 481  *              it has one, or a null pointer.  This replacement node is
 482  *              returned in @*replace_out@.
 483  *
 484  *              The modified nodes are all on the @path@; updating them is
 485  *              left for the caller.
 486  */
 487
 488 void bstree_remove(struct bstnode **del_out, struct bstnode **subst_out,
 489                    struct bstnode **replace_out,
 490                    struct bstnode ***path, int *k_inout)
 491 {
 492   struct bstnode *t, *s, *n, *l, *r;
 493   struct bstnode **tlink, **slink;
 494   int j, k;
 495
 496   /* Let's take a look at the node we're supposed to remove. */
 497   k = *k_inout; tlink = path[k]; t = *tlink; assert(t);
 498   l = t->left; r = t->right;
 499
 500   if (!l) {
 501     /* This node has no left child.  Replace it with its right child. */
 502
 503     *tlink = n = r; s = 0;
 504   } else if (!r) {
 505     /* This node has no right child.  Replace it with its left child. */
 506
 507     *tlink = n = l; s = 0;
 508   } else {
 509     /* This node has two children, so we'll have to rearrange some links in
 510      * the tree.  We'll replace it with its successor -- the smallest node in
 511      * its right subtree, and then proceed to fix up the tree as if we'd
 512      * deleted the successor node.
 513      *
 514      * Usually, textbooks will copy the successor node's payload into the
 515      * target node and then remove the successor, but that won't do for us
 516      * because node identity is significant.  The caller allocated them and
 517      * there might be all sorts of weird stuff in the same allocated block
 518      * that we don't understand.  So we'll have to actually unhook the nodes
 519      * and relink them into their new places.  And we'll have to adjust the
 520      * path as well.
 521      */
 522
 523     /* We must descend the tree to find the successor node and extend the
 524      * path.  We're going to replace the current node, so there's no point
 525      * capturing its rightward link yet.
 526      */
 527     s = r; n = s->left;
 528     if (!n) {
 529       /* The right child is %$t$%'s successor.
 530        *
 531        *                *
 532        *                |                               *
 533        *                t                               |
 534        *             /     \                            s
 535        *          l           s         --->         /     \
 536        *        /   \       /   \                 l           n
 537        *                 _|_      n             /   \       /   \
 538        *                        /   \
 539        */
 540
 541       n = s->right;
 542       *tlink = s; s->left = l;
 543       path[++k] = &s->right;
 544     } else {
 545       /* The right child has a non-empty left subtree, so descend to the left
 546        * to find %$t$%'s successor.
 547        *
 548        *                *
 549        *                |                               *
 550        *                t                               |
 551        *             /      \                           s
 552        *          l            r        --->         /     \
 553        *        /   \        /   \                l           r
 554        *                    :                   /   \       /   \
 555        *                   /                               :
 556        *                 s                                /
 557        *               /   \                            n
 558        *            _|_      n                        /   \
 559        *                   /   \
 560        */
 561
 562       /* Descend to the left, extending the path. */
 563       j = ++k;
 564       do { path[++k] = slink = &s->left; s = n; n = s->left; } while (n);
 565
 566       /* Collect the substitute node. */
 567       n = s->right;
 568
 569       /* Hook the successor into place and fill in the gap in the path. */
 570       *tlink = s; *slink = n;
 571       s->left = l; s->right = r;
 572       path[j] = &s->right;
 573     }
 574     *k_inout = k;
 575   }
 576
 577   /* Return the results. */
 578   *del_out = t; *subst_out = s; *replace_out = n;
 579 }
 580
 581 /* --- @bstree_unisect@ --- *
 582  *
 583  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 584  *              @struct bstnode **uni_out@ = where to write the union root
 585  *              @int *uniht_out@ = where to put the union height (or null)
 586  *              @struct bstnode **isect_out@ = where to write the
 587  *                      intersection root
 588  *              @int *isectht_out@ = where to put the intersection height (or
 589  *                      null)
 590  *              @struct bstnode *a@ = pointer to first operand root node
 591  *              @int aht@ = first operand height
 592  *              @struct bstnode *b@ = pointer to second operand root node
 593  *              @int bht@ = second operand height
 594  *              @const struct bstree_treeops *ops@ = pointer to tree
 595  *                      (split/join) operations table
 596  *              @struct bstree_setopstack *stack@ = pointer to sufficiently
 597  *                      large stack vector
 598  *
 599  * Returns:     ---
 600  *
 601  * Use:         Compute the union and intersection of the two operand trees.
 602  *
 603  *              The original trees are destroyed.  Each node in the original
 604  *              operands trees ends up in exactly one of the result trees.
 605  */
 606
 607 void bstree_unisect(struct bstree_nodecls *cls,
 608                     struct bstnode **uni_out, int *uniht_out,
 609                     struct bstnode **isect_out, int *isectht_out,
 610                     struct bstnode *a, int aht,
 611                     struct bstnode *b, int bht,
 612                     const struct bstree_treeops *ops,
 613                     struct bstree_setopstack *stack)
 614 {
 615   struct bstnode *uni, *isect, *node;
 616   int uniht, isectht;
 617   struct bstree_nodeops nodeops = *cls->ops;
 618   struct bstree_treeops treeops = *ops;
 619   int sp = 0;
 620
 621   enum { RIGHT, JOIN };
 622
 623   /* This is an essentially recursive procedure based on the following
 624    * observations.  Let %$A$% and %$B$% be sets of ordered elements.
 625    *
 626    *   * If %$A = \emptyset%$ then %$A \cup B = B$% and
 627    *     %$A \cap B = \emptyset$%.
 628    *
 629    *   * If %$B = \emptyset%$ then %$A \cup B = A$% and
 630    *     %$A \cap B = \emptyset$%.
 631    *
 632    *   * Otherwise, let %$a \in A$% be any element.  Let
 633    *
 634    *       -- %$A_L = \setcomp{x \in A}{x < A}$%,
 635    *       -- %$A_R = \setcomp{x \in A}{x > A}$%,
 636    *       -- %$B_L = \setcomp{x \in B}{x < B}$%,
 637    *       -- %$B_M = B \cap \set{a}$%, and
 638    *       -- %$B_R = \setcomp{x \in B}{x > B}$%.
 639    *
 640    * Then
 641    *
 642    *   * %$A \cup B = (A_L \cup B_L) \uplus \set{a} \uplus (A_R \cup B_R)$%,
 643    *     and
 644    *
 645    *   * %$A \cap B = (A_L \cap B_L) \uplus \B_M \uplus (A_R \cap B_R)$%.
 646    *
 647    * In practice, we select %$a$% as the root of the %$A$% tree: the provided
 648    * @splitroot@ operation selects %$a$% and determines %$A_L$% and %$A_R$%;
 649    * the @splitat@ operation determines %$B_L$%, %$B_M$%, and %$B_R$%; and
 650    * the @join@ operator performs the disjoint unions.
 651    *
 652    * Rather than actual recursion, we maintain an explicit stack.  A
 653    * recursive call is replaced by pushing the remaining state on a stack and
 654    * returning to the initial label @entry@.  A `return' pops a state from
 655    * the stack and forces control back to the appropriate place.  If you
 656    * squint, then a sequence @stack[sp++].op = FOO; goto entry; foo:@ takes
 657    * the place of a recursive call.
 658    */
 659
 660 entry:
 661   if (!a) {
 662     /* First base case.  If %$A$% is empty, then the union must be %$B$%, and
 663      * the intersection is empty.
 664      */
 665
 666     uni = b; uniht = bht; isect = 0; isectht = 0;
 667   } else if (!b) {
 668     /* Second base case.  Symmetrically, if %$B$% is empty, then the union
 669      * must be %$A$%, and the intersection is empty.
 670      */
 671
 672     uni = a; uniht = aht; isect = 0; isectht = 0;
 673   } else {
 674     /* Recursive case. */
 675
 676     /* Select an element %$a \in A$% and split %$A - \set{a}$% into two
 677      * halves.
 678      */
 679     node = treeops.splitroot(&a, &aht, 0,
 680                              &stack[sp].u.right.a, &stack[sp].u.right.aht,
 681                              &a, aht);
 682     stack[sp].am = node;
 683
 684     /* Split %$B$% into three pieces. */
 685     stack[sp].bm = treeops.splitat(cls,
 686                                    &b, &bht, 0,
 687                                    &stack[sp].u.right.b,
 688                                      &stack[sp].u.right.bht,
 689                                    &b, nodeops.key(cls, node));
 690
 691     /* Recursively compute the union and intersection of the low halves. */
 692     stack[sp++].op = RIGHT; goto entry;
 693
 694   right:
 695     /* Recursively compute the union and intersection of the high halves.
 696      * This is mostly just shuffling the data about.
 697      */
 698
 699     a = stack[sp].u.right.a; aht = stack[sp].u.right.aht;
 700     b = stack[sp].u.right.b; bht = stack[sp].u.right.bht;
 701     stack[sp].u.join_union.uni = uni;
 702     stack[sp].u.join_union.uniht = uniht;
 703     stack[sp].u.join_union.isect = isect;
 704     stack[sp].u.join_union.isectht = isectht;
 705     stack[sp++].op = JOIN; goto entry;
 706
 707   join:
 708     /* Stitch the answers together to compute the result. */
 709
 710     uniht = treeops.join(cls, &uni,
 711                          &stack[sp].u.join_union.uni,
 712                            stack[sp].u.join_union.uniht,
 713                          stack[sp].am,
 714                          &uni, uniht);
 715     isectht = treeops.join(cls, &isect,
 716                            &stack[sp].u.join_union.isect,
 717                            stack[sp].u.join_union.isectht,
 718                            stack[sp].bm,
 719                            &isect, isectht);
 720   }
 721
 722   /* If the stack isn't empty then we've performed a `recursive' step and
 723    * should return to the appropriate place.
 724    */
 725   if (sp) switch (stack[--sp].op) {
 726     case RIGHT: goto right;
 727     case JOIN: goto join;
 728     default: assert(0);
 729   }
 730
 731   /* All is done. */
 732   *uni_out = uni; if (uniht_out) *uniht_out = uniht;
 733   *isect_out = isect; if (isectht_out) *isectht_out = isectht;
 734 }
 735
 736 /* --- @bstree_diffsect@ --- *
 737  *
 738  * Arguments:   @struct bstree_nodecls *cls@ = node class for the tree
 739  *              @struct bstnode **diff_out@ = where to write the difference
 740  *                      root
 741  *              @int *diffht_out@ = where to put the difference height (or
 742  *                      null)
 743  *              @struct bstnode **isect_out@ = where to write the
 744  *                      intersection root
 745  *              @int *isectht_out@ = where to put the intersection height (or
 746  *                      null)
 747  *              @struct bstnode *a@ = pointer to first operand root node
 748  *              @int aht@ = first operand height
 749  *              @struct bstnode *b@ = pointer to second operand root node
 750  *              @const struct bstree_treeops *ops@ = pointer to tree
 751  *                      (split/join) operations table
 752  *              @struct bstree_setopstack *stack@ = pointer to sufficiently
 753  *                      large stack vector
 754  *
 755  * Returns:     ---
 756  *
 757  * Use:         Compute the difference -- i.e., those nodes in %$a$% without
 758  *              matching nodes in %$b$% -- and intersection of the two
 759  *              operand trees.
 760  *
 761  *              The original tree %$a$% is destroyed.  Each node in the
 762  *              original operands tree ends up in exactly one of the result
 763  *              trees.  The input tree %$b$% is unchanged.
 764  */
 765
 766 void bstree_diffsect(struct bstree_nodecls *cls,
 767                      struct bstnode **diff_out, int *diffht_out,
 768                      struct bstnode **isect_out, int *isectht_out,
 769                      struct bstnode *a, int aht,
 770                      struct bstnode *b,
 771                      const struct bstree_treeops *ops,
 772                      struct bstree_setopstack *stack)
 773 {
 774   struct bstnode *diff, *isect;
 775   int diffht, isectht;
 776   struct bstree_nodeops nodeops = *cls->ops;
 777   struct bstree_treeops treeops = *ops;
 778   int sp = 0;
 779
 780   enum { RIGHT, JOIN };
 781
 782   /* This is an essentially recursive procedure, similar to %$bstree_unisect@
 783    * above, based on the following observations.  Let %$A$% and %$B$% be sets
 784    * of ordered elements.
 785    *
 786    *   * If %$A = \emptyset%$ then %$A - B = \emptyset $% and
 787    *     %$A \cap B = \emptyset$%.
 788    *
 789    *   * If %$B = \emptyset%$ then %$A - B = A$% and
 790    *     %$A \cap B = \emptyset$%.
 791    *
 792    *   * Otherwise, let %$b \in B$% be any element.  Let
 793    *
 794    *       -- %$A_L = \setcomp{x \in A}{x < A}$%,
 795    *       -- %$A_M = A \cap \set{b}$%,
 796    *       -- %$A_R = \setcomp{x \in A}{x > A}$%,
 797    *       -- %$B_L = \setcomp{x \in B}{x < B}$%, and
 798    *       -- %$B_R = \setcomp{x \in B}{x > B}$%.
 799    *
 800    * Then
 801    *
 802    *   * %$A - B = (A_L - B_L) \uplus (A_R - B_R)$%, and
 803    *
 804    *   * %$A \cap B = (A_L \cap B_L) \uplus \A_M \uplus (A_R \cap B_R)$%.
 805    *
 806    * In practice, we select %$b$% as the root of the %$B$% tree, and %$B_L$%
 807    * and %$B_R$% are simply its left and right subtrees; it's safe to treat
 808    * %$B$% as a simple binary search tree, since we never actually pass nodes
 809    * of %$B$% to the provided operations.  The @splitat@ operation determines
 810    * %$A_L$%, %$A_M$%, and %$A_R$%; and the @join@ operation performs the
 811    * disjoint unions.
 812    *
 813    * Rather than actual recursion, we maintain an explicit stack.  A
 814    * recursive call is replaced by pushing the remaining state on a stack and
 815    * returning to the initial label @entry@.  A `return' pops a state from
 816    * the stack and forces control back to the appropriate place.  If you
 817    * squint, then a sequence @stack[sp++].op = FOO; goto entry; foo:@ takes
 818    * the place of a recursive call.
 819    */
 820
 821 entry:
 822   if (!a) {
 823     /* First base case.  If %$A$% is empty, then the difference and
 824      * intersection must be both be empty.
 825      */
 826
 827     diff = 0; diffht = 0; isect = 0; isectht = 0;
 828   } else if (!b) {
 829     /* Second base case.  If %$B$% is empty, then the difference is %$A$%,
 830      * and the intersection is empty.
 831      */
 832
 833     diff = a; diffht = aht; isect = 0; isectht = 0;
 834   } else {
 835     /* Recursive case. */
 836
 837     /* Split %$A$% into three pieces according to the root of the %$B$%
 838      * tree.
 839      */
 840     stack[sp].am = treeops.splitat(cls,
 841                                    &a, &aht, 0,
 842                                    &stack[sp].u.right.a,
 843                                      &stack[sp].u.right.aht,
 844                                    &a, nodeops.key(cls, b));
 845
 846     /* Recursively compute the difference and intersection of the low
 847      * halves.
 848      */
 849     stack[sp].u.right.b = b->right;
 850     b = b->left;
 851     stack[sp++].op = RIGHT; goto entry;
 852
 853   right:
 854     /* Recursively compute the union and intersection of the high halves.
 855      * This is mostly just shuffling the data about.
 856      */
 857
 858     a = stack[sp].u.right.a; aht = stack[sp].u.right.aht;
 859     b = stack[sp].u.right.b;
 860     stack[sp].u.join_diff.diff = diff;
 861     stack[sp].u.join_diff.diffht = diffht;
 862     stack[sp].u.join_diff.isect = isect;
 863     stack[sp].u.join_diff.isectht = isectht;
 864     stack[sp++].op = JOIN; goto entry;
 865
 866   join:
 867     /* Stitch the answers together to compute the result. */
 868
 869     diffht = treeops.join(cls, &diff,
 870                           &stack[sp].u.join_diff.diff,
 871                             stack[sp].u.join_diff.diffht,
 872                           0,
 873                           &diff, diffht);
 874     isectht = treeops.join(cls, &isect,
 875                            &stack[sp].u.join_diff.isect,
 876                              stack[sp].u.join_diff.isectht,
 877                            stack[sp].am,
 878                            &isect, isectht);
 879   }
 880
 881   /* If the stack isn't empty then we've performed a `recursive' step and
 882    * should return to the appropriate place.
 883    */
 884   if (sp) switch (stack[--sp].op) {
 885     case RIGHT: goto right;
 886     case JOIN: goto join;
 887     default: assert(0);
 888   }
 889
 890   /* All is done. */
 891   *diff_out = diff; if (diffht_out) *diffht_out = diffht;
 892   *isect_out = isect; if (isectht_out) *isectht_out = isectht;
 893 }