src/libpspp/abt.h

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 #ifndef LIBPSPP_ABT_H
  20 #define LIBPSPP_ABT_H 1
  21
  22 /* Augmented binary tree (ABT) data structure.
  23
  24    A data structure can be "augmented" by defining new
  25    information for it to maintain.  One commonly useful way to
  26    augment a binary search tree-based data structure is to define
  27    part of its data as a function of its immediate children's
  28    data.  Furthermore, augmented data defined in this way can be
  29    efficiently maintained as the tree changes over time.
  30
  31    For example, suppose we define the "size" of a node as the sum
  32    of the "size" of its immediate children, plus 1.  In such an
  33    annotated BST with height H, we can find the node that would
  34    be Kth in in-order traversal in O(H) time, instead of O(K)
  35    time, which is a significant saving for balanced trees.
  36
  37    The ABT data structure partially abstracts augmentation.  The
  38    client passes in a "reaugmentation" function that accepts a
  39    node and its left and right children.  This function must
  40    recalculate the node's augmentation data based on its own
  41    contents and the contents of its children, and store the new
  42    augmentation data in the node.
  43
  44    The ABT automatically calls the reaugmentation function
  45    whenever it can tell that a node's augmentation data might
  46    need to be updated: when the node is inserted or when a node's
  47    descendants change due to insertion or deletion.  The ABT does
  48    not know to call the reaugmentation function if a node's data
  49    is updated while it is in the ABT.  In such a case, call the
  50    abt_reaugmented or abt_changed function to update the
  51    augmentation.
  52
  53    Augmentation is only partially abstracted: we do not provide
  54    any way to search an ABT based on its augmentations.  The
  55    tree structure is thus exposed to the client to allow it to
  56    implement search.
  57
  58    To allow for optimization, the ABT implementation assumes that
  59    the augmentation function in use is unaffected by the shape of
  60    a binary search tree.  That is, if a given subtree within a
  61    larger tree is rearranged, e.g. via a series of rotations,
  62    then the implementation will not call the reaugmentation
  63    function outside of the subtree, because the overall
  64    augmentation data for the subtree is assumed not to changed.
  65    This optimization is valid for the forms of augmentation
  66    described in CLR and Knuth (see below), and it is possible
  67    that it is valid for every efficient binary search tree
  68    augmentation.
  69
  70    The client should not need to be aware of the form of
  71    balancing applied to the ABT, as its operation should be fully
  72    encapsulated by the reaugmentation function.  The current
  73    implementation uses an AA (Arne Andersson) tree, but this is
  74    subject to change.
  75
  76    The following example illustrates how to use an ABT to build a
  77    tree that can be searched either by a data value or in-order
  78    position:
  79
  80      // Test data element.
  81      struct element
  82        {
  83          struct abt_node node;       // Embedded binary tree element.
  84          int data;                   // Primary value.
  85          int count;                  // Number of nodes in subtree,
  86                                      // including this node.
  87        };
  88
  89      // Returns the `struct element' that NODE is embedded within.
  90      static struct element *
  91      node_to_element (const struct abt_node *node)
  92      {
  93        return abt_data (node, struct element, node);
  94      }
  95
  96      // Compares the DATA values in A and B and returns a
  97      // strcmp-type return value.
  98      static int
  99      compare_elements (const struct abt_node *a_, const struct abt_node *b_,
 100                        const void *aux)
 101      {
 102        const struct element *a = node_to_element (a_);
 103        const struct element *b = node_to_element (b_);
 104
 105        return a->data < b->data ? -1 : a->data > b->data;
 106      }
 107
 108      // Recalculates the count for NODE's subtree by adding up the
 109      // counts for its LEFT and RIGHT child subtrees.
 110      static void
 111      reaugment_elements (struct abt_node *node_,
 112                          const struct abt_node *left,
 113                          const struct abt_node *right,
 114                          const void *aux)
 115      {
 116        struct element *node = node_to_element (node_);
 117        node->count = 1;
 118        if (left != NULL)
 119          node->count += node_to_element (left)->count;
 120        if (right != NULL)
 121          node->count += node_to_element (right)->count;
 122      }
 123
 124      // Finds and returns the element in ABT that is in the given
 125      // 0-based POSITION in in-order.
 126      static struct element *
 127      find_by_position (struct abt *abt, int position)
 128      {
 129        struct abt_node *p;
 130        for (p = abt->root; p != NULL; )
 131          {
 132            int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
 133            if (position == p_pos)
 134              return node_to_element (p);
 135            else if (position < p_pos)
 136              p = p->down[0];
 137            else
 138              {
 139                p = p->down[1];
 140                position -= p_pos + 1;
 141              }
 142          }
 143        return NULL;
 144      }
 145
 146    For more information on augmenting binary search tree-based
 147    data structures, see Cormen-Leiserson-Rivest, chapter 15, or
 148    Knuth vol. 3, section 6.2.3, under "Linear list
 149    representation."  For more information on AA trees, see
 150    <http://en.wikipedia.org/wiki/AA_tree>, which includes source
 151    code and links to other resources, such as the original AA
 152    tree paper.  */
 153
 154 #include <stddef.h>
 155
 156 /* Returns the data structure corresponding to the given NODE,
 157    assuming that NODE is embedded as the given MEMBER name in
 158    data type STRUCT. */
 159 #define abt_data(NODE, STRUCT, MEMBER)                                  \
 160         ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
 161
 162 /* Node in an augmented binary tree. */
 163 struct abt_node
 164   {
 165     struct abt_node *up;        /* Parent (NULL for root). */
 166     struct abt_node *down[2];   /* Left child, right child. */
 167     int level;                  /* AA tree level (not ordinary BST level). */
 168   };
 169
 170 /* Compares nodes A and B, with the tree's AUX.
 171    Returns a strcmp-like result. */
 172 typedef int abt_compare_func (const struct abt_node *a,
 173                               const struct abt_node *b,
 174                               const void *aux);
 175
 176 /* Recalculates NODE's augmentation based on NODE's data and that
 177    of its LEFT and RIGHT children, with the tree's AUX. */
 178 typedef void abt_reaugment_func (struct abt_node *node,
 179                                  const struct abt_node *left,
 180                                  const struct abt_node *right,
 181                                  const void *aux);
 182
 183 /* An augmented binary tree. */
 184 struct abt
 185   {
 186     struct abt_node *root;         /* Tree's root, NULL if empty. */
 187     abt_compare_func *compare;     /* To compare nodes. */
 188     abt_reaugment_func *reaugment; /* To augment a node using its children. */
 189     const void *aux;               /* Auxiliary data. */
 190   };
 191
 192 void abt_init (struct abt *, abt_compare_func *, abt_reaugment_func *,
 193                const void *aux);
 194
 195 struct abt_node *abt_insert (struct abt *, struct abt_node *);
 196 void abt_delete (struct abt *, struct abt_node *);
 197
 198 struct abt_node *abt_first (const struct abt *);
 199 struct abt_node *abt_last (const struct abt *);
 200 struct abt_node *abt_find (const struct abt *, const struct abt_node *);
 201 struct abt_node *abt_next (const struct abt *, const struct abt_node *);
 202 struct abt_node *abt_prev (const struct abt *, const struct abt_node *);
 203
 204 void abt_reaugmented (const struct abt *, struct abt_node *);
 205 struct abt_node *abt_changed (struct abt *, struct abt_node *);
 206 void abt_moved (struct abt *, struct abt_node *);
 207
 208 #endif /* libpspp/abt.h */