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

   1 /* -*-c-*-
   2  *
   3  * Iteration 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_inititer(const struct xyla_bt_node *root,
  34                          struct xyla_treap_iter *it)
  35 {
  36   /* Initialize the iterator IT to start returning nodes in left-to-right
  37    * order from the tree rooted at *ROOT.
  38    */
  39
  40   int rc;
  41
  42   it->sp = 0;
  43   XYLA_BT_STEPITER(rc, root, it->stack, it->sp, XYLA_TREAP_HTMAX, left);
  44     if (rc) xyla__treap_boundfail();
  45 }
  46
  47 void *xyla_treap_next(struct xyla_treap_iter *it)
  48 {
  49   /* Advances a tree iterator.  Inserting or removing elements invalidates
  50    * the iterator.  As a special exception, it is permitted to free all of
  51    * the nodes by iterating over the tree in the obvious manner:
  52    *
  53    *    xyla_treap_inititer(tree, &it);
  54    *    for (;;) {
  55    *      node = xyla_treap_next(&it); if (!node) break;
  56    *      free(node);
  57    *    }
  58    *
  59    * It's probably better to use `xyla_bt_severfirst' for this task.
  60    */
  61
  62   const struct xyla_bt_node *node;
  63   int rc, sp = it->sp;
  64
  65   if (!sp) return (0);
  66   node = it->stack[--sp];
  67   XYLA_BT_STEPITER(rc, node->right, it->stack, sp, XYLA_TREAP_HTMAX, left);
  68     if (rc) xyla__treap_boundfail();
  69   it->sp = sp; return (UNCONST(void, node));
  70 }
  71
  72 void xyla_treap_initriter(const struct xyla_bt_node *root,
  73                           struct xyla_treap_riter *rit)
  74 {
  75   /* Initialize the iterator RIT to start returning nodes in right-to-left
  76    * order from the tree rooted at ROOT.
  77    */
  78
  79   int rc;
  80
  81   rit->sp = 0;
  82   XYLA_BT_STEPITER(rc, root, rit->stack, rit->sp, XYLA_TREAP_HTMAX, right);
  83     XYLA__ASSERT(!rc);
  84 }
  85
  86 void *xyla_treap_prev(struct xyla_treap_riter *rit)
  87 {
  88   /* Advance the iterator RIT, returning the previous node, or null if the
  89    * iteration is complete.
  90    *
  91    * Inserting or removing elements invalidates the iterator.  As a special
  92    * exception, it is permitted to free all of the nodes by iterating over
  93    * the tree in the obvious manner:
  94    *
  95    *    xyla_treap_initriter(tree, &rit);
  96    *    for (;;) {
  97    *      node = xyla_treap_prev(&it); if (!node) break;
  98    *      free(node);
  99    *    }
 100    *
 101    * It's probably better to use `xyla_bt_severfirst' for this task.
 102    */
 103
 104   const struct xyla_bt_node *node;
 105   int rc, sp = rit->sp;
 106
 107   if (!sp) return (0);
 108   node = rit->stack[--sp];
 109   XYLA_BT_STEPITER(rc, node->left, rit->stack, sp, XYLA_TREAP_HTMAX, right);
 110     XYLA__ASSERT(!rc);
 111   rit->sp = sp; return (UNCONST(void, node));
 112 }
 113
 114 /*----- That's all, folks -------------------------------------------------*/