(move_range): New function.

[pspp-builds.git] / src / libpspp / array.c

diff --git a/src/libpspp/array.c b/src/libpspp/array.c
index 3d834ff5e4f4a7c0f343fc578d088caf58f437bd..f375f83dfa9851bdb6208d0875d2356031c7501f 100644 (file)
--- a/src/libpspp/array.c
+++ b/src/libpspp/array.c
@@ -1,6 +1,5 @@
 /* PSPP - computes sample statistics.
    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
 /* PSPP - computes sample statistics.
    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.

-   Written by Ben Pfaff <blp@gnu.org>.

 
    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License as
 
    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License as


@@ -91,20 +90,15 @@
 
 #include <config.h>
 #include "array.h"
 
 #include <config.h>
 #include "array.h"

-#include <gsl/gsl_rng.h>

 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
 #include "alloc.h"
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
 #include "alloc.h"

+#include <libpspp/assertion.h>

 
 

-/* Some of the assertions in this file are very expensive.  We
-   don't use them by default. */
-#ifdef EXTRA_CHECKS
-#define expensive_assert(X) assert(X)
-#else
-#define expensive_assert(X) ((void) 0)
-#endif

 #include "message.h"
 #include "message.h"

+
+#include "minmax.h"

 \f
 /* Finds an element in ARRAY, which contains COUNT elements of
    SIZE bytes each, using COMPARE for comparisons.  Returns the
 \f
 /* Finds an element in ARRAY, which contains COUNT elements of
    SIZE bytes each, using COMPARE for comparisons.  Returns the


@@ -114,7 +108,7 @@
 void *
 find (const void *array, size_t count, size_t size,
       const void *target,
 void *
 find (const void *array, size_t count, size_t size,
       const void *target,

-      algo_compare_func *compare, void *aux) 
+      algo_compare_func *compare, const void *aux) 

 {
   const char *element = array;
 
 {
   const char *element = array;
 


@@ -136,7 +130,7 @@ find (const void *array, size_t count, size_t size,
 size_t
 count_equal (const void *array, size_t count, size_t size,
              const void *element,
 size_t
 count_equal (const void *array, size_t count, size_t size,
              const void *element,

-             algo_compare_func *compare, void *aux)
+             algo_compare_func *compare, const void *aux)

 {
   const char *first = array;
   size_t equal_cnt = 0;
 {
   const char *first = array;
   size_t equal_cnt = 0;


@@ -154,24 +148,24 @@ count_equal (const void *array, size_t count, size_t size,
 
 /* Counts and return the number of elements in ARRAY, which
    contains COUNT elements of SIZE bytes each, for which
 
 /* Counts and return the number of elements in ARRAY, which
    contains COUNT elements of SIZE bytes each, for which

-   PREDICATE returns nonzero.  AUX is passed as auxiliary data to
+   PREDICATE returns true.  AUX is passed as auxiliary data to

    PREDICATE. */
 size_t
 count_if (const void *array, size_t count, size_t size,
    PREDICATE. */
 size_t
 count_if (const void *array, size_t count, size_t size,

-          algo_predicate_func *predicate, void *aux) 
+          algo_predicate_func *predicate, const void *aux) 

 {
   const char *first = array;
 {
   const char *first = array;

-  size_t nonzero_cnt = 0;
+  size_t true_cnt = 0;

 
   while (count-- > 0) 
     {
       if (predicate (first, aux) != 0)
 
   while (count-- > 0) 
     {
       if (predicate (first, aux) != 0)

-        nonzero_cnt++;
+        true_cnt++;

       
       first += size;
     }
 
       
       first += size;
     }
 

-  return nonzero_cnt;
+  return true_cnt;

 }
 \f
 /* Byte-wise swap two items of size SIZE. */
 }
 \f
 /* Byte-wise swap two items of size SIZE. */


