gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / abt.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 /* Augmented binary tree (ABT) data structure. */
18
19 /* These library routines have no external dependencies other
20    than the standard C library.
21
22    If you add routines in this file, please add a corresponding
23    test to abt-test.c.  This test program should achieve 100%
24    coverage of lines and branches in this code, as reported by
25    "gcov -b". */
26
27 #ifdef HAVE_CONFIG_H
28 #include <config.h>
29 #endif
30
31 #include "libpspp/abt.h"
32
33 #include <stdbool.h>
34
35 #include "libpspp/cast.h"
36 #include "libpspp/assertion.h"
37
38 static struct abt_node **down_link (struct abt *, struct abt_node *);
39 static struct abt_node *skew (struct abt *, struct abt_node *);
40 static struct abt_node *split (struct abt *, struct abt_node *);
41
42 /* Initializes ABT as an empty ABT that uses COMPARE and
43    REAUGMENT functions, passing in AUX as auxiliary data.
44
45    The comparison function is optional.  If it is null, this
46    indicates that the tree is being used for its augmentations
47    only.  ABT functions that compare nodes may not be used with
48    trees that lack comparison functions; contrariwise, other
49    functions that could disrupt the ordering of a tree may not be
50    used if a comparison function is specified.  Refer to
51    individual function descriptions for details. */
52 void
53 abt_init (struct abt *abt,
54           abt_compare_func *compare,
55           abt_reaugment_func *reaugment,
56           const void *aux)
57 {
58   assert (reaugment != NULL);
59   abt->root = NULL;
60   abt->compare = compare;
61   abt->reaugment = reaugment;
62   abt->aux = aux;
63 }
64
65 /* Inserts the given NODE into ABT.
66    Returns a null pointer if successful.
67    Returns the existing node already in ABT equal to NODE, on
68    failure.
69    This function may be used only if ABT has a comparison
70    function. */
71 struct abt_node *
72 abt_insert (struct abt *abt, struct abt_node *node)
73 {
74   node->down[0] = NULL;
75   node->down[1] = NULL;
76   node->level = 1;
77
78   if (abt->root == NULL)
79     {
80       abt->root = node;
81       node->up = NULL;
82       abt_reaugmented (abt, node);
83     }
84   else
85     {
86       struct abt_node *p = abt->root;
87       for (;;)
88         {
89           int cmp, dir;
90
91           cmp = abt->compare (node, p, abt->aux);
92           if (cmp == 0)
93             return p;
94
95           dir = cmp > 0;
96           if (p->down[dir] == NULL)
97             {
98               p->down[dir] = node;
99               node->up = p;
100               abt_reaugmented (abt, node);
101               break;
102             }
103           p = p->down[dir];
104         }
105     }
106
107   while ((node = node->up) != NULL)
108     {
109       node = skew (abt, node);
110       node = split (abt, node);
111     }
112
113   return NULL;
114 }
115
116 /* Inserts NODE before or after node P in ABT, depending on the
117    value of AFTER.
118    If P is null, then the node is inserted as the first node in
119    the tree, if AFTER is true, or the last node, if AFTER is
120    false. */
121 static inline void
122 insert_relative (struct abt *abt, const struct abt_node *p, bool after,
123                  struct abt_node *node)
124 {
125   node->down[0] = NULL;
126   node->down[1] = NULL;
127   node->level = 1;
128
129   if (abt->root == NULL)
130     {
131       assert (p == NULL);
132       abt->root = node;
133       node->up = NULL;
134       abt_reaugmented (abt, node);
135     }
136   else
137     {
138       int dir = after;
139       if (p == NULL)
140         {
141           p = abt->root;
142           dir = !after;
143         }
144       while (p->down[dir] != NULL)
145         {
146           p = p->down[dir];
147           dir = !after;
148         }
149       CONST_CAST (struct abt_node *, p)->down[dir] = node;
150       node->up = CONST_CAST (struct abt_node *, p);
151       abt_reaugmented (abt, node);
152     }
153
154   while ((node = node->up) != NULL)
155     {
156       node = skew (abt, node);
157       node = split (abt, node);
158     }
159 }
160
161 /* Inserts NODE after node P in ABT.
162    If P is null, then the node is inserted as the first node in
163    the tree.
164    This function may be used only if ABT lacks a comparison
165    function. */
166 void
167 abt_insert_after (struct abt *abt,
168                   const struct abt_node *p, struct abt_node *node)
169 {
170   assert (abt->compare == NULL);
171   insert_relative (abt, p, true, node);
172 }
173
174 /* Inserts NODE before node P in ABT.
175    If P is null, then the node is inserted as the last node in
176    the tree.
177    This function may be used only if ABT lacks a comparison
178    function. */
179 void
180 abt_insert_before (struct abt *abt,
181                    const struct abt_node *p, struct abt_node *node)
182 {
183   assert (abt->compare == NULL);
184   insert_relative (abt, p, false, node);
185 }
186
187 /* Deletes P from ABT. */
188 void
189 abt_delete (struct abt *abt, struct abt_node *p)
190 {
191   struct abt_node **q = down_link (abt, p);
192   struct abt_node *r = p->down[1];
193   if (r == NULL)
194     {
195       *q = NULL;
196       p = p->up;
197     }
198   else if (r->down[0] == NULL)
199     {
200       r->down[0] = p->down[0];
201       *q = r;
202       r->up = p->up;
203       if (r->down[0] != NULL)
204         r->down[0]->up = r;
205       r->level = p->level;
206       p = r;
207     }
208   else
209     {
210       struct abt_node *s = r->down[0];
211       while (s->down[0] != NULL)
212         s = s->down[0];
213       r = s->up;
214       r->down[0] = s->down[1];
215       s->down[0] = p->down[0];
216       s->down[1] = p->down[1];
217       *q = s;
218       s->down[0]->up = s;
219       s->down[1]->up = s;
220       s->up = p->up;
221       s->level = p->level;
222       if (r->down[0] != NULL)
223         r->down[0]->up = r;
224       p = r;
225     }
226   abt_reaugmented (abt, p);
227
228   for (; p != NULL; p = p->up)
229     if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
230         || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
231       {
232         p->level--;
233         if (p->down[1] != NULL && p->down[1]->level > p->level)
234           p->down[1]->level = p->level;
235
236         p = skew (abt, p);
237         skew (abt, p->down[1]);
238         if (p->down[1]->down[1] != NULL)
239           skew (abt, p->down[1]->down[1]);
240
241         p = split (abt, p);
242         split (abt, p->down[1]);
243       }
244 }
245
246 /* Returns the node with minimum value in ABT, or a null pointer
247    if ABT is empty. */
248 struct abt_node *
249 abt_first (const struct abt *abt)
250 {
251   struct abt_node *p = abt->root;
252   if (p != NULL)
253     while (p->down[0] != NULL)
254       p = p->down[0];
255   return p;
256 }
257
258 /* Returns the node with maximum value in ABT, or a null pointer
259    if ABT is empty. */
260 struct abt_node *
261 abt_last (const struct abt *abt)
262 {
263   struct abt_node *p = abt->root;
264   if (p != NULL)
265     while (p->down[1] != NULL)
266       p = p->down[1];
267   return p;
268 }
269
270 /* Searches ABT for a node equal to TARGET.
271    Returns the node if found, or a null pointer otherwise.
272    This function may be used only if ABT has a comparison
273    function. */
274 struct abt_node *
275 abt_find (const struct abt *abt, const struct abt_node *target)
276 {
277   const struct abt_node *p;
278   int cmp;
279
280   for (p = abt->root; p != NULL; p = p->down[cmp > 0])
281     {
282       cmp = abt->compare (target, p, abt->aux);
283       if (cmp == 0)
284         return CONST_CAST (struct abt_node *, p);
285     }
286
287   return NULL;
288 }
289
290 /* Returns the node in ABT following P in in-order.
291    If P is null, returns the minimum node in ABT.
292    Returns a null pointer if P is the maximum node in ABT or if P
293    is null and ABT is empty. */
294 struct abt_node *
295 abt_next (const struct abt *abt, const struct abt_node *p)
296 {
297   if (p == NULL)
298     return abt_first (abt);
299   else if (p->down[1] == NULL)
300     {
301       struct abt_node *q;
302       for (q = p->up; ; p = q, q = q->up)
303         if (q == NULL || p == q->down[0])
304           return q;
305     }
306   else
307     {
308       p = p->down[1];
309       while (p->down[0] != NULL)
310         p = p->down[0];
311       return CONST_CAST (struct abt_node *, p);
312     }
313 }
314
315 /* Returns the node in ABT preceding P in in-order.
316    If P is null, returns the maximum node in ABT.
317    Returns a null pointer if P is the minimum node in ABT or if P
318    is null and ABT is empty. */
319 struct abt_node *
320 abt_prev (const struct abt *abt, const struct abt_node *p)
321 {
322   if (p == NULL)
323     return abt_last (abt);
324   else if (p->down[0] == NULL)
325     {
326       struct abt_node *q;
327       for (q = p->up; ; p = q, q = q->up)
328         if (q == NULL || p == q->down[1])
329           return q;
330     }
331   else
332     {
333       p = p->down[0];
334       while (p->down[1] != NULL)
335         p = p->down[1];
336       return CONST_CAST (struct abt_node *, p);
337     }
338 }
339
340 /* Calls ABT's reaugmentation function to compensate for
341    augmentation data in P having been modified.  Use abt_changed,
342    instead, if the key data in P has changed.
343
344    It is not safe to update more than one node's augmentation
345    data, then to call this function for each node.  Instead,
346    update a single node's data, call this function, update
347    another node's data, and so on.  Alternatively, remove all
348    affected nodes from the tree, update their values, then
349    re-insert all of them. */
350 void
351 abt_reaugmented (const struct abt *abt, struct abt_node *p)
352 {
353   for (; p != NULL; p = p->up)
354     abt->reaugment (p, abt->aux);
355 }
356
357 /* Moves P around in ABT to compensate for its key having
358    changed.  Returns a null pointer if successful.  If P's new
359    value is equal to that of some other node in ABT, returns the
360    other node after removing P from ABT.
361
362    This function is an optimization only if it is likely that P
363    can actually retain its relative position in ABT, e.g. its key
364    has only been adjusted slightly.  Otherwise, it is more
365    efficient to simply remove P from ABT, change its key, and
366    re-insert P.
367
368    It is not safe to update more than one node's key, then to
369    call this function for each node.  Instead, update a single
370    node's key, call this function, update another node's key, and
371    so on.  Alternatively, remove all affected nodes from the
372    tree, update their keys, then re-insert all of them.
373
374    This function may be used only if ABT has a comparison
375    function.  If it doesn't, then you probably just want
376    abt_reaugmented. */
377 struct abt_node *
378 abt_changed (struct abt *abt, struct abt_node *p)
379 {
380   struct abt_node *prev = abt_prev (abt, p);
381   struct abt_node *next = abt_next (abt, p);
382
383   if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
384       || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
385     {
386       abt_delete (abt, p);
387       return abt_insert (abt, p);
388     }
389   else
390     {
391       abt_reaugmented (abt, p);
392       return NULL;
393     }
394 }
395
396 /* ABT nodes may be moved around in memory as necessary, e.g. as
397    the result of an realloc operation on a block that contains a
398    node.  Once this is done, call this function passing node P
399    that was moved and its ABT before attempting any other
400    operation on ABT.
401
402    It is not safe to move more than one node, then to call this
403    function for each node.  Instead, move a single node, call
404    this function, move another node, and so on.  Alternatively,
405    remove all affected nodes from the tree, move them, then
406    re-insert all of them.
407
408    This function may be used only if ABT has a comparison
409    function. */
410 void
411 abt_moved (struct abt *abt, struct abt_node *p)
412 {
413   if (p->up != NULL)
414     {
415       int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
416       p->up->down[d] = p;
417     }
418   else
419     abt->root = p;
420   if (p->down[0] != NULL)
421     p->down[0]->up = p;
422   if (p->down[1] != NULL)
423     p->down[1]->up = p;
424 }
425 \f
426 /* Returns the address of the pointer that points down to P
427    within ABT. */
428 static struct abt_node **
429 down_link (struct abt *abt, struct abt_node *p)
430 {
431   return (p->up != NULL
432           ? &p->up->down[p->up->down[0] != p]
433           : &abt->root);
434 }
435
436 /* Remove a left "horizontal link" at A, if present.
437    Returns the node that occupies the position previously
438    occupied by A. */
439 static struct abt_node *
440 skew (struct abt *abt, struct abt_node *a)
441 {
442   struct abt_node *b = a->down[0];
443   if (b != NULL && b->level == a->level)
444     {
445       /* Rotate right. */
446       a->down[0] = b->down[1];
447       b->down[1] = a;
448       *down_link (abt, a) = b;
449
450       if (a->down[0] != NULL)
451         a->down[0]->up = a;
452       b->up = a->up;
453       a->up = b;
454
455       abt->reaugment (a, abt->aux);
456       abt->reaugment (b, abt->aux);
457
458       return b;
459     }
460   else
461     return a;
462 }
463
464 /* Removes a pair of consecutive right "horizontal links" at A,
465    if present.
466    Returns the node that occupies the position previously
467    occupied by A. */
468 static struct abt_node *
469 split (struct abt *abt, struct abt_node *a)
470 {
471   struct abt_node *b = a->down[1];
472   if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
473     {
474       /* Rotate left. */
475       a->down[1] = b->down[0];
476       b->down[0] = a;
477       *down_link (abt, a) = b;
478
479       if (a->down[1] != NULL)
480         a->down[1]->up = a;
481       b->up = a->up;
482       a->up = b;
483
484       b->level++;
485
486       abt->reaugment (a, abt->aux);
487       abt->reaugment (b, abt->aux);
488
489       return b;
490     }
491   else
492     return a;
493 }