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 <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 *next_node (const struct tower *,
  29                                      const struct tower_node *);
  30 static unsigned long int get_subtree_height (const struct abt_node *);
  31 static void reaugment_tower_node (struct abt_node *,
  32                                   const struct abt_node *,
  33                                   const struct abt_node *,
  34                                   const void *aux);
  35
  36 /* Initializes T as an empty tower. */
  37 void
  38 tower_init (struct tower *t)
  39 {
  40   abt_init (&t->abt, NULL, reaugment_tower_node, NULL);
  41 }
  42
  43 /* Returns true if T contains no nodes, false otherwise. */
  44 bool
  45 tower_is_empty (const struct tower *t)
  46 {
  47   return t->abt.root == NULL;
  48 }
  49
  50 /* Returns the total height of tower T. */
  51 unsigned long
  52 tower_height (const struct tower *t)
  53 {
  54   return get_subtree_height (t->abt.root);
  55 }
  56
  57 /* Inserts node NEW with the specified HEIGHT into T just below
  58    node UNDER, or at the top of T if UNDER is a null pointer. */
  59 void
  60 tower_insert (struct tower *t, unsigned long height, struct tower_node *new,
  61               struct tower_node *under)
  62 {
  63   assert (height > 0);
  64   new->height = height;
  65   abt_insert_before (&t->abt, under ? &under->abt_node : NULL,
  66                      &new->abt_node);
  67 }
  68
  69 /* Deletes NODE from tower T. */
  70 struct tower_node *
  71 tower_delete (struct tower *t, struct tower_node *node)
  72 {
  73   struct tower_node *next = next_node (t, node);
  74   abt_delete (&t->abt, &node->abt_node);
  75   return next;
  76 }
  77
  78 /* Changes the height of NODE in tower T to NEW_HEIGHT. */
  79 void
  80 tower_resize (struct tower *t, struct tower_node *node,
  81               unsigned long new_height)
  82 {
  83   assert (new_height > 0);
  84   node->height = new_height;
  85   abt_reaugmented (&t->abt, &node->abt_node);
  86 }
  87
  88 /* Removes nodes FIRST through LAST (exclusive) from tower SRC
  89    and splices them into tower DST just below node UNDER, or at
  90    the top of DST if UNDER is a null pointer.
  91
  92    It might be better to implement an abt_splice function and
  93    turn this into a wrapper, but the asymptotic performance would
  94    be the same. */
  95 void
  96 tower_splice (struct tower *dst, struct tower_node *under,
  97               struct tower *src,
  98               struct tower_node *first, struct tower_node *last)
  99 {
 100   struct tower_node *next;
 101
 102   /* Conceptually, DST == SRC is valid.
 103      Practically, it's more difficult to get it right, and our
 104      client code doesn't need it. */
 105   assert (dst != src);
 106
 107   for (; first != last; first = next)
 108     {
 109       next = tower_delete (src, first);
 110       abt_insert_before (&dst->abt, under ? &under->abt_node : NULL,
 111                          &first->abt_node);
 112     }
 113 }
 114
 115 /* Returns the node at the given HEIGHT from the bottom of tower
 116    T.  HEIGHT must be less than T's height (as returned by
 117    tower_height).  Stores in *NODE_START the height of the bottom
 118    of the returned node, which may be less than HEIGHT if HEIGHT
 119    refers to the middle of a node instead of its bottom. */
 120 struct tower_node *
 121 tower_lookup (const struct tower *t,
 122               unsigned long height,
 123               unsigned long *node_start)
 124 {
 125   struct abt_node *p;
 126
 127   assert (height < tower_height (t));
 128
 129   *node_start = 0;
 130   p = t->abt.root;
 131   for (;;)
 132     {
 133       unsigned long left_height = get_subtree_height (p->down[0]);
 134       if (height < left_height)
 135         {
 136           /* Our goal height must lie within the left subtree. */
 137           p = p->down[0];
 138         }
 139       else
 140         {
 141           /* Our goal height cannot be in the left subtree. */
 142           struct tower_node *node = abt_to_tower_node (p);
 143           unsigned long int node_height = node->height;
 144
 145           height -= left_height;
 146           *node_start += left_height;
 147           if (height < node_height)
 148             {
 149               /* Our goal height is in P. */
 150               return node;
 151             }
 152           else
 153             {
 154               /* Our goal height is in the right subtree. */
 155               p = p->down[1];
 156               height -= node_height;
 157               *node_start += node_height;
 158             }
 159         }
 160     }
 161 }
 162
 163 /* Returns the node at height 0 in tower T, or a null pointer if
 164    T is empty. */
 165 struct tower_node *
 166 tower_first (const struct tower *t)
 167 {
 168   return first_node (t);
 169 }
 170
 171 /* If NODE is nonnull, returns the node just above NODE in tower
 172    T, or a null pointer if NODE is the topmost node in T.
 173    If NODE is null, acts like tower_first. */
 174 struct tower_node *
 175 tower_next (const struct tower *t, const struct tower_node *node)
 176 {
 177   return node != NULL ? next_node (t, node) : first_node (t);
 178 }
 179 \f
 180 /* Returns the tower node corresponding to the given ABT_NODE. */
 181 static struct tower_node *
 182 abt_to_tower_node (const struct abt_node *abt_node)
 183 {
 184   return abt_data (abt_node, struct tower_node, abt_node);
 185 }
 186
 187 /* Returns the first node in TOWER. */
 188 static struct tower_node *
 189 first_node (const struct tower *t)
 190 {
 191   struct abt_node *abt_node = abt_first (&t->abt);
 192   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
 193 }
 194
 195 /* Returns the next node in TOWER after NODE. */
 196 static struct tower_node *
 197 next_node (const struct tower *t, const struct tower_node *node)
 198 {
 199   struct abt_node *abt_node = abt_next (&t->abt, &node->abt_node);
 200   return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
 201 }
 202
 203 /* Returns the total height of the nodes in the subtree rooted at
 204    P, or 0 if P is null. */
 205 static unsigned long int
 206 get_subtree_height (const struct abt_node *p)
 207 {
 208   return p != NULL ? abt_to_tower_node (p)->subtree_height : 0;
 209 }
 210
 211 /* Recalculates the subtree_height of NODE based on its LEFT and
 212    RIGHT children's subtree_heights. */
 213 static void
 214 reaugment_tower_node (struct abt_node *node_,
 215                       const struct abt_node *left,
 216                       const struct abt_node *right,
 217                       const void *aux UNUSED)
 218 {
 219   struct tower_node *node = abt_to_tower_node (node_);
 220   node->subtree_height = node->height;
 221   if (left != NULL)
 222     node->subtree_height += abt_to_tower_node (left)->subtree_height;
 223   if (right != NULL)
 224     node->subtree_height += abt_to_tower_node (right)->subtree_height;
 225 }