1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007 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/>. */
19 #include <libpspp/tower.h>
23 #include <libpspp/assertion.h>
24 #include <libpspp/compiler.h>
26 static struct tower_node *abt_to_tower_node (const struct abt_node *);
27 static struct tower_node *first_node (const struct tower *);
28 static struct tower_node *last_node (const struct tower *);
29 static struct tower_node *next_node (const struct tower *,
30 const struct tower_node *);
31 static struct tower_node *prev_node (const struct tower *,
32 const struct tower_node *);
33 static unsigned long int get_subtree_height (const struct abt_node *);
34 static void reaugment_tower_node (struct abt_node *,
35 const struct abt_node *,
36 const struct abt_node *,
39 /* Initializes T as an empty tower. */
41 tower_init (struct tower *t)
43 abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
44 t->cache_bottom = ULONG_MAX;
47 /* Returns true if T contains no nodes, false otherwise. */
49 tower_is_empty (const struct tower *t)
51 return t->abt.root == NULL;
54 /* Returns the total height of tower T. */
56 tower_height (const struct tower *t)
58 return get_subtree_height (t->abt.root);
61 /* Inserts node NEW with the specified HEIGHT into T just below
62 node UNDER, or at the top of T if UNDER is a null pointer. */
64 tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
65 struct tower_node *under)
69 abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
71 t->cache_bottom = ULONG_MAX;
74 /* Deletes NODE from tower T. */
76 tower_delete (struct tower *t, struct tower_node *node)
78 struct tower_node *next = next_node (t, node);
79 abt_delete (&t->abt, &node->abt_node);
80 t->cache_bottom = ULONG_MAX;
84 /* Changes the height of NODE in tower T to NEW_HEIGHT. */
86 tower_resize (struct tower *t, struct tower_node *node,
87 unsigned long new_height)
89 assert (new_height > 0);
90 node->height = new_height;
91 abt_reaugmented (&t->abt, &node->abt_node);
92 t->cache_bottom = ULONG_MAX;
95 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
96 and splices them into tower DST just below node UNDER, or at
97 the top of DST if UNDER is a null pointer.
99 It might be better to implement an abt_splice function and
100 turn this into a wrapper, but the asymptotic performance would
103 tower_splice (struct tower *dst, struct tower_node *under,
105 struct tower_node *first, struct tower_node *last)
107 struct tower_node *next;
109 /* Conceptually, DST == SRC is valid.
110 Practically, it's more difficult to get it right, and our
111 client code doesn't need it. */
114 for (; first != last; first = next)
116 next = tower_delete (src, first);
117 abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
120 dst->cache_bottom = src->cache_bottom = ULONG_MAX;
123 /* Returns the node at the given HEIGHT from the bottom of tower
124 T. HEIGHT must be less than T's height (as returned by
125 tower_height). Stores in *NODE_START the height of the bottom
126 of the returned node, which may be less than HEIGHT if HEIGHT
127 refers to the middle of a node instead of its bottom. */
129 tower_lookup (const struct tower *t_,
130 unsigned long height,
131 unsigned long *node_start)
133 struct tower *t = (struct tower *) t_;
136 assert (height < tower_height (t));
138 if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->height)
140 *node_start = t->cache_bottom;
148 unsigned long left_height = get_subtree_height (p->down[0]);
149 if (height < left_height)
151 /* Our goal height must lie within the left subtree. */
156 /* Our goal height cannot be in the left subtree. */
157 struct tower_node *node = abt_to_tower_node (p);
158 unsigned long int node_height = node->height;
160 height -= left_height;
161 *node_start += left_height;
162 if (height < node_height)
164 /* Our goal height is in P. */
166 t->cache_bottom = *node_start;
171 /* Our goal height is in the right subtree. */
173 height -= node_height;
174 *node_start += node_height;
180 /* Returns the node at height 0 in tower T, or a null pointer if
183 tower_first (const struct tower *t)
185 return first_node (t);
188 /* Returns the node at the top of tower T, or a null pointer if T
191 tower_last (const struct tower *t)
193 return last_node (t);
196 /* If NODE is nonnull, returns the node just above NODE in tower
197 T, or a null pointer if NODE is the topmost node in T.
198 If NODE is null, acts like tower_first. */
200 tower_next (const struct tower *t, const struct tower_node *node)
202 return node != NULL ? next_node (t, node) : first_node (t);
205 /* If NODE is nonnull, returns the node just below NODE in tower
206 T, or a null pointer if NODE is the bottommost node in T.
207 If NODE is null, acts like tower_last. */
209 tower_prev (const struct tower *t, const struct tower_node *node)
211 return node != NULL ? prev_node (t, node) : last_node (t);
214 /* Returns the tower node corresponding to the given ABT_NODE. */
215 static struct tower_node *
216 abt_to_tower_node (const struct abt_node *abt_node)
218 return abt_data (abt_node, struct tower_node, abt_node);
221 /* Returns the tower node corresponding to the given ABT_NODE. */
222 static struct tower_node *
223 abt_to_tower_node_null (const struct abt_node *abt_node)
225 return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
228 /* Returns the first node in TOWER. */
229 static struct tower_node *
230 first_node (const struct tower *t)
232 return abt_to_tower_node_null (abt_first (&t->abt));
235 /* Returns the first node in TOWER. */
236 static struct tower_node *
237 last_node (const struct tower *t)
239 return abt_to_tower_node_null (abt_last (&t->abt));
242 /* Returns the next node in TOWER after NODE. */
243 static struct tower_node *
244 next_node (const struct tower *t, const struct tower_node *node)
246 return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
249 /* Returns the previous node in TOWER before NODE. */
250 static struct tower_node *
251 prev_node (const struct tower *t, const struct tower_node *node)
253 return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
256 /* Returns the total height of the nodes in the subtree rooted at
257 P, or 0 if P is null. */
258 static unsigned long int
259 get_subtree_height (const struct abt_node *p)
261 return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
264 /* Recalculates the subtree_height of NODE based on its LEFT and
265 RIGHT children's subtree_heights. */
267 reaugment_tower_node (struct abt_node *node_,
268 const struct abt_node *left,
269 const struct abt_node *right,
270 const void *aux UNUSED)
272 struct tower_node *node = abt_to_tower_node (node_);
273 node->subtree_height = node->height;
275 node->subtree_height += abt_to_tower_node (left)->subtree_height;
277 node->subtree_height += abt_to_tower_node (right)->subtree_height;