Add heap data structure to src/libpspp, and a test to tests/libpspp.
authorBen Pfaff <blp@gnu.org>
Wed, 10 Jan 2007 14:50:16 +0000 (14:50 +0000)
committerBen Pfaff <blp@gnu.org>
Wed, 10 Jan 2007 14:50:16 +0000 (14:50 +0000)
Thanks to John Darrington for review.

src/libpspp/ChangeLog
src/libpspp/automake.mk
src/libpspp/heap.c [new file with mode: 0644]
src/libpspp/heap.h [new file with mode: 0644]
tests/ChangeLog
tests/automake.mk
tests/libpspp/heap-test.c [new file with mode: 0644]

index 3412d669f209c1f2a9e888fd6edc9669dbb9e4c4..ecdad8745e474412efa01b95103c1b1a195f46f5 100644 (file)
@@ -1,3 +1,11 @@
+Wed Jan 10 06:49:38 2007  Ben Pfaff  <blp@gnu.org>
+
+       * automake.mk: Add heap.c, heap.h to sources.
+
+       * heap.c: New file.
+
+       * heap.h: New file.
+
 Sun Dec 10 13:54:03 2006  Ben Pfaff  <blp@gnu.org>
 
        * str.c (ss_tokenize): Skip the first delimiter character
index 512d59fa4a4eb72c1a73f743eb777d9d3827b8a1..942a72f30b08767426727a0ad7ce874864e919c2 100644 (file)
@@ -23,6 +23,8 @@ src_libpspp_libpspp_a_SOURCES = \
        src/libpspp/getl.c \
        src/libpspp/hash.c \
        src/libpspp/hash.h \
+       src/libpspp/heap.c \
+       src/libpspp/heap.h \
        src/libpspp/i18n.c \
        src/libpspp/i18n.h \
        src/libpspp/integer-format.c \
