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

   1 /* -*-c-*-
   2  *
   3  * Set operations 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 /*----- Tree operations ---------------------------------------------------*/
  32
  33 static int join_set(struct xyla_bt_nodecls *cls,
  34                     struct xyla_bt_node **root_out, int *rootht_out,
  35                     struct xyla_bt_node **left, int lht,
  36                     struct xyla_bt_node *mid,
  37                     struct xyla_bt_node **right, int rht)
  38 {
  39   int rc;
  40
  41   rc = xyla_treap_join(cls, root_out, left, mid, right);
  42   *rootht_out = 0; return (rc);
  43 }
  44
  45 static int split_set_at(struct xyla_bt_nodecls *cls,
  46                         struct xyla_bt_node **left_out, int *lht_out,
  47                         struct xyla_bt_node **mid_out,
  48                         struct xyla_bt_node **right_out, int *rht_out,
  49                         struct xyla_bt_node **root, const void *key)
  50 {
  51   int rc;
  52
  53   rc= xyla_treap_splitat(cls, left_out, mid_out, right_out, root, key);
  54   *lht_out = *rht_out = 0; return (rc);
  55 }
  56
  57 static int split_set_root(struct xyla_bt_node **left_out, int *lht_out,
  58                           struct xyla_bt_node **root_out,
  59                           struct xyla_bt_node **right_out, int *rht_out,
  60                           struct xyla_bt_node **root, int ht)
  61 {
  62   int rc;
  63
  64   rc = xyla_treap_splitroot(left_out, root_out, right_out, root);
  65   *lht_out = *rht_out = 0; return (rc);
  66 }
  67
  68 static const struct xyla_bt_treeops treap_ops =
  69   { join_set, split_set_at, split_set_root };
  70
  71 /*----- Main code ---------------------------------------------------------*/
  72
  73 int xyla_treap_unisect(struct xyla_bt_nodecls *cls,
  74                        struct xyla_bt_node **uni_out,
  75                        struct xyla_bt_node **isect_out,
  76                        struct xyla_bt_node **aroot,
  77                        struct xyla_bt_node **broot)
  78 {
  79   /* Compute the union and intersection of two trees.
  80    *
  81    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
  82    * trees are considered to represent sets, with one element per node; the
  83    * element is determined by the `key' node-class operation.  On exit,
  84    * *UNI_OUT points to the root of a tree containing (one copy of) each
  85    * element present in either a or b, and *ISECT_OUT points to the root of a
  86    * tree containing the other copy of each element present in both a and b.
  87    * If AROOT and/or BROOT are distinct from UNI_OUT and ISECT_OUT, then null
  88    * pointers are stored in them.  The original trees are destroyed; each
  89    * node in the original operands trees ends up in exactly one of the result
  90    * trees.
  91    *
  92    * Returns `XYLA_RC_OK'.
  93    */
  94
  95   struct xyla_bt_setopstack stack[XYLA_TREAP_HTMAX];
  96   int rc;
  97
  98   rc = xyla_bt_unisect(cls, uni_out, 0, isect_out, 0,
  99                        aroot, 0, broot, 0,
 100                        &treap_ops, stack, XYLA_TREAP_HTMAX);
 101     if (rc) xyla__treap_boundfail();
 102   return (rc);
 103 }
 104
 105 int xyla_treap_diffsect(struct xyla_bt_nodecls *cls,
 106                         struct xyla_bt_node **diff_out,
 107                         struct xyla_bt_node **isect_out,
 108                         struct xyla_bt_node **aroot,
 109                         struct xyla_bt_node **broot)
 110 {
 111   /* Compute the set difference of the two operand trees.
 112    *
 113    * On entry, *AROOT and *BROOT are the roots of two trees a and b.  The
 114    * trees are considered to represent sets, with one element per node; the
 115    * element is determined by the `key' node-class operation.  On exit,
 116    * *DIFF_OUT points to the root of a tree containing each element of a but
 117    * not b, and *ISECT_OUT points to the root of a tree containing each
 118    * element of a that's also in b.  If AROOT and/or BROOT are distinct from
 119    * DIFF_OUT and ISECT_OUT, then null pointers are stored in them.  The
 120    * original a tree is destroyed; each node in the original operands trees
 121    * ends up in exactly one of the result trees.  The input b tree is
 122    * unchanged.
 123    *
 124    * Returns `XYLA_RC_OK'.
 125    */
 126
 127   struct xyla_bt_setopstack stack[XYLA_TREAP_HTMAX];
 128   int rc;
 129
 130   rc = xyla_bt_diffsect(cls, diff_out, 0, isect_out, 0,
 131                         aroot, 0, broot,
 132                         &treap_ops, stack, XYLA_TREAP_HTMAX);
 133     if (rc) xyla__treap_boundfail();
 134   return (rc);
 135 }
 136
 137 /*----- That's all, folks -------------------------------------------------*/