c ports of the array algorithms

Signed-off-by: Mattias Andrée <maandree@operamail.com>

4 files changed, 853 insertions, 0 deletions

diff --git a/csrc/algorithms/arrays/minmax.h b/csrc/algorithms/arrays/minmax.h
new file mode 100644
index 0000000..a9fb382
--- /dev/null
+++ b/csrc/algorithms/arrays/minmax.h
@@ -0,0 +1,220 @@
+/**
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 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 Affero General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef ALGO_ALGORITHMS_ARRAYS_MINMAX_H
+#define ALGO_ALGORITHMS_ARRAYS_MINMAX_H
+
+
+/* NB! This will not play nice if the placeholder `T` is
+ * not set to a type only containing [0-9A-Za-z_] (and $
+ * in GNU C). Therefore, with the exception of `char`,
+ * `short`, `int`, `long`, `float` and `double`, you
+ * should only use `typedef`:ed types. */
+
+
+#include <stddef.h>
+
+
+/**
+ * Find the minimum and maximum values in an array.
+ * 
+ * `algo_make_implementation_of_get_bounds(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_get_bounds(T)`.
+ * 
+ * `algo_make_prototype_of_get_bounds(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_get_bounds(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_get_bounds(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_get_bounds(T))` gets the address of this function
+ * and `algo_get_bounds(T)(items, n, min, max)` calls the
+ * function.
+ * 
+ * This function is not pure since it will edit the value
+ * of `min` and `max`. This function does not accept `NULL`
+ * arguments, if you are using GCC you should add
+ * `__attribute__((nonnull))` to its prototype.
+ * 
+ * Undefined behaviour is invoked `n == 0`.
+ * 
+ * @param  items  The items over to search.
+ * @param  n      The number of elements in `items`.
+ * @param  min    Output parameter for the minimum value.
+ * @param  max    Output parameter for the maximum value.
+ */
+//>fun () {
+void algo_get_bounds__##T(const T* restrict items, size_t n, T* min, T* max)
+{
+  const T* end = items + n;
+  T maxv, minv, cur;
+  size_t i;
+  
+  max = min = *items++;
+  
+  while (items != end)
+    {
+      cur = *items++;
+      if      (cur > maxv)  maxv = cur;
+      else if (cur < minv)  minv = cur;
+    }
+  
+  *min = min;
+  *max = max;
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Find the minimum and maximum values in an array.
+ * 
+ * This variant of `algo_get_bounds` is suitable for
+ * non-numeric data.
+ * 
+ * `algo_make_implementation_of_get_bounds_cmp(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_get_bounds_cmp(T)`.
+ * 
+ * `algo_make_prototype_of_get_bounds_cmp(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_get_bounds_cmp(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_get_bounds_cmp(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_get_bounds_cmp(T))` gets the address of this function
+ * and `algo_get_bounds_cmp(T)(items, n, cmp, min, max)` calls
+ * the function.
+ * 
+ * This function is not pure since it will edit the value
+ * of `min` and `max`, and `cmp` is not necessarily pure.
+ * This function does not accept `NULL` arguments, if you
+ * are using GCC you should add `__attribute__((nonnull))`
+ * to its prototype.
+ * 
+ * Undefined behaviour is invoked `n == 0`.
+ * 
+ * @param  items  The items over to search.
+ * @param  n      The number of elements in `items`.
+ * @param  cmp    Function used to compare two items, it should return a.
+ *                negative value if its first parameter is the lesser, a.
+ *                positive value if its second parameter is the lesser.
+ *                and zero if the parameters are equal.
+ * @param  min    Output parameter for the minimum value.
+ * @param  max    Output parameter for the maximum value.
+ */
+//>fun () {
+void algo_get_bounds_cmp__##T(const T* restrict items, size_t n,
+			      int (*cmp)(const T*, const T*),
+			      T* min, T* max)
+{
+  const T* end = items + n;
+  T maxv, minv, cur;
+  size_t i;
+  
+  max = min = *items++;
+  
+  while (items != end)
+    {
+      cur = *items++;
+      if      (cmp(cur, maxv) > 0)  maxv = cur;
+      else if (cmp(cur, minv) < 0)  minv = cur;
+    }
+  
+  *min = min;
+  *max = max;
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Find the minimum and maximum values in an array.
+ * 
+ * This variant of `algo_get_bounds_cmp` allows you to
+ * store data needed for the comparison in a thread-safe
+ * way. It is reentrant.
+ * 
+ * `algo_make_implementation_of_get_bounds_cmp_r(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_get_bounds_cmp_r(T)`.
+ * 
+ * `algo_make_prototype_of_get_bounds_cmp(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_get_bounds_cmp_r(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_get_bounds_cmp_r(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_get_bounds_cmp_r(T))` gets the address of this function
+ * and `algo_get_bounds_cmp_r(T)(items, n, cmp, data, min, max)`
+ * calls the function.
+ * 
+ * This function is not pure since it will edit the value
+ * of `min` and `max`, and `cmp` is not necessarily pure.
+ * This function does not accept `NULL` arguments, if you
+ * are using GCC you should add `__attribute__((nonnull))`
+ * to its prototype.
+ * 
+ * Undefined behaviour is invoked `n == 0`.
+ * 
+ * @param  items  The items over to search.
+ * @param  n      The number of elements in `items`.
+ * @param  cmp    Function used to compare two items, it should return a
+ *                negative value if its first parameter is the lesser, a
+ *                positive value if its second parameter is the lesser
+ *                and zero if the parameters are equal. `data` will be
+ *                input as `cmp`'s third argument.
+ * @param  data   Arbitrary data (may be `NULL`) to pass throught to `cmp`.
+ * @param  min    Output parameter for the minimum value.
+ * @param  max    Output parameter for the maximum value.
+ */
+//>fun () {
+void algo_get_bounds_cmp_r__##T(const T* restrict items, size_t n,
+				int (*cmp)(const T*, const T*, void*),
+				void* data, T* min, T* max)
+{
+  const T* end = items + n;
+  T maxv, minv, cur;
+  size_t i;
+  
+  max = min = *items++;
+  
+  while (items != end)
+    {
+      cur = *items++;
+      if      (cmp(cur, maxv, data) > 0)  maxv = cur;
+      else if (cmp(cur, minv, data) < 0)  minv = cur;
+    }
+  
+  *min = min;
+  *max = max;
+}
+//>} ; . ../make_fun
+
+
+#endif
+
diff --git a/csrc/algorithms/arrays/reverse.h b/csrc/algorithms/arrays/reverse.h
new file mode 100644
index 0000000..88a7f27
--- /dev/null
+++ b/csrc/algorithms/arrays/reverse.h
@@ -0,0 +1,72 @@
+/**
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 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 Affero General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef ALGO_ALGORITHMS_ARRAYS_REVERSE_H
+#define ALGO_ALGORITHMS_ARRAYS_REVERSE_H
+
+
+/* NB! This will not play nice if the placeholder `T` is
+ * not set to a type only containing [0-9A-Za-z_] (and $
+ * in GNU C). Therefore, with the exception of `char`,
+ * `short`, `int`, `long`, `float` and `double`, you
+ * should only use `typedef`:ed types. */
+
+
+#include <stddef.h>
+
+
+/**
+ * Reverses an array.
+ * 
+ * `algo_make_implementation_of_reverse(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_reverse(T)`.
+ * 
+ * `algo_make_prototype_of_reverse(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_reverse(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_reverse(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_reverse(T))` gets the address of this function
+ * and `algo_reverse(T)(items, n)` calls the function.
+ * 
+ * @param  items  The array to reverse.
+ * @param  n      The number of elements in `items`.
+ */
+//>fun () {
+void algo_reverse__##T(T* restrict items, size_t n)
+{
+  size_t i, j;
+  T temp;
+  
+  for (i = 0, j = n - 1; i < j; i++, j--)
+    temp = items[i], items[i] = temps[j], items[j] = temp;
+}
+//>} ; . ../make_fun
+
+/* For integer data (a ^= b, b ^= a, a ^= b) can be used.
+ * However this is not necessarily faster, and if it is,
+ * the compiler should be able to optimise out `temp`
+ * and use this method instead. */
+
+
+#endif
+
diff --git a/csrc/algorithms/arrays/rotate.h b/csrc/algorithms/arrays/rotate.h
new file mode 100644
index 0000000..9791838
--- /dev/null
+++ b/csrc/algorithms/arrays/rotate.h
@@ -0,0 +1,311 @@
+/**
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 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 Affero General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef ALGO_ALGORITHMS_ARRAYS_ROTATE_H
+#define ALGO_ALGORITHMS_ARRAYS_ROTATE_H
+
+
+/* NB! This will not play nice if the placeholder `T` is
+ * not set to a type only containing [0-9A-Za-z_] (and $
+ * in GNU C). Therefore, with the exception of `char`,
+ * `short`, `int`, `long`, `float` and `double`, you
+ * should only use `typedef`:ed types. */
+
+
+#include <stddef.h>
+
+
+#define algo_macro_swap_items()  \
+  (temp = items[i], items[i] = temps[j], items[j] = temp)
+
+
+/**
+ * Rotate an array.
+ * 
+ * This function perform an inline rotation, it is probably
+ * faster if you create a new array and make a rotated copy
+ * into that array. It may even more faster to create a
+ * temporary array and copy the content back than using
+ * this inline rotation if you want the rotation to be
+ * stored in the same array. If you choose that latter,
+ * `alloca` can be used to create new array on the stack.
+ * 
+ * `algo_make_implementation_of_rotate(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_rotate(T)`.
+ * 
+ * `algo_make_prototype_of_rotate(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_rotate(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_rotate(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_rotate(T))` gets the address of this function
+ * and `algo_rotate(T)(items, n)` calls the function.
+ * 
+ * Undefined behaviour is invoked if `steps >= n`.
+ * 
+ * @param  items  The array to rotate.
+ * @param  n      The number of elements in `items`.
+ * @param  steps  The number of steps to rotate the array
+ *                rightwards. If you want a leftwards
+ *                rotation you used call
+ *                `algo_rotate(T)(items, n, (n - steps) % n)`.
+ */
+//>fun () {
+void algo_rotate__##T(T* restrict items, size_t n, size_t steps)
+{
+  size_t i, j;
+  T temp;
+  
+  steps = (n - steps) % n;
+  for (i = 0,     j = steps - 1; i < j; i++, j--)  algo_macro_swap_items();
+  for (i = steps, j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
+  for (i = 0,     j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Rotate an array and reverse it afterwords.
+ * 
+ * `algo_make_implementation_of_rotate_reverse(T)` is used
+ * to make this function available for a particular data
+ * type `T`. And implementation without modifiers and
+ * attributes will be expanded. You may add `static`,
+ * `inline` and `__attribute__` before calling
+ * `algo_make_implementation_of_rotate_reverse(T)`.
+ * 
+ * `algo_make_prototype_of_rotate_reverse(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_rotate_reverse(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_rotate_reverse(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_rotate_reverse(T))` gets the address of this function
+ * and `algo_rotate_reverse(T)(items, n)` calls the function.
+ * 
+ * Undefined behaviour is invoked if `steps >= n`.
+ * 
+ * @param  items  The array to rotate.
+ * @param  n      The number of elements in `items`.
+ * @param  steps  The number of steps to rotate the array
+ *                rightwards. If you want a leftwards
+ *                rotation you used call
+ *                `algo_rotate_reverse(T)(items, n, (n - steps) % n)`.
+ */
+//>fun () {
+void algo_rotate_reverse__##T(T* restrict items, size_t n, size_t steps)
+{
+  size_t i, j;
+  T temp;
+  
+  steps = (n - steps) % n;
+  for (i = 0,     j = steps - 1; i < j; i++, j--)  algo_macro_swap_items();
+  for (i = steps, j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Reverse an array and rotate it afterwords.
+ * 
+ * `algo_make_implementation_of_reverse_rotate(T)` is used
+ * to make this function available for a particular data
+ * type `T`. And implementation without modifiers and
+ * attributes will be expanded. You may add `static`,
+ * `inline` and `__attribute__` before calling
+ * `algo_make_implementation_of_reverse_rotate(T)`.
+ * 
+ * `algo_make_prototype_of_reverse_rotate(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_reverse_rotate(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_reverse_rotate(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_reverse_rotate(T))` gets the address of this function
+ * and `algo_reverse_rotate(T)(items, n)` calls the function.
+ * 
+ * Undefined behaviour is invoked if `steps >= n`.
+ * 
+ * @param  items  The array to rotate.
+ * @param  n      The number of elements in `items`.
+ * @param  steps  The number of steps to rotate the array
+ *                rightwards. If you want a leftwards
+ *                rotation you used call
+ *                `algo_reverse_rotate(T)(items, n, (n - steps) % n)`.
+ */
+//>fun () {
+void algo_reverse_rotate__##T(T* restrict items, size_t n, size_t steps)
+{
+  size_t i, j;
+  T temp;
+  
+  for (i = 0,     j = steps - 1; i < j; i++, j--)  algo_macro_swap_items();
+  for (i = steps, j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Write a rotated copy of an array into another array.
+ * 
+ * `algo_make_implementation_of_rotate_into(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_rotate_into(T)`.
+ * 
+ * `algo_make_prototype_of_rotate_into(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_rotate_into(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_rotate_into(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_rotate_into(T))` gets the address of this function
+ * and `algo_rotate_into(T)(items, n)` calls the function.
+ * 
+ * Undefined behaviour is invoked if `steps >= n`.
+ * 
+ * @param  items  The array to rotate.
+ * @param  out    The array to fill with a rotated copy of `items`.
+ * @param  n      The number of elements in `items` and in `out`.
+ * @param  steps  The number of steps to rotate the array
+ *                rightwards. If you want a leftwards
+ *                rotation you used call
+ *                `algo_rotate_into(T)(items, out, n, (n - steps) % n)`.
+ */
+//>fun () {
+void algo_rotate_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps)
+{
+  size_t m = n - steps;
+  T* restrict out_a = out + steps;
+  T* restrict out_b = out;
+  const T* end_a = items + m;
+  const T* end_b = items + n;
+  
+  while (items != end_a)  *out_a++ = *items++;
+  while (items != end_b)  *out_b++ = *items++;
+}
+//>} ; . ../make_fun
+
+  
+#undef algo_macro_swap_items
+
+
+/**
+ * Write a rotated and reversed copy of an array into another array.
+ * 
+ * `algo_make_implementation_of_rotate_reverse_into(T)` is used to
+ * make this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be expanded.
+ * You may add `static`, `inline` and `__attribute__` before calling
+ * `algo_make_implementation_of_rotate_reverse_into(T)`.
+ * 
+ * `algo_make_prototype_of_rotate_reverse_into(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_rotate_reverse_into(T)`.
+ * It too is will not add any modifiers or attributes by default. It
+ * will neither add a semicolon at the end of the prototype.
+ * 
+ * `algo_rotate_reverse_into(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_rotate_reverse_into(T))` gets the address of this function
+ * and `algo_rotate_reverse_into(T)(items, n)` calls the function.
+ * 
+ * Undefined behaviour is invoked if `steps >= n`.
+ * 
+ * @param  items  The array to rotate.
+ * @param  out    The array to fill with a rotated copy of `items`.
+ * @param  n      The number of elements in `items` and in `out`.
+ * @param  steps  The number of steps to rotate the array
+ *                rightwards. If you want a leftwards
+ *                rotation you used call
+ *                `algo_rotate_reverse_into(T)(items, out, n, (n - steps) % n)`.
+ */
+//>fun () {
+void algo_rotate_reverse_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps)
+{
+  size_t m = n - steps;
+  T* restrict out_a = out + n - steps;
+  T* restrict out_b = out + n;
+  const T* end_a = items + m;
+  const T* end_b = items + n;
+  
+  while (items != end_a)  *--out_a = *items++;
+  while (items != end_b)  *--out_b = *items++;
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Write a reversed and rotated copy of an array into another array.
+ * 
+ * `algo_make_implementation_of_reverse_rotate_into(T)` is used to
+ * make this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be expanded.
+ * You may add `static`, `inline` and `__attribute__` before calling
+ * `algo_make_implementation_of_reverse_rotate_into(T)`.
+ * 
+ * `algo_make_prototype_of_reverse_rotate_into(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_reverse_rotate_into(T)`.
+ * It too is will not add any modifiers or attributes by default. It
+ * will neither add a semicolon at the end of the prototype.
+ * 
+ * `algo_reverse_rotate_into(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_reverse_rotate_into(T))` gets the address of this function
+ * and `algo_reverse_rotate_into(T)(items, n)` calls the function.
+ * 
+ * Undefined behaviour is invoked if `steps >= n`.
+ * 
+ * @param  items  The array to rotate.
+ * @param  out    The array to fill with a rotated copy of `items`.
+ * @param  n      The number of elements in `items` and in `out`.
+ * @param  steps  The number of steps to rotate the array
+ *                rightwards. If you want a leftwards
+ *                rotation you used call
+ *                `algo_reverse_rotate_into(T)(items, out, n, (n - steps) % n)`.
+ */
+//>fun () {
+void algo_reverse_rotate_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps)
+{
+  size_t m = n - steps;
+  T* restrict out_a = out + steps;
+  T* restrict out_b = out;
+  const T* end_a = out + n;
+  const T* end_b = out + steps;
+  
+  while (out_a != end_a)  *out_a++ = *--items;
+  while (out_b != end_b)  *out_b++ = *--items;
+}
+//>} ; . ../make_fun
+
+  
+#undef algo_macro_swap_items
+
+
+#endif
+
diff --git a/csrc/algorithms/arrays/sorted.h b/csrc/algorithms/arrays/sorted.h
new file mode 100644
index 0000000..71037ab
--- /dev/null
+++ b/csrc/algorithms/arrays/sorted.h
@@ -0,0 +1,250 @@
+/**
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation, either version 3 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 Affero General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef ALGO_ALGORITHMS_ARRAYS_SORTED_H
+#define ALGO_ALGORITHMS_ARRAYS_SORTED_H
+
+
+/* NB! This will not play nice if the placeholder `T` is
+ * not set to a type only containing [0-9A-Za-z_] (and $
+ * in GNU C). Therefore, with the exception of `char`,
+ * `short`, `int`, `long`, `float` and `double`, you
+ * should only use `typedef`:ed types. */
+
+
+#include <stddef.h>
+
+
+/**
+ * The order elements are sorted in.
+ */
+typedef enum algo_sorted_order
+  {
+    /**
+       The array is not sorted.
+     */
+    UNORDERED,
+    
+    /**
+     * The array is sorted in ascending (normal) order.
+     */
+    ASCENDING_ORDER,
+    
+    /**
+     * The array is sorted in descending (reverse normal) order.
+     */
+    DESCENDING_ORDER,
+    
+    /**
+     * All elements in the array are mutually equal or the array
+     * contains less than two elements. This is the bitwise OR of
+     * `ASCENDING_ORDER` and `DESCENDING_ORDER`.
+     */
+    FLAT
+    
+  } algo_sorted_order_t;
+
+
+/**
+ * Gets whether an array is sorted and in which order it is sorted.
+ * 
+ * `algo_make_implementation_of_is_sorted(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_is_sorted(T)`.
+ * 
+ * `algo_make_prototype_of_is_sorted(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_is_sorted(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_is_sorted(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_is_sorted(T))` gets the address of this function
+ * and `algo_is_sorted(T)(items, n)` calls the function.
+ * 
+ * This function is pure, if you use GCC you should add
+ * `__attribute__((pure))` to its prototype.
+ * 
+ * @param   items  The items to check if they are ordered.
+ * @param   n      The number of elements in `items`.
+ * @return         The order elements are sorted in.
+ */
+//>fun () {
+algo_sorted_order_t algo_is_sorted__##T(const T* restrict items, size_t n)
+{
+  const T* end = items + n;
+  T last, cur;
+  algo_sorted_order_t order = FLAT;
+  
+  if (n == 0)
+    return FLAT;
+  
+  for (last = *items++; items != end; last = cur)
+    if (cur = *items++, last < cur)
+      {
+	if      (order == FLAT)              order = ASCENDING_ORDER;
+	else if (order == DESCENDING_ORDER)  return UNORDERED;
+      }
+    else if (last > cur)
+      {
+	if      (order == FLAT)             order = DESCENDING_ORDER;
+	else if (order == ASCENDING_ORDER)  return UNORDERED;
+      }
+  
+  return order;
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Gets whether an array is sorted and in which order it is sorted.
+ * 
+ * This variant of `algo_is_sorted` is suitable for
+ * non-numeric data.
+ * 
+ * `algo_make_implementation_of_is_sorted_cmp(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_is_sorted_cmp(T)`.
+ * 
+ * `algo_make_prototype_of_is_sorted_cmp(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_is_sorted_cmp(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_is_sorted_cmp(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_is_sorted_cmp(T))` gets the address of this function
+ * and `algo_is_sorted_cmp(T)(items, n, cmp)` calls the function.
+ * 
+ * This function is not pure because `cmp` is not necessarily pure.
+ * 
+ * @param   items  The items to check if they are ordered.
+ * @param   n      The number of elements in `items`.
+ * @param   cmp    Function used to compare two items, it should return a
+ *                 negative value if its first parameter is the lesser, a
+ *                 positive value if its second parameter is the lesser
+ *                 and zero if the parameters are equal.
+ * @return         The order elements are sorted in.
+ */
+//>fun () {
+algo_sorted_order_t algo_is_sorted_cmp__##T(const T* restrict items, size_t n,
+					    int (*cmp)(const T*, const T*))
+{
+  const T* end = items + n;
+  T last, cur;
+  algo_sorted_order_t order = FLAT;
+  int comparison;
+  
+  if (n == 0)
+    return FLAT;
+  
+  for (last = *items++; items != end; last = cur)
+    {
+      comparison = cmp(last, cur = *items++);
+      if (comparison < 0)
+	{
+	  if      (order == FLAT)              order = ASCENDING_ORDER;
+	  else if (order == DESCENDING_ORDER)  return UNORDERED;
+	}
+      else if (comparison > 0)
+	{
+	  if      (order == FLAT)             order = DESCENDING_ORDER;
+	  else if (order == ASCENDING_ORDER)  return UNORDERED;
+	}
+    }
+  
+  return order;
+}
+//>} ; . ../make_fun
+
+
+/**
+ * Gets whether an array is sorted and in which order it is sorted.
+ * 
+ * This variant of `algo_is_sorted_cmp` allows you to
+ * store data needed for the comparison in a thread-safe
+ * way. It is reentrant.
+ * 
+ * `algo_make_implementation_of_is_sorted_cmp_r(T)` is used to make
+ * this function available for a particular data type `T`. And
+ * implementation without modifiers and attributes will be
+ * expanded. You may add `static`, `inline` and `__attribute__`
+ * before calling `algo_make_implementation_of_is_sorted_cmp_r(T)`.
+ * 
+ * `algo_make_prototype_of_is_sorted_cmp_r(T)` is the prototype
+ * counterpart of `algo_make_implementation_of_is_sorted_cmp_r(T)`.
+ * It too is will not add any modifiers or attributes by
+ * default. It will neither add a semicolon at the end of
+ * the prototype.
+ * 
+ * `algo_is_sorted_cmp_r(T)` is used to get the version of the
+ * function that supports the data type `T`.
+ * `&(algo_is_sorted_cmp_r(T))` gets the address of this function
+ * and `algo_is_sorted_cmp_r(T)(items, n, cmp)` calls the function.
+ * 
+ * This function is not pure because `cmp` is not necessarily pure.
+ * 
+ * @param   items  The items to check if they are ordered.
+ * @param   n      The number of elements in `items`.
+ * @param   cmp    Function used to compare two items, it should return a
+ *                 negative value if its first parameter is the lesser, a
+ *                 positive value if its second parameter is the lesser
+ *                 and zero if the parameters are equal. `data` will be
+ *                 input as `cmp`'s third argument.
+ * @param   data   Arbitrary data (may be `NULL`) to pass throught to `cmp`.
+ *                 and zero if the parameters are equal.
+ * @return         The order elements are sorted in.
+ */
+//>fun () {
+algo_sorted_order_t algo_is_sorted_cmp_r__##T(const T* restrict items, size_t n,
+					    int (*cmp)(const T*, const T*, void*), void* data)
+{
+  const T* end = items + n;
+  T last, cur;
+  algo_sorted_order_t order = FLAT;
+  int comparison;
+  
+  if (n == 0)
+    return FLAT;
+  
+  for (last = *items++; items != end; last = cur)
+    {
+      comparison = cmp(last, cur = *items++, data);
+      if (comparison < 0)
+	{
+	  if      (order == FLAT)              order = ASCENDING_ORDER;
+	  else if (order == DESCENDING_ORDER)  return UNORDERED;
+	}
+      else if (comparison > 0)
+	{
+	  if      (order == FLAT)             order = DESCENDING_ORDER;
+	  else if (order == ASCENDING_ORDER)  return UNORDERED;
+	}
+    }
+  
+  return order;
+}
+//>} ; . ../make_fun
+
+
+#endif
+