@@@ tweak

[xyla] / avl.h

/* -*-c-*-
 *
 * AVL trees
 *
 * (c) 2024 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Xyla, a library of binary trees.
 *
 * Xyla is free software: you can redistribute it and/or modify it under
 * the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 3 of the License, or (at your
 * option) any later version.
 *
 * Xyla is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
 */

#ifndef XYLA_AVL_H
#define XYLA_AVL_H

/*----- Header files ------------------------------------------------------*/

#include "bt.h"

/*----- Data structures ---------------------------------------------------*/

struct xyla_avl_nodeslots {
  unsigned f;
#define XYLA_AVLF_BALMASK 3u
#define XYLA_AVLBAL_LBIAS 1u
#define XYLA_AVLBAL_EVEN 0u
#define XYLA_AVLBAL_RBIAS 2u
};
#define XYLA_AVL_NODEPFX XYLA_BT_NODEPFX; struct xyla_avl_nodeslots avl
struct xyla_avl_node { XYLA_AVL_NODEPFX; };
#define XYLA_AVL_NODEUSFX struct xyla_avl_node avl; XYLA_BT_NODEUSFX
union xyla_avl_nodeu { XYLA_AVL_NODEUSFX; };

/* The maximum possible height H_n for an AVL tree containing n nodes is
 * somewhat annoying to calculate.  The best way to start is to reverse the
 * question and find the smallest number N_h of nodes which can force the
 * tree to have height h.
 *
 * This is going to involve a recurrence.  The base case is the rather
 * unsurprising observations that N_0 = 0 and N_1 = 1.
 *
 * The imbalance between the root's left and right subtrees can be at most 1.
 * The cheapest way we can make a tree with height h, then, is if the root is
 * biased to the left (say) and then its left and right subtrees are the
 * smallest trees with height h - 1 and h - 2 respectively.  We have the
 * oddly familiar recurrence
 *
 *      N_h = N_{h-1} + N_{h-2} + 1 .
 *
 * Guess that N_h = x^h + C for some constants x and C.  Then
 *
 *      x^h + C = x^{h-1} + x^{h-2} + 2 C + 1 ,
 *
 * and
 *
 *      x^h = x^{h-1} + x^{h-2} + C + 1 ,
 *
 * so setting C = -1 seems like the best bet; that leaves
 *
 *      x^h = x^{h-1} + x^{h-2} ,
 *
 * which is well-known to be solved by setting x = φ or x = φ̄, where
 *
 *          1 + √5                1 - √5
 *      φ = ------     and     φ̄ = ------ .
 *             2                       2
 *
 * This relationship clearly holds for any linear combination of φ and φ̄.  So
 * we finally set
 *
 *      N_h = A φ^h + B φ̄^h - 1
 *
 * and check the initial conditions: N_0 = 0 forces A + B = 1; and N_1 = 1
 * means
 *
 *      A φ + B φ̄ = 2 ;
 *
 * substituting φ and φ̄ and rearranging gives
 *
 *      (A + B) + √5 (A - B) = 4 .
 *
 * We know A + B = 1, so A - B = 3/√5 = 3 √5/5.  Adding these two gives
 *
 *          5 + 3 √5              5 - 3 √5
 *      A = --------    and     B = -------- .
 *             10                      10
 *
 * What we actually wanted to know was the maximum possible height H_n for an
 * AVL tree with n nodes.  Suppose, then, that, for some h, the tree has
 * n >= N_h >= A φ^h + B φ̄^h - 1 nodes.  Notice that |B < 1 and |φ̄| < 1;
 * therefore, |B φ̄^h| < 1, and we have n >= A φ^h - 2.  (Sadly, φ̄ is
 * negative.)
 *
 * Continuing, we see A φ^h <= n + 2.  Taking (binary) logs gives h lg φ +
 * lg A <= lg (n + 2), whence
 *
 *           lg (n + 2) - lg A
 *      h <= ----------------- .
 *                  lg φ
 *
 * This is pretty gnarly to evaluate with the C preprocessor.  Fortunately,
 * 0 < 13/9 - 1/lg φ < 1/200, so
 *
 *           13              lg A
 *      h <= -- lg (n + 2) - ---- .
 *            9              lg φ
 *
 * In fact, we can do better.  As n gets larger, the difference lg (n + 2) -
 * lg n tends to zero.  There is therefore a value N such that
 *
 *      13         lg (n + 2) - lg A
 *      -- lg n <= -----------------
 *       9                lg φ
 *
 * whenever n >= N.
 *
 * This is too horrid to solve by hand, but numerical methods show that
 * N = 12 satisfies our requirements.  We must, of course, round up rather
 * than down while computing this.
 *
 * Our n of interest is the largest value that can fit in `size_t', which is
 * an unsigned type; therefore n = 2^k - 1 for some k, and ⌊lg (n + 2)⌋ = k.
 * Alas, C doesn't give us k directly, but it can certainly be no more than
 * `CHAR_BIT*sizeof(size_t)'; since padding bits in integers are extremely
 * rare, this is usually the exact value.  C permits objects at least
 * 2^{15} - 1 bytes in size, so this must be at least that large.  In
 * particular, it's larger than 12, so we can apply this simplification.
 *
 * On conventional 32-bit targets, this is 47; on 64-bit targets, it's 93.
 * Both overestimate by one entry.
 */

