Experimenting with K Order Markovian chains.

I do not recommend using this branch ATM, it has not been tested.

3 files changed, 99 insertions, 0 deletions

diff --git a/src/tool/CMakeLists.txt b/src/tool/CMakeLists.txt
index 3a1d947..3ad122b 100644
--- a/src/tool/CMakeLists.txt
+++ b/src/tool/CMakeLists.txt
@@ -1,6 +1,7 @@
 set(
    SRC_FILES ${SRC_FILES}
    ${CMAKE_CURRENT_SOURCE_DIR}/strings.c
+   ${CMAKE_CURRENT_SOURCE_DIR}/sorted_list.c
 )
 
 set(SRC_FILES ${SRC_FILES} PARENT_SCOPE)
diff --git a/src/tool/sorted_list.c b/src/tool/sorted_list.c
new file mode 100644
index 0000000..880a4b5
--- /dev/null
+++ b/src/tool/sorted_list.c
@@ -0,0 +1,79 @@
+#include "./sorted_list.h"
+
+int ZoO_sorted_list_index_of
+(
+   ZoO_index const list_length,
+   const void * const sorted_list,
+   const void * const elem,
+   size_t const type_size,
+   int (*compare) (const void *, const void *, const void *),
+   const void * const other,
+   ZoO_index result [const restrict static 1]
+)
+{
+   int cmp;
+   ZoO_index i, current_min, current_max;
+   const char * sorted_list_access;
+
+   sorted_list_access = (char *) sorted_list;
+
+   /* This is a binary search. */
+
+   if (list_length == 0)
+   {
+      *result = 0;
+
+      return -1;
+   }
+
+   current_min = 0;
+
+   current_max = (list_length - 1);
+
+   for (;;)
+   {
+      /* FIXME: overflow-safe? */
+      i = ((current_min + current_max) / 2);
+
+      if (i == list_length)
+      {
+         /* FIXME: I don't see how this one can be true */
+         *result = list_length;
+
+         return -1;
+      }
+
+      cmp = compare(elem, (sorted_list_access + (i * type_size)), other);
+
+      if (cmp > 0)
+      {
+         if ((current_min > current_max))
+         {
+            *result = (i + 1);
+
+            return -1;
+         }
+
+         /* FIXME: overflow-safe? */
+         current_min = (i + 1);
+      }
+      else if (cmp < 0)
+      {
+         if ((current_min > current_max) || (i == 0))
+         {
+            *result = i;
+
+            return -1;
+         }
+
+         /* overflow-safe */
+         current_max = (i - 1);
+      }
+      else
+      {
+         *result = i;
+
+         return 0;
+      }
+   }
+}
diff --git a/src/tool/sorted_list.h b/src/tool/sorted_list.h
new file mode 100644
index 0000000..72bd893
--- /dev/null
+++ b/src/tool/sorted_list.h
@@ -0,0 +1,19 @@
+#ifndef _ZoO_TOOL_SORTED_LIST_H_
+#define _ZoO_TOOL_SORTED_LIST_H_
+
+#include <stdlib.h>
+
+#include "../pervasive.h"
+
+int ZoO_sorted_list_index_of
+(
+   ZoO_index const list_length,
+   const void * const sorted_list,
+   const void * const elem,
+   size_t const type_size,
+   int (*compare) (const void *, const void *, const void *),
+   const void * const other,
+   ZoO_index result [const restrict static 1]
+);
+
+#endif