diff --git a/src/libpspp/heap.c b/src/libpspp/heap.c
new file mode 100644 (file)
index 0000000..d262d04
--- /dev/null
@@ -0,0 +1,283 @@
+/* PSPP - computes sample statistics.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA. */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <libpspp/heap.h>
+#include <libpspp/pool.h>
+#include <libpspp/assertion.h>
+
+#include "xalloc.h"
+
+/* A heap. */
+struct heap 
+  {
+    /* Comparison function and auxiliary data. */
+    heap_compare_func *compare;
+    const void *aux;
+
+    /* Contents. */
+    struct heap_node **nodes;   /* Element 0 unused, 1...CNT are the heap. */
+    size_t cnt;                 /* Number of elements in heap. */
+    size_t cap;                 /* Max CNT without allocating more memory. */
+  };
+
+static inline void set_node (struct heap *, size_t idx, struct heap_node *);
+static inline bool less (const struct heap *, size_t a, size_t b);
+static bool UNUSED is_heap (const struct heap *);
+static inline void propagate_down (struct heap *, size_t idx);
+static inline bool propagate_up (struct heap *, size_t idx);
+
+/* Creates and return a new min-heap.  COMPARE is used as
+   comparison function and passed AUX as auxiliary data.
+
+   To obtain a max-heap, negate the return value of the
+   comparison function. */
+struct heap *
+heap_create (heap_compare_func *compare, const void *aux) 
+{
+  struct heap *h = xmalloc (sizeof *h);
+  h->compare = compare;
+  h->aux = aux;
+  h->nodes = NULL;
+  h->cap = 0;
+  h->cnt = 0;
+  return h;
+}
+
+/* Destroys H (callback for pool). */
+static void
+destroy_callback (void *h) 
+{
+  heap_destroy (h);
+}
+
+/* Creates and return a new min-heap and registers for its
+   destruction with POOL.  COMPARE is used as comparison function
+   and passed AUX as auxiliary data.
+
+   To obtain a max-heap, negate the return value of the
+   comparison function. */
+struct heap *
+heap_create_pool (struct pool *pool,
+                  heap_compare_func *compare, const void *aux) 
+{
+  struct heap *h = heap_create (compare, aux);
+  pool_register (pool, destroy_callback, h);
+  return h;
+}
+
+/* Destroys heap H. */
+void
+heap_destroy (struct heap *h) 
+{
+  if (h != NULL) 
+    {
+      free (h->nodes);
+      free (h);
+    }
+}
+
+/* Returns true if H is empty, false if it contains at least one
+   element. */
+bool
+heap_is_empty (const struct heap *h) 
+{
+  return h->cnt == 0;
+}
+
+/* Returns the number of elements in H. */
+size_t
+heap_count (const struct heap *h) 
+{
+  return h->cnt;
+}
+
+/* Heap nodes may be moved around in memory as necessary, e.g. as
+   the result of an realloc operation on a block that contains a
+   heap node.  Once this is done, call this function passing the
+   NODE that was moved and its heap H before attempting any other
+   operation on H. */
+void
+heap_moved (struct heap *h, struct heap_node *node) 
+{
+  assert (node->idx <= h->cnt);
+  h->nodes[node->idx] = node;
+}
+
+/* Returns the node with the minimum value in H, which must not
+   be empty. */
+struct heap_node *
+heap_minimum (const struct heap *h) 
+{
+  assert (!heap_is_empty (h));
+  return h->nodes[1];
+}
+
+/* Inserts the given NODE into H. */
+void
+heap_insert (struct heap *h, struct heap_node *node)
+{
+  if (h->cnt >= h->cap) 
+    {
+      h->cap = 2 * (h->cap + 8);
+      h->nodes = xnrealloc (h->nodes, h->cap + 1, sizeof *h->nodes);
+    }
+
+  h->cnt++;
+  set_node (h, h->cnt, node);
+  propagate_up (h, h->cnt);
+
+  expensive_assert (is_heap (h));
+}
+
+/* Deletes the given NODE from H. */
+void
+heap_delete (struct heap *h, struct heap_node *node)
+{
+  assert (node->idx <= h->cnt);
+  assert (h->nodes[node->idx] == node);
+
+  if (node->idx < h->cnt) 
+    {
+      set_node (h, node->idx, h->nodes[h->cnt--]);
+      heap_changed (h, h->nodes[node->idx]);
+    }
+  else 
+    h->cnt--;
+}
+
+/* After client code changes the value represented by a heap
+   node, it must use this function to update the heap structure.
+   It is also safe (but not useful) to call this function if
+   NODE's value has not changed.
+
+   It is not safe to update more than one node's value in the
+   heap, then to call this function for each node.  Instead,
+   update a single node's value, call this function, update
+   another node's value, and so on.  Alternatively, remove all
+   the nodes from the heap, update their values, then re-insert
+   all of them. */
+void
+heap_changed (struct heap *h, struct heap_node *node) 
+{
+  assert (node->idx <= h->cnt);
+  assert (h->nodes[node->idx] == node);
+
+  if (!propagate_up (h, node->idx))
+    propagate_down (h, node->idx);
+
+  expensive_assert (is_heap (h));
+}
+\f
+static inline size_t lesser_node (const struct heap *, size_t a, size_t b);
+static inline void swap_nodes (struct heap *, size_t a, size_t b);
+
+/* Sets h->nodes[IDX] and updates NODE's 'idx' field
+   accordingly. */
+static void
+set_node (struct heap *h, size_t idx, struct heap_node *node) 
+{
+  h->nodes[idx] = node;
+  h->nodes[idx]->idx = idx;
+}
+
+/* Moves the node with the given IDX down the heap as necessary
+   to restore the heap property. */
+static void
+propagate_down (struct heap *h, size_t idx) 
+{
+  for (;;) 
+    {
+      size_t least;
+      least = lesser_node (h, idx, 2 * idx);
+      least = lesser_node (h, least, 2 * idx + 1);
+      if (least == idx)
+        break;
+
+      swap_nodes (h, least, idx);
+      idx = least;
+    }
+}
+
+/* Moves the node with the given IDX up the heap as necessary
+   to restore the heap property.  Returns true if the node was
+   moved, false otherwise.*/
+static bool
+propagate_up (struct heap *h, size_t idx) 
+{
+  bool moved = false;
+  for (; idx > 1 && less (h, idx, idx / 2); idx /= 2) 
+    {
+      swap_nodes (h, idx, idx / 2);
+      moved = true; 
+    }
+  return moved;
+}
+
+/* Returns true if, in H, the node with index A has value less
+   than the node with index B.  */
+static bool
+less (const struct heap *h, size_t a, size_t b) 
+{
+  return h->compare (h->nodes[a], h->nodes[b], h->aux) < 0;
+}
+
+/* Returns A or B according to which is the index of the node
+   with the lesser value.  B is allowed to be out of the range of
+   valid node indexes, in which case A is returned. */
+static size_t
+lesser_node (const struct heap *h, size_t a, size_t b) 
+{
+  assert (a <= h->cnt);
+  return b > h->cnt || less (h, a, b) ? a : b;
+}
+
+/* Swaps, in H, the nodes with indexes A and B. */
+static void
+swap_nodes (struct heap *h, size_t a, size_t b) 
+{
+  struct heap_node *t;
+  
+  assert (a <= h->cnt);
+  assert (b <= h->cnt);
+
+  t = h->nodes[a];
+  set_node (h, a, h->nodes[b]);
+  set_node (h, b, t);
+}
+
+/* Returns true if H is a valid heap,
+   false otherwise. */
+static bool UNUSED
+is_heap (const struct heap *h) 
+{
+  size_t i;
+  
+  for (i = 2; i <= h->cnt; i++) 
+    if (less (h, i, i / 2)) 
+      return false;
+
+  for (i = 1; i <= h->cnt; i++)
+    if (h->nodes[i]->idx != i)
+      return false;
+
+  return true;
+}
diff --git a/src/libpspp/heap.h b/src/libpspp/heap.h
new file mode 100644 (file)
index 0000000..70401c9
--- /dev/null
@@ -0,0 +1,109 @@
+/* PSPP - computes sample statistics.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA. */
+
+/* Embedded priority queue, implemented as a heap.
+
+   Operations have the following cost, where N is the number of
+   nodes already in the heap:
+
+        - Insert: O(lg N).
+
+        - Find minimum: O(1).
+
+        - Delete any node in the heap: O(lg N).
+
+        - Change value of an node: O(lg N) in general; O(1) in
+          the typically common case where the node does not
+          change its position relative to other nodes.
+
+        - Search for a node: O(N).  (Not implemented; if you need
+          such a routine, use a different data structure or
+          maintain a separate index.)
+
+   A heap data structure is structured as a packed array.  If an
+   array is a natural data structure for your application, then
+   use the push_heap, pop_heap, make_heap, sort_heap, and is_heap
+   functions declared in libpspp/array.h.  Otherwise, if your
+   data structure is more dynamic, this implementation may be
+   easier to use.
+
+   An embedded heap is represented as `struct heap'.  Each node
+   in the heap, presumably a structure type, must include a
+   `struct heap_node' member.
+
+   Here's an example of a structure type that includes a `struct
+   heap_node':
+
+     struct foo
+       {
+         struct heap_node node;   // Heap node member.
+         int x;                   // Another member.
+       };
+
+   Here's an example of how to find the minimum value in such a
+   heap and delete it:
+
+     struct heap *h = ...;
+     if (!heap_is_empty (h)) 
+       {
+         struct foo *foo = heap_data (heap_minimum (h), struct foo, node);
+         printf ("Minimum is %d.\n", foo->x);
+         heap_delete (h, &foo->node);
+       }
+     else
+       printf ("Heap is empty.\n");
+*/
+
+#ifndef LIBPSPP_HEAP_H
+#define LIBPSPP_HEAP_H 1
+
+#include <stdbool.h>
+#include <stddef.h>
+
+struct pool;
+
+/* Returns the data structure corresponding to the given heap
+   NODE, assuming that NODE is embedded as the given MEMBER name
+   in data type STRUCT. */
+#define heap_data(NODE, STRUCT, MEMBER)                                 \
+        ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+
+/* A node in a heap.  Opaque.
+   One of these structures must be embedded in your heap node. */
+struct heap_node
+  {
+    size_t idx;
+  };
+
+/* Returns negative if A < B, zero if A == B, positive if A > B. */
+typedef int heap_compare_func (const struct heap_node *a,
+                               const struct heap_node *b, const void *aux);
+
+struct heap *heap_create (heap_compare_func *, const void *aux);
+struct heap *heap_create_pool (struct pool *,
+                               heap_compare_func *, const void *aux);
+void heap_destroy (struct heap *);
+bool heap_is_empty (const struct heap *);
+size_t heap_count (const struct heap *);
+void heap_moved (struct heap *, struct heap_node *);
+struct heap_node *heap_minimum (const struct heap *);
+void heap_insert (struct heap *, struct heap_node *);
+void heap_delete (struct heap *, struct heap_node *);
+void heap_changed (struct heap *, struct heap_node *);
+
+#endif /* libpspp/heap.h */
index 238e2c3558d6e26815a3580470f7578fea363685..c6a34d637fa559dc02a583b8696b4c1418b819a4 100644 (file)
@@ -1,3 +1,9 @@
+Wed Jan 10 06:50:01 2007  Ben Pfaff  <blp@gnu.org>
+
+       * automake.mk: Add tests/libpspp/heap-test.
+
+       * test/libpspp/heap-test.c: New test.
+
 Wed Dec 13 21:00:46 2006  Ben Pfaff  <blp@gnu.org>
 
        * command/rank.sh (activity): Use DELETE VAR (which is new)
