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/>. */
17 /* "Tower" data structure, implemented as an augmented binary
20 Imagine a tall stack of books on a table; actually, call it a
21 "tower" of books because "stack" is already taken. If you're
22 careful enough and strong enough, you can pull individual
23 books out of the stack, as well as insert new books between
24 existing ones or at the bottom or top of the stack.
26 At any given time, you can refer to a book in the tower by
27 measuring the book's height above the tower in some unit,
28 e.g. mm. This isn't necessarily equivalent to the number of
29 books in the tower below the book in question, like an array
30 index, because the books in the stack aren't necessarily all
31 the same thickness: some might be as thin as K&R and others as
32 thick as _Introduction to Algorithms_.
34 This is the analogy behind this data structure. Each node in
35 the data structure has a "thickness", which is actually called
36 the node's "size" because "thickness" is just too awkward a
37 name. The primary way to look up nodes is by a height from
38 the bottom of the tower; any height within a node retrieves
39 that node, not just the distance to the bottom of the node.
40 You can insert a new node between any two existing nodes, or
41 at either end, which shifts up the height of all the nodes
42 above it. You can also delete any node, which shifts down the
43 height of all the nodes above it.
45 The tower data structure also implements efficient access to
46 nodes by index, i.e. by 0-based count of nodes from the bottom
49 #ifndef LIBPSPP_TOWER_H
50 #define LIBPSPP_TOWER_H
53 #include <libpspp/abt.h>
55 /* Returns the data structure corresponding to the given NODE,
56 assuming that NODE is embedded as the given MEMBER name in
58 #define tower_data(NODE, STRUCT, MEMBER) \
59 ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
61 /* A node within a tower. */
64 struct abt_node abt_node; /* ABT node. */
65 unsigned long int subtree_size; /* Node size plus descendants' sizes. */
66 unsigned long int size; /* Size. */
67 unsigned long int subtree_count; /* Number of descendants, plus 1. */
70 /* Returns the size of a tower node. */
71 static inline unsigned long
72 tower_node_get_size (const struct tower_node *node)
77 unsigned long int tower_node_get_level (const struct tower_node *);
78 unsigned long int tower_node_get_index (const struct tower_node *);
83 struct abt abt; /* Tree. */
84 struct tower_node *cache; /* Cache node. */
85 unsigned long int cache_bottom; /* Height of cache's bottom. */
88 void tower_init (struct tower *);
90 bool tower_is_empty (const struct tower *);
91 unsigned long int tower_count (const struct tower *);
92 unsigned long int tower_height (const struct tower *);
94 void tower_insert (struct tower *, unsigned long int size,
95 struct tower_node *new, struct tower_node *under);
96 struct tower_node *tower_delete (struct tower *, struct tower_node *);
97 void tower_resize (struct tower *, struct tower_node *,
98 unsigned long int new_size);
99 void tower_splice (struct tower *dst, struct tower_node *under,
101 struct tower_node *first, struct tower_node *last);
103 struct tower_node *tower_lookup (const struct tower *,
104 unsigned long int level,
105 unsigned long int *node_start);
106 struct tower_node *tower_get (const struct tower *, unsigned long int index);
107 struct tower_node *tower_first (const struct tower *);
108 struct tower_node *tower_last (const struct tower *);
109 struct tower_node *tower_next (const struct tower *,
110 const struct tower_node *);
111 struct tower_node *tower_prev (const struct tower *,
112 const struct tower_node *);
114 #endif /* libpspp/tower.h */