gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / tower.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2009, 2011 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 #include <config.h>
18
19 #include "libpspp/tower.h"
20
21 #include <limits.h>
22
23 #include "libpspp/assertion.h"
24 #include "libpspp/cast.h"
25 #include "libpspp/compiler.h"
26
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);
37
38 /* Returns the height of the bottom of the given tower NODE.
39
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)
50 {
51   const struct abt_node *p = &node->abt_node;
52   unsigned long level = get_subtree_size (p->down[0]);
53   while (p->up != NULL) 
54     {
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;
59     }
60   return level;
61 }
62
63 /* Returns the index of the given tower NODE.
64
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)
72 {
73   const struct abt_node *p = &node->abt_node;
74   unsigned long index = get_subtree_count (p->down[0]);
75   while (p->up != NULL) 
76     {
77       if (p == p->up->down[1])
78         index += get_subtree_count (p->up->down[0]) + 1;
79       p = p->up;
80     }
81   return index;
82 }
83
84 /* Initializes T as an empty tower. */
85 void
86 tower_init (struct tower *t)
87 {
88   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
89   t->cache_bottom = ULONG_MAX;
90 }
91
92 /* Returns true if T contains no nodes, false otherwise. */
93 bool
94 tower_is_empty (const struct tower *t)
95 {
96   return t->abt.root == NULL;
97 }
98
99 /* Returns the number of nodes in tower T. */
100 unsigned long int
101 tower_count (const struct tower *t)
102 {
103   return get_subtree_count (t->abt.root);
104 }
105
106 /* Returns the total height of tower T. */
107 unsigned long
108 tower_height (const struct tower *t)
109 {
110   return get_subtree_size (t->abt.root);
111 }
112
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)
118 {
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;
124 }
125
126 /* Deletes NODE from tower T. */
127 struct tower_node *
128 tower_delete (struct tower *t, struct tower_node *node)
129 {
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;
134 }
135
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)
140 {
141   assert (new_size > 0);
142   node->size = new_size;
143   abt_reaugmented (&t->abt, &node->abt_node);
144   t->cache_bottom = ULONG_MAX;
145 }
146
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.
150
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)
158 {
159   struct tower_node *next;
160
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);
165
166   for (; first != last; first = next)
167     {
168       next = tower_delete (src, first);
169       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
170                          &first->abt_node);
171     }
172   dst->cache_bottom = src->cache_bottom = ULONG_MAX;
173 }
174
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)
184 {
185   struct tower *t = CONST_CAST (struct tower *, t_);
186   struct abt_node *p;
187
188   assert (height < tower_height (t));
189
190   if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->size)
191     {
192       *node_start = t->cache_bottom;
193       return t->cache;
194     }
195
196   *node_start = 0;
197   p = t->abt.root;
198   for (;;)
199     {
200       unsigned long left_size = get_subtree_size (p->down[0]);
201       if (height < left_size)
202         {
203           /* Our goal height must lie within the left subtree. */
204           p = p->down[0];
205         }
206       else
207         {
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;
211
212           height -= left_size;
213           *node_start += left_size;
214           if (height < node_size)
215             {
216               /* Our goal height is in P. */
217               t->cache = node;
218               t->cache_bottom = *node_start;
219               return node;
220             }
221           else
222             {
223               /* Our goal height is in the right subtree. */
224               p = p->down[1];
225               height -= node_size;
226               *node_start += node_size;
227             }
228         }
229     }
230 }
231
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) 
237 {
238   struct tower *t = CONST_CAST (struct tower *, t_);
239   struct abt_node *p;
240
241   assert (index < tower_count (t));
242
243   p = t->abt.root;
244   for (;;)
245     {
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
252         {
253           p = p->down[1];
254           index -= left_count + 1;
255         }
256     }
257 }
258
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)
263 {
264   return first_node (t);
265 }
266
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)
271 {
272   return last_node (t);
273 }
274
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)
280 {
281   return node != NULL ? next_node (t, node) : first_node (t);
282 }
283
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)
289 {
290   return node != NULL ? prev_node (t, node) : last_node (t);
291 }
292 \f
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)
296 {
297   return abt_data (abt_node, struct tower_node, abt_node);
298 }
299
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)
303 {
304   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
305 }
306
307 /* Returns the first node in TOWER. */
308 static struct tower_node *
309 first_node (const struct tower *t)
310 {
311   return abt_to_tower_node_null (abt_first (&t->abt));
312 }
313
314 /* Returns the first node in TOWER. */
315 static struct tower_node *
316 last_node (const struct tower *t)
317 {
318   return abt_to_tower_node_null (abt_last (&t->abt));
319 }
320
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)
324 {
325   return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
326 }
327
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)
331 {
332   return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
333 }
334
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)
339 {
340   return p != NULL ? abt_to_tower_node (p)->subtree_size : 0;
341 }
342
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)
347 {
348   return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
349 }
350
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)
355 {
356   struct tower_node *node = abt_to_tower_node (node_);
357   node->subtree_size = node->size;
358   node->subtree_count = 1;
359
360   if (node->abt_node.down[0] != NULL)
361     {
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;
365     }
366
367   if (node->abt_node.down[1] != NULL)
368     {
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;
372     }
373 }