index 72481b631a4df6fabbdc0ad7380d820ae06beff8..c682bbd2b2e7858cb736aedef5fe54dd504ff75d 100644 (file)
@@ -131,10 +131,14 @@ TESTS = \
        tests/expressions/variables.sh \
        tests/expressions/vectors.sh \
        tests/libpspp/ll-test \
-       tests/libpspp/llx-test
+       tests/libpspp/llx-test \
+       tests/libpspp/heap-test
 
-check_PROGRAMS += tests/libpspp/ll-test tests/libpspp/llx-test \
-       tests/formats/inexactify
+check_PROGRAMS += \
+       tests/libpspp/ll-test \
+       tests/libpspp/llx-test \
+       tests/formats/inexactify \
+       tests/libpspp/heap-test
 
 tests_libpspp_ll_test_SOURCES = \
        src/libpspp/ll.c \
@@ -148,6 +152,15 @@ tests_libpspp_llx_test_SOURCES = \
        src/libpspp/llx.h \
        tests/libpspp/llx-test.c
 
+tests_libpspp_heap_test_SOURCES = \
+       src/libpspp/heap.c \
+       src/libpspp/heap.h \
+       src/libpspp/pool.c \
+       src/libpspp/pool.h \
+       tests/libpspp/heap-test.c
+tests_libpspp_heap_test_LDADD = gl/libgl.la
+tests_libpspp_heap_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+
 tests_formats_inexactify_SOURCES = tests/formats/inexactify.c
 
 EXTRA_DIST += $(TESTS) tests/weighting.data tests/data-list.data tests/list.data \
