<commit_before>#pragma once
#include <memory>
#include <utility>
#include <vector>

#include "array.hh"
#include "optional.hh"

namespace {

static uint64_t algoLog2(uint64_t x) {
  uint64_t y;
  __asm__("\tbsr %1, %0\n" : "=r"(y) : "r"(x));
  return y;
}
};

namespace xtd {

template <typename T, uint8_t N = 0>
class vector {
  static constexpr size_t segmentCapacity() { return 1 << N; }
  static constexpr size_t segmentSize() {
    return sizeof(T) * segmentCapacity();
  }

  using segment_index_t = int;
  using index_t = int;
  using segment_t = array<T, std::aligned_storage_t<sizeof(T), alignof(T)>[segmentCapacity()]>;
  using block_t = array<segment_t, std::unique_ptr<segment_t[]>>;

  std::vector<block_t> m_data;  // begin, end
  uint32_t m_d;

  uint32_t m_s;
  uint32_t m_n;
  uint32_t m_od;
  uint32_t m_nd;
  uint32_t m_os;
  uint32_t m_ns;
  bool m_emptyDb;

  uint32_t m_oseg;

  void grow() {
    if (m_od == m_nd) {
      if (m_os == m_ns) {
        if (++m_s & 1)
          m_ns <<= 1;
        else
          m_nd <<= 1;
        m_os = 0;
      }
      if (!m_emptyDb) {
        m_data.emplace_back(new segment_t[m_nd]);
      }
      m_emptyDb = 0;
      ++m_d;
      ++m_os;
      m_od = 0;
    }
    ++m_n;
    ++m_od;
  }

  void shrink() {
    --m_n;
    --m_od;
    if (m_od == 0) {
      if (m_emptyDb) m_data.pop_back();
      --m_d;
      --m_os;
      if (m_os == 0) {
        --m_s;
        if (!(m_s & 1))
          m_ns >>= 1;
        else
          m_nd >>= 1;
        m_os = m_ns;
      }
      m_od = m_nd;
      m_emptyDb = true;
    }
    if (m_n == 0) {
      m_od = 1;
      m_os = 0;
      m_nd = 1;
      m_ns = 1;
      m_s = 1;
      m_d = 0;
      m_oseg = segmentCapacity();
      m_emptyDb = true;
    }
  };

 public:
  vector()
      : m_d{0},
        m_s{1},
        m_n{0},
        m_oseg{segmentCapacity()},
        m_od{1},
        m_os{0},
        m_nd{1},
        m_ns{1},
        m_emptyDb{true} {
    m_data.emplace_back(new segment_t[m_nd]);
  }

  template <typename... Args>
  vector& push(Args&&... args) {
    if (m_oseg < segmentCapacity())
      m_oseg++;
    else {
      grow();
      m_oseg = 1;
    }
    m_data[m_d - 1][m_od - 1]
        .overwrite(m_oseg - 1)
        .emplace(std::forward<Args>(args)...);
    return *this;
  }

