1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
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.
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.
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/>. */
18 #define LIBPSPP_ABT_H 1
20 /* Augmented binary tree (ABT) data structure.
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.
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.
35 The ABT data structure partially abstracts augmentation. The
36 client passes in a "reaugmentation" function that accepts a
37 node. This function must recalculate the node's augmentation
38 data based on its own contents and the contents of its
39 children, and store the new augmentation data in the node.
41 The ABT automatically calls the reaugmentation function
42 whenever it can tell that a node's augmentation data might
43 need to be updated: when the node is inserted or when a node's
44 descendants change due to insertion or deletion. The ABT does
45 not know to call the reaugmentation function if a node's data
46 is updated while it is in the ABT. In such a case, call the
47 abt_reaugmented or abt_changed function to update the
50 Augmentation is only partially abstracted: we do not provide
51 any way to search an ABT based on its augmentations. The
52 tree structure is thus exposed to the client to allow it to
55 To allow for optimization, the ABT implementation assumes that
56 the augmentation function in use is unaffected by the shape of
57 a binary search tree. That is, if a given subtree within a
58 larger tree is rearranged, e.g. via a series of rotations,
59 then the implementation will not call the reaugmentation
60 function outside of the subtree, because the overall
61 augmentation data for the subtree is assumed not to change.
62 This optimization is valid for the forms of augmentation
63 described in CLR and Knuth (see below), and it is possible
64 that it is valid for every efficient binary search tree
67 The client should not need to be aware of the form of
68 balancing applied to the ABT, as its operation should be fully
69 encapsulated by the reaugmentation function. The current
70 implementation uses an AA (Arne Andersson) tree, but this is
73 The following example illustrates how to use an ABT to build a
74 tree that can be searched either by a data value or in-order
80 struct abt_node node; // Embedded binary tree element.
81 int data; // Primary value.
82 int count; // Number of nodes in subtree,
83 // including this node.
86 // Returns the `struct element' that NODE is embedded within.
87 static struct element *
88 node_to_element (const struct abt_node *node)
90 return ABT_DATA (node, struct element, node);
93 // Compares the DATA values in A and B and returns a
94 // strcmp-type return value.
96 compare_elements (const struct abt_node *a_, const struct abt_node *b_,
99 const struct element *a = node_to_element (a_);
100 const struct element *b = node_to_element (b_);
102 return a->data < b->data ? -1 : a->data > b->data;
105 // Recalculates the count for NODE's subtree by adding up the
106 // counts for its left and right child subtrees.
108 reaugment_elements (struct abt_node *node_, const void *aux)
110 struct element *node = node_to_element (node_);
112 if (node->node.down[0] != NULL)
113 node->count += node_to_element (node->node.down[0])->count;
114 if (node->node.down[1] != NULL)
115 node->count += node_to_element (node->node.down[1])->count;
118 // Finds and returns the element in ABT that is in the given
119 // 0-based POSITION in in-order.
120 static struct element *
121 find_by_position (struct abt *abt, int position)
124 for (p = abt->root; p != NULL;)
126 int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
127 if (position == p_pos)
128 return node_to_element (p);
129 else if (position < p_pos)
134 position -= p_pos + 1;
140 For more information on augmenting binary search tree-based
141 data structures, see Cormen-Leiserson-Rivest, chapter 15, or
142 Knuth vol. 3, section 6.2.3, under "Linear list
143 representation." For more information on AA trees, see
144 <http://en.wikipedia.org/wiki/AA_tree>, which includes source
145 code and links to other resources, such as the original AA
150 #include "libpspp/cast.h"
152 /* Returns the data structure corresponding to the given NODE, assuming that
153 NODE is embedded as the given MEMBER name in data type STRUCT. NODE must
154 not be a null pointer. */
155 #define ABT_DATA(NODE, STRUCT, MEMBER) \
156 (CHECK_POINTER_HAS_TYPE (NODE, struct abt_node *), \
157 UP_CAST (NODE, STRUCT, MEMBER))
159 /* Like ABT_DATA, except that a null NODE yields a null pointer result. */
160 #define ABT_NULLABLE_DATA(NODE, STRUCT, MEMBER) \
161 ((STRUCT *) abt_nullable_data__ (NODE, offsetof (STRUCT, MEMBER)))
163 /* Node in an augmented binary tree. */
166 struct abt_node *up; /* Parent (NULL for root). */
167 struct abt_node *down[2]; /* Left child, right child. */
168 int level; /* AA tree level (not ordinary BST level). */
171 /* Compares nodes A and B, with the tree's AUX.
172 Returns a strcmp-like result. */
173 typedef int abt_compare_func (const struct abt_node *a,
174 const struct abt_node *b,
177 /* Recalculates NODE's augmentation based on NODE's data and that of its left
178 and right children NODE->down[0] and NODE[1], respectively, with the tree's
180 typedef void abt_reaugment_func (struct abt_node *node, const void *aux);
182 /* An augmented binary tree. */
185 struct abt_node *root; /* Tree's root, NULL if empty. */
186 abt_compare_func *compare; /* To compare nodes. */
187 abt_reaugment_func *reaugment; /* To augment a node using its children. */
188 const void *aux; /* Auxiliary data. */
190 #define ABT_INITIALIZER(COMPARE, REAUGMENT, AUX) \
191 { .compare = COMPARE, .reaugment = REAUGMENT, .aux = AUX }
193 void abt_init (struct abt *, abt_compare_func *, abt_reaugment_func *,
196 static inline bool abt_is_empty (const struct abt *);
198 struct abt_node *abt_insert (struct abt *, struct abt_node *);
199 void abt_insert_after (struct abt *,
200 const struct abt_node *, struct abt_node *);
201 void abt_insert_before (struct abt *,
202 const struct abt_node *, struct abt_node *);
203 void abt_delete (struct abt *, struct abt_node *);
205 struct abt_node *abt_first (const struct abt *);
206 struct abt_node *abt_last (const struct abt *);
207 struct abt_node *abt_find (const struct abt *, const struct abt_node *);
208 struct abt_node *abt_next (const struct abt *, const struct abt_node *);
209 struct abt_node *abt_prev (const struct abt *, const struct abt_node *);
211 void abt_reaugmented (const struct abt *, struct abt_node *);
212 struct abt_node *abt_changed (struct abt *, struct abt_node *);
213 void abt_moved (struct abt *, struct abt_node *);
215 /* Convenience macros for iteration.
217 These macros automatically use ABT_DATA to obtain the data elements that
218 encapsulate abt nodes, which often saves typing and can make code easier to
219 read. Refer to the large comment near the top of this file for an example.
221 These macros evaluate their arguments many times. */
222 #define ABT_FIRST(STRUCT, MEMBER, ABT) \
223 ABT_NULLABLE_DATA (abt_first (ABT), STRUCT, MEMBER)
224 #define ABT_NEXT(DATA, STRUCT, MEMBER, ABT) \
225 ABT_NULLABLE_DATA (abt_next (ABT, &(DATA)->MEMBER), STRUCT, MEMBER)
226 #define ABT_FOR_EACH(DATA, STRUCT, MEMBER, ABT) \
227 for ((DATA) = ABT_FIRST (STRUCT, MEMBER, ABT); \
229 (DATA) = ABT_NEXT (DATA, STRUCT, MEMBER, ABT))
230 #define ABT_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, ABT) \
231 for ((DATA) = ABT_FIRST (STRUCT, MEMBER, ABT); \
233 ? ((NEXT) = ABT_NEXT (DATA, STRUCT, MEMBER, ABT), 1) \
237 /* Returns true if ABT contains no nodes, false if ABT contains at least one
240 abt_is_empty (const struct abt *abt)
242 return abt->root == NULL;
245 /* Helper for ABT_NULLABLE_DATA (to avoid evaluating its NODE argument more
248 abt_nullable_data__ (struct abt_node *node, size_t member_offset)
250 return node != NULL ? (char *) node - member_offset : NULL;
253 #endif /* libpspp/abt.h */