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

   1 /* -*-c-*-
   2  *
   3  * Set operations for AVL 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 "avl.h"
  30
  31 /*----- Tree operations ---------------------------------------------------*/
  32
  33 static const struct xyla_bt_treeops avl_ops =
  34   { xyla_avl_join, xyla_avl_splitat, xyla_avl_splitroot };
  35
  36 /*----- Main code ---------------------------------------------------------*/
  37
  38 int xyla_avl_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 heights in AHT and BHT, if the caller knows them, or -1
  48    * otherwise.  The trees are considered to represent sets, with one element
  49    * per node; the element is determined by the `key' node-class operation.
  50    * On exit, *UNI_OUT points to the root of a tree containing (one copy of)
  51    * each element present in either a or b, and *ISECT_OUT points to the root
  52    * of a tree containing the other copy of each element present in both a
  53    * and b; the heights of the output trees are stored in *UNIHT_OUT and
  54    * *ISECTHT_OUT, if these are not null.  If AROOT and/or BROOT are distinct
  55    * from UNI_OUT and ISECT_OUT, then null pointers are stored in them.  The
  56    * original trees are destroyed; each node in the original operands trees
  57    * ends up in exactly one of the result trees.
  58    *
  59    * Returns `XYLA_RC_OK'.
  60    */
  61
  62   struct xyla_bt_setopstack stack[XYLA_AVL_HTMAX];
  63   int rc;
  64
  65   if (aht < 0) aht = xyla_avl_height(AVL_NODE(*aroot));
  66   if (bht < 0) bht = xyla_avl_height(AVL_NODE(*broot));
  67
  68   rc = xyla_bt_unisect(cls, uni_out, uniht_out, isect_out, isectht_out,
  69                        aroot, &aht, broot, &bht,
  70                        &avl_ops, stack, XYLA_AVL_HTMAX);
  71     XYLA__ASSERT(!rc);
  72   return (rc);
  73 }
  74
  75 int xyla_avl_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    * height in AHT, if the caller knows it, or -1 otherwise (the height of b
  85    * is not significant).  The trees are considered to represent sets, with
  86    * one element per node; the element is determined by the `key' node-class
  87    * operation.  On exit, *DIFF_OUT points to the root of a tree containing
  88    * each element of a but not b, and *ISECT_OUT points to the root of a tree
  89    * containing each element of a that's also in b; the heights of the output
  90    * trees are stored in *DIFFHT_OUT and *ISECTHT_OUT, if these are not null.
  91    * If AROOT and/or BROOT are distinct from DIFF_OUT and ISECT_OUT, then
  92    * null pointers are stored in them.  The original a tree is destroyed;
  93    * each node in the original operands trees ends up in exactly one of the
  94    * result trees.  The input b tree is unchanged.
  95    *
  96    * Returns `XYLA_RC_OK'.
  97    */
  98
  99   struct xyla_bt_setopstack stack[XYLA_AVL_HTMAX];
 100   int rc;
 101
 102   if (aht < 0) aht = xyla_avl_height(AVL_NODE(*aroot));
 103
 104   rc = xyla_bt_diffsect(cls, diff_out, diffht_out, isect_out, isectht_out,
 105                         aroot, &aht, broot,
 106                         &avl_ops, stack, XYLA_AVL_HTMAX);
 107     XYLA__ASSERT(!rc);
 108   return (rc);
 109 }
 110
 111 /*----- That's all, folks -------------------------------------------------*/