src/libpspp/tower.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   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.
   8
   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.
  13
  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
  17    02110-1301, USA. */
  18
  19 #include <config.h>
  20
  21 #include <libpspp/tower.h>
  22
  23 #include <limits.h>
  24
  25 #include <libpspp/assertion.h>
  26 #include <libpspp/compiler.h>
  27
  28 static struct tower_node *abt_to_tower_node (const struct abt_node *);
  29 static struct tower_node *first_node (const struct tower *);
  30 static struct tower_node *last_node (const struct tower *);
  31 static struct tower_node *next_node (const struct tower *,
  32                                      const struct tower_node *);
  33 static struct tower_node *prev_node (const struct tower *,
  34                                      const struct tower_node *);
  35 static unsigned long int get_subtree_height (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 /* Initializes T as an empty tower. */
  42 void
  43 tower_init (struct tower *t)
  44 {
  45   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
  46   t->cache_bottom = ULONG_MAX;
  47 }
  48
  49 /* Returns true if T contains no nodes, false otherwise. */
  50 bool
  51 tower_is_empty (const struct tower *t)
  52 {
  53   return t->abt.root == NULL;
  54 }
  55
  56 /* Returns the total height of tower T. */
  57 unsigned long
  58 tower_height (const struct tower *t)
  59 {
  60   return get_subtree_height (t->abt.root);
  61 }
  62
  63 /* Inserts node NEW with the specified HEIGHT into T just below
  64    node UNDER, or at the top of T if UNDER is a null pointer. */
  65 void
  66 tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
  67               struct tower_node *under)
  68 {
  69   assert (height > 0);
  70   new->height = height;
  71   abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
  72                      &new->abt_node);
  73   t->cache_bottom = ULONG_MAX;
  74 }
  75
  76 /* Deletes NODE from tower T. */
  77 struct tower_node *
  78 tower_delete (struct tower *t, struct tower_node *node)
  79 {
  80   struct tower_node *next = next_node (t, node);
  81   abt_delete (&t->abt, &node->abt_node);
  82   t->cache_bottom = ULONG_MAX;
  83   return next;
  84 }
  85
  86 /* Changes the height of NODE in tower T to NEW_HEIGHT. */
  87 void
  88 tower_resize (struct tower *t, struct tower_node *node,
  89               unsigned long new_height)
  90 {
  91   assert (new_height > 0);
  92   node->height = new_height;
  93   abt_reaugmented (&t->abt, &node->abt_node);
  94   t->cache_bottom = ULONG_MAX;
  95 }
  96
  97 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
  98    and splices them into tower DST just below node UNDER, or at
  99    the top of DST if UNDER is a null pointer.
 100
 101    It might be better to implement an abt_splice function and
 102    turn this into a wrapper, but the asymptotic performance would
 103    be the same. */
 104 void
 105 tower_splice (struct tower *dst, struct tower_node *under,
 106               struct tower *src,
 107               struct tower_node *first, struct tower_node *last)
 108 {
 109   struct tower_node *next;
 110
 111   /* Conceptually, DST == SRC is valid.
 112      Practically, it's more difficult to get it right, and our
 113      client code doesn't need it. */
 114   assert (dst != src);
 115
 116   for (; first != last; first = next)
 117     {
 118       next = tower_delete (src, first);
 119       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
 120                          &first->abt_node);
 121     }
 122   dst->cache_bottom = src->cache_bottom = ULONG_MAX;
 123 }
 124
 125 /* Returns the node at the given HEIGHT from the bottom of tower
 126    T.  HEIGHT must be less than T's height (as returned by
 127    tower_height).  Stores in *NODE_START the height of the bottom
 128    of the returned node, which may be less than HEIGHT if HEIGHT
 129    refers to the middle of a node instead of its bottom. */
 130 struct tower_node *
 131 tower_lookup (const struct tower *t_,
 132               unsigned long height,
 133               unsigned long *node_start)
 134 {
 135   struct tower *t = (struct tower *) t_;
 136   struct abt_node *p;
 137
 138   assert (height < tower_height (t));
 139
 140   if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->height)
 141     {
 142       *node_start = t->cache_bottom;
 143       return t->cache;
 144     }
 145
 146   *node_start = 0;
 147   p = t->abt.root;
 148   for (;;)
 149     {
 150       unsigned long left_height = get_subtree_height (p->down[0]);
 151       if (height < left_height)
 152         {
 153           /* Our goal height must lie within the left subtree. */
 154           p = p->down[0];
 155         }
 156       else
 157         {
 158           /* Our goal height cannot be in the left subtree. */
 159           struct tower_node *node = abt_to_tower_node (p);
 160           unsigned long int node_height = node->height;
 161
 162           height -= left_height;
 163           *node_start += left_height;
 164           if (height < node_height)
 165             {
 166               /* Our goal height is in P. */
 167               t->cache = node;
 168               t->cache_bottom = *node_start;
 169               return node;
 170             }
 171           else
 172             {
 173               /* Our goal height is in the right subtree. */
 174               p = p->down[1];
 175               height -= node_height;
 176               *node_start += node_height;
 177             }
 178         }
 179     }
 180 }
 181
 182 /* Returns the node at height 0 in tower T, or a null pointer if
 183    T is empty. */
 184 struct tower_node *
 185 tower_first (const struct tower *t)
 186 {
 187   return first_node (t);
 188 }
 189
 190 /* Returns the node at the top of tower T, or a null pointer if T
 191    is empty. */
 192 struct tower_node *
 193 tower_last (const struct tower *t)
 194 {
 195   return last_node (t);
 196 }
 197
 198 /* If NODE is nonnull, returns the node just above NODE in tower
 199    T, or a null pointer if NODE is the topmost node in T.
 200    If NODE is null, acts like tower_first. */
 201 struct tower_node *
 202 tower_next (const struct tower *t, const struct tower_node *node)
 203 {
 204   return node != NULL ? next_node (t, node) : first_node (t);
 205 }
 206
 207 /* If NODE is nonnull, returns the node just below NODE in tower
 208    T, or a null pointer if NODE is the bottommost node in T.
 209    If NODE is null, acts like tower_last. */
 210 struct tower_node *
 211 tower_prev (const struct tower *t, const struct tower_node *node)
 212 {
 213   return node != NULL ? prev_node (t, node) : last_node (t);
 214 }
 215 \f
 216 /* Returns the tower node corresponding to the given ABT_NODE. */
 217 static struct tower_node *
 218 abt_to_tower_node (const struct abt_node *abt_node)
 219 {
 220   return abt_data (abt_node, struct tower_node, abt_node);
 221 }
 222
 223 /* Returns the tower node corresponding to the given ABT_NODE. */
 224 static struct tower_node *
 225 abt_to_tower_node_null (const struct abt_node *abt_node)
 226 {
 227   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
 228 }
 229
 230 /* Returns the first node in TOWER. */
 231 static struct tower_node *
 232 first_node (const struct tower *t)
 233 {
 234   return abt_to_tower_node_null (abt_first (&t->abt));
 235 }
 236
 237 /* Returns the first node in TOWER. */
 238 static struct tower_node *
 239 last_node (const struct tower *t)
 240 {
 241   return abt_to_tower_node_null (abt_last (&t->abt));
 242 }
 243
 244 /* Returns the next node in TOWER after NODE. */
 245 static struct tower_node *
 246 next_node (const struct tower *t, const struct tower_node *node)
 247 {
 248   return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
 249 }
 250
 251 /* Returns the previous node in TOWER before NODE. */
 252 static struct tower_node *
 253 prev_node (const struct tower *t, const struct tower_node *node)
 254 {
 255   return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
 256 }
 257
 258 /* Returns the total height of the nodes in the subtree rooted at
 259    P, or 0 if P is null. */
 260 static unsigned long int
 261 get_subtree_height (const struct abt_node *p)
 262 {
 263   return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
 264 }
 265
 266 /* Recalculates the subtree_height of NODE based on its LEFT and
 267    RIGHT children's subtree_heights. */
 268 static void
 269 reaugment_tower_node (struct abt_node *node_,
 270                       const struct abt_node *left,
 271                       const struct abt_node *right,
 272                       const void *aux UNUSED)
 273 {
 274   struct tower_node *node = abt_to_tower_node (node_);
 275   node->subtree_height = node->height;
 276   if (left != NULL)
 277     node->subtree_height += abt_to_tower_node (left)->subtree_height;
 278   if (right != NULL)
 279     node->subtree_height += abt_to_tower_node (right)->subtree_height;
 280 }