From fd458396b376d0f9fff3dd5a03b1ef95c8cf870e Mon Sep 17 00:00:00 2001 From: Mitya Selivanov <0x7fffff@guattari.ru> Date: Sun, 7 Aug 2022 08:33:25 +0400 Subject: Lower bound --- source/kit/CMakeLists.txt | 3 +- source/kit/lower_bound.c | 1 + source/kit/lower_bound.h | 42 ++++++++ source/kit_test/run_tests.c | 2 +- source/test/unittests/CMakeLists.txt | 3 +- source/test/unittests/lower_bound.test.c | 178 +++++++++++++++++++++++++++++++ 6 files changed, 226 insertions(+), 3 deletions(-) create mode 100644 source/kit/lower_bound.c create mode 100644 source/kit/lower_bound.h create mode 100644 source/test/unittests/lower_bound.test.c 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 $ @@ -10,4 +10,5 @@ target_sources( $ $ $ + $ $) 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); +} -- cgit v1.2.3