Changed all the licence notices in all the files.

[pspp-builds.git] / src / algorithm.c

diff --git a/src/algorithm.c b/src/algorithm.c
index aaa2b8469d77ec8b8e3495b17ec0e917107f1f7b..209b0b0f63cce3e3c256adf8f4ef9293ac0fdd1a 100644 (file)
--- a/src/algorithm.c
+++ b/src/algorithm.c
@@ -14,8 +14,8 @@
 
    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., 59 Temple Place - Suite 330, Boston, MA
-   02111-1307, USA. */
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301, USA. */
 
 /* Copyright (C) 2001 Free Software Foundation, Inc.
   
@@ -32,7 +32,7 @@
 
    You should have received a copy of the GNU General Public License along
    with this library; see the file COPYING.  If not, write to the Free
-   Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+   Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    USA.
 
    As a special exception, you may use this file as part of a free software
@@ -86,23 +86,26 @@
 
    You should have received a copy of the GNU Lesser General Public
    License along with the GNU C Library; if not, write to the Free
-   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
-   02111-1307 USA.  */
+   Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+   02110-1301 USA.  */
 
 #include <config.h>
 #include "algorithm.h"
+#include <gsl/gsl_rng.h>
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
 #include "alloc.h"
-#include "random.h"
-
-/* Some of the assertions in this file are very expensive.  If
-   we're optimizing, don't include them. */
-#if __OPTIMIZE__
-#define NDEBUG
+#include "settings.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 <assert.h>
+#include "error.h"
 \f
 /* Finds an element in ARRAY, which contains COUNT elements of
    SIZE bytes each, using COMPARE for comparisons.  Returns the
@@ -202,7 +205,8 @@ unique (void *array, size_t count, size_t size,
       first += size;
       if (first >= last) 
         {
-          assert (adjacent_find_equal (array, count, size, compare, aux) == NULL);
+          assert (adjacent_find_equal (array, count,
+                                       size, compare, aux) == NULL);
           return count; 
         }
 
@@ -307,7 +311,8 @@ is_partitioned (const void *array, size_t count, size_t size,
 unsigned
 algo_default_random (unsigned max, void *aux UNUSED) 
 {
-  return rng_get_unsigned (pspp_rng ()) % max;
+  unsigned long r_min = gsl_rng_min (get_rng ());
+  return (gsl_rng_get (get_rng ()) - r_min) % max;
 }
 
 /* Randomly reorders ARRAY, which contains COUNT elements of SIZE
@@ -360,6 +365,34 @@ copy_if (const void *array, size_t count, size_t size,
   return nonzero_cnt;
 }
 
+/* Removes N elements starting at IDX from ARRAY, which consists
+   of COUNT elements of SIZE bytes each, by shifting the elements
+   following them, if any, into its position. */
+void
+remove_range (void *array_, size_t count, size_t size,
+              size_t idx, size_t n) 
+{
+  char *array = array_;
+  
+  assert (array != NULL);
+  assert (idx <= count);
+  assert (idx + n <= count);
+
+  if (idx + n < count)
+    memmove (array + idx * size, array + (idx + n) * size,
+             size * (count - idx - n));
+}
+
+/* Removes element IDX from ARRAY, which consists of COUNT
+   elements of SIZE bytes each, by shifting the elements
+   following it, if any, into its position. */
+void
+remove_element (void *array, size_t count, size_t size,
+                size_t idx) 
+{
+  remove_range (array, count, size, idx, 1);
+}
+
 /* A predicate and its auxiliary data. */
 struct pred_aux 
   {
@@ -471,7 +504,7 @@ binary_search (const void *array, size_t count, size_t size,
         }
     }
 
-  assert (find (array, count, size, value, compare, aux) == NULL);
+  expensive_assert (find (array, count, size, value, compare, aux) == NULL);
   return NULL;
 }
 \f
@@ -508,7 +541,10 @@ lexicographical_compare_3way (const void *array1, size_t count1,
    Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
    Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
 
+#ifdef HAVE_ALLOCA_H
 #include <alloca.h>
+#endif
+
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
@@ -825,7 +861,8 @@ push_heap (void *array, size_t count, size_t size,
   unsigned char *first = array;
   size_t i;
   
-  assert (count < 1 || is_heap (array, count - 1, size, compare, aux));
+  expensive_assert (count < 1 || is_heap (array, count - 1,
+                                          size, compare, aux));
   for (i = count; i > 1; i /= 2) 
     {
       unsigned char *parent = first + (i / 2 - 1) * size;
@@ -835,7 +872,7 @@ push_heap (void *array, size_t count, size_t size,
       else
         break; 
     }
-  assert (is_heap (array, count, size, compare, aux));
+  expensive_assert (is_heap (array, count, size, compare, aux));
 }
 
 /* ARRAY contains COUNT elements of SIZE bytes each.  Initially
@@ -886,10 +923,11 @@ pop_heap (void *array, size_t count, size_t size,
 {
   unsigned char *first = array;
 
-  assert (is_heap (array, count, size, compare, aux));
+  expensive_assert (is_heap (array, count, size, compare, aux));
   SWAP (first, first + (count - 1) * size, size);
   heapify (first, count - 1, size, 1, compare, aux);
-  assert (count < 1 || is_heap (array, count - 1, size, compare, aux));
+  expensive_assert (count < 1 || is_heap (array, count - 1,
+                                          size, compare, aux));
 }
 
 /* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
@@ -903,7 +941,7 @@ make_heap (void *array, size_t count, size_t size,
   
   for (idx = count / 2; idx >= 1; idx--)
     heapify (array, count, size, idx, compare, aux);
-  assert (count < 1 || is_heap (array, count, size, compare, aux));
+  expensive_assert (count < 1 || is_heap (array, count, size, compare, aux));
 }
 
 /* ARRAY contains COUNT elements of SIZE bytes each.  Initially
@@ -917,13 +955,13 @@ sort_heap (void *array, size_t count, size_t size,
   unsigned char *first = array;
   size_t idx;
 
-  assert (is_heap (array, count, size, compare, aux));
+  expensive_assert (is_heap (array, count, size, compare, aux));
   for (idx = count; idx >= 2; idx--)
     {
       SWAP (first, first + (idx - 1) * size, size);
       heapify (array, idx - 1, size, 1, compare, aux);
     }
-  assert (is_sorted (array, count, size, compare, aux));
+  expensive_assert (is_sorted (array, count, size, compare, aux));
 }
 
 /* ARRAY contains COUNT elements of SIZE bytes each.  This