#ifndef MERCURY_KERNEL_UTILITY_HPP
#define MERCURY_KERNEL_UTILITY_HPP

#include <optional>
#include <cstdint>

namespace mercury::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];
  };

  template <class value_t>
  struct string_tree {

    std::optional<value_t> value_here = {};
    string_tree<value_t> *parent = 0;
    string_tree<value_t> *subtrees[256] = {};

    //if there is a node whose key has a prefix in common with str, then this
    //returns the deepest such node, and sets leftover_out to point to the
    //character of str after the common prefix with that returned node. if
    //there is no such node, this returns the current node and sets
    //leftover_out to a null pointer.
    string_tree &max_common_prefix(
        const char *str, size_t str_len, const char *&leftover_out) {

      string_tree<value_t> *last_with_value = 0;
      const char *leftover_at_last_with_value = 0;
      string_tree<value_t> *on = this;
      size_t len_so_far = 0;

      while (true) {

        if (on->value_here) {
          last_with_value = on;
          leftover_at_last_with_value = str + len_so_far;
        }

        if (len_so_far == str_len)
          break;

        on = on->subtrees[(uint8_t)str[len_so_far]];
        if (!on)
          break;

        ++len_so_far;

      }

      if (last_with_value) {
        leftover_out = leftover_at_last_with_value;
        return *last_with_value;
      }

      leftover_out = 0;
      return *this;

    }

    bool try_insert(const char *str, size_t str_len, value_t value) {

      string_tree<value_t> *on = this;
      for (size_t i = 0; i < str_len; ++i) {
        string_tree<value_t> *&subtree = on->subtrees[(uint8_t)str[i]];
        if (!subtree) {
          subtree = new string_tree<value_t>();
          subtree->parent = on;
        }
        on = subtree;
      }

      if (on->value_here)
        return false;
      on->value_here = value;
      return true;

    }

  };

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

  template <class value_t>
  struct flist {

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

    node *first;

    flist() : first(0) {}

    void insert(value_t value) {
      first = new node {
        .value = value,
        .next = first
      };
    }

  };

}

#endif