@@ -193,7 +187,7 @@ count_if (const void *array, size_t count, size_t size,
    arrays only.  Arguments same as for sort() above. */
 size_t
 unique (void *array, size_t count, size_t size,
    arrays only.  Arguments same as for sort() above. */
 size_t
 unique (void *array, size_t count, size_t size,

-        algo_compare_func *compare, void *aux) 
+        algo_compare_func *compare, const void *aux) 

 {
   char *first = array;
   char *last = first + size * count;
 {
   char *first = array;
   char *last = first + size * count;


@@ -223,25 +217,25 @@ unique (void *array, size_t count, size_t size,
 /* Helper function that calls sort(), then unique(). */
 size_t
 sort_unique (void *array, size_t count, size_t size,
 /* Helper function that calls sort(), then unique(). */
 size_t
 sort_unique (void *array, size_t count, size_t size,

-             algo_compare_func *compare, void *aux) 
+             algo_compare_func *compare, const void *aux) 

 {
   sort (array, count, size, compare, aux);
   return unique (array, count, size, compare, aux);
 }
 \f
 /* Reorders ARRAY, which contains COUNT elements of SIZE bytes
 {
   sort (array, count, size, compare, aux);
   return unique (array, count, size, compare, aux);
 }
 \f
 /* Reorders ARRAY, which contains COUNT elements of SIZE bytes

-   each, so that the elements for which PREDICATE returns nonzero
+   each, so that the elements for which PREDICATE returns true

    precede those for which PREDICATE returns zero.  AUX is
    passed to each predicate as auxiliary data.  Returns the
    precede those for which PREDICATE returns zero.  AUX is
    passed to each predicate as auxiliary data.  Returns the

-   number of elements for which PREDICATE returns nonzero.  Not
+   number of elements for which PREDICATE returns true.  Not

    stable. */
 size_t 
 partition (void *array, size_t count, size_t size,
    stable. */
 size_t 
 partition (void *array, size_t count, size_t size,

-           algo_predicate_func *predicate, void *aux) 
+           algo_predicate_func *predicate, const void *aux) 

 {
 {

-  size_t nonzero_cnt = count;
+  size_t true_cnt = count;

   char *first = array;
   char *first = array;

-  char *last = first + nonzero_cnt * size;
+  char *last = first + true_cnt * size;

 
   for (;;)
     {
 
   for (;;)
     {


@@ -256,7 +250,7 @@ partition (void *array, size_t count, size_t size,
 
           first += size; 
         }
 
           first += size; 
         }

-      nonzero_cnt--;
+      true_cnt--;

 
       /* Move LAST backward to point to last element that passes
          PREDICATE. */
 
       /* Move LAST backward to point to last element that passes
          PREDICATE. */


@@ -269,7 +263,7 @@ partition (void *array, size_t count, size_t size,
           else if (predicate (last, aux)) 
             break;
           else
           else if (predicate (last, aux)) 
             break;
           else

-            nonzero_cnt--;
+            true_cnt--;

         }
       
       /* By swapping FIRST and LAST we extend the starting and
         }
       
       /* By swapping FIRST and LAST we extend the starting and


@@ -280,30 +274,30 @@ partition (void *array, size_t count, size_t size,
     }
 
  done:
     }
 
  done:

-  assert (is_partitioned (array, count, size, nonzero_cnt, predicate, aux));
-  return nonzero_cnt; 
+  assert (is_partitioned (array, count, size, true_cnt, predicate, aux));
+  return true_cnt; 

 }
 
 /* Checks whether ARRAY, which contains COUNT elements of SIZE
 }
 
 /* Checks whether ARRAY, which contains COUNT elements of SIZE

-   bytes each, is partitioned such that PREDICATE returns nonzero
-   for the first NONZERO_CNT elements and zero for the remaining
+   bytes each, is partitioned such that PREDICATE returns true
+   for the first TRUE_CNT elements and zero for the remaining

    elements.  AUX is passed as auxiliary data to PREDICATE. */
    elements.  AUX is passed as auxiliary data to PREDICATE. */

-int
+bool

 is_partitioned (const void *array, size_t count, size_t size,
 is_partitioned (const void *array, size_t count, size_t size,

-                size_t nonzero_cnt,
-                algo_predicate_func *predicate, void *aux) 
+                size_t true_cnt,
+                algo_predicate_func *predicate, const void *aux) 

 {
   const char *first = array;
   size_t idx;
 
 {
   const char *first = array;
   size_t idx;
 

-  assert (nonzero_cnt <= count);
-  for (idx = 0; idx < nonzero_cnt; idx++)
+  assert (true_cnt <= count);
+  for (idx = 0; idx < true_cnt; idx++)

     if (predicate (first + idx * size, aux) == 0)
     if (predicate (first + idx * size, aux) == 0)

-      return 0;
-  for (idx = nonzero_cnt; idx < count; idx++)
+      return false;
+  for (idx = true_cnt; idx < count; idx++)

     if (predicate (first + idx * size, aux) != 0)
     if (predicate (first + idx * size, aux) != 0)

-      return 0;
-  return 1;
+      return false;
+  return true;

 }
 \f
 /* Copies the COUNT elements of SIZE bytes each from ARRAY to
 }
 \f
 /* Copies the COUNT elements of SIZE bytes each from ARRAY to


@@ -313,7 +307,7 @@ is_partitioned (const void *array, size_t count, size_t size,
 size_t 
 copy_if (const void *array, size_t count, size_t size,
          void *result,
 size_t 
 copy_if (const void *array, size_t count, size_t size,
          void *result,

-         algo_predicate_func *predicate, void *aux) 
+         algo_predicate_func *predicate, const void *aux) 

 {
   const char *input = array;
   const char *last = input + size * count;
 {
   const char *input = array;
   const char *last = input + size * count;


@@ -366,6 +360,31 @@ remove_element (void *array, size_t count, size_t size,
   remove_range (array, count, size, idx, 1);
 }
 
   remove_range (array, count, size, idx, 1);
 }
 

+/* Makes room for N elements starting at IDX in ARRAY, which
+   initially consists of COUNT elements of SIZE bytes each, by
+   shifting elements IDX...COUNT (exclusive) to the right by N
+   positions. */
+void
+insert_range (void *array_, size_t count, size_t size,
+              size_t idx, size_t n) 
+{
+  char *array = array_;
+
+  assert (idx <= count);
+  memmove (array + (idx + n) * size, array + idx * size, (count - idx) * size);
+}
+
+/* Makes room for a new element at IDX in ARRAY, which initially
+   consists of COUNT elements of SIZE bytes each, by shifting
+   elements IDX...COUNT (exclusive) to the right by one
+   positions. */
+void
+insert_element (void *array, size_t count, size_t size,
+                size_t idx) 
+{
+  insert_range (array, count, size, idx, 1);
+}
+

 /* Moves an element in ARRAY, which consists of COUNT elements of
    SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around
    other elements as needed.  Runs in O(abs(OLD_IDX - NEW_IDX))
 /* Moves an element in ARRAY, which consists of COUNT elements of
    SIZE bytes each, from OLD_IDX to NEW_IDX, shifting around
    other elements as needed.  Runs in O(abs(OLD_IDX - NEW_IDX))


@@ -396,15 +415,45 @@ move_element (void *array_, size_t count, size_t size,
     }
 }
 
     }
 }
 

+/* Moves N elements in ARRAY starting at OLD_IDX, which consists
+   of COUNT elements of SIZE bytes each, so that they now start
+   at NEW_IDX, shifting around other elements as needed. */
+void
+move_range (void *array_, size_t count, size_t size,
+            size_t old_idx, size_t new_idx, size_t n)
+{
+  assert (array_ != NULL || count == 0);
+  assert (n <= count);
+  assert (old_idx + n <= count);
+  assert (new_idx + n <= count);
+  
+  if (old_idx != new_idx && n > 0) 
+    {
+      char *array = array_;
+      char *range = xmalloc (size * n);
+      char *new = array + new_idx * size;
+      char *old = array + old_idx * size;
+
+      memcpy (range, old, size * n);
+      if (new < old)
+        memmove (new + size * n, new, (old_idx - new_idx) * size);
+      else
+        memmove (old, old + size * n, (new_idx - old_idx) * size);
+      memcpy (new, range, size * n);
+
+      free (range);
+    }
+}
+

 /* A predicate and its auxiliary data. */
 struct pred_aux 
   {
     algo_predicate_func *predicate;
 /* A predicate and its auxiliary data. */
 struct pred_aux 
   {
     algo_predicate_func *predicate;

-    void *aux;
+    const void *aux;

   };
 
   };
 

-static int
-not (const void *data, void *pred_aux_) 
+static bool
+not (const void *data, const void *pred_aux_) 

 {
   const struct pred_aux *pred_aux = pred_aux_;
 
 {
   const struct pred_aux *pred_aux = pred_aux_;
 


@@ -418,7 +467,7 @@ not (const void *data, void *pred_aux_)
 size_t
 remove_equal (void *array, size_t count, size_t size,
               void *element,
 size_t
 remove_equal (void *array, size_t count, size_t size,
               void *element,

-              algo_compare_func *compare, void *aux) 
+              algo_compare_func *compare, const void *aux) 

 {
   char *first = array;
   char *last = first + count * size;
 {
   char *first = array;
   char *last = first + count * size;


@@ -464,7 +513,7 @@ remove_equal (void *array, size_t count, size_t size,
 size_t 
 remove_copy_if (const void *array, size_t count, size_t size,
                 void *result,
 size_t 
 remove_copy_if (const void *array, size_t count, size_t size,
                 void *result,

-                algo_predicate_func *predicate, void *aux) 
+                algo_predicate_func *predicate, const void *aux) 

 {
   struct pred_aux pred_aux;
   pred_aux.predicate = predicate;
 {
   struct pred_aux pred_aux;
   pred_aux.predicate = predicate;


@@ -480,7 +529,7 @@ remove_copy_if (const void *array, size_t count, size_t size,
 void *
 binary_search (const void *array, size_t count, size_t size,
                void *value,
 void *
 binary_search (const void *array, size_t count, size_t size,
                void *value,

-               algo_compare_func *compare, void *aux) 
+               algo_compare_func *compare, const void *aux) 

 {
   assert (array != NULL);
   assert (count <= INT_MAX);
 {
   assert (array != NULL);
   assert (count <= INT_MAX);


@@ -520,7 +569,7 @@ int
 lexicographical_compare_3way (const void *array1, size_t count1,
                               const void *array2, size_t count2,
                               size_t size,
 lexicographical_compare_3way (const void *array1, size_t count1,
                               const void *array2, size_t count2,
                               size_t size,

-                              algo_compare_func *compare, void *aux) 
+                              algo_compare_func *compare, const void *aux) 

 {
   const char *first1 = array1;
   const char *first2 = array2;
 {
   const char *first1 = array1;
   const char *first2 = array2;


@@ -595,8 +644,8 @@ typedef struct
       stack size is needed (actually O(1) in this case)!  */
 
 void
       stack size is needed (actually O(1) in this case)!  */
 
 void

-sort (const void *array, size_t count, size_t size,
-      algo_compare_func *compare, void *aux)
+sort (void *array, size_t count, size_t size,
+           algo_compare_func *compare, const void *aux)

 {
   char *const first = array;
   const size_t max_thresh = MAX_THRESH * size;
 {
   char *const first = array;
   const size_t max_thresh = MAX_THRESH * size;


@@ -706,12 +755,10 @@ sort (const void *array, size_t count, size_t size,
      of the array to sort, and END_PTR points at the very last element in
      the array (*not* one beyond it!). */
 
      of the array to sort, and END_PTR points at the very last element in
      the array (*not* one beyond it!). */
 

-#define min(x, y) ((x) < (y) ? (x) : (y))
-

   {
     char *const end_ptr = &first[size * (count - 1)];
     char *tmp_ptr = first;
   {
     char *const end_ptr = &first[size * (count - 1)];
     char *tmp_ptr = first;

-    char *thresh = min(end_ptr, first + max_thresh);
+    char *thresh = MIN (end_ptr, first + max_thresh);

     register char *run_ptr;
 
     /* Find smallest element in first threshold and place it at the
     register char *run_ptr;
 
     /* Find smallest element in first threshold and place it at the


@@ -759,18 +806,18 @@ sort (const void *array, size_t count, size_t size,
 /* Tests whether ARRAY, which contains COUNT elements of SIZE
    bytes each, is sorted in order according to COMPARE.  AUX is
    passed to COMPARE as auxiliary data. */
 /* Tests whether ARRAY, which contains COUNT elements of SIZE
    bytes each, is sorted in order according to COMPARE.  AUX is
    passed to COMPARE as auxiliary data. */

-int
+bool

 is_sorted (const void *array, size_t count, size_t size,
 is_sorted (const void *array, size_t count, size_t size,

-           algo_compare_func *compare, void *aux) 
+           algo_compare_func *compare, const void *aux) 

 {
   const char *first = array;
   size_t idx;
       
   for (idx = 0; idx + 1 < count; idx++)
     if (compare (first + idx * size, first + (idx + 1) * size, aux) > 0)
 {
   const char *first = array;
   size_t idx;
       
   for (idx = 0; idx + 1 < count; idx++)
     if (compare (first + idx * size, first + (idx + 1) * size, aux) > 0)

-      return 0; 
+      return false; 

   
   

-  return 1;
+  return true;

 }
 \f
 /* Computes the generalized set difference, ARRAY1 minus ARRAY2,
 }
 \f
 /* Computes the generalized set difference, ARRAY1 minus ARRAY2,


@@ -785,7 +832,7 @@ size_t set_difference (const void *array1, size_t count1,
                        const void *array2, size_t count2,
                        size_t size,
                        void *result_,
                        const void *array2, size_t count2,
                        size_t size,
                        void *result_,

-                       algo_compare_func *compare, void *aux) 
+                       algo_compare_func *compare, const void *aux) 

 {
   const char *first1 = array1;
   const char *last1 = first1 + count1 * size;
 {
   const char *first1 = array1;
   const char *last1 = first1 + count1 * size;


@@ -832,7 +879,7 @@ size_t set_difference (const void *array1, size_t count1,
    data. */
 void *
 adjacent_find_equal (const void *array, size_t count, size_t size,
    data. */
 void *
 adjacent_find_equal (const void *array, size_t count, size_t size,

-                     algo_compare_func *compare, void *aux) 
+                     algo_compare_func *compare, const void *aux) 

 {
   const char *first = array;
   const char *last = first + count * size;
 {
   const char *first = array;
   const char *last = first + count * size;


@@ -855,7 +902,7 @@ adjacent_find_equal (const void *array, size_t count, size_t size,
    data. */
 void
 push_heap (void *array, size_t count, size_t size,
    data. */
 void
 push_heap (void *array, size_t count, size_t size,

-           algo_compare_func *compare, void *aux) 
+           algo_compare_func *compare, const void *aux) 

 {
   char *first = array;
   size_t i;
 {
   char *first = array;
   size_t i;


@@ -882,7 +929,7 @@ push_heap (void *array, size_t count, size_t size,
 static void
 heapify (void *array, size_t count, size_t size,
          size_t idx,
 static void
 heapify (void *array, size_t count, size_t size,
          size_t idx,

-         algo_compare_func *compare, void *aux) 
+         algo_compare_func *compare, const void *aux) 

 {
   char *first = array;
   
 {
   char *first = array;
   


@@ -918,7 +965,7 @@ heapify (void *array, size_t count, size_t size,
    AUX as auxiliary data. */
 void
 pop_heap (void *array, size_t count, size_t size,
    AUX as auxiliary data. */
 void
 pop_heap (void *array, size_t count, size_t size,

-          algo_compare_func *compare, void *aux) 
+          algo_compare_func *compare, const void *aux) 

 {
   char *first = array;
 
 {
   char *first = array;
 


@@ -934,7 +981,7 @@ pop_heap (void *array, size_t count, size_t size,
    auxiliary data. */
 void
 make_heap (void *array, size_t count, size_t size,
    auxiliary data. */
 void
 make_heap (void *array, size_t count, size_t size,

-           algo_compare_func *compare, void *aux) 
+           algo_compare_func *compare, const void *aux) 

 {
   size_t idx;
   
 {
   size_t idx;
   


@@ -949,7 +996,7 @@ make_heap (void *array, size_t count, size_t size,
    passing AUX as auxiliary data. */
 void
 sort_heap (void *array, size_t count, size_t size,
    passing AUX as auxiliary data. */
 void
 sort_heap (void *array, size_t count, size_t size,

-           algo_compare_func *compare, void *aux) 
+           algo_compare_func *compare, const void *aux) 

 {
   char *first = array;
   size_t idx;
 {
   char *first = array;
   size_t idx;


@@ -964,12 +1011,12 @@ sort_heap (void *array, size_t count, size_t size,
 }
 
 /* ARRAY contains COUNT elements of SIZE bytes each.  This
 }
 
 /* ARRAY contains COUNT elements of SIZE bytes each.  This

-   function tests whether ARRAY is a heap and returns 1 if so, 0
-   otherwise.  Uses COMPARE to compare elements, passing AUX as
-   auxiliary data. */
-int
+   function tests whether ARRAY is a heap and returns true if so, 
+   false otherwise.  Uses COMPARE to compare elements, passing 
+   AUX as auxiliary data. */
+bool

 is_heap (const void *array, size_t count, size_t size,
 is_heap (const void *array, size_t count, size_t size,

-         algo_compare_func *compare, void *aux) 
+         algo_compare_func *compare, const void *aux) 

 {
   const char *first = array;
   size_t child;
 {
   const char *first = array;
   size_t child;


@@ -979,9 +1026,9 @@ is_heap (const void *array, size_t count, size_t size,
       size_t parent = child / 2;
       if (compare (first + (parent - 1) * size,
                    first + (child - 1) * size, aux) < 0)
       size_t parent = child / 2;
       if (compare (first + (parent - 1) * size,
                    first + (child - 1) * size, aux) < 0)

-        return 0;
+        return false;

     }
 
     }
 

-  return 1;
+  return true;

 }
 
 }