src/libpspp/tower.c

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