+
+/* 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
+is_sorted (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned 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 1;
+}
+\f
+/* Computes the generalized set difference, ARRAY1 minus ARRAY2,
+ into RESULT, and returns the number of elements written to
+ RESULT. If a value appears M times in ARRAY1 and N times in
+ ARRAY2, then it will appear max(M - N, 0) in RESULT. ARRAY1
+ and ARRAY2 must be sorted, and RESULT is sorted and stable.
+ ARRAY1 consists of COUNT1 elements, ARRAY2 of COUNT2 elements,
+ each SIZE bytes. AUX is passed to COMPARE as auxiliary
+ data. */
+size_t set_difference (const void *array1, size_t count1,
+ const void *array2, size_t count2,
+ size_t size,
+ void *result_,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first1 = array1;
+ const unsigned char *last1 = first1 + count1 * size;
+ const unsigned char *first2 = array2;
+ const unsigned char *last2 = first2 + count2 * size;
+ unsigned char *result = result_;
+ size_t result_count = 0;
+
+ while (first1 != last1 && first2 != last2)
+ {
+ int cmp = compare (first1, first2, aux);
+ if (cmp < 0)
+ {
+ memcpy (result, first1, size);
+ first1 += size;
+ result += size;
+ result_count++;
+ }
+ else if (cmp > 0)
+ first2 += size;
+ else
+ {
+ first1 += size;
+ first2 += size;
+ }
+ }
+
+ while (first1 != last1)
+ {
+ memcpy (result, first1, size);
+ first1 += size;
+ result += size;
+ result_count++;
+ }
+
+ return result_count;
+}
+\f
+/* Finds the first pair of adjacent equal elements in ARRAY,
+ which has COUNT elements of SIZE bytes. Returns the first
+ element in ARRAY such that COMPARE returns zero when it and
+ its successor element are compared, or a null pointer if no
+ such element exists. AUX is passed to COMPARE as auxiliary
+ data. */
+void *
+adjacent_find_equal (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ const unsigned char *last = first + count * size;
+
+ while (first < last && first + size < last)
+ {
+ if (compare (first, first + size, aux) == 0)
+ return (void *) first;
+ first += size;
+ }
+
+ return NULL;
+}
+\f
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the first COUNT - 1 elements of these form a heap, followed by
+ a single element not part of the heap. This function adds the
+ final element, forming a heap of COUNT elements in ARRAY.
+ Uses COMPARE to compare elements, passing AUX as auxiliary
+ data. */
+void
+push_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ size_t i;
+
+ 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;
+ unsigned char *element = first + (i - 1) * size;
+ if (compare (parent, element, aux) < 0)
+ SWAP (parent, element, size);
+ else
+ break;
+ }
+ expensive_assert (is_heap (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the children of ARRAY[idx - 1] are heaps, but ARRAY[idx - 1]
+ may be smaller than its children. This function fixes that,
+ so that ARRAY[idx - 1] itself is a heap. Uses COMPARE to
+ compare elements, passing AUX as auxiliary data. */
+static void
+heapify (void *array, size_t count, size_t size,
+ size_t idx,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+
+ for (;;)
+ {
+ size_t left = 2 * idx;
+ size_t right = left + 1;
+ size_t largest = idx;
+
+ if (left <= count
+ && compare (first + size * (left - 1),
+ first + size * (idx - 1), aux) > 0)
+ largest = left;
+
+ if (right <= count
+ && compare (first + size * (right - 1),
+ first + size * (largest - 1), aux) > 0)
+ largest = right;
+
+ if (largest == idx)
+ break;
+
+ SWAP (first + size * (idx - 1), first + size * (largest - 1), size);
+ idx = largest;
+ }
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function moves the
+ largest element in the heap to the final position in ARRAY and
+ reforms a heap of the remaining COUNT - 1 elements at the
+ beginning of ARRAY. Uses COMPARE to compare elements, passing
+ AUX as auxiliary data. */
+void
+pop_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+
+ expensive_assert (is_heap (array, count, size, compare, aux));
+ SWAP (first, first + (count - 1) * size, size);
+ heapify (first, count - 1, size, 1, compare, aux);
+ expensive_assert (count < 1 || is_heap (array, count - 1,
+ size, compare, aux));
+}
+
+/* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
+ a heap. Uses COMPARE to compare elements, passing AUX as
+ auxiliary data. */
+void
+make_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ size_t idx;
+
+ for (idx = count / 2; idx >= 1; idx--)
+ heapify (array, count, size, idx, compare, aux);
+ expensive_assert (count < 1 || is_heap (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function turns the heap
+ into a fully sorted array. Uses COMPARE to compare elements,
+ passing AUX as auxiliary data. */
+void
+sort_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ size_t idx;
+
+ 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);
+ }
+ expensive_assert (is_sorted (array, count, size, compare, aux));
+}
+
+/* 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
+is_heap (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ size_t child;
+
+ for (child = 2; child <= count; child++)
+ {
+ size_t parent = child / 2;
+ if (compare (first + (parent - 1) * size,
+ first + (child - 1) * size, aux) < 0)
+ return 0;
+ }
+
+ return 1;
+}
+