// Taken from
// https://github.com/skarupke/flat_hash_map/blob/2c4687431f978f02a3780e24b8b701d22aa32d9c/flat_hash_map.hpp
// with fixes applied:
// - https://github.com/skarupke/flat_hash_map/pull/25
// - https://github.com/skarupke/flat_hash_map/pull/26
// - replace size_t with uint64_t to fix it for 32bit
// - add "GCC diagnostic" pragma to ignore -Wshadow
// - make sherwood_v3_table::convertible_to_iterator public because GCC5 seems
// to have issues with it otherwise
// - fix compiler warnings in operator templated_iterator<const value_type>

//          Copyright Malte Skarupke 2017.
// Distributed under the Boost Software License, Version 1.0.
//    (See http://www.boost.org/LICENSE_1_0.txt)

#pragma once

#include <c10/macros/Macros.h>
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iterator>
#include <stdexcept>
#include <type_traits>
#include <utility>

C10_CLANG_DIAGNOSTIC_PUSH()
#if C10_CLANG_HAS_WARNING("-Wimplicit-int-float-conversion")
C10_CLANG_DIAGNOSTIC_IGNORE("-Wimplicit-int-float-conversion")
#endif

#ifdef _MSC_VER
#define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__
#else
#define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline))
#endif

namespace ska {
struct prime_number_hash_policy;
struct power_of_two_hash_policy;
struct fibonacci_hash_policy;

namespace detailv3 {
template <typename Result, typename Functor>
struct functor_storage : Functor {
  functor_storage() = default;
  functor_storage(const Functor& functor) : Functor(functor) {}
  template <typename... Args>
  Result operator()(Args&&... args) {
    return static_cast<Functor&>(*this)(std::forward<Args>(args)...);
  }
  template <typename... Args>
  Result operator()(Args&&... args) const {
    return static_cast<const Functor&>(*this)(std::forward<Args>(args)...);
  }
};
template <typename Result, typename... Args>
struct functor_storage<Result, Result (*)(Args...)> {
  typedef Result (*function_ptr)(Args...);
  function_ptr function;
  functor_storage(function_ptr function) : function(function) {}
  Result operator()(Args... args) const {
    return function(std::forward<Args>(args)...);
  }
  operator function_ptr&() {
    return function;
  }
  operator const function_ptr&() {
    return function;
  }
};
template <typename key_type, typename value_type, typename hasher>
struct KeyOrValueHasher : functor_storage<uint64_t, hasher> {
  typedef functor_storage<uint64_t, hasher> hasher_storage;
  KeyOrValueHasher() = default;
  KeyOrValueHasher(const hasher& hash) : hasher_storage(hash) {}
  uint64_t operator()(const key_type& key) {
    return static_cast<hasher_storage&>(*this)(key);
  }
  uint64_t operator()(const key_type& key) const {
    return static_cast<const hasher_storage&>(*this)(key);
  }
  uint64_t operator()(const value_type& value) {
    return static_cast<hasher_storage&>(*this)(value.first);
  }
  uint64_t operator()(const value_type& value) const {
    return static_cast<const hasher_storage&>(*this)(value.first);
  }
  template <typename F, typename S>
  uint64_t operator()(const std::pair<F, S>& value) {
    return static_cast<hasher_storage&>(*this)(value.first);
  }
  template <typename F, typename S>
  uint64_t operator()(const std::pair<F, S>& value) const {
    return static_cast<const hasher_storage&>(*this)(value.first);
  }
};
template <typename key_type, typename value_type, typename key_equal>
struct KeyOrValueEquality : functor_storage<bool, key_equal> {
  typedef functor_storage<bool, key_equal> equality_storage;
  KeyOrValueEquality() = default;
  KeyOrValueEquality(const key_equal& equality) : equality_storage(equality) {}
  bool operator()(const key_type& lhs, const key_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs, rhs);
  }
  bool operator()(const key_type& lhs, const value_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs, rhs.first);
  }
  bool operator()(const value_type& lhs, const key_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs);
  }
  bool operator()(const value_type& lhs, const value_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
  template <typename F, typename S>
  bool operator()(const key_type& lhs, const std::pair<F, S>& rhs) {
    return static_cast<equality_storage&>(*this)(lhs, rhs.first);
  }
  template <typename F, typename S>
  bool operator()(const std::pair<F, S>& lhs, const key_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs);
  }
  template <typename F, typename S>
  bool operator()(const value_type& lhs, const std::pair<F, S>& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
  template <typename F, typename S>
  bool operator()(const std::pair<F, S>& lhs, const value_type& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
  template <typename FL, typename SL, typename FR, typename SR>
  bool operator()(const std::pair<FL, SL>& lhs, const std::pair<FR, SR>& rhs) {
    return static_cast<equality_storage&>(*this)(lhs.first, rhs.first);
  }
};
static constexpr int8_t min_lookups = 4;
template <typename T>
struct sherwood_v3_entry {
  sherwood_v3_entry() = default;
  sherwood_v3_entry(int8_t distance_from_desired)
      : distance_from_desired(distance_from_desired) {}
  ~sherwood_v3_entry() = default;

  bool has_value() const {
    return distance_from_desired >= 0;
  }
  bool is_empty() const {
    return distance_from_desired < 0;
  }
  bool is_at_desired_position() const {
    return distance_from_desired <= 0;
  }
  template <typename... Args>
  void emplace(int8_t distance, Args&&... args) {
    new (std::addressof(value)) T(std::forward<Args>(args)...);
    distance_from_desired = distance;
  }

  void destroy_value() {
    value.~T();
    distance_from_desired = -1;
  }

  int8_t distance_from_desired = -1;
  static constexpr int8_t special_end_value = 0;
  union {
    T value;
  };
};

inline int8_t log2(uint64_t value) {
  static constexpr int8_t table[64] = {
      63, 0,  58, 1,  59, 47, 53, 2,  60, 39, 48, 27, 54, 33, 42, 3,
      61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
      62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
      56, 45, 25, 31, 35, 16, 9,  12, 44, 24, 15, 8,  23, 7,  6,  5};
  value |= value >> 1;
  value |= value >> 2;
  value |= value >> 4;
  value |= value >> 8;
  value |= value >> 16;
  value |= value >> 32;
  return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58];
}

