src/libpspp/tower.c

   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 #include <config.h>
  18
  19 #include <libpspp/tower.h>
  20
  21 #include <limits.h>
  22
  23 #include <libpspp/assertion.h>
  24 #include <libpspp/cast.h>
  25 #include <libpspp/compiler.h>
  26
  27 static struct tower_node *abt_to_tower_node (const struct abt_node *);
  28 static struct tower_node *first_node (const struct tower *);
  29 static struct tower_node *last_node (const struct tower *);
  30 static struct tower_node *next_node (const struct tower *,
  31                                      const struct tower_node *);
  32 static struct tower_node *prev_node (const struct tower *,
  33                                      const struct tower_node *);
  34 static unsigned long int get_subtree_size (const struct abt_node *);
  35 static unsigned long int get_subtree_count (const struct abt_node *);
  36 static void reaugment_tower_node (struct abt_node *,
  37                                   const struct abt_node *,
  38                                   const struct abt_node *,
  39                                   const void *aux);
  40
  41 /* Returns the height of the bottom of the given tower NODE.
  42
  43    The performance of this function is O(lg n) in the number of
  44    nodes in the tower.  It is often possible to avoid calling
  45    this function, either by taking advantage of the NODE_START
  46    parameter to tower_lookup or by incrementally keeping track of
  47    height while iterating through a tower.  In the former case
  48    the asymptotic performance is no different, since tower_lookup
  49    is also O(lg n), but in the latter case performance improves
  50    from O(lg n) to O(1). */
  51 unsigned long int
  52 tower_node_get_level (const struct tower_node *node)
  53 {
  54   const struct abt_node *p = &node->abt_node;
  55   unsigned long level = get_subtree_size (p->down[0]);
  56   while (p->up != NULL)
  57     {
  58       if (p == p->up->down[1])
  59         level += (get_subtree_size (p->up->down[0])
  60                   + abt_to_tower_node (p->up)->size);
  61       p = p->up;
  62     }
  63   return level;
  64 }
  65
  66 /* Returns the index of the given tower NODE.
  67
  68    The performance of this function is O(lg n) in the number of
  69    nodes in the tower.  It is often possible to avoid calling
  70    this function by keeping track of the index while iterating
  71    through a tower.  Doing so when possible will improve
  72    performance from O(lg n) to O(1). */
  73 unsigned long int
  74 tower_node_get_index (const struct tower_node *node)
  75 {
  76   const struct abt_node *p = &node->abt_node;
  77   unsigned long index = get_subtree_count (p->down[0]);
  78   while (p->up != NULL)
  79     {
  80       if (p == p->up->down[1])
  81         index += get_subtree_count (p->up->down[0]) + 1;
  82       p = p->up;
  83     }
  84   return index;
  85 }
  86
  87 /* Initializes T as an empty tower. */
  88 void
  89 tower_init (struct tower *t)
  90 {
  91   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
  92   t->cache_bottom = ULONG_MAX;
  93 }
  94
  95 /* Returns true if T contains no nodes, false otherwise. */
  96 bool
  97 tower_is_empty (const struct tower *t)
  98 {
  99   return t->abt.root == NULL;
 100 }
 101
 102 /* Returns the number of nodes in tower T. */
 103 unsigned long int
 104 tower_count (const struct tower *t)
 105 {
 106   return get_subtree_count (t->abt.root);
 107 }
 108
 109 /* Returns the total height of tower T. */
 110 unsigned long
 111 tower_height (const struct tower *t)
 112 {
 113   return get_subtree_size (t->abt.root);
 114 }
 115
 116 /* Inserts node NEW with the specified SIZE into T just below
 117    node UNDER, or at the top of T if UNDER is a null pointer. */
 118 void
 119 tower_insert (struct tower *t, unsigned long size, struct tower_node *new,
 120               struct tower_node *under)
 121 {
 122   assert (size > 0);
 123   new->size = size;
 124   abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
 125                      &new->abt_node);
 126   t->cache_bottom = ULONG_MAX;
 127 }
 128
 129 /* Deletes NODE from tower T. */
 130 struct tower_node *
 131 tower_delete (struct tower *t, struct tower_node *node)
 132 {
 133   struct tower_node *next = next_node (t, node);
 134   abt_delete (&t->abt, &node->abt_node);
 135   t->cache_bottom = ULONG_MAX;
 136   return next;
 137 }
 138
 139 /* Changes the size of NODE in tower T to NEW_SIZE. */
 140 void
 141 tower_resize (struct tower *t, struct tower_node *node,
 142               unsigned long new_size)
 143 {
 144   assert (new_size > 0);
 145   node->size = new_size;
 146   abt_reaugmented (&t->abt, &node->abt_node);
 147   t->cache_bottom = ULONG_MAX;
 148 }
 149
 150 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
 151    and splices them into tower DST just below node UNDER, or at
 152    the top of DST if UNDER is a null pointer.
 153
 154    It might be better to implement an abt_splice function and
 155    turn this into a wrapper, but the asymptotic performance would
 156    be the same. */
 157 void
 158 tower_splice (struct tower *dst, struct tower_node *under,
 159               struct tower *src,
 160               struct tower_node *first, struct tower_node *last)
 161 {
 162   struct tower_node *next;
 163
 164   /* Conceptually, DST == SRC is valid.
 165      Practically, it's more difficult to get it right, and our
 166      client code doesn't need it. */
 167   assert (dst != src);
 168
 169   for (; first != last; first = next)
 170     {
 171       next = tower_delete (src, first);
 172       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
 173                          &first->abt_node);
 174     }
 175   dst->cache_bottom = src->cache_bottom = ULONG_MAX;
 176 }
 177
 178 /* Returns the node at the given HEIGHT from the bottom of tower
 179    T.  HEIGHT must be less than T's height (as returned by
 180    tower_height).  Stores in *NODE_START the height of the bottom
 181    of the returned node, which may be less than HEIGHT if HEIGHT
 182    refers to the middle of a node instead of its bottom. */
 183 struct tower_node *
 184 tower_lookup (const struct tower *t_,
 185               unsigned long height,
 186               unsigned long *node_start)
 187 {
 188   struct tower *t = CONST_CAST (struct tower *, t_);
 189   struct abt_node *p;
 190
 191   assert (height < tower_height (t));
 192
 193   if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->size)
 194     {
 195       *node_start = t->cache_bottom;
 196       return t->cache;
 197     }
 198
 199   *node_start = 0;
 200   p = t->abt.root;
 201   for (;;)
 202     {
 203       unsigned long left_size = get_subtree_size (p->down[0]);
 204       if (height < left_size)
 205         {
 206           /* Our goal height must lie within the left subtree. */
 207           p = p->down[0];
 208         }
 209       else
 210         {
 211           /* Our goal height cannot be in the left subtree. */
 212           struct tower_node *node = abt_to_tower_node (p);
 213           unsigned long int node_size = node->size;
 214
 215           height -= left_size;
 216           *node_start += left_size;
 217           if (height < node_size)
 218             {
 219               /* Our goal height is in P. */
 220               t->cache = node;
 221               t->cache_bottom = *node_start;
 222               return node;
 223             }
 224           else
 225             {
 226               /* Our goal height is in the right subtree. */
 227               p = p->down[1];
 228               height -= node_size;
 229               *node_start += node_size;
 230             }
 231         }
 232     }
 233 }
 234
 235 /* Returns the node with the given 0-based INDEX, which must be
 236    less than the number of nodes in T (as returned by
 237    tower_count). */
 238 struct tower_node *
 239 tower_get (const struct tower *t_, unsigned long int index)
 240 {
 241   struct tower *t = CONST_CAST (struct tower *, t_);
 242   struct abt_node *p;
 243
 244   assert (index < tower_count (t));
 245
 246   p = t->abt.root;
 247   for (;;)
 248     {
 249       unsigned long left_count = get_subtree_count (p->down[0]);
 250       if (index < left_count)
 251         p = p->down[0];
 252       else if (index == left_count)
 253         return abt_to_tower_node (p);
 254       else
 255         {
 256           p = p->down[1];
 257           index -= left_count + 1;
 258         }
 259     }
 260 }
 261
 262 /* Returns the node at height 0 in tower T, or a null pointer if
 263    T is empty. */
 264 struct tower_node *
 265 tower_first (const struct tower *t)
 266 {
 267   return first_node (t);
 268 }
 269
 270 /* Returns the node at the top of tower T, or a null pointer if T
 271    is empty. */
 272 struct tower_node *
 273 tower_last (const struct tower *t)
 274 {
 275   return last_node (t);
 276 }
 277
 278 /* If NODE is nonnull, returns the node just above NODE in tower
 279    T, or a null pointer if NODE is the topmost node in T.
 280    If NODE is null, acts like tower_first. */
 281 struct tower_node *
 282 tower_next (const struct tower *t, const struct tower_node *node)
 283 {
 284   return node != NULL ? next_node (t, node) : first_node (t);
 285 }
 286
 287 /* If NODE is nonnull, returns the node just below NODE in tower
 288    T, or a null pointer if NODE is the bottommost node in T.
 289    If NODE is null, acts like tower_last. */
 290 struct tower_node *
 291 tower_prev (const struct tower *t, const struct tower_node *node)
 292 {
 293   return node != NULL ? prev_node (t, node) : last_node (t);
 294 }
 295 \f
 296 /* Returns the tower node corresponding to the given ABT_NODE. */
 297 static struct tower_node *
 298 abt_to_tower_node (const struct abt_node *abt_node)
 299 {
 300   return abt_data (abt_node, struct tower_node, abt_node);
 301 }
 302
 303 /* Returns the tower node corresponding to the given ABT_NODE. */
 304 static struct tower_node *
 305 abt_to_tower_node_null (const struct abt_node *abt_node)
 306 {
 307   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
 308 }
 309
 310 /* Returns the first node in TOWER. */
 311 static struct tower_node *
 312 first_node (const struct tower *t)
 313 {
 314   return abt_to_tower_node_null (abt_first (&t->abt));
 315 }
 316
 317 /* Returns the first node in TOWER. */
 318 static struct tower_node *
 319 last_node (const struct tower *t)
 320 {
 321   return abt_to_tower_node_null (abt_last (&t->abt));
 322 }
 323
 324 /* Returns the next node in TOWER after NODE. */
 325 static struct tower_node *
 326 next_node (const struct tower *t, const struct tower_node *node)
 327 {
 328   return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
 329 }
 330
 331 /* Returns the previous node in TOWER before NODE. */
 332 static struct tower_node *
 333 prev_node (const struct tower *t, const struct tower_node *node)
 334 {
 335   return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
 336 }
 337
 338 /* Returns the total size of the nodes in the subtree rooted at
 339    P, or 0 if P is null. */
 340 static unsigned long int
 341 get_subtree_size (const struct abt_node *p)
 342 {
 343   return p != NULL ? abt_to_tower_node (p)->subtree_size : 0;
 344 }
 345
 346 /* Returns the total number of nodes in the subtree rooted at P,
 347    or 0 if P is null. */
 348 static unsigned long int
 349 get_subtree_count (const struct abt_node *p)
 350 {
 351   return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
 352 }
 353
 354 /* Recalculates the subtree_size of NODE based on its LEFT and
 355    RIGHT children's subtree_sizes. */
 356 static void
 357 reaugment_tower_node (struct abt_node *node_,
 358                       const struct abt_node *left,
 359                       const struct abt_node *right,
 360                       const void *aux UNUSED)
 361 {
 362   struct tower_node *node = abt_to_tower_node (node_);
 363   node->subtree_size = node->size;
 364   node->subtree_count = 1;
 365   if (left != NULL)
 366     {
 367       struct tower_node *left_node = abt_to_tower_node (left);
 368       node->subtree_size += left_node->subtree_size;
 369       node->subtree_count += left_node->subtree_count;
 370     }
 371   if (right != NULL)
 372     {
 373       struct tower_node *right_node = abt_to_tower_node (right);
 374       node->subtree_size += right_node->subtree_size;
 375       node->subtree_count += right_node->subtree_count;
 376     }
 377 }