1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
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.
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.
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
21 #include <libpspp/tower.h>
25 #include <libpspp/assertion.h>
26 #include <libpspp/compiler.h>
28 static struct tower_node *abt_to_tower_node (const struct abt_node *);
29 static struct tower_node *first_node (const struct tower *);
30 static struct tower_node *next_node (const struct tower *,
31 const struct tower_node *);
32 static unsigned long int get_subtree_height (const struct abt_node *);
33 static void reaugment_tower_node (struct abt_node *,
34 const struct abt_node *,
35 const struct abt_node *,
38 /* Initializes T as an empty tower. */
40 tower_init (struct tower *t)
42 abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
43 t->cache_bottom = ULONG_MAX;
46 /* Returns true if T contains no nodes, false otherwise. */
48 tower_is_empty (const struct tower *t)
50 return t->abt.root == NULL;
53 /* Returns the total height of tower T. */
55 tower_height (const struct tower *t)
57 return get_subtree_height (t->abt.root);
60 /* Inserts node NEW with the specified HEIGHT into T just below
61 node UNDER, or at the top of T if UNDER is a null pointer. */
63 tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
64 struct tower_node *under)
68 abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
70 t->cache_bottom = ULONG_MAX;
73 /* Deletes NODE from tower T. */
75 tower_delete (struct tower *t, struct tower_node *node)
77 struct tower_node *next = next_node (t, node);
78 abt_delete (&t->abt, &node->abt_node);
79 t->cache_bottom = ULONG_MAX;
83 /* Changes the height of NODE in tower T to NEW_HEIGHT. */
85 tower_resize (struct tower *t, struct tower_node *node,
86 unsigned long new_height)
88 assert (new_height > 0);
89 node->height = new_height;
90 abt_reaugmented (&t->abt, &node->abt_node);
91 t->cache_bottom = ULONG_MAX;
94 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
95 and splices them into tower DST just below node UNDER, or at
96 the top of DST if UNDER is a null pointer.
98 It might be better to implement an abt_splice function and
99 turn this into a wrapper, but the asymptotic performance would
102 tower_splice (struct tower *dst, struct tower_node *under,
104 struct tower_node *first, struct tower_node *last)
106 struct tower_node *next;
108 /* Conceptually, DST == SRC is valid.
109 Practically, it's more difficult to get it right, and our
110 client code doesn't need it. */
113 for (; first != last; first = next)
115 next = tower_delete (src, first);
116 abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
119 dst->cache_bottom = src->cache_bottom = ULONG_MAX;
122 /* Returns the node at the given HEIGHT from the bottom of tower
123 T. HEIGHT must be less than T's height (as returned by
124 tower_height). Stores in *NODE_START the height of the bottom
125 of the returned node, which may be less than HEIGHT if HEIGHT
126 refers to the middle of a node instead of its bottom. */
128 tower_lookup (const struct tower *t_,
129 unsigned long height,
130 unsigned long *node_start)
132 struct tower *t = (struct tower *) t_;
135 assert (height < tower_height (t));
137 if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->height)
139 *node_start = t->cache_bottom;
147 unsigned long left_height = get_subtree_height (p->down[0]);
148 if (height < left_height)
150 /* Our goal height must lie within the left subtree. */
155 /* Our goal height cannot be in the left subtree. */
156 struct tower_node *node = abt_to_tower_node (p);
157 unsigned long int node_height = node->height;
159 height -= left_height;
160 *node_start += left_height;
161 if (height < node_height)
163 /* Our goal height is in P. */
165 t->cache_bottom = *node_start;
170 /* Our goal height is in the right subtree. */
172 height -= node_height;
173 *node_start += node_height;
179 /* Returns the node at height 0 in tower T, or a null pointer if
182 tower_first (const struct tower *t)
184 return first_node (t);
187 /* If NODE is nonnull, returns the node just above NODE in tower
188 T, or a null pointer if NODE is the topmost node in T.
189 If NODE is null, acts like tower_first. */
191 tower_next (const struct tower *t, const struct tower_node *node)
193 return node != NULL ? next_node (t, node) : first_node (t);
196 /* Returns the tower node corresponding to the given ABT_NODE. */
197 static struct tower_node *
198 abt_to_tower_node (const struct abt_node *abt_node)
200 return abt_data (abt_node, struct tower_node, abt_node);
203 /* Returns the first node in TOWER. */
204 static struct tower_node *
205 first_node (const struct tower *t)
207 struct abt_node *abt_node = abt_first (&t->abt);
208 return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
211 /* Returns the next node in TOWER after NODE. */
212 static struct tower_node *
213 next_node (const struct tower *t, const struct tower_node *node)
215 struct abt_node *abt_node = abt_next (&t->abt, &node->abt_node);
216 return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
219 /* Returns the total height of the nodes in the subtree rooted at
220 P, or 0 if P is null. */
221 static unsigned long int
222 get_subtree_height (const struct abt_node *p)
224 return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
227 /* Recalculates the subtree_height of NODE based on its LEFT and
228 RIGHT children's subtree_heights. */
230 reaugment_tower_node (struct abt_node *node_,
231 const struct abt_node *left,
232 const struct abt_node *right,
233 const void *aux UNUSED)
235 struct tower_node *node = abt_to_tower_node (node_);
236 node->subtree_height = node->height;
238 node->subtree_height += abt_to_tower_node (left)->subtree_height;
240 node->subtree_height += abt_to_tower_node (right)->subtree_height;