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

   1 /* -*-c-*-
   2  *
   3  * Path utilities for 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 void *xyla_treap_current(const struct xyla_treap_path *path)
  34 {
  35   /* Return the node currently designated by PATH, or null if PATH is
  36    * empty.
  37    */
  38
  39   return (XYLA_BT_CURRENT(path->p, path->k));
  40 }
  41
  42 void xyla_treap_copypath(struct xyla_treap_path *newpath,
  43                          const struct xyla_treap_path *path)
  44 {
  45   /* Make a copy of PATH as NEWPATH.  This has the same effect as simply
  46    * assigning the path structures, but may be significantly faster because
  47    * it only copies the active part of the path vector.
  48    */
  49
  50   int k = path->k;
  51
  52   XYLA_BT_COPYPATH(newpath->p, path->p, k);
  53   newpath->k = k;
  54 }
  55
  56 void *xyla_treap_firstpath(struct xyla_bt_node **root,
  57                            struct xyla_treap_path *path)
  58 {
  59   /* Return the first node in the tree, together with a PATH to the requested
  60    * node, which can be used to remove them, or to navigate to other nodes in
  61    * the tree.  Return null if the tree is empty.
  62    */
  63
  64   struct xyla_bt_node *node;
  65   int rc;
  66
  67   XYLA_BT_EXTRMPATH(rc, node, root, path->p, path->k,
  68                     left, XYLA_TREAP_HTMAX);
  69     if (rc) xyla__treap_boundfail();
  70   return (node);
  71 }
  72
  73 void *xyla_treap_lastpath(struct xyla_bt_node **root,
  74                           struct xyla_treap_path *path)
  75 {
  76   /* Return the last node in the tree, together with a PATH to the requested
  77    * node, which can be used to remove them, or to navigate to other nodes in
  78    * the tree.  Return null if the tree is empty.
  79    */
  80
  81   struct xyla_bt_node *node;
  82   int rc;
  83
  84   XYLA_BT_EXTRMPATH(rc, node, root, path->p, path->k,
  85                     right, XYLA_TREAP_HTMAX);
  86     if (rc) xyla__treap_boundfail();
  87   return (node);
  88 }
  89
  90 void *xyla_treap_nextpath(struct xyla_treap_path *path)
  91 {
  92   /* Return the next node in the tree, and update the PATH to the requested
  93    * node, which can be used to remove them, or to navigate to other nodes in
  94    * the tree.
  95    *
  96    * If the path is full, i.e., refers to an existing node, then the function
  97    * returns that node's successor.  If the path is empty, i.e., refers to a
  98    * space between nodes where a new node can be inserted, then the function
  99    * returns the node at the upper end of the gap, unless the `gap' is
 100    * actually at the extreme right of the tree and no such node exists.  In
 101    * the latter case, a null pointer is returned.  The path is modified to
 102    * refer to the new node, if any, or to the gap at the extreme right of the
 103    * tree.
 104    */
 105
 106   struct xyla_bt_node *node;
 107   int rc;
 108
 109   XYLA_BT_STEPPATH(rc, node, path->p, path->k,
 110                    right, left, XYLA_TREAP_HTMAX);
 111     if (rc) xyla__treap_boundfail();
 112   return (node);
 113 }
 114
 115 void *xyla_treap_prevpath(struct xyla_treap_path *path)
 116 {
 117   /* Return the previous node in the tree, and update the PATH to the
 118    * requested node, which can be used to remove them, or to navigate to
 119    * other nodes in the tree.
 120    *
 121    * If the path is full, i.e., refers to an existing node, then the function
 122    * returns that node's predecessor.  If the path is empty, i.e., refers to
 123    * a space between nodes where a new node can be inserted, then the
 124    * function returns the node at the lower end of the gap, unless the `gap'
 125    * is actually at the extreme left of the tree and no such node exists.  In
 126    * the latter case, a null pointer is returned.  The path is modified to
 127    * refer to the new node, if any, or to the gap at the extreme left of the
 128    * tree.
 129    */
 130
 131   struct xyla_bt_node *node;
 132   int rc;
 133
 134   XYLA_BT_STEPPATH(rc, node, path->p, path->k,
 135                    left, right, XYLA_TREAP_HTMAX);
 136     if (rc) xyla__treap_boundfail();
 137   return (node);
 138 }
 139
 140 void xyla_treap_beforepath(struct xyla_treap_path *path)
 141 {
 142   /* Advance the PATH to just before the current node.  The path thereby
 143    * becomes empty, suitable to insert an element or split the tree just
 144    * before the previously selected node.
 145    */
 146
 147   int rc;
 148
 149   XYLA_BT_NUDGEPATH(rc, path->p, path->k, left, right, XYLA_TREAP_HTMAX);
 150     if (rc) xyla__treap_boundfail();
 151 }
 152
 153 void xyla_treap_afterpath(struct xyla_treap_path *path)
 154 {
 155   /* Advance the PATH to just after the current node.  The path thereby
 156    * becomes empty, suitable to insert an element or split the tree just
 157    * after the previously selected node.
 158    */
 159
 160   int rc;
 161
 162   XYLA_BT_NUDGEPATH(rc, path->p, path->k, right, left, XYLA_TREAP_HTMAX);
 163     if (rc) xyla__treap_boundfail();
 164 }
 165
 166 void *xyla_treap_rootpath(struct xyla_bt_node **root,
 167                           struct xyla_treap_path *path)
 168 {
 169   /* Initialize PATH to refer to the tree root, given the address ROOT of the
 170    * root link, and return this root node.  The resulting path will be empty
 171    * if and only if the tree is empty.
 172    */
 173
 174   struct xyla_bt_node *node;
 175
 176   XYLA_BT_ROOTPATH(node, root, path->p, path->k);
 177   return (node);
 178 }
 179
 180 void *xyla_treap_uppath(unsigned *pos_out, struct xyla_treap_path *path)
 181 {
 182   /* Update the PATH to refer to the parent of the link currently designated;
 183    * return this parent node, and set *POS_OUT to the `XYLA_BTPOS_...'
 184    * constant describing the link's relation to the parent.  If the path
 185    * initially designated the tree's root link, then return null, set
 186    * *POS_OUT to `XYLA_BTPOS_ROOT', and leave the path unchanged; otherwise,
 187    * the tree becomes full.
 188    */
 189
 190   struct xyla_bt_node *node;
 191
 192   XYLA_BT_PARENTPATH(node, *pos_out, path->p, path->k);
 193   return (node);
 194 }
 195
 196 void *xyla_treap_leftpath(struct xyla_treap_path *path)
 197 {
 198   /* Update the PATH to refer to the left child of the node currently
 199    * designated, and set NODE to be this child node.  The PATH must initially
 200    * have been full, and may become empty as a result.
 201    */
 202
 203   struct xyla_bt_node *node;
 204   int rc;
 205
 206   XYLA_BT_CHILDPATH(rc, node, path->p, path->k, left, XYLA_TREAP_HTMAX);
 207     if (rc) xyla__treap_boundfail();
 208   return (node);
 209 }
 210
 211 void *xyla_treap_rightpath(struct xyla_treap_path *path)
 212 {
 213   /* Update the PATH to refer to the right child of the node currently
 214    * designated, and set NODE to be this child node.  The PATH must initially
 215    * have been full, and may become empty as a result.
 216    */
 217
 218   struct xyla_bt_node *node;
 219   int rc;
 220
 221   XYLA_BT_CHILDPATH(rc, node, path->p, path->k, right, XYLA_TREAP_HTMAX);
 222     if (rc) xyla__treap_boundfail();
 223   return (node);
 224 }
 225
 226 void xyla_treap_replace(const struct xyla_treap_path *path,
 227                         struct xyla_treap_node *node)
 228 {
 229   /* Replace the node identified by the PATH with the given NODE.  The node's
 230    * links need not be initialized.  The replacement node's weight is copied
 231    * from the original.  Paths and iterators are not invalidated.  It is the
 232    * caller's responsibility to ensure that any ordering invariants are
 233    * respected as a result of the change.
 234    */
 235
 236   struct xyla_treap_node *old_node;
 237   int k = path->k;
 238
 239   old_node = TREAP_NODE(*path->p[k]); XYLA__ASSERT(old_node);
 240   node->bt = old_node->bt; node->trp.wt = old_node->trp.wt;
 241 }
 242
 243 void xyla_treap_ripple(struct xyla_bt_nodecls *cls,
 244                        const struct xyla_treap_path *path)
 245 {
 246   /* Update a node's ancestors -- i.e., call the node class `upd' function on
 247    * them, in ascending order -- after it has been modified.  The PATH
 248    * describes a full path to the node that has been changed.  The PATH
 249    * remains valid.
 250    */
 251
 252   XYLA_BT_RIPPLE(cls, path->p, path->k);
 253 }
 254
 255 int xyla_treap_ascend(xyla_bt_ascendfn *fn,
 256                       const struct xyla_treap_path *path, void *arg)
 257 {
 258   /* Ascend the tree along the PATH, allowing FN to accumulate summary data
 259    * from the nodes to the root; see `XYLA_BT_ASCEND' for details.  If FN
 260    * returns nonzero, then stop and return the nonzero value; otherwise
 261    * return zero.  The PATH remains valid.
 262    */
 263
 264   int rc;
 265
 266   XYLA_BT_ASCEND(rc, fn, path->p, path->k, arg);
 267   return (rc);
 268 }
 269
 270 /*----- That's all, folks -------------------------------------------------*/