#define XYLA_AVL_HTMAX (13*(sizeof(size_t)*CHAR_BIT + 8)/9)

struct xyla_avl_iter {
  int sp;
  const struct xyla_bt_node *stack[XYLA_AVL_HTMAX];
};
struct xyla_avl_riter {
  int sp;
  const struct xyla_bt_node *stack[XYLA_AVL_HTMAX];
};

struct xyla_avl_path {
  int k;
  struct xyla_bt_node **p[XYLA_AVL_HTMAX + 1];
};

/*----- Miscellaneous utilities -------------------------------------------*/

extern int xyla_avl_height(const struct xyla_avl_node */*node*/);
  /* Return the height for the (sub)tree rooted at NODE.  This is primarily
   * useful as input to `xyla_avl_join' and `xyla_avl_split'.
   */

/*----- Iteration ---------------------------------------------------------*/

extern void xyla_avl_inititer(const struct xyla_bt_node */*root*/,
                              struct xyla_avl_iter */*it*/);
  /* Initialize the iterator IT to start returning nodes in left-to-right
   * order from the tree rooted at ROOT.
   */

extern void *xyla_avl_next(struct xyla_avl_iter */*it*/);
  /* Advance the iterator IT, returning the next node, or null if the
   * iteration is complete.
   *
   * Inserting or removing elements invalidates the iterator.  As a special
   * exception, it is permitted to free all of the nodes by iterating over
   * the tree in the obvious manner:
   *
   *    xyla_avl_inititer(tree, &it);
   *    for (;;) {
   *      node = xyla_avl_next(&it); if (!node) break;
   *      free(node);
   *    }
   *
   * It's probably better to use `xyla_bt_severfirst' for this task.
   */

extern void xyla_avl_initriter(const struct xyla_bt_node */*root*/,
                               struct xyla_avl_riter */*rit*/);
  /* Initialize the iterator RIT to start returning nodes in right-to-left
   * order from the tree rooted at ROOT.
   */

extern void *xyla_avl_prev(struct xyla_avl_riter */*rit*/);
  /* Advance the iterator RIT, returning the previous node, or null if the
   * iteration is complete.
   *
   * Inserting or removing elements invalidates the iterator.  As a special
   * exception, it is permitted to free all of the nodes by iterating over
   * the tree in the obvious manner:
   *
   *    xyla_avl_inititer(tree, &rit);
   *    for (;;) {
   *      node = xyla_avl_next(&rit); if (!node) break;
   *      free(node);
   *    }
   *
   * It's probably better to use `xyla_bt_severfirst' for this task.
   */

/*----- Paths -------------------------------------------------------------*/

extern void *xyla_avl_current(const struct xyla_avl_path */*path*/);
  /* Return the node currently designated by PATH, or null if PATH is
   * empty.
   */

extern void xyla_avl_copypath(struct xyla_avl_path */*newpath*/,
                              const struct xyla_avl_path */*path*/);
  /* Make a copy of PATH as NEWPATH.  This has the same effect as simply
   * assigning the path structures, but may be significantly faster because
   * it only copies the active part of the path vector.
   */

extern void *xyla_avl_firstpath(struct xyla_bt_node **/*root*/,
                                struct xyla_avl_path */*path*/);
extern void *xyla_avl_lastpath(struct xyla_bt_node **/*root*/,
                               struct xyla_avl_path */*path*/);
  /* Return the first or last node in the tree, together with a PATH to the
   * requested node, which can be used to remove them, or to navigate to
   * other nodes in the tree.  Return null if the tree is empty.
   */

