[Pspp-cvs] pspp src/libpspp/ChangeLog src/libpspp/tower.c ...

[Ben Pfaff]

CVSROOT:        /cvsroot/pspp
Module name:    pspp
Changes by:     Ben Pfaff <blp> 07/06/04 01:36:06

Modified files:
        src/libpspp    : ChangeLog tower.c tower.h 
        tests          : ChangeLog 
        tests/libpspp  : tower-test.c 

Log message:
        Add ability for reverse iteration to tower code, and corresponding
        tests.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ChangeLog?cvsroot=pspp&r1=1.69&r2=1.70
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/tower.c?cvsroot=pspp&r1=1.3&r2=1.4
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/tower.h?cvsroot=pspp&r1=1.3&r2=1.4
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/ChangeLog?cvsroot=pspp&r1=1.88&r2=1.89
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/tower-test.c?cvsroot=pspp&r1=1.2&r2=1.3

Patches:
Index: src/libpspp/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/ChangeLog,v
retrieving revision 1.69
retrieving revision 1.70
diff -u -b -r1.69 -r1.70
--- src/libpspp/ChangeLog       4 Jun 2007 01:29:08 -0000       1.69
+++ src/libpspp/ChangeLog       4 Jun 2007 01:36:06 -0000       1.70
@@ -1,5 +1,17 @@
 2007-06-03  Ben Pfaff  <address@hidden>
 
+       Add ability for reverse iteration to tower code.
+       
+       * tower.c (tower_last): New function.
+       (tower_prev): New function.
+       (abt_to_tower_node): New function.
+       (first_node): Use abt_to_tower_node.
+       (last_node): New function.
+       (next_ndoe): Use abt_to_tower_node.
+       (prev_node): New function.
+
+2007-06-03  Ben Pfaff  <address@hidden>
+
        * tower.c: Cache repeated lookups of a single tower element.  This
        turns such lookups into O(1) operations without harming the big-O
        of other operations.

Index: src/libpspp/tower.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/tower.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -b -r1.3 -r1.4
--- src/libpspp/tower.c 4 Jun 2007 01:29:08 -0000       1.3
+++ src/libpspp/tower.c 4 Jun 2007 01:36:06 -0000       1.4
@@ -27,8 +27,11 @@
 
 static struct tower_node *abt_to_tower_node (const struct abt_node *);
 static struct tower_node *first_node (const struct tower *);
+static struct tower_node *last_node (const struct tower *);
 static struct tower_node *next_node (const struct tower *,
                                      const struct tower_node *);
+static struct tower_node *prev_node (const struct tower *,
+                                     const struct tower_node *);
 static unsigned long int get_subtree_height (const struct abt_node *);
 static void reaugment_tower_node (struct abt_node *,
                                   const struct abt_node *,
@@ -184,6 +187,14 @@
   return first_node (t);
 }
 
+/* Returns the node at the top of tower T, or a null pointer if T
+   is empty. */
+struct tower_node *
+tower_last (const struct tower *t) 
+{
+  return last_node (t);
+}
+
 /* If NODE is nonnull, returns the node just above NODE in tower
    T, or a null pointer if NODE is the topmost node in T.
    If NODE is null, acts like tower_first. */
@@ -193,6 +204,15 @@
   return node != NULL ? next_node (t, node) : first_node (t);
 }
 
+/* If NODE is nonnull, returns the node just below NODE in tower
+   T, or a null pointer if NODE is the bottommost node in T.
+   If NODE is null, acts like tower_last. */
+struct tower_node *
+tower_prev (const struct tower *t, const struct tower_node *node) 
+{
+  return node != NULL ? prev_node (t, node) : last_node (t);
+}
+
 /* Returns the tower node corresponding to the given ABT_NODE. */
 static struct tower_node *
 abt_to_tower_node (const struct abt_node *abt_node) 
@@ -200,20 +220,39 @@
   return abt_data (abt_node, struct tower_node, abt_node);
 }
 
+/* Returns the tower node corresponding to the given ABT_NODE. */
+static struct tower_node *
+abt_to_tower_node_null (const struct abt_node *abt_node) 
+{
+  return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+}
+
 /* Returns the first node in TOWER. */
 static struct tower_node *
 first_node (const struct tower *t) 
 {
-  struct abt_node *abt_node = abt_first (&t->abt);
-  return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+  return abt_to_tower_node_null (abt_first (&t->abt));
+}
+
+/* Returns the first node in TOWER. */
+static struct tower_node *
+last_node (const struct tower *t) 
+{
+  return abt_to_tower_node_null (abt_last (&t->abt));
 }
 
 /* Returns the next node in TOWER after NODE. */
 static struct tower_node *
 next_node (const struct tower *t, const struct tower_node *node) 
 {
-  struct abt_node *abt_node = abt_next (&t->abt, &node->abt_node);
-  return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+  return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
+}
+
+/* Returns the previous node in TOWER before NODE. */
+static struct tower_node *
+prev_node (const struct tower *t, const struct tower_node *node) 
+{
+  return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
 }
 
 /* Returns the total height of the nodes in the subtree rooted at

Index: src/libpspp/tower.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/tower.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -b -r1.3 -r1.4
--- src/libpspp/tower.h 4 Jun 2007 01:29:08 -0000       1.3
+++ src/libpspp/tower.h 4 Jun 2007 01:36:06 -0000       1.4
@@ -97,7 +97,10 @@
                                  unsigned long int level,
                                  unsigned long int *node_start);
 struct tower_node *tower_first (const struct tower *);
+struct tower_node *tower_last (const struct tower *);
 struct tower_node *tower_next (const struct tower *,
                                const struct tower_node *);
+struct tower_node *tower_prev (const struct tower *,
+                               const struct tower_node *);
 
 #endif /* libpspp/tower.h */

Index: tests/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/ChangeLog,v
retrieving revision 1.88
retrieving revision 1.89
diff -u -b -r1.88 -r1.89
--- tests/ChangeLog     4 Jun 2007 01:22:48 -0000       1.88
+++ tests/ChangeLog     4 Jun 2007 01:36:06 -0000       1.89
@@ -1,5 +1,7 @@
 2007-06-03  Ben Pfaff  <address@hidden>
 
+       * tests/tower-test.c: Also test tower_last, tower_prev functions.
+
        * tests/range-set-test.c: Also test the range_set_clone function.
 
 2007-05-06  Ben Pfaff  <address@hidden>

Index: tests/libpspp/tower-test.c
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/libpspp/tower-test.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -b -r1.2 -r1.3
--- tests/libpspp/tower-test.c  3 Apr 2007 22:55:07 -0000       1.2
+++ tests/libpspp/tower-test.c  4 Jun 2007 01:36:06 -0000       1.3
@@ -32,6 +32,7 @@
 
 #include <assert.h>
 #include <limits.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -289,6 +290,15 @@
       check (tower_node_to_block (node)->x == blocks[i].x);
     }
   check (i == block_cnt);
+
+  for (node = tower_last (t), i = block_cnt - 1;
+       node != NULL;
+       node = tower_prev (t, node), i--) 
+    {
+      check (tower_node_get_height (node) == blocks[i].height);
+      check (tower_node_to_block (node)->x == blocks[i].x);
+    }
+  check (i == SIZE_MAX);
 }
 
 /* Tests inserting all possible sets of block heights into a