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
19 /* "Tower" data structure, implemented as an augmented binary
22 Imagine a tall stack of books on a table; actually, call it a
23 "tower" of books because "stack" is already taken. If you're
24 careful enough and strong enough, you can pull individual
25 books out of the stack, as well as insert new books between
26 existing ones or at the bottom or top of the stack.
28 At any given time, you can refer to a book in the tower by
29 measuring the book's height above the tower in some unit,
30 e.g. mm. This isn't necessarily equivalent to the number of
31 books in the tower below the book in question, like an array
32 index, because the books in the stack aren't necessarily all
33 the same thickness: some might be as thin as K&R and others as
34 thick as _Introduction to Algorithms_.
36 This is the analogy behind this data structure. Each node in
37 the data structure has a "thickness", which is actually called
38 the node's "height" because "thickness" is just too awkward a
39 name. The primary way to look up nodes is by a height from
40 the bottom of the tower; any height within a node retrieves
41 that node, not just the distance to the bottom of the node.
42 You can insert a new node between any two existing nodes, or
43 at either end, which shifts up the height of all the nodes
44 above it. You can also delete any node, which shifts down the
45 height of all the nodes above it. */
47 #ifndef LIBPSPP_TOWER_H
48 #define LIBPSPP_TOWER_H
51 #include <libpspp/abt.h>
53 /* Returns the data structure corresponding to the given NODE,
54 assuming that NODE is embedded as the given MEMBER name in
56 #define tower_data(NODE, STRUCT, MEMBER) \
57 ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
59 /* A node within a tower. */
62 struct abt_node abt_node; /* ABT node. */
63 unsigned long int subtree_height; /* Node's plus descendants' heights. */
64 unsigned long int height; /* Height. */
67 /* Returns the height of a tower node. */
68 static inline unsigned long
69 tower_node_get_height (const struct tower_node *node)
77 struct abt abt; /* Tree. */
78 struct tower_node *cache; /* Cache node. */
79 unsigned long int cache_bottom; /* Height of cache's bottom. */
82 void tower_init (struct tower *);
84 bool tower_is_empty (const struct tower *);
85 unsigned long int tower_height (const struct tower *);
87 void tower_insert (struct tower *, unsigned long int height,
88 struct tower_node *new, struct tower_node *under);
89 struct tower_node *tower_delete (struct tower *, struct tower_node *);
90 void tower_resize (struct tower *, struct tower_node *,
91 unsigned long int new_height);
92 void tower_splice (struct tower *dst, struct tower_node *under,
94 struct tower_node *first, struct tower_node *last);
96 struct tower_node *tower_lookup (const struct tower *,
97 unsigned long int level,
98 unsigned long int *node_start);
99 struct tower_node *tower_first (const struct tower *);
100 struct tower_node *tower_last (const struct tower *);
101 struct tower_node *tower_next (const struct tower *,
102 const struct tower_node *);
103 struct tower_node *tower_prev (const struct tower *,
104 const struct tower_node *);
106 #endif /* libpspp/tower.h */