extern void *xyla_avl_nextpath(struct xyla_avl_path */*path*/);
extern void *xyla_avl_prevpath(struct xyla_avl_path */*path*/);
  /* Return the next or previous node in the tree, and update the PATH to the
   * requested node, which can be used to remove them, or to navigate to
   * other nodes in the tree.
   *
   * If the path is full, i.e., refers to an existing node, then the
   * functions return that node's successor or predecessor.  If the path is
   * empty, i.e., refers to a space between nodes where a new node can be
   * inserted, then the functions return the node at the upper or lower end
   * of the gap, unless the `gap' is actually at an extreme of the tree and
   * no such node exists.  In the latter case, a null pointer is returned.
   * The path is modified to refer to the new node, if any, or to the gap at
   * the appropriate extreme of the tree.
   */

extern void xyla_avl_beforepath(struct xyla_avl_path */*path*/);
extern void xyla_avl_afterpath(struct xyla_avl_path */*path*/);
  /* Advance the PATH to just before or after the current node.  The path
   * thereby becomes empty, suitable to insert an element or split the tree
   * just before or after the previously selected node.
   */

extern void *xyla_avl_rootpath(struct xyla_bt_node **/*root*/,
                               struct xyla_avl_path */*path*/);
  /* Initialize PATH to refer to the tree root, given the address ROOT of the
   * root link, and return this root node.  The resulting path will be empty
   * if and only if the tree is empty.
   */

extern void *xyla_avl_uppath(unsigned */*pos_out*/,
                             struct xyla_avl_path */*path*/);
  /* Update the PATH to refer to the parent of the link currently designated;
   * return this parent node, and set *POS_OUT to the `XYLA_BTPOS_...'
   * constant describing the link's relation to the parent.  If the path
   * initially designated the tree's root link, then return null, set
   * *POS_OUT to `XYLA_BTPOS_ROOT', and leave the path unchanged; otherwise,
   * the tree becomes full.
   */

extern void *xyla_avl_leftpath(struct xyla_avl_path */*path*/);
extern void *xyla_avl_rightpath(struct xyla_avl_path */*path*/);
  /* Update the PATH to refer to the left or right child of the node
   * currently designated, and set NODE to be this child node.  The PATH must
   * initially have been full, and may become empty as a result.
   */

extern void xyla_avl_replace(const struct xyla_avl_path */*path*/,
                             struct xyla_avl_node */*node*/);
  /* Replace the node identified by the PATH with the given NODE.  The node's
   * links need not be initialized.  Paths and iterators are not invalidated.
   * It is the caller's responsibility to ensure that any ordering invariants
   * are respected as a result of the change.
   */

extern void xyla_avl_ripple(struct xyla_bt_nodecls */*cls*/,
                            const struct xyla_avl_path */*path*/);
  /* Update a node's ancestors -- i.e., call the node class `upd' function on
   * them, in ascending order -- after it has been modified.  The PATH
   * describes a full path to the node that has been changed.  The PATH
   * remains valid.
   */

extern int xyla_avl_ascend(xyla_bt_ascendfn */*fn*/,
                           const struct xyla_avl_path */*path*/,
                           void */*arg*/);
  /* Ascend the tree along the PATH, allowing FN to accumulate summary data
   * from the nodes to the root; see `XYLA_BT_ASCEND' for details.  If FN
   * returns nonzero, then stop and return the nonzero value; otherwise
   * return zero.  The PATH remains valid.
   */

/*----- Searching ---------------------------------------------------------*/

extern void *xyla_avl_lookup(struct xyla_bt_nodecls */*cls*/,
                             struct xyla_bt_node **/*root*/,
                             xyla_bt_navfn */*navfn*/, void */*arg*/);
  /* Search for a node within the tree rooted at ROOT.  The search is guided
   * by NAVFN, passing it ARG at each node.  Return the node that the
   * function matches, or null if no matching node exists.
   */

extern void *xyla_avl_probe(struct xyla_bt_nodecls */*cls*/,
                            struct xyla_bt_node **/*root*/,
                            xyla_bt_navfn */*navfn*/, void */*arg*/,
                            struct xyla_avl_path */*path*/);
  /* Search for a node within the tree rooted at ROOT.  The search is guided
   * by NAVFN, passing it ARG at each node.  Record the search path in PATH.
   * This can be used later, e.g., by `xyla_avl_insert' to insert a new node
   * if none was found, or by `xyla_avl_remove' to remove the node that was
   * found.  Return the node that the function matches, or null if no
   * matching node exists.
   */

/*----- Insertion and removal ---------------------------------------------*/

