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