template <typename T, bool>
struct AssignIfTrue {
  void operator()(T& lhs, const T& rhs) {
    lhs = rhs;
  }
  void operator()(T& lhs, T&& rhs) {
    lhs = std::move(rhs);
  }
};
template <typename T>
struct AssignIfTrue<T, false> {
  void operator()(T&, const T&) {}
  void operator()(T&, T&&) {}
};

inline uint64_t next_power_of_two(uint64_t i) {
  --i;
  i |= i >> 1;
  i |= i >> 2;
  i |= i >> 4;
  i |= i >> 8;
  i |= i >> 16;
  i |= i >> 32;
  ++i;
  return i;
}

// Implementation taken from http://en.cppreference.com/w/cpp/types/void_t
// (it takes CWG1558 into account and also works for older compilers)
template <typename... Ts>
struct make_void {
  typedef void type;
};
template <typename... Ts>
using void_t = typename make_void<Ts...>::type;

template <typename T, typename = void>
struct HashPolicySelector {
  typedef fibonacci_hash_policy type;
};
template <typename T>
struct HashPolicySelector<T, void_t<typename T::hash_policy>> {
  typedef typename T::hash_policy type;
};

template <
    typename T,
    typename FindKey,
    typename ArgumentHash,
    typename DetailHasher,
    typename ArgumentEqual,
    typename Equal,
    typename ArgumentAlloc,
    typename EntryAlloc>
class sherwood_v3_table : private EntryAlloc,
                          private DetailHasher,
                          private Equal {
  using Entry = detailv3::sherwood_v3_entry<T>;
  using AllocatorTraits = std::allocator_traits<EntryAlloc>;
  using EntryPointer = typename AllocatorTraits::pointer;

 public:
  struct convertible_to_iterator;

  using value_type = T;
  using size_type = uint64_t;
  using difference_type = std::ptrdiff_t;
  using hasher = ArgumentHash;
  using key_equal = ArgumentEqual;
  using allocator_type = EntryAlloc;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = value_type*;
  using const_pointer = const value_type*;

  sherwood_v3_table() = default;
  explicit sherwood_v3_table(
      size_type bucket_count,
      const ArgumentHash& hash = ArgumentHash(),
      const ArgumentEqual& equal = ArgumentEqual(),
      const ArgumentAlloc& alloc = ArgumentAlloc())
      : EntryAlloc(alloc), DetailHasher(hash), Equal(equal) {
    rehash(bucket_count);
  }
  sherwood_v3_table(size_type bucket_count, const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            bucket_count,
            ArgumentHash(),
            ArgumentEqual(),
            alloc) {}
  sherwood_v3_table(
      size_type bucket_count,
      const ArgumentHash& hash,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc) {}
  explicit sherwood_v3_table(const ArgumentAlloc& alloc) : EntryAlloc(alloc) {}
  template <typename It>
  sherwood_v3_table(
      It first,
      It last,
      size_type bucket_count = 0,
      const ArgumentHash& hash = ArgumentHash(),
      const ArgumentEqual& equal = ArgumentEqual(),
      const ArgumentAlloc& alloc = ArgumentAlloc())
      : sherwood_v3_table(bucket_count, hash, equal, alloc) {
    insert(first, last);
  }
  template <typename It>
  sherwood_v3_table(
      It first,
      It last,
      size_type bucket_count,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            first,
            last,
            bucket_count,
            ArgumentHash(),
            ArgumentEqual(),
            alloc) {}
  template <typename It>
  sherwood_v3_table(
      It first,
      It last,
      size_type bucket_count,
      const ArgumentHash& hash,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            first,
            last,
            bucket_count,
            hash,
            ArgumentEqual(),
            alloc) {}
  sherwood_v3_table(
      std::initializer_list<T> il,
      size_type bucket_count = 0,
      const ArgumentHash& hash = ArgumentHash(),
      const ArgumentEqual& equal = ArgumentEqual(),
      const ArgumentAlloc& alloc = ArgumentAlloc())
      : sherwood_v3_table(bucket_count, hash, equal, alloc) {
    if (bucket_count == 0)
      rehash(il.size());
    insert(il.begin(), il.end());
  }
  sherwood_v3_table(
      std::initializer_list<T> il,
      size_type bucket_count,
      const ArgumentAlloc& alloc)
      : sherwood_v3_table(
            il,
            bucket_count,
            ArgumentHash(),
            ArgumentEqual(),
            alloc) {}
  sherwood_v3_table(
      std::initializer_list<T> il,
      size_type bucket_count,