#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;
  }
};