Lower bound

6 files changed, 226 insertions, 3 deletions

diff --git a/source/kit/CMakeLists.txt b/source/kit/CMakeLists.txt
index 761f572..c7bb204 100644
--- a/source/kit/CMakeLists.txt
+++ b/source/kit/CMakeLists.txt
@@ -1,7 +1,7 @@
 target_sources(
   ${KIT_LIBRARY}
     PRIVATE
-      input_buffer.c input_stream.c string_ref.c
+      input_buffer.c input_stream.c lower_bound.c string_ref.c
       async_function.c allocator.c array_ref.c dynamic_array.c
     PUBLIC
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/allocator.h>
@@ -10,4 +10,5 @@ target_sources(
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/async_function.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/input_stream.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/input_buffer.h>
+      $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/lower_bound.h>
       $<BUILD_INTERFACE:${CMAKE_CURRENT_LIST_DIR}/array_ref.h>)
diff --git a/source/kit/lower_bound.c b/source/kit/lower_bound.c
new file mode 100644
index 0000000..0ae8489
--- /dev/null
+++ b/source/kit/lower_bound.c
@@ -0,0 +1 @@
+#include "lower_bound.h"
diff --git a/source/kit/lower_bound.h b/source/kit/lower_bound.h
new file mode 100644
index 0000000..5b04557
--- /dev/null
+++ b/source/kit/lower_bound.h
@@ -0,0 +1,42 @@
+#ifndef KIT_LOWER_BOUND_H
+#define KIT_LOWER_BOUND_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define KIT_LOWER_BOUND(return_val, array, value, op)        \
+  {                                                          \
+    ptrdiff_t position_ = 0;                                 \
+    ptrdiff_t count_    = (array).size;                      \
+    while (count_ > 0) {                                     \
+      ptrdiff_t delta_ = count_ / 2;                         \
+      if (op((array).values[position_ + delta_], (value))) { \
+        position_ += delta_ + 1;                             \
+        count_ -= delta_ + 1;                                \
+      } else                                                 \
+        count_ = delta_;                                     \
+    }                                                        \
+    (return_val) = position_;                                \
+  }
+
+#define KIT_LOWER_BOUND_REF(return_val, array, value, op)      \
+  {                                                            \
+    ptrdiff_t position_ = 0;                                   \
+    ptrdiff_t count_    = (array).size;                        \
+    while (count_ > 0) {                                       \
+      ptrdiff_t delta_ = count_ / 2;                           \
+      if (op((array).values + position_ + delta_, &(value))) { \
+        position_ += delta_ + 1;                               \
+        count_ -= delta_ + 1;                                  \
+      } else                                                   \
+        count_ = delta_;                                       \
+    }                                                          \
+    (return_val) = position_;                                  \
+  }
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/source/kit_test/run_tests.c b/source/kit_test/run_tests.c
index 1cb391c..1bb6e67 100644
--- a/source/kit_test/run_tests.c
+++ b/source/kit_test/run_tests.c
@@ -24,7 +24,7 @@ static long long sec_to_ms(long long sec) {
   return 1000 * sec;
 }
 
-enum code_value { white, yellow, red, green };
+enum { white, yellow, red, green };
 
 static void color_code(int term_color, int c) {
   if (term_color) {
diff --git a/source/test/unittests/CMakeLists.txt b/source/test/unittests/CMakeLists.txt
index ff99c9c..75b1f3f 100644
--- a/source/test/unittests/CMakeLists.txt
+++ b/source/test/unittests/CMakeLists.txt
@@ -2,4 +2,5 @@ target_sources(
   ${KIT_TEST_SUITE}
     PRIVATE
       async_function.test.c main.test.c array_ref.test.c
-      input_stream.test.c input_buffer.test.c dynamic_array.test.c)
+      input_stream.test.c lower_bound.test.c input_buffer.test.c
+      dynamic_array.test.c)
diff --git a/source/test/unittests/lower_bound.test.c b/source/test/unittests/lower_bound.test.c
new file mode 100644
index 0000000..275acd6
--- /dev/null
+++ b/source/test/unittests/lower_bound.test.c
@@ -0,0 +1,178 @@
+#include "../../kit/lower_bound.h"
+#include "../../kit/array_ref.h"
+
+#define KIT_TEST_FILE lower_bound
+#include "../../kit_test/test.h"
+
+static int kit_less_int(int left, int right) {
+  return left < right;
+}
+
+static int kit_less_int_ref(int const *left, int const *right) {
+  return *left < *right;
+}
+
+TEST("lower bound empty") {
+  AR_CONST(ref, int) = { .size = 0, .values = NULL };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 42, kit_less_int);
+  REQUIRE(index == 0);
+}
+
+TEST("lower bound single left") {
+  int const v[1]     = { 42 };
+  AR_CONST(ref, int) = { .size = 1, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 42, kit_less_int);
+  REQUIRE(index == 0);
+}
+
+TEST("lower bound single right") {
+  int const v[1]     = { 42 };
+  AR_CONST(ref, int) = { .size = 1, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 43, kit_less_int);
+  REQUIRE(index == 1);
+}
+
+TEST("lower bound first of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 1, kit_less_int);
+  REQUIRE(index == 0);
+}
+
+TEST("lower bound second of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 2, kit_less_int);
+  REQUIRE(index == 1);
+}
+
+TEST("lower bound third of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 3, kit_less_int);
+  REQUIRE(index == 2);
+}
+
+TEST("lower bound forth of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 4, kit_less_int);
+  REQUIRE(index == 3);
+}
+
+TEST("lower bound fifth of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 5, kit_less_int);
+  REQUIRE(index == 4);
+}
+
+TEST("lower bound first of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 1, kit_less_int);
+  REQUIRE(index == 0);
+}
+
+TEST("lower bound second of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 2, kit_less_int);
+  REQUIRE(index == 1);
+}
+
+TEST("lower bound third of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 3, kit_less_int);
+  REQUIRE(index == 2);
+}
+
+TEST("lower bound forth of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 4, kit_less_int);
+  REQUIRE(index == 3);
+}
+
+TEST("lower bound fifth of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 5, kit_less_int);
+  REQUIRE(index == 4);
+}
+
+TEST("lower bound sixth of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND(index, ref, 6, kit_less_int);
+  REQUIRE(index == 5);
+}
+
+TEST("lower bound ref first of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  int const value    = 1;
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND_REF(index, ref, value, kit_less_int_ref);
+  REQUIRE(index == 0);
+}
+
+TEST("lower bound ref second of four") {
+  int const v[4]     = { 1, 2, 3, 4 };
+  int const value    = 2;
+  AR_CONST(ref, int) = { .size = 4, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND_REF(index, ref, value, kit_less_int_ref);
+  REQUIRE(index == 1);
+}
+
+TEST("lower bound ref fifth of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  int const value    = 5;
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND_REF(index, ref, value, kit_less_int_ref);
+  REQUIRE(index == 4);
+}
+
+TEST("lower bound ref sixth of five") {
+  int const v[5]     = { 1, 2, 3, 4, 5 };
+  int const value    = 6;
+  AR_CONST(ref, int) = { .size = 5, .values = v };
+
+  ptrdiff_t index;
+  KIT_LOWER_BOUND_REF(index, ref, value, kit_less_int_ref);
+  REQUIRE(index == 5);
+}