[Pspp-cvs] pspp tests/libpspp/bt-test.c src/libpspp/bt.h s... [simpler-proc]

[Ben Pfaff]

CVSROOT:        /cvsroot/pspp
Module name:    pspp
Branch:         simpler-proc
Changes by:     Ben Pfaff <blp> 07/03/30 16:43:05

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

Log message:
        Add bt_ features wanted by range_set.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/bt-test.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=1.1.2.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/bt.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=1.1.2.2
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/bt.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1.2.1&r2=1.1.2.2

Patches:
Index: tests/libpspp/bt-test.c
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/libpspp/Attic/bt-test.c,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -b -r1.1.2.1 -r1.1.2.2
--- tests/libpspp/bt-test.c     28 Mar 2007 04:58:42 -0000      1.1.2.1
+++ tests/libpspp/bt-test.c     30 Mar 2007 16:43:05 -0000      1.1.2.2
@@ -542,6 +542,59 @@
   free (values);
 }
 
+/* Tests bt_find_ge and bt_find_le. */
+static void
+test_find_ge_le (void) 
+{
+  const int max_elems = 10;
+  struct element *elements;
+  int *values;
+  unsigned int inc_pat;
+
+  elements = xnmalloc (max_elems, sizeof *elements);
+  values = xnmalloc (max_elems, sizeof *values);
+  for (inc_pat = 0; inc_pat < (1u << max_elems); inc_pat++) 
+    {
+      struct bt bt;
+      int elem_cnt = 0;
+      int i;
+
+      /* Insert the values in the pattern into BT. */
+      bt_init (&bt, compare_elements, &aux_data);
+      for (i = 0; i < max_elems; i++)
+        if (inc_pat & (1u << i)) 
+          {
+            values[elem_cnt] = elements[elem_cnt].data = i;
+            check (bt_insert (&bt, &elements[elem_cnt].node) == NULL);
+            elem_cnt++;
+          }
+      check_bt (&bt, values, elem_cnt);
+
+      /* Try find_ge and find_le for each possible element value. */
+      for (i = -1; i <= max_elems; i++) 
+        {
+          struct element tmp;
+          struct bt_node *ge, *le;
+          int j;
+          
+          ge = le = NULL;
+          for (j = 0; j < elem_cnt; j++) 
+            {
+              if (ge == NULL && values[j] >= i)
+                ge = &elements[j].node;
+              if (values[j] <= i)
+                le = &elements[j].node;
+            }
+
+          tmp.data = i;
+          check (bt_find_ge (&bt, &tmp.node) == ge);
+          check (bt_find_le (&bt, &tmp.node) == le);
+        }
+    }
+  free (elements);
+  free (values);
+}
+
 /* Inserts elements into an BT, then moves the nodes around in
    memory. */
 static void
@@ -676,6 +729,7 @@
             "insert and delete in random sequence");
   run_test (test_insert_ordered,
             "insert in ascending order");
+  run_test (test_find_ge_le, "find_ge and find_le");
   run_test (test_moved, "move elements around in memory");
   run_test (test_changed, "change key data in nodes");
   putchar ('\n');

Index: src/libpspp/bt.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/Attic/bt.h,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -b -r1.1.2.1 -r1.1.2.2
--- src/libpspp/bt.h    28 Mar 2007 04:58:42 -0000      1.1.2.1
+++ src/libpspp/bt.h    30 Mar 2007 16:43:05 -0000      1.1.2.2
@@ -61,6 +61,10 @@
 struct bt_node *bt_insert (struct bt *, struct bt_node *);
 void bt_delete (struct bt *, struct bt_node *);
 
+struct bt_node *bt_find (const struct bt *, const struct bt_node *);
+struct bt_node *bt_find_ge (const struct bt *, const struct bt_node *);
+struct bt_node *bt_find_le (const struct bt *, const struct bt_node *);
+
 struct bt_node *bt_first (const struct bt *);
 struct bt_node *bt_last (const struct bt *);
 struct bt_node *bt_find (const struct bt *, const struct bt_node *);

Index: src/libpspp/bt.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/Attic/bt.c,v
retrieving revision 1.1.2.1
retrieving revision 1.1.2.2
diff -u -b -r1.1.2.1 -r1.1.2.2
--- src/libpspp/bt.c    28 Mar 2007 04:58:42 -0000      1.1.2.1
+++ src/libpspp/bt.c    30 Mar 2007 16:43:05 -0000      1.1.2.2
@@ -94,9 +94,7 @@
 /* Inserts the given NODE into BT.
    Returns a null pointer if successful.
    Returns the existing node already in BT equal to NODE, on
-   failure.
-   This function may be used only if BT has a comparison
-   function. */
+   failure. */
 struct bt_node *
 bt_insert (struct bt *bt, struct bt_node *node)
 {
@@ -242,9 +240,7 @@
 }
 
 /* Searches BT for a node equal to TARGET.
-   Returns the node if found, or a null pointer otherwise.
-   This function may be used only if BT has a comparison
-   function. */
+   Returns the node if found, or a null pointer otherwise. */
 struct bt_node *
 bt_find (const struct bt *bt, const struct bt_node *target)
 {
@@ -261,6 +257,67 @@
   return NULL;
 }
 
+/* Searches BT for, and returns, the first node in in-order whose
+   value is greater than or equal to TARGET.  Returns a null
+   pointer if all nodes in BT are less than TARGET.
+
+   Another way to look at the return value is that it is the node
+   that would be returned by "bt_next (BT, TARGET)" if TARGET
+   were inserted in BT (assuming that TARGET would not be a
+   duplicate). */
+struct bt_node *
+bt_find_ge (const struct bt *bt, const struct bt_node *target)
+{
+  const struct bt_node *p = bt->root;
+  const struct bt_node *q = NULL;
+  while (p != NULL) 
+    {
+      int cmp = bt->compare (target, p, bt->aux);
+      if (cmp > 0)
+        p = p->down[1];
+      else 
+        {
+          q = p;
+          if (cmp < 0)
+            p = p->down[0];
+          else
+            break;
+        }
+    }
+  return (struct bt_node *) q;
+}
+
+/* Searches BT for, and returns, the last node in in-order whose
+   value is less than or equal to TARGET, which should not be in
+   BT.  Returns a null pointer if all nodes in BT are greater
+   than TARGET.
+
+   Another way to look at the return value is that it is the node
+   that would be returned by "bt_prev (BT, TARGET)" if TARGET
+   were inserted in BT (assuming that TARGET would not be a
+   duplicate). */
+struct bt_node *
+bt_find_le (const struct bt *bt, const struct bt_node *target)
+{
+  const struct bt_node *p = bt->root;
+  const struct bt_node *q = NULL;
+  while (p != NULL) 
+    {
+      int cmp = bt->compare (target, p, bt->aux);
+      if (cmp < 0)
+        p = p->down[0];
+      else 
+        {
+          q = p;
+          if (cmp > 0)
+            p = p->down[1];
+          else
+            break;
+        }
+    }
+  return (struct bt_node *) q;
+}
+
 /* Returns the node in BT following P in in-order.
    If P is null, returns the minimum node in BT.
    Returns a null pointer if P is the maximum node in BT or if P
@@ -352,10 +409,7 @@
    function for each node.  Instead, move a single node, call
    this function, move another node, and so on.  Alternatively,
    remove all affected nodes from the tree, move them, then
-   re-insert all of them.
-
-   This function may be used only if BT has a comparison
-   function. */
+   re-insert all of them. */
 void
 bt_moved (struct bt *bt, struct bt_node *p)
 {