- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
+ This program is free software: you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
This is the analogy behind this data structure. Each node in
the data structure has a "thickness", which is actually called
This is the analogy behind this data structure. Each node in
the data structure has a "thickness", which is actually called
name. The primary way to look up nodes is by a height from
the bottom of the tower; any height within a node retrieves
that node, not just the distance to the bottom of the node.
You can insert a new node between any two existing nodes, or
at either end, which shifts up the height of all the nodes
above it. You can also delete any node, which shifts down the
name. The primary way to look up nodes is by a height from
the bottom of the tower; any height within a node retrieves
that node, not just the distance to the bottom of the node.
You can insert a new node between any two existing nodes, or
at either end, which shifts up the height of all the nodes
above it. You can also delete any node, which shifts down the
- height of all the nodes above it. */
+ height of all the nodes above it.
+
+ The tower data structure also implements efficient access to
+ nodes by index, i.e. by 0-based count of nodes from the bottom
+ of the tower. */
- unsigned long int subtree_height; /* Node's plus descendants' heights. */
- unsigned long int height; /* Height. */
+ unsigned long int subtree_size; /* Node size plus descendants' sizes. */
+ unsigned long int size; /* Size. */
+ unsigned long int subtree_count; /* Number of descendants, plus 1. */
struct tower_node *new, struct tower_node *under);
struct tower_node *tower_delete (struct tower *, struct tower_node *);
void tower_resize (struct tower *, struct tower_node *,
struct tower_node *new, struct tower_node *under);
struct tower_node *tower_delete (struct tower *, struct tower_node *);
void tower_resize (struct tower *, struct tower_node *,
void tower_splice (struct tower *dst, struct tower_node *under,
struct tower *src,
struct tower_node *first, struct tower_node *last);
void tower_splice (struct tower *dst, struct tower_node *under,
struct tower *src,
struct tower_node *first, struct tower_node *last);
struct tower_node *tower_lookup (const struct tower *,
unsigned long int level,
unsigned long int *node_start);
struct tower_node *tower_lookup (const struct tower *,
unsigned long int level,
unsigned long int *node_start);
struct tower_node *tower_first (const struct tower *);
struct tower_node *tower_last (const struct tower *);
struct tower_node *tower_next (const struct tower *,
struct tower_node *tower_first (const struct tower *);
struct tower_node *tower_last (const struct tower *);
struct tower_node *tower_next (const struct tower *,