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

   1 /* -*-c-*-
   2  *
   3  * Set operations for red-black trees
   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 "rb.h"
  30
  31 /*----- Tree operations ---------------------------------------------------*/
  32
  33 static const struct xyla_bt_treeops rb_ops =
  34   { xyla_rb_join, xyla_rb_splitat, xyla_rb_splitroot };
  35
  36 /*----- Main code ---------------------------------------------------------*/
  37
  38 int xyla_rb_unisect(struct xyla_bt_nodecls *cls,
  39                     struct xyla_bt_node **uni_out, int *uniht_out,
  40                     struct xyla_bt_node **isect_out, int *isectht_out,
  41                     struct xyla_bt_node **aroot, int aht,
  42                     struct xyla_bt_node **broot, int bht)
  43 {
  44   /* Compute the union and intersection of two trees.
  45    *
  46    * On entry, *AROOT and *BROOT are the roots of two trees a and b, with
  47    * their respective black-heights in AHT and BHT, if the caller knows them,
  48    * or -1 otherwise.  The trees are considered to represent sets, with one
  49    * element per node; the element is determined by the `key' node-class
  50    * operation.  On exit, *UNI_OUT points to the root of a tree containing
  51    * (one copy of) each element present in either a or b, and *ISECT_OUT
  52    * points to the root of a tree containing the other copy of each element
  53    * present in both a and b; the black-heights of the output trees are
  54    * stored in *UNIHT_OUT and *ISECTHT_OUT, if these are not null.  If AROOT
  55    * and/or BROOT are distinct from UNI_OUT and ISECT_OUT, then null pointers
  56    * are stored in them.  The original trees are destroyed; each node in the
  57    * original operands trees ends up in exactly one of the result trees.
  58    *
  59    * Returns `XYLA_RC_OK'.
  60    */
  61
  62   struct xyla_bt_setopstack stack[XYLA_RB_HTMAX];
  63   int rc;
  64
  65   if (aht < 0) aht = xyla_rb_height(RB_NODE(*aroot));
  66   if (bht < 0) bht = xyla_rb_height(RB_NODE(*broot));
  67
  68   rc = xyla_bt_unisect(cls, uni_out, uniht_out, isect_out, isectht_out,
  69                        aroot, &aht, broot, &bht,
  70                        &rb_ops, stack, XYLA_RB_HTMAX);
  71     XYLA__ASSERT(!rc);
  72   return (rc);
  73 }
  74
  75 int xyla_rb_diffsect(struct xyla_bt_nodecls *cls,
  76                      struct xyla_bt_node **diff_out, int *diffht_out,
  77                      struct xyla_bt_node **isect_out, int *isectht_out,
  78                      struct xyla_bt_node **aroot, int aht,
  79                      struct xyla_bt_node **broot)
  80 {
  81   /* Compute the set difference of the two operand trees.
  82    *
  83    * On entry, *AROOT and *BROOT are the roots of two trees a and b, with a's
  84    * black-height in AHT, if the caller knows it, or -1 otherwise (the black-
  85    * height of b is not significant).  The trees are considered to represent
  86    * sets, with one element per node; the element is determined by the `key'
  87    * node-class operation.  On exit, *DIFF_OUT points to the root of a tree
  88    * containing each element of a but not b, and *ISECT_OUT points to the
  89    * root of a tree containing each element of a that's also in b; the
  90    * black-heights of the output trees are stored in *DIFFHT_OUT and
  91    * *ISECTHT_OUT, if these are not null.  If AROOT and/or BROOT are distinct
  92    * from DIFF_OUT and ISECT_OUT, then null pointers are stored in them.  The
  93    * original a tree is destroyed; each node in the original operands trees
  94    * ends up in exactly one of the result trees.  The input b tree is
  95    * unchanged.
  96    *
  97    * Returns `XYLA_RC_OK'.
  98    */
  99
 100   struct xyla_bt_setopstack stack[XYLA_RB_HTMAX];
 101   int rc;
 102
 103   if (aht < 0) aht = xyla_rb_height(RB_NODE(*aroot));
 104
 105   rc = xyla_bt_diffsect(cls, diff_out, diffht_out, isect_out, isectht_out,
 106                         aroot, &aht, broot,
 107                         &rb_ops, stack, XYLA_RB_HTMAX);
 108     XYLA__ASSERT(!rc);
 109   return (rc);
 110 }
 111
 112 /*----- That's all, folks -------------------------------------------------*/