diff --git a/tests/libpspp/heap-test.c b/tests/libpspp/heap-test.c
new file mode 100644 (file)
index 0000000..34ece38
--- /dev/null
@@ -0,0 +1,675 @@
+/* PSPP - computes sample statistics.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2 of the
+   License, or (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA. */
+
+/* This is a test program for the routines defined in heap.c.
+   This test program aims to be as comprehensive as possible.
+   With -DNDEBUG, "gcov -b" should report 100% coverage of lines
+   and branches in heap.c routines, except for the is_heap
+   function, which is not called at all with -DNDEBUG.  (Without
+   -DNDEBUG, branches caused by failed assertions will also not
+   be taken.)  "valgrind --leak-check=yes --show-reachable=yes"
+   should give a clean report, both with and without -DNDEBUG. */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <libpspp/heap.h>
+
+#include <assert.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <libpspp/compiler.h>
+
+#include "xalloc.h"
+\f
+/* Currently running test. */
+static const char *test_name;
+
+/* Exit with a failure code.
+   (Place a breakpoint on this function while debugging.) */
+static void
+check_die (void) 
+{
+  exit (EXIT_FAILURE);   
+}
+
+/* If OK is not true, prints a message about failure on the
+   current source file and the given LINE and terminates. */
+static void
+check_func (bool ok, int line) 
+{
+  if (!ok) 
+    {
+      printf ("Check failed in %s test at %s, line %d\n",
+              test_name, __FILE__, line);
+      check_die ();
+    }
+}
+
+/* Verifies that EXPR evaluates to true.
+   If not, prints a message citing the calling line number and
+   terminates. */
+#define check(EXPR) check_func ((EXPR), __LINE__)
+\f
+/* Node type and support routines. */
+
+/* Test data element. */
+struct element
+  {
+    struct heap_node node;      /* Embedded heap element. */
+    int x;                      /* Primary value. */
+  };
+
+int aux_data;
+
+/* Returns the `struct element' that NODE is embedded within. */
+static struct element *
+heap_node_to_element (const struct heap_node *node)
+{
+  return heap_data (node, struct element, node);
+}
+
+/* Compares the `x' values in A and B and returns a strcmp-type
+   return value.  Verifies that AUX points to aux_data. */
+static int
+compare_elements (const struct heap_node *a_, const struct heap_node *b_,
+                  const void *aux) 
+{
+  const struct element *a = heap_node_to_element (a_);
+  const struct element *b = heap_node_to_element (b_);
+
+  check (aux == &aux_data);
+  return a->x < b->x ? -1 : a->x > b->x;
+}
+
+/* Returns the smallest of the N integers in ARRAY. */
+static int
+min_int (int *array, size_t n) 
+{
+  int min;
+  size_t i;
+
+  min = INT_MAX;
+  for (i = 0; i < n; i++)
+    if (array[i] < min)
+      min = array[i];
+  return min;
+}
+
+/* Swaps *A and *B. */
+static void
+swap (int *a, int *b) 
+{
+  int t = *a;
+  *a = *b;
+  *b = t;
+}
+
+/* Reverses the order of the CNT integers starting at VALUES. */
+static void
+reverse (int *values, size_t cnt) 
+{
+  for (; cnt > 1; cnt -= 2, values++)
+    swap (values, &values[cnt - 1]);
+}
+
+/* Arranges the CNT elements in VALUES into the lexicographically
+   next greater permutation.  Returns true if successful.
+   If VALUES is already the lexicographically greatest
+   permutation of its elements (i.e. ordered from greatest to
+   smallest), arranges them into the lexicographically least
+   permutation (i.e. ordered from smallest to largest) and
+   returns false. */
+static bool
+next_permutation (int *values, size_t cnt)
+{
+  if (cnt > 0)
+    {
+      size_t i = cnt - 1;
+      while (i != 0) 
+        {
+          i--;
+          if (values[i] < values[i + 1])
+            {
+              size_t j;
+              for (j = cnt - 1; values[i] >= values[j]; j--)
+                continue;
+              swap (values + i, values + j);
+              reverse (values + (i + 1), cnt - (i + 1));
+              return true;
+            } 
+        }
+      
+      reverse (values, cnt);
+    }
+  
+  return false;
+}
+
+/* Returns N!. */
+static unsigned
+factorial (unsigned n) 
+{
+  unsigned value = 1;
+  while (n > 1)
+    value *= n--;
+  return value;
+}
+
+/* Returns the number of permutations of the CNT values in
+   VALUES.  If VALUES contains duplicates, they must be
+   adjacent. */
+static unsigned
+expected_perms (int *values, size_t cnt) 
+{
+  size_t i, j;
+  unsigned perm_cnt;
+  
+  perm_cnt = factorial (cnt);
+  for (i = 0; i < cnt; i = j) 
+    {
+      for (j = i + 1; j < cnt; j++)
+        if (values[i] != values[j])
+          break;
+      perm_cnt /= factorial (j - i);
+    }
+  return perm_cnt;
+}
+
+/* Tests whether PARTS is a K-part integer composition of N.
+   Returns true if so, false otherwise. */
+static bool UNUSED
+is_k_composition (int n, int k, const int parts[]) 
+{
+  int sum;
+  int i;
+
+  sum = 0;
+  for (i = 0; i < k; i++)
+    {
+      if (parts[i] < 1 || parts[i] > n)
+        return false;
+      sum += parts[i];
+    }
+  return sum == n;
+}
+
+/* Advances the K-part integer composition of N stored in PARTS
+   to the next lexicographically greater one.
+   Returns true if successful, false if the composition was
+   already the greatest K-part composition of N (in which case
+   PARTS is unaltered). */
+static bool
+next_k_composition (int n UNUSED, int k, int parts[]) 
+{
+  int x, i;
+
+  assert (is_k_composition (n, k, parts));
+  if (k == 1)
+    return false;
+
+  for (i = k - 1; i > 0; i--)
+    if (parts[i] > 1)
+      break;
+  if (i == 0)
+    return false;
+
+  x = parts[i] - 1;
+  parts[i] = 1;
+  parts[i - 1]++;
+  parts[k - 1] = x;
+
+  assert (is_k_composition (n, k, parts));
+  return true;
+}
+
+/* Advances *K and PARTS to the next integer composition of N.
+   Compositions are ordered from shortest to longest and in
+   lexicographical order within a given length.
+   Before the first call, initialize *K to 0.
+   After each successful call, *K contains the length of the
+   current composition and the *K elements in PARTS contain its
+   parts.
+   Returns true if successful, false if the set of compositions
+   has been exhausted. */
+static bool
+next_composition (int n, int *k, int parts[]) 
+{
+  if (*k >= 1 && next_k_composition (n, *k, parts))
+    return true;
+  else if (*k < n)
+    {
+      int i;
+      for (i = 0; i < *k; i++)
+        parts[i] = 1;
+      parts[i] = n - *k;
+      (*k)++;
+      return true;
+    }
+  else
+    return false;
+}
+\f
+/* Inserts sequences without duplicates into a heap, and then
+   ensures that they appear as the minimum element in the correct
+   order as we delete them.  Exhaustively tests every input
+   permutation up to 'max_elems' elements. */
+static void
+test_insert_no_dups_delete_min (void) 
+{
+  const int max_elems = 8;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      struct heap *h;
+      struct element *elements;
+      int *values;
+      unsigned int permutation_cnt;
+      int i;
+
+      values = xnmalloc (cnt, sizeof *values);
+      elements = xnmalloc (cnt, sizeof *elements);
+      for (i = 0; i < cnt; i++) 
+        values[i] = i;
+
+      h = heap_create (compare_elements, &aux_data);
+      permutation_cnt = 0;
+      while (permutation_cnt == 0 || next_permutation (values, cnt)) 
+        {
+          int i;
+
+          for (i = 0; i < cnt; i++) 
+            elements[i].x = values[i];
+
+          check (heap_is_empty (h));
+          for (i = 0; i < cnt; i++) 
+            {
+              heap_insert (h, &elements[i].node);
+              check (heap_node_to_element (heap_minimum (h))->x
+                     == min_int (values, i + 1));
+              check (heap_count (h) == i + 1);
+            }
+
+          for (i = 0; i < cnt; i++)
+            {
+              check (heap_node_to_element (heap_minimum (h))->x == i);
+              heap_delete (h, heap_minimum (h));
+            }
+          check (heap_is_empty (h));
+          permutation_cnt++;
+        }
+      check (permutation_cnt == factorial (cnt));
+      heap_destroy (h);
+      free (values);
+      free (elements);
+    }
+}
+
+/* Inserts sequences with duplicates into a heap, and then
+   ensures that they appear as the minimum element in the correct
+   order as we delete them.  Exhaustively tests every input
+   permutation up to 'max_elems' elements.
+
+   See Usenet article <87mz4utika.fsf@blp.benpfaff.org> for
+   details of the algorithm used here. */
+static void
+test_insert_with_dups_delete_min (void) 
+{
+  const int max_elems = 7;
+  int cnt;
+
+  for (cnt = 1; cnt <= max_elems; cnt++) 
+    {
+      unsigned int composition_cnt;
+      int *dups;
+      int unique_cnt;
+      int *values;
+      int *sorted_values;
+      struct element *elements;
+      int n = 0;
+      
+      dups = xnmalloc (cnt, sizeof *dups);
+      values = xnmalloc (cnt, sizeof *values);
+      sorted_values = xnmalloc (cnt, sizeof *sorted_values);
+      elements = xnmalloc (cnt, sizeof *elements);
+
+      unique_cnt = 0;
+      composition_cnt = 0;
+      while (next_composition (cnt, &unique_cnt, dups)) 
+        {
+          struct heap *h;
+          int i, j, k;
+          unsigned int permutation_cnt;
+
+          k = 0;
+          for (i = 0; i < unique_cnt; i++) 
+            for (j = 0; j < dups[i]; j++)
+              {
+                values[k] = i;
+                sorted_values[k] = i;
+                k++;
+              }
+          check (k == cnt);
+
+          h = heap_create (compare_elements, &aux_data);
+          permutation_cnt = 0;
+          while (permutation_cnt == 0 || next_permutation (values, cnt)) 
+            {
+              int min = INT_MAX;
+
+              for (i = 0; i < cnt; i++)
+                elements[i].x = values[i];
+              n++;
+
+              check (heap_is_empty (h));
+              for (i = 0; i < cnt; i++) 
+                {
+                  heap_insert (h, &elements[i].node);
+                  if (values[i] < min)
+                    min = values[i];
+                  check (heap_node_to_element (heap_minimum (h))->x == min);
+                  check (heap_count (h) == i + 1);
+                }
+
+              for (i = 0; i < cnt; i++)
+                {
+                  struct element *min = heap_node_to_element (heap_minimum (h));
+                  check (min->x == sorted_values[i]);
+                  heap_delete (h, heap_minimum (h));
+                }
+              check (heap_is_empty (h));
+              permutation_cnt++;
+            }
+          check (permutation_cnt == expected_perms (values, cnt));
+          heap_destroy (h);
+          
+          composition_cnt++;
+        }
+      check (composition_cnt == 1 << (cnt - 1));
+
+      free (dups);
+      free (values);
+      free (sorted_values);
+      free (elements);
+    }
+}
+
+/* Inserts a sequence without duplicates into a heap, then
+   deletes them in a different order. */
+static void
+test_insert_no_dups_delete_random (void) 
+{
+  const int max_elems = 5;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      struct heap *h;
+      struct element *elements;
+      int *insert, *delete;
+      unsigned int insert_perm_cnt;
+      int i;
+
+      insert = xnmalloc (cnt, sizeof *insert);
+      delete = xnmalloc (cnt, sizeof *delete);
+      elements = xnmalloc (cnt, sizeof *elements);
+      for (i = 0; i < cnt; i++) 
+        {
+          insert[i] = i;
+          delete[i] = i;
+          elements[i].x = i;
+        }
+
+      h = heap_create (compare_elements, &aux_data);
+      insert_perm_cnt = 0;
+      while (insert_perm_cnt == 0 || next_permutation (insert, cnt)) 
+        {
+          unsigned int delete_perm_cnt = 0;
+
+          while (delete_perm_cnt == 0 || next_permutation (delete, cnt)) 
+            {
+              int min;
+              int i;
+
+              check (heap_is_empty (h));
+              min = INT_MAX;
+              for (i = 0; i < cnt; i++) 
+                {
+                  heap_insert (h, &elements[insert[i]].node);
+                  if (insert[i] < min)
+                    min = insert[i];
+                  check (heap_node_to_element (heap_minimum (h))->x == min);
+                  check (heap_count (h) == i + 1);
+                }
+
+              for (i = 0; i < cnt; i++)
+                {
+                  int new_min = min_int (delete + i + 1, cnt - i - 1);
+                  heap_delete (h, &elements[delete[i]].node);
+                  check (heap_count (h) == cnt - i - 1);
+                  if (!heap_is_empty (h))
+                    check (heap_node_to_element (heap_minimum (h))->x == new_min);
+                }
+              check (heap_is_empty (h));
+              delete_perm_cnt++;
+            }
+          check (delete_perm_cnt == factorial (cnt));
+          insert_perm_cnt++; 
+        }
+      check (insert_perm_cnt == factorial (cnt));
+      heap_destroy (h);
+      free (insert);
+      free (delete);
+      free (elements);
+    }
+}
+
+/* Inserts a set of values into a heap, then changes them to a 
+   different random set of values, then removes them in sorted
+   order. */
+static void
+test_inc_dec (void) 
+{
+  const int max_elems = 8;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      struct heap *h;
+      struct element *elements;
+      int *insert, *delete;
+      unsigned int insert_perm_cnt;
+      int i;
+
+      insert = xnmalloc (cnt, sizeof *insert);
+      delete = xnmalloc (cnt, sizeof *delete);
+      elements = xnmalloc (cnt, sizeof *elements);
+      for (i = 0; i < cnt; i++) 
+        insert[i] = i;
+
+      h = heap_create (compare_elements, &aux_data);
+      insert_perm_cnt = 0;
+      while (insert_perm_cnt == 0 || next_permutation (insert, cnt)) 
+        {
+          for (i = 0; i < cnt; i++) 
+            elements[i].x = insert[i];
+
+          check (heap_is_empty (h));
+          for (i = 0; i < cnt; i++) 
+            {
+              int new_min = min_int (insert, i + 1);
+              heap_insert (h, &elements[i].node);
+              check (heap_node_to_element (heap_minimum (h))->x == new_min);
+              check (heap_count (h) == i + 1);
+            }
+
+          for (i = 0; i < cnt; i++)
+            delete[i] = insert[i];
+          for (i = 0; i < cnt; i++) 
+            {
+              int old_value, old_min, new_min;
+              old_min = min_int (delete, cnt);
+              old_value = delete[i];
+              elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
+              new_min = min_int (delete, cnt);
+              heap_changed (h, &elements[i].node);
+              check (heap_node_to_element (heap_minimum (h))->x
+                     == min_int (delete, cnt));
+            }
+
+          for (i = 0; i < cnt; i++)
+            {
+              int new_min = min_int (delete + i + 1, cnt - i - 1);
+              heap_delete (h, &elements[i].node);
+              check (heap_count (h) == cnt - i - 1);
+              if (!heap_is_empty (h))
+                check (heap_node_to_element (heap_minimum (h))->x == new_min);
+            }
+          check (heap_is_empty (h));
+          insert_perm_cnt++; 
+        }
+      check (insert_perm_cnt == factorial (cnt));
+      heap_destroy (h);
+      free (insert);
+      free (delete);
+      free (elements);
+    }
+}
+
+/* Performs a random sequence of insertions and deletions in a
+   heap. */
+static void
+test_random_insert_delete (void) 
+{
+  const int max_elems = 64;
+  const int num_actions = 250000;
+  struct heap *h;
+  int *values;
+  struct element *elements;
+  int cnt;
+  int insert_chance;
+  int i;
+
+  values = xnmalloc (max_elems, sizeof *values);
+  elements = xnmalloc (max_elems, sizeof *elements);
+  cnt = 0;
+  insert_chance = 5;
+
+  h = heap_create (compare_elements, &aux_data);
+  for (i = 0; i < num_actions; i++) 
+    {
+      enum { INSERT, DELETE } action;
+
+      if (cnt == 0) 
+        {
+          action = INSERT;
+          if (insert_chance < 9)
+            insert_chance++; 
+        }
+      else if (cnt == max_elems) 
+        {
+          action = DELETE;
+          if (insert_chance > 0)
+            insert_chance--; 
+        }
+      else
+        action = rand () % 10 < insert_chance ? INSERT : DELETE;
+
+      if (action == INSERT) 
+        {
+          int new_value;
+          int old_min;
+
+          new_value = rand () % max_elems;
+          values[cnt] = new_value;
+          elements[cnt].x = new_value;
+
+          heap_insert (h, &elements[cnt].node);
+
+          old_min = min_int (values, cnt);
+
+          cnt++;
+        }
+      else if (action == DELETE)
+        {
+          int del_idx;
+          int del_value;
+          int old_min, new_min;
+
+          old_min = min_int (values, cnt);
+
+          del_idx = rand () % cnt;
+          del_value = values[del_idx];
+          heap_delete (h, &elements[del_idx].node);
+
+          cnt--;
+          if (del_idx != cnt) 
+            {
+              values[del_idx] = values[cnt];
+              elements[del_idx] = elements[cnt];
+              heap_moved (h, &elements[del_idx].node);
+            }
+
+          new_min = min_int (values, cnt);
+        }
+      else
+        abort ();
+
+      check (heap_count (h) == cnt);
+      check (heap_is_empty (h) == (cnt == 0));
+      if (cnt > 0)
+        check (heap_node_to_element (heap_minimum (h))->x
+               == min_int (values, cnt));
+    }
+  heap_destroy (h);
+  free (elements);
+  free (values);
+}
+\f
+/* Main program. */
+
+/* Runs TEST_FUNCTION and prints a message about NAME. */
+static void
+run_test (void (*test_function) (void), const char *name) 
+{
+  test_name = name;
+  putchar ('.');
+  fflush (stdout);
+  test_function ();
+}
+
+int
+main (void) 
+{
+  run_test (test_insert_no_dups_delete_min,
+            "insert (no dups), delete minimum values");
+  run_test (test_insert_with_dups_delete_min,
+            "insert with dups, delete minimum values");
+  run_test (test_insert_no_dups_delete_random,
+            "insert (no dups), delete in random order");
+  run_test (test_inc_dec, "increase and decrease values");
+  run_test (test_random_insert_delete, "random insertions and deletions");
+  putchar ('\n');
+
+  return 0;
+}