pivot-output: Fix crash when layers axis has no leaves.
[pspp.git] / src / libpspp / tower.c
blob39f9d23ce7a36d51fc959c218b0153fc5b83008f
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/>. */
17 #include <config.h>
19 #include "libpspp/tower.h"
21 #include <limits.h>
23 #include "libpspp/assertion.h"
24 #include "libpspp/cast.h"
25 #include "libpspp/compiler.h"
27 static struct tower_node *abt_to_tower_node (const struct abt_node *);
28 static struct tower_node *first_node (const struct tower *);
29 static struct tower_node *last_node (const struct tower *);
30 static struct tower_node *next_node (const struct tower *,
31 const struct tower_node *);
32 static struct tower_node *prev_node (const struct tower *,
33 const struct tower_node *);
34 static unsigned long int get_subtree_size (const struct abt_node *);
35 static unsigned long int get_subtree_count (const struct abt_node *);
36 static void reaugment_tower_node (struct abt_node *, const void *aux);
38 /* Returns the height of the bottom of the given tower NODE.
40 The performance of this function is O(lg n) in the number of
41 nodes in the tower. It is often possible to avoid calling
42 this function, either by taking advantage of the NODE_START
43 parameter to tower_lookup or by incrementally keeping track of
44 height while iterating through a tower. In the former case
45 the asymptotic performance is no different, since tower_lookup
46 is also O(lg n), but in the latter case performance improves
47 from O(lg n) to O(1). */
48 unsigned long int
49 tower_node_get_level (const struct tower_node *node)
51 const struct abt_node *p = &node->abt_node;
52 unsigned long level = get_subtree_size (p->down[0]);
53 while (p->up != NULL)
55 if (p == p->up->down[1])
56 level += (get_subtree_size (p->up->down[0])
57 + abt_to_tower_node (p->up)->size);
58 p = p->up;
60 return level;
63 /* Returns the index of the given tower NODE.
65 The performance of this function is O(lg n) in the number of
66 nodes in the tower. It is often possible to avoid calling
67 this function by keeping track of the index while iterating
68 through a tower. Doing so when possible will improve
69 performance from O(lg n) to O(1). */
70 unsigned long int
71 tower_node_get_index (const struct tower_node *node)
73 const struct abt_node *p = &node->abt_node;
74 unsigned long index = get_subtree_count (p->down[0]);
75 while (p->up != NULL)
77 if (p == p->up->down[1])
78 index += get_subtree_count (p->up->down[0]) + 1;
79 p = p->up;
81 return index;
84 /* Initializes T as an empty tower. */
85 void
86 tower_init (struct tower *t)
88 abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
89 t->cache_bottom = ULONG_MAX;
92 /* Returns true if T contains no nodes, false otherwise. */
93 bool
94 tower_is_empty (const struct tower *t)
96 return t->abt.root == NULL;
99 /* Returns the number of nodes in tower T. */
100 unsigned long int
101 tower_count (const struct tower *t)
103 return get_subtree_count (t->abt.root);
106 /* Returns the total height of tower T. */
107 unsigned long
108 tower_height (const struct tower *t)
110 return get_subtree_size (t->abt.root);
113 /* Inserts node NEW with the specified SIZE into T just below
114 node UNDER, or at the top of T if UNDER is a null pointer. */
115 void
116 tower_insert (struct tower *t, unsigned long size, struct tower_node *new,
117 struct tower_node *under)
119 assert (size > 0);
120 new->size = size;
121 abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
122 &new->abt_node);
123 t->cache_bottom = ULONG_MAX;
126 /* Deletes NODE from tower T. */
127 struct tower_node *
128 tower_delete (struct tower *t, struct tower_node *node)
130 struct tower_node *next = next_node (t, node);
131 abt_delete (&t->abt, &node->abt_node);
132 t->cache_bottom = ULONG_MAX;
133 return next;
136 /* Changes the size of NODE in tower T to NEW_SIZE. */
137 void
138 tower_resize (struct tower *t, struct tower_node *node,
139 unsigned long new_size)
141 assert (new_size > 0);
142 node->size = new_size;
143 abt_reaugmented (&t->abt, &node->abt_node);
144 t->cache_bottom = ULONG_MAX;
147 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
148 and splices them into tower DST just below node UNDER, or at
149 the top of DST if UNDER is a null pointer.
151 It might be better to implement an abt_splice function and
152 turn this into a wrapper, but the asymptotic performance would
153 be the same. */
154 void
155 tower_splice (struct tower *dst, struct tower_node *under,
156 struct tower *src,
157 struct tower_node *first, struct tower_node *last)
159 struct tower_node *next;
161 /* Conceptually, DST == SRC is valid.
162 Practically, it's more difficult to get it right, and our
163 client code doesn't need it. */
164 assert (dst != src);
166 for (; first != last; first = next)
168 next = tower_delete (src, first);
169 abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
170 &first->abt_node);
172 dst->cache_bottom = src->cache_bottom = ULONG_MAX;
175 /* Returns the node at the given HEIGHT from the bottom of tower
176 T. HEIGHT must be less than T's height (as returned by
177 tower_height). Stores in *NODE_START the height of the bottom
178 of the returned node, which may be less than HEIGHT if HEIGHT
179 refers to the middle of a node instead of its bottom. */
180 struct tower_node *
181 tower_lookup (const struct tower *t_,
182 unsigned long height,
183 unsigned long *node_start)
185 struct tower *t = CONST_CAST (struct tower *, t_);
186 struct abt_node *p;
188 assert (height < tower_height (t));
190 if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->size)
192 *node_start = t->cache_bottom;
193 return t->cache;
196 *node_start = 0;
197 p = t->abt.root;
198 for (;;)
200 unsigned long left_size = get_subtree_size (p->down[0]);
201 if (height < left_size)
203 /* Our goal height must lie within the left subtree. */
204 p = p->down[0];
206 else
208 /* Our goal height cannot be in the left subtree. */
209 struct tower_node *node = abt_to_tower_node (p);
210 unsigned long int node_size = node->size;
212 height -= left_size;
213 *node_start += left_size;
214 if (height < node_size)
216 /* Our goal height is in P. */
217 t->cache = node;
218 t->cache_bottom = *node_start;
219 return node;
221 else
223 /* Our goal height is in the right subtree. */
224 p = p->down[1];
225 height -= node_size;
226 *node_start += node_size;
232 /* Returns the node with the given 0-based INDEX, which must be
233 less than the number of nodes in T (as returned by
234 tower_count). */
235 struct tower_node *
236 tower_get (const struct tower *t_, unsigned long int index)
238 struct tower *t = CONST_CAST (struct tower *, t_);
239 struct abt_node *p;
241 assert (index < tower_count (t));
243 p = t->abt.root;
244 for (;;)
246 unsigned long left_count = get_subtree_count (p->down[0]);
247 if (index < left_count)
248 p = p->down[0];
249 else if (index == left_count)
250 return abt_to_tower_node (p);
251 else
253 p = p->down[1];
254 index -= left_count + 1;
259 /* Returns the node at height 0 in tower T, or a null pointer if
260 T is empty. */
261 struct tower_node *
262 tower_first (const struct tower *t)
264 return first_node (t);
267 /* Returns the node at the top of tower T, or a null pointer if T
268 is empty. */
269 struct tower_node *
270 tower_last (const struct tower *t)
272 return last_node (t);
275 /* If NODE is nonnull, returns the node just above NODE in tower
276 T, or a null pointer if NODE is the topmost node in T.
277 If NODE is null, acts like tower_first. */
278 struct tower_node *
279 tower_next (const struct tower *t, const struct tower_node *node)
281 return node != NULL ? next_node (t, node) : first_node (t);
284 /* If NODE is nonnull, returns the node just below NODE in tower
285 T, or a null pointer if NODE is the bottommost node in T.
286 If NODE is null, acts like tower_last. */
287 struct tower_node *
288 tower_prev (const struct tower *t, const struct tower_node *node)
290 return node != NULL ? prev_node (t, node) : last_node (t);
293 /* Returns the tower node corresponding to the given ABT_NODE. */
294 static struct tower_node *
295 abt_to_tower_node (const struct abt_node *abt_node)
297 return ABT_DATA (abt_node, struct tower_node, abt_node);
300 /* Returns the tower node corresponding to the given ABT_NODE. */
301 static struct tower_node *
302 abt_to_tower_node_null (const struct abt_node *abt_node)
304 return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
307 /* Returns the first node in TOWER. */
308 static struct tower_node *
309 first_node (const struct tower *t)
311 return abt_to_tower_node_null (abt_first (&t->abt));
314 /* Returns the first node in TOWER. */
315 static struct tower_node *
316 last_node (const struct tower *t)
318 return abt_to_tower_node_null (abt_last (&t->abt));
321 /* Returns the next node in TOWER after NODE. */
322 static struct tower_node *
323 next_node (const struct tower *t, const struct tower_node *node)
325 return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
328 /* Returns the previous node in TOWER before NODE. */
329 static struct tower_node *
330 prev_node (const struct tower *t, const struct tower_node *node)
332 return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
335 /* Returns the total size of the nodes in the subtree rooted at
336 P, or 0 if P is null. */
337 static unsigned long int
338 get_subtree_size (const struct abt_node *p)
340 return p != NULL ? abt_to_tower_node (p)->subtree_size : 0;
343 /* Returns the total number of nodes in the subtree rooted at P,
344 or 0 if P is null. */
345 static unsigned long int
346 get_subtree_count (const struct abt_node *p)
348 return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
351 /* Recalculates the subtree_size of NODE based on the subtree_sizes of its
352 children. */
353 static void
354 reaugment_tower_node (struct abt_node *node_, const void *aux UNUSED)
356 struct tower_node *node = abt_to_tower_node (node_);
357 node->subtree_size = node->size;
358 node->subtree_count = 1;
360 if (node->abt_node.down[0] != NULL)
362 struct tower_node *left = abt_to_tower_node (node->abt_node.down[0]);
363 node->subtree_size += left->subtree_size;
364 node->subtree_count += left->subtree_count;
367 if (node->abt_node.down[1] != NULL)
369 struct tower_node *right = abt_to_tower_node (node->abt_node.down[1]);
370 node->subtree_size += right->subtree_size;
371 node->subtree_count += right->subtree_count;