extern int xyla_avl_insert(struct xyla_bt_nodecls */*cls*/,
                           struct xyla_avl_path */*path*/,
                           struct xyla_avl_node */*node*/);
  /* Add a new node to the tree, in the place determined by the empty PATH.
   * It's the caller's responsibility to ensure that inserting the node here
   * respects any ordering invariants.  Returns `XYLA_RC_HTCHG' if the tree
   * has increased in height, or `XYLA_RC_OK' if its height remains
   * unchanged.
   *
   * The new node is not copied, and its storage must remain valid until the
   * node is removed or the tree is discarded.
   */

extern int xyla_avl_remove(struct xyla_bt_nodecls */*cls*/,
                           struct xyla_avl_path */*path*/);
  /* Remove the node identified by the PATH.  The node was allocated by the
   * caller, and should be freed by the caller in whatever way is
   * appropriate.  Returns `XYLA_RC_HTCHG' if the tree has decreased in
   * height, or `XYLA_RC_OK' if its height remains unchanged.
   */

/*----- Splitting and joining ---------------------------------------------*/

extern int xyla_avl_join(struct xyla_bt_nodecls */*cls*/,
                         struct xyla_bt_node **/*root_out*/,
                           int */*rootht_out*/,
                         struct xyla_bt_node **/*left*/, int /*lht*/,
                         struct xyla_bt_node */*mid*/,
                         struct xyla_bt_node **/*right*/, int /*rht*/);
  /* Concatenate the two trees rooted at LEFT and RIGHT in order; if MID is
   * not null, then place this node between them.  The root of the resulting
   * tree is stored in *ROOT_OUT.  It's the caller's responsibility to ensure
   * that this respects any ordering invariants.
   *
   * If the heights of the LEFT and RIGHT trees are known, then they can be
   * passed in as LHT and RHT; otherwise, LHT and/or RHT must be -1.  The
   * height of the combined tree is stored in *ROOTHT_OUT if this is not
   * null.
   *
   * The ROOT_OUT pointer may equal either LEFT or RIGHT (or, indeed, both,
   * only if both are empty).  If LEFT is distinct from ROOT_OUT then *LEFT
   * is set null on exit; similarly, if RIGHT is distinct from ROOT_OUT, then
   * *RIGHT is set null on exit.
   *
   * Returns `XYLA_RC_OK'.
   */

extern int xyla_avl_split(struct xyla_bt_nodecls */*cls*/,
                          struct xyla_bt_node **/*left_out*/,
                            int */*lht_out*/,
                          struct xyla_bt_node **/*mid_out*/,
                          struct xyla_bt_node **/*right_out*/,
                            int */*rht_out*/,
                          struct xyla_avl_path */*path*/);
  /* Split a tree tree into two at the indicated place indicated by the PATH.
   * Store in *LEFT_OUT and *RIGHT_OUT the roots of trees containing every
   * node respectively preceding and following the PATH, and in *LHT_OUT and
   * *RHT_OUT the heights of the respective output trees; either or both of
   * LHT_OUT and RHT_OUT may be null to discard this information.
   *
   * If the PATH is full, i.e., it denotes a node in the input tree, then
   * that becomes the `middle node', which does not appear in either output
   * tree; a pointer to this node is stored in *MID_OUT.
   *
   * Returns `XYLA_RC_OK'.
   */

extern int xyla_avl_splitat(struct xyla_bt_nodecls */*cls*/,
                            struct xyla_bt_node **/*left_out*/,
                              int */*lht_out*/,
                            struct xyla_bt_node **/*mid_out*/,
                            struct xyla_bt_node **/*right_out*/,
                              int */*rht_out*/,
                            struct xyla_bt_node **/*root*/,
                            const void */*key*/);
  /* Split the tree rooted at ROOT into two at an indicated KEY.  Store in
   * *LEFT_OUT and *RIGHT_OUT the roots of trees containing every node whose
   * key is respectively less than and greater than the KEY, and in *LHT_OUT
   * and *RHT_OUT the heights of the respective output trees; either or both
   * of LHT_OUT and RHT_OUT may be null to discard this information.
   *
   * If a node matching the KEY exists in the input tree, then that becomes
   * the `middle node', which does not appear in either output tree; a
   * pointer to this node is stored in *MID_OUT.
   *
   * This operation assumes that the tree traversal ordering matches an
   * ordering on search keys, which is implemented by the node-class `nav'
   * function.
   *
   * Returns `XYLA_RC_OK'.
   */

