feat: Implement expt_0821

Signed-off-by: KunoiSayami <[email protected]>

1 files changed, 81 insertions, 0 deletions

diff --git a/sortlib.h b/sortlib.h
new file mode 100644
index 0000000..c00c07f
--- /dev/null
+++ b/sortlib.h
@@ -0,0 +1,81 @@
+#pragma once
+#include <cassert>
+#include <cstddef>
+#include <cstdio>
+
+template <typename C> class CustomSort {
+public:
+  CustomSort(size_t length, int move_offset)
+      : LENGTH(length), MOVE_OFFSET(move_offset) {}
+  const size_t LENGTH;
+  const int MOVE_OFFSET;
+
+  static size_t fast_log(size_t a) {
+    float t = a;
+    return (((*(int *)&t) >> 23) + 1) & 127;
+  }
+  size_t calculate_location(size_t index) const {
+    size_t bit_low = (LENGTH + 1) >> fast_log(++index) >> 1;
+    return (((index << 1) | 1) * bit_low - LENGTH - 1);
+  }
+
+  size_t calculate_location_inverse(size_t index) const {
+    index++;
+    size_t low_bit = index & (-index);
+    return ((LENGTH + index) / low_bit) >> 1;
+  }
+
+  __attribute__((unused)) void testCalculation() const {
+    for (size_t i = 0; i < LENGTH; i++) {
+      auto l = calculate_location(i);
+      auto l2 = calculate_location_inverse(l - 1);
+      assert(l == l2);
+    }
+  }
+  template <typename T> const T *binary_search(T *const start, const T val) {
+
+    int step_limit = (int)fast_log(LENGTH);
+    T *last_known_point = start;
+    auto son = 0;
+
+    for (int i = 0; i < step_limit; i++) {
+      const auto next_level_start = start + (1 << (i + 1)) - 1;
+      if (*last_known_point == val) {
+        return last_known_point;
+      }
+
+      // son = get_son_from_step(son, (*last_known_point > val));
+      auto tmp = (int)((*last_known_point - val) >> MOVE_OFFSET);
+      printf("%llu %llu ", val, *last_known_point);
+      son = son * 2 + tmp;
+      puts(tmp == 0 ? "1:left" : "1:right");
+      // if (son < 0) son = 0;
+      /*printf("%d %d %d\n", (1 << (i + 1)), son,
+             -(int)((*last_known_point - val) >> MOVE_OFFSET));*/
+      last_known_point = next_level_start + son;
+    }
+    return last_known_point;
+  }
+  template <typename T> T *original_binary_search(T *start, T *end, T &val) {
+    auto begin = start;
+    T *last_known_point = nullptr;
+    while (begin < end) {
+      auto mid = (end - begin) / 2;
+      auto mid_val = *(begin + mid);
+      if (val == mid_val) {
+        return begin + mid;
+      }
+      printf("%llu %llu ", val, mid_val);
+      puts(val > mid_val ? "right" : "left");
+      /*begin += (int)((mid_val - val) >> MOVE_OFFSET) & (mid + 1);
+      end -= (int)(~((mid_val - val) >> MOVE_OFFSET)) & (mid + 1);*/
+      if (val > mid_val) {
+        begin = begin + mid + 1;
+      } else {
+        end = end - mid - 1;
+      }
+      last_known_point = begin;
+    }
+    return last_known_point;
+  }
+};