#ifndef HILBERT_KERNEL_UTILITY_HPP
#define HILBERT_KERNEL_UTILITY_HPP

#include <optional>
#include <cstdint>

namespace hilbert::kernel::utility {

  template <class t>
  static inline t min(t a, t b) {
    return a < b ? a : b;
  }

  //includes start_i, does not include end_i
  void mark_bitmap_region_zero(uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
  //includes start_i, does not include end_i
  void mark_bitmap_region_one(uint64_t *bitmap, uint64_t start_i, uint64_t end_i);

  struct uuid {
    uint8_t bytes[16];
  };

  //if c appears in str, this returns the index of the first time it appears.
  //otherwise, this returns len.
  static inline unsigned find(const char *str, unsigned len, char c) {
    for (unsigned i = 0; i < len; ++i)
      if (str[i] == c)
        return i;
    return len;
  }

  //if c appears in str, this returns the index of the last time it appears.
  //otherwise, this returns len.
  static inline unsigned find_last(const char *str, unsigned len, char c) {
    for (unsigned i = len; i > 0; --i)
      if (str[i - 1] == c)
        return i - 1;
    return len;
  }

  //str1 starts with str2
  static inline bool starts_with(
    const char *str1, unsigned str1_len, const char *str2, unsigned str2_len
  ) {
    if (str1_len < str2_len)
      return false;
    for (unsigned i = 0; i < str2_len; ++i)
      if (str1[i] != str2[i])
        return false;
    return true;
  }

  template <class value_t>
  struct list {

    struct node {
      value_t value;
      node *next;
      node *prev;
    };

    node *first;
    node *last;

    list() : first(0), last(0) {}

    ~list() {
      if (first) {
        for (node *n = first->next; n; n = n->next)
          delete n->prev;
        delete last;
      }
    }

    void insert_end(const value_t &value) {
      node *n = new node {};
      n->value = value;
      n->next = 0;
      n->prev = last;
      last = n;
    }

    void insert_end(value_t &&value) {
      node *n = new node {};
      n->value = value;
      n->next = 0;
      n->prev = last;
      last = n;
    }

    void clear() {
      for (node *n = first; n; n = n->next)
        delete n;
      first = 0;
      last = 0;
    }

    //assumes there is a last.
    void remove_last() {
      node *new_last = last->prev;
      if (new_last)
        new_last->next = 0;
      else
        first = 0;
      delete last;
      last = new_last;
    }

    void remove(node *n) {
      if (n->prev)
        n->prev->next = n->next;
      else
        first = n->next;
      if (n->next)
        n->next->prev = n->prev;
      else
        last = n->prev;
      delete n;
    }

  };

  template <class value_t>
  struct vector {

    value_t *buffer;
    unsigned buffer_len;
    unsigned count;

    vector(unsigned buffer_len = 16)
      : buffer(new value_t[buffer_len]), buffer_len(buffer_len), count(0) {}

    vector(const value_t *copy_from, unsigned len)
      : buffer(new value_t[len]), buffer_len(len), count(len) {
      for (unsigned i = 0; i < len; ++i)
        buffer[i] = copy_from[i];
    }

    vector(const vector<value_t> &other)
      : buffer(new value_t[other.buffer_len]),
        buffer_len(other.buffer_len), count(other.count)
    {
      for (unsigned i = 0; i < count; ++i)
        buffer[i] = other.buffer[i];
    }

    ~vector() {
      if (buffer)
        delete[] buffer;
    }

    vector<value_t> &operator =(const vector<value_t> &other) {
      if (buffer)
        delete[] buffer;
      buffer = new value_t[other.buffer_len];
      buffer_len = other.buffer_len;
      count = other.count;
      for (unsigned i = 0; i < other.count; ++i)
        buffer[i] = other.buffer[i];
      return *this;
    }

    vector<value_t> &operator =(vector<value_t> &&other) {
      if (buffer)
        delete[] buffer;
      buffer = other.buffer;
      buffer_len = other.buffer_len;
      count = other.count;
      other.buffer = 0;
      return *this;
    }

    bool operator ==(const vector<value_t> &other) {
      if (other.count != count)
        return false;
      for (unsigned i = 0; i < count; ++i)
        if (other.buffer[i] != buffer[i])
          return false;
      return true;
    }

    void verify_buffer_len(unsigned target_len) {
      if (buffer_len >= target_len)
        return;
      unsigned new_buffer_len = buffer_len;
      do
        new_buffer_len *= 2;
      while (new_buffer_len < target_len);
      value_t *new_buffer = new value_t[new_buffer_len];
      for (unsigned i = 0; i < count; ++i)
        new_buffer[i] = std::move(buffer[i]);
      delete[] buffer;
      buffer = new_buffer;
      buffer_len = new_buffer_len;
    }

    void add_end(value_t &&v) {
      verify_buffer_len(count + 1);
      buffer[count] = std::move(v);
      ++count;
    }

    void add_end(const value_t &v) {
      verify_buffer_len(count + 1);
      buffer[count] = v;
      ++count;
    }

    bool starts_with(const vector<value_t> &other) {
      if (count < other.count)
        return false;
      for (unsigned i = 0; i < other.count; ++i)
        if (buffer[i] != other.buffer[i])
          return false;
      return true;
    }

  };

  typedef vector<char> string;

}

#endif