extern int xyla_avl_splitroot(struct xyla_bt_node **/*left_out*/,
                                int */*lht_out*/,
                              struct xyla_bt_node **/*root_out*/,
                              struct xyla_bt_node **/*right_out*/,
                                int */*rht_out*/,
                              struct xyla_bt_node **/*root*/, int /*ht*/);
  /* Split the tree rooted at ROOT into two at its root.  Store in *ROOT_OUT
   * a pointer to the original root node, or null if the tree was initially
   * empty; store in *LEFT_OUT and *RIGHT_OUT the root of the original root's
   * left and right subtrees respectively, and in *LHT_OUT and *RHT_OUT the
   * heights of the respective output trees; either or both of LHT_OUT and
   * RHT_OUT may be null to discard this information.  If the initial tree
   * height is known, it can be passed in as HT; otherwise, HT must be -1.
   *
   * Returns `XYLA_RC_OK'.
   */

/*----- Set operations ----------------------------------------------------*/

extern int xyla_avl_unisect(struct xyla_bt_nodecls */*cls*/,
                            struct xyla_bt_node **/*uni_out*/,
                              int */*uniht_out*/,
                            struct xyla_bt_node **/*isect_out*/,
                              int */*isectht_out*/,
                            struct xyla_bt_node **/*aroot*/, int /*aht*/,
                            struct xyla_bt_node **/*broot*/, int /*bht*/);
  /* Compute the union and intersection of two trees.
   *
   * On entry, *AROOT and *BROOT are the roots of two trees a and b, with
   * their respective heights in AHT and BHT, if the caller knows them, or -1
   * otherwise.  The trees are considered to represent sets, with one element
   * per node; the element is determined by the `key' node-class operation.
   * On exit, *UNI_OUT points to the root of a tree containing (one copy of)
   * each element present in either a or b, and *ISECT_OUT points to the root
   * of a tree containing the other copy of each element present in both a
   * and b; the heights of the output trees are stored in *UNIHT_OUT and
   * *ISECTHT_OUT, if these are not null.  If AROOT and/or BROOT are distinct
   * from UNI_OUT and ISECT_OUT, then null pointers are stored in them.  The
   * original trees are destroyed; each node in the original operands trees
   * ends up in exactly one of the result trees.
   *
   * Returns `XYLA_RC_OK'.
   */

extern int xyla_avl_diffsect(struct xyla_bt_nodecls */*cls*/,
                             struct xyla_bt_node **/*diff_out*/,
                               int */*diffht_out*/,
                             struct xyla_bt_node **/*isect_out*/,
                               int */*isectht_out*/,
                             struct xyla_bt_node **/*aroot*/, int /*aht*/,
                             struct xyla_bt_node **/*broot*/);
  /* Compute the set difference of the two operand trees.
   *
   * On entry, *AROOT and *BROOT are the roots of two trees a and b, with a's
   * height in AHT, if the caller knows it, or -1 otherwise (the height of b
   * is not significant).  The trees are considered to represent sets, with
   * one element per node; the element is determined by the `key' node-class
   * operation.  On exit, *DIFF_OUT points to the root of a tree containing
   * each element of a but not b, and *ISECT_OUT points to the root of a tree
   * containing each element of a that's also in b; the heights of the output
   * trees are stored in *DIFFHT_OUT and *ISECTHT_OUT, if these are not null.
   * If AROOT and/or BROOT are distinct from DIFF_OUT and ISECT_OUT, then
   * null pointers are stored in them.  The original a tree is destroyed;
   * each node in the original operands trees ends up in exactly one of the
   * result trees.  The input b tree is unchanged.
   *
   * Returns `XYLA_RC_OK'.
   */

/*----- Checking ----------------------------------------------------------*/

#ifndef XYLA_FREESTANDING

extern int xyla_avl_check(struct xyla_bt_nodecls */*cls*/,
                          struct xyla_bt_node *const */*root*/,
                          FILE */*fp*/, unsigned /*f*/,
                          int /*expht*/, void */*arg*/);
  /* Examine an AVL tree, checking that it satisfies all of the necessary
   * invariants.  If EXPHT is not equal to -1, then check that the overall
   * tree height is equal to EXPHT.
   *
   * This function uses the `xyla_bt_check' framework; see the description of
   * that function for details.  Returns `XYLA_RC_OK' on success,
   * `XYLA_RC_BAD' if problems are found, or some other code if verification
   * had to finish prematurely.
   */

#endif

/*----- That's all, folks -------------------------------------------------*/

#endif