chiark - git - mdw - xyla/blob - treap-splitjoin.c

   1 /* -*-c-*-
   2  *
   3  * Splitting and joining treaps
   4  *
   5  * (c) 2024 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Xyla, a library of binary trees.
  11  *
  12  * Xyla is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU Lesser General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Xyla is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20  * License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include "lib.h"
  29 #include "treap.h"
  30
  31 /*----- Main code ---------------------------------------------------------*/
  32
  33 int xyla_treap_join(struct xyla_bt_nodecls *cls,
  34                     struct xyla_bt_node **root_out,
  35                     struct xyla_bt_node **left,
  36                     struct xyla_bt_node *mid,
  37                     struct xyla_bt_node **right)
  38 {
  39   /* Concatenate the two trees rooted at LEFT and RIGHT in order; if MID is
  40    * not null, then place this node between them.  The root of the resulting
  41    * tree is stored in *ROOT_OUT.  It's the caller's responsibility to ensure
  42    * that this respects any ordering invariants.
  43    *
  44    * The ROOT_OUT pointer may equal either LEFT or RIGHT (or, indeed, both,
  45    * only if both are empty).  If LEFT is distinct from ROOT_OUT then *LEFT
  46    * is set null on exit; similarly, if RIGHT is distinct from ROOT_OUT, then
  47    * *RIGHT is set null on exit.
  48    *
  49    * Returns `XYLA_RC_OK'.
  50    */
  51
  52   struct xyla_treap_node
  53     *l = TREAP_NODE(*left), *m = TREAP_NODE(mid), *r = TREAP_NODE(*right);
  54   struct xyla_bt_node **nlink;
  55   size_t mwt, lwt, rwt;
  56   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
  57   struct xyla_treap_path path;
  58
  59   if (!m) {
  60     /* There's no joining node, and we just have to stitch the two trees
  61      * together.  Suppose that the left root is lighter than the right root.
  62      * Work down the right edge of the left tree until we find a node that's
  63      * heavier than the right root, replace the subtree rooted at that
  64      * heavier node by the right tree, and switch to joining the now-detached
  65      * subtree into the left edge of the right tree.
  66      */
  67
  68     /* Before we really get stuck in, there are some special cases. */
  69     if (!r) { *root_out = l ? &l->bt : 0; goto end; }
  70     else if (!l) { *root_out = r ? &r->bt : 0; goto end; }
  71
  72     /* Set up the path and the weights, and dispatch. */
  73     nlink = path.p[0] = root_out; path.k = 0;
  74     lwt = l->trp.wt; rwt = r->trp.wt;
  75     if (lwt <= rwt) goto stitch_right;
  76     else goto stitch_left;
  77
  78 #define JOIN_STITCH(right, r, rwt, left, l, lwt) do {                   \
  79   stitch_##right:                                                       \
  80     /* The left node is lighter. */                                     \
  81                                                                         \
  82     V( if (xyla__verbout && (xyla__verbose&XYLA__VF_JOIN))              \
  83          fputs("XYLA-TREAP JOIN stitch " #right " edge\n",              \
  84                xyla__verbout); )                                        \
  85                                                                         \
  86     /* Hook the left tree onto the most recent tree. */                 \
  87     *nlink = &l->bt;                                                    \
  88                                                                         \
  89     /* Work along the right edge to find a node heavier than the right  \
  90      * root, and then switch.  If we reach the end, then just hook the  \
  91      * right tree in entirely.                                          \
  92      */                                                                 \
  93     for (;;) {                                                          \
  94       if (path.k >= XYLA_TREAP_HTMAX) xyla__treap_boundfail();          \
  95       nlink = path.p[++path.k] = &l->bt.right;                          \
  96       l = TREAP_NODE(l->bt.right);                                      \
  97       if (!l) { *nlink = &r->bt; goto stitch_done; }                    \
  98       lwt = l->trp.wt; if (lwt > rwt) goto stitch_##left;               \
  99     }                                                                   \
 100 } while (0)
 101     JOIN_STITCH(right, r, rwt, left, l, lwt);
 102     JOIN_STITCH(left, l, lwt, right, r, rwt);
 103 #undef JOIN_STITCH
 104
 105   stitch_done:
 106     /* Follow the rest of the path up to the root, updating the nodes. */
 107     if (updfn) while (path.k) updfn(cls, *path.p[--path.k]);
 108
 109   } else {
 110     /* We have two trees and a joining node.  If we pretend that the joining
 111      * node is very light, it will serve as the new root of the combined
 112      * tree.  Then we allow it to sink down to the right level according to
 113      * its actual weight.  The details are a bit messy, however: this is the
 114      * only point in the code where we do a full `downheap' operation where
 115      * we need to consider the relative ordering of three different nodes.
 116      */
 117
 118     /* Clear the input trees. */
 119     *left = *right = 0;
 120     nlink = path.p[0] = root_out; path.k = 0;
 121
 122     /* Initial dispatch. */
 123     mwt = m->trp.wt;
 124     if (!l) {
 125       if (r) { rwt = r->trp.wt; goto mid_right; }
 126       else goto mid_done;
 127     }
 128     lwt = l->trp.wt;
 129     if (!r) goto mid_left;
 130     rwt = r->trp.wt; goto mid_both;
 131
 132   mid_both:
 133     /* The current slot has two children.  Further dispatching. */
 134
 135     for (;;) {
 136       if (lwt <= rwt)
 137 #define JOIN_MID(left, l, lwt, right, r, rwt, next) do {                \
 138         if (mwt <= lwt) goto mid_done;                                  \
 139                                                                         \
 140         /* Promote the left child.                                      \
 141          *                                                              \
 142          *                                              l               \
 143          *            n                           (*)                   \
 144          *              ( )                     /     \     n           \
 145          *      l     /     \     r     --->            ( )             \
 146          *        (*)         (*)                      /   \    r       \
 147          *       /   \       /   \                          (*)         \
 148          *                                                 /   \        \
 149          */                                                             \
 150         V( if (xyla__verbout && (xyla__verbose&XYLA__VF_JOIN))          \
 151              fputs("XYLA-TREAP JOIN mid float " #left                   \
 152                    " (next " #next ")\n", xyla__verbout); )             \
 153           if (path.k >= XYLA_TREAP_HTMAX) xyla__treap_boundfail();      \
 154         *nlink = &l->bt; nlink = path.p[++path.k] = &l->bt.right;       \
 155         l = TREAP_NODE(l->bt.right);                                    \
 156         if (!l) goto mid_##next;                                        \
 157         else lwt = l->trp.wt;                                           \
 158 } while (0)
 159         JOIN_MID(left, l, lwt, right, r, rwt, right);
 160       else
 161         JOIN_MID(right, r, rwt, left, l, lwt, left);
 162     }
 163
 164   mid_left:
 165     /* The current node has only a left child.  Either it's lighter than the
 166      * left child, in which case we're done, or we rotate.  In the latter
 167      * case, it's clear from the diagram above that the right subtree of our
 168      * focus node remains null.
 169      */
 170     for (;;) JOIN_MID(left, l, lwt, right, r, rwt, done);
 171
 172   mid_right:
 173     /* The current node has only a right child. */
 174     for (;;) JOIN_MID(right, r, rwt, left, l, lwt, done);
 175
 176 #undef JOIN_MID
 177
 178   mid_done:
 179     /* We've found the level.  Hook the joining node into place. */
 180     *nlink = &m->bt;
 181     m->bt.left = l ? &l->bt : 0;
 182     m->bt.right = r ? &r->bt : 0;
 183
 184     /* Follow the rest of the path up to the root, updating the nodes. */
 185     if (updfn) {
 186       updfn(cls, &m->bt);
 187       while (path.k) updfn(cls, *path.p[--path.k]);
 188     }
 189   }
 190
 191 end:
 192   /* All done. */
 193   return (XYLA_RC_OK);
 194 }
 195
 196 int xyla_treap_split(struct xyla_bt_nodecls *cls,
 197                      struct xyla_bt_node **left_out,
 198                      struct xyla_bt_node **mid_out,
 199                      struct xyla_bt_node **right_out,
 200                      struct xyla_treap_path *path)
 201 {
 202   /* Split a tree tree into two at the indicated place indicated by the PATH.
 203    * Store in *LEFT_OUT and *RIGHT_OUT the roots of trees containing every
 204    * node respectively preceding and following the PATH.
 205    *
 206    * If the PATH is full, i.e., it denotes a node in the input tree, then
 207    * that becomes the `middle node', which does not appear in either output
 208    * tree; a pointer to this node is stored in *MID_OUT.
 209    *
 210    * Returns `XYLA_RC_OK'.
 211    */
 212
 213   struct xyla_treap_node *n, *p, *l, *r;
 214   struct xyla_bt_node **nlink, **plink;
 215   xyla_bt_updfn *updfn = cls ? cls->ops->upd : 0;
 216   int k = path->k;
 217
 218   /* This is essentially the reverse of joining.  We pretend that the
 219    * selected node -- or an imaginary node, if the path is empty -- has
 220    * become very light and let it float all the way up until becomes the tree
 221    * root, at which point the tree just falls apart into two pieces.  This
 222    * doesn't actually involve any weight comparisons!
 223    */
 224
 225   /* Initial setup. */
 226   nlink = path->p[k]; n = TREAP_NODE(*nlink);
 227   if (!n)
 228     l = r = 0;
 229   else {
 230     l = TREAP_NODE(n->bt.left); r = TREAP_NODE(n->bt.right);
 231     n->bt.left = n->bt.right = 0;
 232   }
 233
 234   /* Float the node up. */
 235   while (k) {
 236     plink = path->p[--k]; p = TREAP_NODE(*plink);
 237
 238     /* Adjust the links. */
 239     if (nlink == &p->bt.left)
 240 #define FIXUP_SPLIT(left, l, right, r) do {                             \
 241       /* We're the left child.                                          \
 242        *                                                                \
 243        *               p                                                \
 244        *                 (*)                         ( )                \
 245        *               /     \                     /     \              \
 246        *           ( )                  --->    l          (*)          \
 247        *          /   \                                   /   \         \
 248        *        l       r                               r               \
 249        */                                                               \
 250                                                                         \
 251       V( if (xyla__verbout && (xyla__verbose&XYLA__VF_SPLIT))           \
 252            fputs("XYLA-TREAP SPLIT " #left " child\n",                  \
 253                  xyla__verbout); )                                      \
 254       p->bt.left = r ? &r->bt : 0; r = p;                               \
 255 } while (0)
 256       FIXUP_SPLIT(left, l, right, r);
 257     else
 258       FIXUP_SPLIT(right, r, left, l);
 259 #undef FIXUP_SPLIT
 260
 261     /* And ascend the tree. */
 262     if (updfn) updfn(cls, &p->bt);
 263     nlink = plink;
 264   }
 265
 266   /* And we're done. */
 267   *nlink = 0;
 268   *left_out = l ? &l->bt : 0;
 269   *mid_out = n ? &n->bt : 0;
 270   *right_out = r ? &r->bt : 0;
 271   return (XYLA_RC_OK);
 272 }
 273
 274 int xyla_treap_splitat(struct xyla_bt_nodecls *cls,
 275                        struct xyla_bt_node **left_out,
 276                        struct xyla_bt_node **mid_out,
 277                        struct xyla_bt_node **right_out,
 278                        struct xyla_bt_node **root, const void *key)
 279 {
 280   /* Split the tree rooted at ROOT into two at an indicated KEY.  Store in
 281    * *LEFT_OUT and *RIGHT_OUT the roots of trees containing every node whose
 282    * key is respectively less than and greater than the KEY.
 283    *
 284    * If a node matching the KEY exists in the input tree, then that becomes
 285    * the `middle node', which does not appear in either output tree; a
 286    * pointer to this node is stored in *MID_OUT.
 287    *
 288    * This operation assumes that the tree traversal ordering matches an
 289    * ordering on search keys, which is implemented by the node-class `nav'
 290    * function.
 291    *
 292    * Returns `XYLA_RC_OK'.
 293    */
 294
 295   const struct xyla_bt_ordops *ops = ORDER_OPS(cls->ops);
 296   struct xyla_bt_node *node;
 297   struct xyla_treap_path path;
 298   int rc;
 299
 300   XYLA_BT_PROBE(rc, node, cls, root, ops->ord.nav, UNCONST(void, key),
 301                 path.p, path.k, XYLA_TREAP_HTMAX); (void)node;
 302     if (rc) xyla__treap_boundfail();
 303   return (xyla_treap_split(cls, left_out, mid_out, right_out, &path));
 304 }
 305
 306 int xyla_treap_splitroot(struct xyla_bt_node **left_out,
 307                          struct xyla_bt_node **root_out,
 308                          struct xyla_bt_node **right_out,
 309                          struct xyla_bt_node **root)
 310 {
 311   /* Split the tree rooted at ROOT into two at its root.  Store in *ROOT_OUT
 312    * a pointer to the original root node, or null if the tree was initially
 313    * empty; store in *LEFT_OUT and *RIGHT_OUT the root of the original root's
 314    * left and right subtrees respectively.
 315    *
 316    * Returns `XYLA_RC_OK'.
 317    */
 318
 319   struct xyla_bt_node *node;
 320
 321   node = *root; *root = 0;
 322   if (!node)
 323     *left_out = *right_out = 0;
 324   else {
 325     *left_out = node->left;
 326     *right_out = node->right;
 327     node->left = node->right = 0;
 328   }
 329   *root_out = node;
 330   return (XYLA_RC_OK);
 331 }
 332
 333 /*----- That's all, folks -------------------------------------------------*/