src/libpspp/tower.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2009 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 /* "Tower" data structure, implemented as an augmented binary
  18    tree.
  19
  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.
  25
  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_.
  33
  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.
  44
  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
  47    of the tower. */
  48
  49 #ifndef LIBPSPP_TOWER_H
  50 #define LIBPSPP_TOWER_H
  51
  52 #include <stdbool.h>
  53 #include <libpspp/abt.h>
  54 #include <libpspp/cast.h>
  55
  56 /* Returns the data structure corresponding to the given NODE,
  57    assuming that NODE is embedded as the given MEMBER name in
  58    data type STRUCT. */
  59 #define tower_data(NODE, STRUCT, MEMBER)                        \
  60         (CHECK_POINTER_HAS_TYPE (NODE, struct tower_node *),    \
  61          UP_CAST (NODE, STRUCT, MEMBER))
  62
  63 /* A node within a tower. */
  64 struct tower_node
  65   {
  66     struct abt_node abt_node;         /* ABT node. */
  67     unsigned long int subtree_size;   /* Node size plus descendants' sizes. */
  68     unsigned long int size;           /* Size. */
  69     unsigned long int subtree_count;  /* Number of descendants, plus 1. */
  70   };
  71
  72 /* Returns the size of a tower node. */
  73 static inline unsigned long
  74 tower_node_get_size (const struct tower_node *node)
  75 {
  76   return node->size;
  77 }
  78
  79 unsigned long int tower_node_get_level (const struct tower_node *);
  80 unsigned long int tower_node_get_index (const struct tower_node *);
  81
  82 /* A tower. */
  83 struct tower
  84   {
  85     struct abt abt;                   /* Tree. */
  86     struct tower_node *cache;         /* Cache node. */
  87     unsigned long int cache_bottom;   /* Height of cache's bottom. */
  88   };
  89
  90 void tower_init (struct tower *);
  91
  92 bool tower_is_empty (const struct tower *);
  93 unsigned long int tower_count (const struct tower *);
  94 unsigned long int tower_height (const struct tower *);
  95
  96 void tower_insert (struct tower *, unsigned long int size,
  97                    struct tower_node *new, struct tower_node *under);
  98 struct tower_node *tower_delete (struct tower *, struct tower_node *);
  99 void tower_resize (struct tower *, struct tower_node *,
 100                    unsigned long int new_size);
 101 void tower_splice (struct tower *dst, struct tower_node *under,
 102                    struct tower *src,
 103                    struct tower_node *first, struct tower_node *last);
 104
 105 struct tower_node *tower_lookup (const struct tower *,
 106                                  unsigned long int level,
 107                                  unsigned long int *node_start);
 108 struct tower_node *tower_get (const struct tower *, unsigned long int index);
 109 struct tower_node *tower_first (const struct tower *);
 110 struct tower_node *tower_last (const struct tower *);
 111 struct tower_node *tower_next (const struct tower *,
 112                                const struct tower_node *);
 113 struct tower_node *tower_prev (const struct tower *,
 114                                const struct tower_node *);
 115
 116 #endif /* libpspp/tower.h */