  template <typename Vector>
  friend auto& at(Vector& v, size_t p) {
    size_t elm = p & (v.segmentCapacity() - 1);
    size_t pos = p >> N;

    if (pos == 0) return v.m_data[0][0][elm];
    if (pos == 1) return v.m_data[1][0][elm];
    if (pos == 2) return v.m_data[1][1][elm];

    pos += 1;
    const uint64_t k = algoLog2(pos);  // the number of the superblock

    const uint64_t kdiv2 = k >> 1;
    const uint64_t oneShlKdiv2 = (1 << kdiv2);
    const uint64_t notKdiv2 = oneShlKdiv2 - 1;

    const uint64_t mask_b = (notKdiv2 << kdiv2)
                            << (k & 1);  // the first floor(k/2) bits after the<commit_msg>Fixed non-static auto return type gcc<commit_after>#pragma once
#include <memory>
#include <utility>
#include <vector>

#include "array.hh"
#include "optional.hh"

namespace {

static uint64_t algoLog2(uint64_t x) {
  uint64_t y;
  __asm__("\tbsr %1, %0\n" : "=r"(y) : "r"(x));
  return y;
}
};

namespace xtd {

template <typename T, uint8_t N = 0>
class vector {
  static constexpr size_t segmentCapacity() { return 1 << N; }
  static constexpr size_t segmentSize() {
    return sizeof(T) * segmentCapacity();
  }

  using segment_index_t = int;
  using index_t = int;
  using segment_t = array<T, std::aligned_storage_t<sizeof(T), alignof(T)>[segmentCapacity()]>;
  using block_t = array<segment_t, std::unique_ptr<segment_t[]>>;

  std::vector<block_t> m_data;  // begin, end
  uint32_t m_d;

  uint32_t m_s;
  uint32_t m_n;
  uint32_t m_od;
  uint32_t m_nd;
  uint32_t m_os;
  uint32_t m_ns;
  bool m_emptyDb;

  uint32_t m_oseg;

  void grow() {
    if (m_od == m_nd) {
      if (m_os == m_ns) {
        if (++m_s & 1)
          m_ns <<= 1;
        else
          m_nd <<= 1;
        m_os = 0;
      }
      if (!m_emptyDb) {
        m_data.emplace_back(new segment_t[m_nd]);
      }
      m_emptyDb = 0;
      ++m_d;
      ++m_os;
      m_od = 0;
    }
    ++m_n;
    ++m_od;
  }

  void shrink() {
    --m_n;
    --m_od;
    if (m_od == 0) {
      if (m_emptyDb) m_data.pop_back();
      --m_d;
      --m_os;
      if (m_os == 0) {
        --m_s;
        if (!(m_s & 1))
          m_ns >>= 1;
        else
          m_nd >>= 1;
        m_os = m_ns;
      }
      m_od = m_nd;
      m_emptyDb = true;
    }
    if (m_n == 0) {
      m_od = 1;
      m_os = 0;
      m_nd = 1;
      m_ns = 1;
      m_s = 1;
      m_d = 0;
      m_oseg = segmentCapacity();
      m_emptyDb = true;
    }
  };

 public:
  vector()
      : m_d{0},
        m_s{1},
        m_n{0},
        m_oseg{segmentCapacity()},
        m_od{1},
        m_os{0},
        m_nd{1},
        m_ns{1},
        m_emptyDb{true} {
    m_data.emplace_back(new segment_t[m_nd]);
  }

  template <typename... Args>
  vector& push(Args&&... args) {
    if (m_oseg < segmentCapacity())
      m_oseg++;
    else {
      grow();
      m_oseg = 1;
    }
    m_data[m_d - 1][m_od - 1]
        .overwrite(m_oseg - 1)
        .emplace(std::forward<Args>(args)...);
    return *this;
  }

  template <typename Vector>
  static auto& at(Vector& v, size_t p) {
    size_t elm = p & (v.segmentCapacity() - 1);
    size_t pos = p >> N;

    if (pos == 0) return v.m_data[0][0][elm];
    if (pos == 1) return v.m_data[1][0][elm];
    if (pos == 2) return v.m_data[1][1][elm];

    pos += 1;
    const uint64_t k = algoLog2(pos);  // the number of the superblock

    const uint64_t kdiv2 = k >> 1;
    const uint64_t oneShlKdiv2 = (1 << kdiv2);
    const uint64_t notKdiv2 = oneShlKdiv2 - 1;

    const uint64_t mask_b = (notKdiv2 << kdiv2)
                            << (k & 1);  // the first floor(k/2) bits after the
{'fraction_non_alphanumeric': 0.15380710659898478, 'fraction_numerical': 0.030795262267343484, 'mean_word_length': 1.9989852866565194, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2827200', 'n_tokens_mistral': 2597, 'n_tokens_neox': 2465, 'n_words': 550}