/**
 * MIT License
 *
 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef TSL_SPARSE_HASH_H
#define TSL_SPARSE_HASH_H

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <memory>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#include "sparse_growth_policy.h"

#ifdef __INTEL_COMPILER
#include <immintrin.h>  // For _popcnt32 and _popcnt64
#endif

#ifdef _MSC_VER
#include <intrin.h>  // For __cpuid, __popcnt and __popcnt64
#endif

#ifdef TSL_DEBUG
#define tsl_sh_assert(expr) assert(expr)
#else
#define tsl_sh_assert(expr) (static_cast<void>(0))
#endif

namespace tsl {

namespace sh {
enum class probing { linear, quadratic };

enum class exception_safety { basic, strong };

enum class sparsity { high, medium, low };
}  // namespace sh

namespace detail_popcount {
/**
 * Define the popcount(ll) methods and pick-up the best depending on the
 * compiler.
 */

// From Wikipedia: https://en.wikipedia.org/wiki/Hamming_weight
inline int fallback_popcountll(unsigned long long int x) {
  static_assert(
      sizeof(unsigned long long int) == sizeof(std::uint64_t),
      "sizeof(unsigned long long int) must be equal to sizeof(std::uint64_t). "
      "Open a feature request if you need support for a platform where it "
      "isn't the case.");

  const std::uint64_t m1 = 0x5555555555555555ull;
  const std::uint64_t m2 = 0x3333333333333333ull;
  const std::uint64_t m4 = 0x0f0f0f0f0f0f0f0full;
  const std::uint64_t h01 = 0x0101010101010101ull;

  x -= (x >> 1ull) & m1;
  x = (x & m2) + ((x >> 2ull) & m2);
  x = (x + (x >> 4ull)) & m4;
  return static_cast<int>((x * h01) >> (64ull - 8ull));
}

inline int fallback_popcount(unsigned int x) {
  static_assert(sizeof(unsigned int) == sizeof(std::uint32_t) ||
                    sizeof(unsigned int) == sizeof(std::uint64_t),
                "sizeof(unsigned int) must be equal to sizeof(std::uint32_t) "
                "or sizeof(std::uint64_t). "
                "Open a feature request if you need support for a platform "
                "where it isn't the case.");

  if (sizeof(unsigned int) == sizeof(std::uint32_t)) {
    const std::uint32_t m1 = 0x55555555;
    const std::uint32_t m2 = 0x33333333;
    const std::uint32_t m4 = 0x0f0f0f0f;
    const std::uint32_t h01 = 0x01010101;

    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return static_cast<int>((x * h01) >> (32 - 8));
  } else {
    return fallback_popcountll(x);
  }
}

#if defined(__clang__) || defined(__GNUC__)
inline int popcountll(unsigned long long int value) {
  return __builtin_popcountll(value);
}

inline int popcount(unsigned int value) { return __builtin_popcount(value); }

#elif defined(_MSC_VER)
/**
 * We need to check for popcount support at runtime on Windows with __cpuid
 * See https://msdn.microsoft.com/en-us/library/bb385231.aspx
 */
inline bool has_popcount_support() {
  int cpu_infos[4];
  __cpuid(cpu_infos, 1);
  return (cpu_infos[2] & (1 << 23)) != 0;
}

inline int popcountll(unsigned long long int value) {
#ifdef _WIN64
  static_assert(
      sizeof(unsigned long long int) == sizeof(std::int64_t),
      "sizeof(unsigned long long int) must be equal to sizeof(std::int64_t). ");

  static const bool has_popcount = has_popcount_support();
  return has_popcount
             ? static_cast<int>(__popcnt64(static_cast<std::int64_t>(value)))
             : fallback_popcountll(value);
#else
  return fallback_popcountll(value);
#endif
}

inline int popcount(unsigned int value) {
  static_assert(sizeof(unsigned int) == sizeof(std::int32_t),
                "sizeof(unsigned int) must be equal to sizeof(std::int32_t). ");

  static const bool has_popcount = has_popcount_support();
  return has_popcount
             ? static_cast<int>(__popcnt(static_cast<std::int32_t>(value)))
             : fallback_popcount(value);
}

#elif defined(__INTEL_COMPILER)
inline int popcountll(unsigned long long int value) {
  static_assert(sizeof(unsigned long long int) == sizeof(__int64), "");
  return _popcnt64(static_cast<__int64>(value));
}

inline int popcount(unsigned int value) {
  return _popcnt32(static_cast<int>(value));
}

#else
inline int popcountll(unsigned long long int x) {
  return fallback_popcountll(x);
}

inline int popcount(unsigned int x) { return fallback_popcount(x); }

#endif
}  // namespace detail_popcount

namespace detail_sparse_hash {

template <typename T>
struct make_void {
  using type = void;
};

template <typename T, typename = void>
struct has_is_transparent : std::false_type {};

template <typename T>
struct has_is_transparent<T,
                          typename make_void<typename T::is_transparent>::type>
    : std::true_type {};

template <typename U>
struct is_power_of_two_policy : std::false_type {};

template <std::size_t GrowthFactor>
struct is_power_of_two_policy<tsl::sh::power_of_two_growth_policy<GrowthFactor>>
    : std::true_type {};

inline constexpr bool is_power_of_two(std::size_t value) {
  return value != 0 && (value & (value - 1)) == 0;
}

inline std::size_t round_up_to_power_of_two(std::size_t value) {
  if (is_power_of_two(value)) {
    return value;
  }

  if (value == 0) {
    return 1;
  }

  --value;
  for (std::size_t i = 1; i < sizeof(std::size_t) * CHAR_BIT; i *= 2) {
    value |= value >> i;
  }

  return value + 1;
}

template <typename T, typename U>
static T numeric_cast(U value,
                      const char *error_message = "numeric_cast() failed.") {
  T ret = static_cast<T>(value);
  if (static_cast<U>(ret) != value) {
    TSL_SH_THROW_OR_ABORT(std::runtime_error, error_message);
  }

  const bool is_same_signedness =
      (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
      (std::is_signed<T>::value && std::is_signed<U>::value);
  if (!is_same_signedness && (ret < T{}) != (value < U{})) {
    TSL_SH_THROW_OR_ABORT(std::runtime_error, error_message);
  }

  return ret;
}

/**
 * Fixed size type used to represent size_type values on serialization. Need to
 * be big enough to represent a std::size_t on 32 and 64 bits platforms, and
 * must be the same size on both platforms.
 */
using slz_size_type = std::uint64_t;
static_assert(std::numeric_limits<slz_size_type>::max() >=
                  std::numeric_limits<std::size_t>::max(),
              "slz_size_type must be >= std::size_t");

template <class T, class Deserializer>
static T deserialize_value(Deserializer &deserializer) {
  // MSVC < 2017 is not conformant, circumvent the problem by removing the
  // template keyword
#if defined(_MSC_VER) && _MSC_VER < 1910
  return deserializer.Deserializer::operator()<T>();
#else
  return deserializer.Deserializer::template operator()<T>();
#endif
}

/**
 * WARNING: the sparse_array class doesn't free the ressources allocated through
 * the allocator passed in parameter in each method. You have to manually call
 * `clear(Allocator&)` when you don't need a sparse_array object anymore.
 *
 * The reason is that the sparse_array doesn't store the allocator to avoid
 * wasting space in each sparse_array when the allocator has a size > 0. It only
 * allocates/deallocates objects with the allocator that is passed in parameter.
 *
 *
 *
 * Index denotes a value between [0, BITMAP_NB_BITS), it is an index similar to
 * std::vector. Offset denotes the real position in `m_values` corresponding to
 * an index.
 *
 * We are using raw pointers instead of std::vector to avoid loosing
 * 2*sizeof(size_t) bytes to store the capacity and size of the vector in each
 * sparse_array. We know we can only store up to BITMAP_NB_BITS elements in the
 * array, we don't need such big types.
 *
 *
 * T must be nothrow move constructible and/or copy constructible.
 * Behaviour is undefined if the destructor of T throws an exception.
 *
 * See https://smerity.com/articles/2015/google_sparsehash.html for details on
 * the idea behinds the implementation.
 *
 * TODO Check to use std::realloc and std::memmove when possible
 */
template <typename T, typename Allocator, tsl::sh::sparsity Sparsity>
class sparse_array {
 public:
  using value_type = T;
  using size_type = std::uint_least8_t;
  using allocator_type = Allocator;
  using iterator = value_type *;
  using const_iterator = const value_type *;

 private:
  static const size_type CAPACITY_GROWTH_STEP =
      (Sparsity == tsl::sh::sparsity::high) ? 2
      : (Sparsity == tsl::sh::sparsity::medium)
          ? 4
          : 8;  // (Sparsity == tsl::sh::sparsity::low)

  /**
   * Bitmap size configuration.
   * Use 32 bits for the bitmap on 32-bits or less environnement as popcount on
   * 64 bits numbers is slow on these environnement. Use 64 bits bitmap
   * otherwise.
   */
#if SIZE_MAX <= UINT32_MAX
  using bitmap_type = std::uint_least32_t;
  static const std::size_t BITMAP_NB_BITS = 32;
  static const std::size_t BUCKET_SHIFT = 5;
#else
  using bitmap_type = std::uint_least64_t;
  static const std::size_t BITMAP_NB_BITS = 64;
  static const std::size_t BUCKET_SHIFT = 6;
#endif

  static const std::size_t BUCKET_MASK = BITMAP_NB_BITS - 1;

  static_assert(is_power_of_two(BITMAP_NB_BITS),
                "BITMAP_NB_BITS must be a power of two.");
  static_assert(std::numeric_limits<bitmap_type>::digits >= BITMAP_NB_BITS,
                "bitmap_type must be able to hold at least BITMAP_NB_BITS.");
  static_assert((std::size_t(1) << BUCKET_SHIFT) == BITMAP_NB_BITS,
                "(1 << BUCKET_SHIFT) must be equal to BITMAP_NB_BITS.");
  static_assert(std::numeric_limits<size_type>::max() >= BITMAP_NB_BITS,
                "size_type must be big enough to hold BITMAP_NB_BITS.");
  static_assert(std::is_unsigned<bitmap_type>::value,
                "bitmap_type must be unsigned.");
  static_assert((std::numeric_limits<bitmap_type>::max() & BUCKET_MASK) ==
                    BITMAP_NB_BITS - 1,
                "");

 public:
  /**
   * Map an ibucket [0, bucket_count) in the hash table to a sparse_ibucket
   * (a sparse_array holds multiple buckets, so there is less sparse_array than
   * bucket_count).
   *
   * The bucket ibucket is in
   * m_sparse_buckets[sparse_ibucket(ibucket)][index_in_sparse_bucket(ibucket)]
   * instead of something like m_buckets[ibucket] in a classical hash table.
   */
  static std::size_t sparse_ibucket(std::size_t ibucket) {
    return ibucket >> BUCKET_SHIFT;
  }

  /**
   * Map an ibucket [0, bucket_count) in the hash table to an index in the
   * sparse_array which corresponds to the bucket.
   *
   * The bucket ibucket is in
   * m_sparse_buckets[sparse_ibucket(ibucket)][index_in_sparse_bucket(ibucket)]
   * instead of something like m_buckets[ibucket] in a classical hash table.
   */
  static typename sparse_array::size_type index_in_sparse_bucket(
      std::size_t ibucket) {
    return static_cast<typename sparse_array::size_type>(
        ibucket & sparse_array::BUCKET_MASK);
  }

  static std::size_t nb_sparse_buckets(std::size_t bucket_count) noexcept {
    if (bucket_count == 0) {
      return 0;
    }

    return std::max<std::size_t>(
        1, sparse_ibucket(tsl::detail_sparse_hash::round_up_to_power_of_two(
               bucket_count)));
  }

 public:
  sparse_array() noexcept
      : m_values(nullptr),
        m_bitmap_vals(0),
        m_bitmap_deleted_vals(0),
        m_nb_elements(0),
        m_capacity(0),
        m_last_array(false) {}

  explicit sparse_array(bool last_bucket) noexcept
      : m_values(nullptr),
        m_bitmap_vals(0),
        m_bitmap_deleted_vals(0),
        m_nb_elements(0),
        m_capacity(0),
        m_last_array(last_bucket) {}

  sparse_array(size_type capacity, Allocator &alloc)
      : m_values(nullptr),
        m_bitmap_vals(0),
        m_bitmap_deleted_vals(0),
        m_nb_elements(0),
        m_capacity(capacity),
        m_last_array(false) {
    if (m_capacity > 0) {
      m_values = alloc.allocate(m_capacity);
      tsl_sh_assert(m_values !=
                    nullptr);  // allocate should throw if there is a failure
    }
  }

  sparse_array(const sparse_array &other, Allocator &alloc)
      : m_values(nullptr),
        m_bitmap_vals(other.m_bitmap_vals),
        m_bitmap_deleted_vals(other.m_bitmap_deleted_vals),
        m_nb_elements(0),
        m_capacity(other.m_capacity),
        m_last_array(other.m_last_array) {
    tsl_sh_assert(other.m_capacity >= other.m_nb_elements);
    if (m_capacity == 0) {
      return;
    }

    m_values = alloc.allocate(m_capacity);
    tsl_sh_assert(m_values !=
                  nullptr);  // allocate should throw if there is a failure
    TSL_SH_TRY {
      for (size_type i = 0; i < other.m_nb_elements; i++) {
        construct_value(alloc, m_values + i, other.m_values[i]);
        m_nb_elements++;
      }
    }
    TSL_SH_CATCH(...) {
      clear(alloc);
      TSL_SH_RETRHOW;
    }
  }

  sparse_array(sparse_array &&other) noexcept
      : m_values(other.m_values),
        m_bitmap_vals(other.m_bitmap_vals),
        m_bitmap_deleted_vals(other.m_bitmap_deleted_vals),
        m_nb_elements(other.m_nb_elements),
        m_capacity(other.m_capacity),
        m_last_array(other.m_last_array) {
    other.m_values = nullptr;
    other.m_bitmap_vals = 0;
    other.m_bitmap_deleted_vals = 0;
    other.m_nb_elements = 0;
    other.m_capacity = 0;
  }

  sparse_array(sparse_array &&other, Allocator &alloc)
      : m_values(nullptr),
        m_bitmap_vals(other.m_bitmap_vals),
        m_bitmap_deleted_vals(other.m_bitmap_deleted_vals),
        m_nb_elements(0),
        m_capacity(other.m_capacity),
        m_last_array(other.m_last_array) {
    tsl_sh_assert(other.m_capacity >= other.m_nb_elements);
    if (m_capacity == 0) {
      return;
    }

    m_values = alloc.allocate(m_capacity);
    tsl_sh_assert(m_values !=
                  nullptr);  // allocate should throw if there is a failure
    TSL_SH_TRY {
      for (size_type i = 0; i < other.m_nb_elements; i++) {
        construct_value(alloc, m_values + i, std::move(other.m_values[i]));
        m_nb_elements++;
      }
    }
    TSL_SH_CATCH(...) {
      clear(alloc);
      TSL_SH_RETRHOW;
    }
  }

  sparse_array &operator=(const sparse_array &) = delete;
  sparse_array &operator=(sparse_array &&) = delete;

  ~sparse_array() noexcept {
    // The code that manages the sparse_array must have called clear before
    // destruction. See documentation of sparse_array for more details.
    tsl_sh_assert(m_capacity == 0 && m_nb_elements == 0 && m_values == nullptr);
  }

  iterator begin() noexcept { return m_values; }
  iterator end() noexcept { return m_values + m_nb_elements; }
  const_iterator begin() const noexcept { return cbegin(); }
  const_iterator end() const noexcept { return cend(); }
  const_iterator cbegin() const noexcept { return m_values; }
  const_iterator cend() const noexcept { return m_values + m_nb_elements; }

  bool empty() const noexcept { return m_nb_elements == 0; }

  size_type size() const noexcept { return m_nb_elements; }

  void clear(allocator_type &alloc) noexcept {
    destroy_and_deallocate_values(alloc, m_values, m_nb_elements, m_capacity);

    m_values = nullptr;
    m_bitmap_vals = 0;
    m_bitmap_deleted_vals = 0;
    m_nb_elements = 0;
    m_capacity = 0;
  }

  bool last() const noexcept { return m_last_array; }

  void set_as_last() noexcept { m_last_array = true; }

  bool has_value(size_type index) const noexcept {
    tsl_sh_assert(index < BITMAP_NB_BITS);
    return (m_bitmap_vals & (bitmap_type(1) << index)) != 0;
  }

  bool has_deleted_value(size_type index) const noexcept {
    tsl_sh_assert(index < BITMAP_NB_BITS);
    return (m_bitmap_deleted_vals & (bitmap_type(1) << index)) != 0;
  }

  iterator value(size_type index) noexcept {
    tsl_sh_assert(has_value(index));
    return m_values + index_to_offset(index);
  }

  const_iterator value(size_type index) const noexcept {
    tsl_sh_assert(has_value(index));
    return m_values + index_to_offset(index);
  }

  /**
   * Return iterator to set value.
   */
  template <typename... Args>
  iterator set(allocator_type &alloc, size_type index, Args &&...value_args) {
    tsl_sh_assert(!has_value(index));

    const size_type offset = index_to_offset(index);
    insert_at_offset(alloc, offset, std::forward<Args>(value_args)...);

    m_bitmap_vals = (m_bitmap_vals | (bitmap_type(1) << index));
    m_bitmap_deleted_vals =
        (m_bitmap_deleted_vals & ~(bitmap_type(1) << index));

    m_nb_elements++;

    tsl_sh_assert(has_value(index));
    tsl_sh_assert(!has_deleted_value(index));

    return m_values + offset;
  }

  iterator erase(allocator_type &alloc, iterator position) {
    const size_type offset =
        static_cast<size_type>(std::distance(begin(), position));
    return erase(alloc, position, offset_to_index(offset));
  }

  // Return the next value or end if no next value
  iterator erase(allocator_type &alloc, iterator position, size_type index) {
    tsl_sh_assert(has_value(index));
    tsl_sh_assert(!has_deleted_value(index));

    const size_type offset =
        static_cast<size_type>(std::distance(begin(), position));
    erase_at_offset(alloc, offset);

    m_bitmap_vals = (m_bitmap_vals & ~(bitmap_type(1) << index));
    m_bitmap_deleted_vals = (m_bitmap_deleted_vals | (bitmap_type(1) << index));

    m_nb_elements--;

    tsl_sh_assert(!has_value(index));
    tsl_sh_assert(has_deleted_value(index));

    return m_values + offset;
  }

  void swap(sparse_array &other) {
    using std::swap;

    swap(m_values, other.m_values);
    swap(m_bitmap_vals, other.m_bitmap_vals);
    swap(m_bitmap_deleted_vals, other.m_bitmap_deleted_vals);
    swap(m_nb_elements, other.m_nb_elements);
    swap(m_capacity, other.m_capacity);
    swap(m_last_array, other.m_last_array);
  }

  static iterator mutable_iterator(const_iterator pos) {
    return const_cast<iterator>(pos);
  }

  template <class Serializer>
  void serialize(Serializer &serializer) const {
    const slz_size_type sparse_bucket_size = m_nb_elements;
    serializer(sparse_bucket_size);

    const slz_size_type bitmap_vals = m_bitmap_vals;
    serializer(bitmap_vals);

    const slz_size_type bitmap_deleted_vals = m_bitmap_deleted_vals;
    serializer(bitmap_deleted_vals);

    for (const value_type &value : *this) {
      serializer(value);
    }
  }

  template <class Deserializer>
  static sparse_array deserialize_hash_compatible(Deserializer &deserializer,
                                                  Allocator &alloc) {
    const slz_size_type sparse_bucket_size =
        deserialize_value<slz_size_type>(deserializer);
    const slz_size_type bitmap_vals =
        deserialize_value<slz_size_type>(deserializer);
    const slz_size_type bitmap_deleted_vals =
        deserialize_value<slz_size_type>(deserializer);

    if (sparse_bucket_size > BITMAP_NB_BITS) {
      TSL_SH_THROW_OR_ABORT(
          std::runtime_error,
          "Deserialized sparse_bucket_size is too big for the platform. "
          "Maximum should be BITMAP_NB_BITS.");
    }

    sparse_array sarray;
    if (sparse_bucket_size == 0) {
      return sarray;
    }

    sarray.m_bitmap_vals = numeric_cast<bitmap_type>(
        bitmap_vals, "Deserialized bitmap_vals is too big.");
    sarray.m_bitmap_deleted_vals = numeric_cast<bitmap_type>(
        bitmap_deleted_vals, "Deserialized bitmap_deleted_vals is too big.");

    sarray.m_capacity = numeric_cast<size_type>(
        sparse_bucket_size, "Deserialized sparse_bucket_size is too big.");
    sarray.m_values = alloc.allocate(sarray.m_capacity);

    TSL_SH_TRY {
      for (size_type ivalue = 0; ivalue < sarray.m_capacity; ivalue++) {
        construct_value(alloc, sarray.m_values + ivalue,
                        deserialize_value<value_type>(deserializer));
        sarray.m_nb_elements++;
      }
    }
    TSL_SH_CATCH(...) {
      sarray.clear(alloc);
      TSL_SH_RETRHOW;
    }

    return sarray;
  }

  /**
   * Deserialize the values of the bucket and insert them all in sparse_hash
   * through sparse_hash.insert(...).
   */
  template <class Deserializer, class SparseHash>
  static void deserialize_values_into_sparse_hash(Deserializer &deserializer,
                                                  SparseHash &sparse_hash) {
    const slz_size_type sparse_bucket_size =
        deserialize_value<slz_size_type>(deserializer);

    const slz_size_type bitmap_vals =
        deserialize_value<slz_size_type>(deserializer);
    static_cast<void>(bitmap_vals);  // Ignore, not needed

    const slz_size_type bitmap_deleted_vals =
        deserialize_value<slz_size_type>(deserializer);
    static_cast<void>(bitmap_deleted_vals);  // Ignore, not needed

    for (slz_size_type ivalue = 0; ivalue < sparse_bucket_size; ivalue++) {
      sparse_hash.insert(deserialize_value<value_type>(deserializer));
    }
  }

 private:
  template <typename... Args>
  static void construct_value(allocator_type &alloc, value_type *value,
                              Args &&...value_args) {
    std::allocator_traits<allocator_type>::construct(
        alloc, value, std::forward<Args>(value_args)...);
  }

  static void destroy_value(allocator_type &alloc, value_type *value) noexcept {
    std::allocator_traits<allocator_type>::destroy(alloc, value);
  }

  static void destroy_and_deallocate_values(
      allocator_type &alloc, value_type *values, size_type nb_values,
      size_type capacity_values) noexcept {
    for (size_type i = 0; i < nb_values; i++) {
      destroy_value(alloc, values + i);
    }

    alloc.deallocate(values, capacity_values);
  }

  static size_type popcount(bitmap_type val) noexcept {
    if (sizeof(bitmap_type) <= sizeof(unsigned int)) {
      return static_cast<size_type>(
          tsl::detail_popcount::popcount(static_cast<unsigned int>(val)));
    } else {
      return static_cast<size_type>(tsl::detail_popcount::popcountll(val));
    }
  }

  size_type index_to_offset(size_type index) const noexcept {
    tsl_sh_assert(index < BITMAP_NB_BITS);
    return popcount(m_bitmap_vals &
                    ((bitmap_type(1) << index) - bitmap_type(1)));
  }

  // TODO optimize
  size_type offset_to_index(size_type offset) const noexcept {
    tsl_sh_assert(offset < m_nb_elements);

    bitmap_type bitmap_vals = m_bitmap_vals;
    size_type index = 0;
    size_type nb_ones = 0;

    while (bitmap_vals != 0) {
      if ((bitmap_vals & 0x1) == 1) {
        if (nb_ones == offset) {
          break;
        }

        nb_ones++;
      }

      index++;
      bitmap_vals = bitmap_vals >> 1;
    }

    return index;
  }

  size_type next_capacity() const noexcept {
    return static_cast<size_type>(m_capacity + CAPACITY_GROWTH_STEP);
  }

  /**
   * Insertion
   *
   * Two situations:
   * - Either we are in a situation where
   * std::is_nothrow_move_constructible<value_type>::value is true. In this
   * case, on insertion we just reallocate m_values when we reach its capacity
   * (i.e. m_nb_elements == m_capacity), otherwise we just put the new value at
   * its appropriate place. We can easily keep the strong exception guarantee as
   * moving the values around is safe.
   * - Otherwise we are in a situation where
   * std::is_nothrow_move_constructible<value_type>::value is false. In this
   * case on EACH insertion we allocate a new area of m_nb_elements + 1 where we
   * copy the values of m_values into it and put the new value there. On
   * success, we set m_values to this new area. Even if slower, it's the only
   * way to preserve to strong exception guarantee.
   */
  template <typename... Args, typename U = value_type,
            typename std::enable_if<
                std::is_nothrow_move_constructible<U>::value>::type * = nullptr>
  void insert_at_offset(allocator_type &alloc, size_type offset,
                        Args &&...value_args) {
    if (m_nb_elements < m_capacity) {
      insert_at_offset_no_realloc(alloc, offset,
                                  std::forward<Args>(value_args)...);
    } else {
      insert_at_offset_realloc(alloc, offset, next_capacity(),
                               std::forward<Args>(value_args)...);
    }
  }

  template <typename... Args, typename U = value_type,
            typename std::enable_if<!std::is_nothrow_move_constructible<
                U>::value>::type * = nullptr>
  void insert_at_offset(allocator_type &alloc, size_type offset,
                        Args &&...value_args) {
    insert_at_offset_realloc(alloc, offset, m_nb_elements + 1,
                             std::forward<Args>(value_args)...);
  }

  template <typename... Args, typename U = value_type,
            typename std::enable_if<
                std::is_nothrow_move_constructible<U>::value>::type * = nullptr>
  void insert_at_offset_no_realloc(allocator_type &alloc, size_type offset,
                                   Args &&...value_args) {
    tsl_sh_assert(offset <= m_nb_elements);
    tsl_sh_assert(m_nb_elements < m_capacity);

    for (size_type i = m_nb_elements; i > offset; i--) {
      construct_value(alloc, m_values + i, std::move(m_values[i - 1]));
      destroy_value(alloc, m_values + i - 1);
    }

    TSL_SH_TRY {
      construct_value(alloc, m_values + offset,
                      std::forward<Args>(value_args)...);
    }
    TSL_SH_CATCH(...) {
      for (size_type i = offset; i < m_nb_elements; i++) {
        construct_value(alloc, m_values + i, std::move(m_values[i + 1]));
        destroy_value(alloc, m_values + i + 1);
      }
      TSL_SH_RETRHOW;
    }
  }

  template <typename... Args, typename U = value_type,
            typename std::enable_if<
                std::is_nothrow_move_constructible<U>::value>::type * = nullptr>
  void insert_at_offset_realloc(allocator_type &alloc, size_type offset,
                                size_type new_capacity, Args &&...value_args) {
    tsl_sh_assert(new_capacity > m_nb_elements);

    value_type *new_values = alloc.allocate(new_capacity);
    // Allocate should throw if there is a failure
    tsl_sh_assert(new_values != nullptr);

    TSL_SH_TRY {
      construct_value(alloc, new_values + offset,
                      std::forward<Args>(value_args)...);
    }
    TSL_SH_CATCH(...) {
      alloc.deallocate(new_values, new_capacity);
      TSL_SH_RETRHOW;
    }

    // Should not throw from here
    for (size_type i = 0; i < offset; i++) {
      construct_value(alloc, new_values + i, std::move(m_values[i]));
    }

    for (size_type i = offset; i < m_nb_elements; i++) {
      construct_value(alloc, new_values + i + 1, std::move(m_values[i]));
    }

    destroy_and_deallocate_values(alloc, m_values, m_nb_elements, m_capacity);

    m_values = new_values;
    m_capacity = new_capacity;
  }

  template <typename... Args, typename U = value_type,
            typename std::enable_if<!std::is_nothrow_move_constructible<
                U>::value>::type * = nullptr>
  void insert_at_offset_realloc(allocator_type &alloc, size_type offset,
                                size_type new_capacity, Args &&...value_args) {
    tsl_sh_assert(new_capacity > m_nb_elements);

    value_type *new_values = alloc.allocate(new_capacity);
    // Allocate should throw if there is a failure
    tsl_sh_assert(new_values != nullptr);

    size_type nb_new_values = 0;
    TSL_SH_TRY {
      for (size_type i = 0; i < offset; i++) {
        construct_value(alloc, new_values + i, m_values[i]);
        nb_new_values++;
      }

      construct_value(alloc, new_values + offset,
                      std::forward<Args>(value_args)...);
      nb_new_values++;

      for (size_type i = offset; i < m_nb_elements; i++) {
        construct_value(alloc, new_values + i + 1, m_values[i]);
        nb_new_values++;
      }
    }
    TSL_SH_CATCH(...) {
      destroy_and_deallocate_values(alloc, new_values, nb_new_values,
                                    new_capacity);
      TSL_SH_RETRHOW;
    }

    tsl_sh_assert(nb_new_values == m_nb_elements + 1);

    destroy_and_deallocate_values(alloc, m_values, m_nb_elements, m_capacity);

    m_values = new_values;
    m_capacity = new_capacity;
  }

  /**
   * Erasure
   *
   * Two situations:
   * - Either we are in a situation where
   * std::is_nothrow_move_constructible<value_type>::value is true. Simply
   * destroy the value and left-shift move the value on the right of offset.
   * - Otherwise we are in a situation where
   * std::is_nothrow_move_constructible<value_type>::value is false. Copy all
   * the values except the one at offset into a new heap area. On success, we
   * set m_values to this new area. Even if slower, it's the only way to
   * preserve to strong exception guarantee.
   */
  template <typename... Args, typename U = value_type,
            typename std::enable_if<
                std::is_nothrow_move_constructible<U>::value>::type * = nullptr>
  void erase_at_offset(allocator_type &alloc, size_type offset) noexcept {
    tsl_sh_assert(offset < m_nb_elements);

    destroy_value(alloc, m_values + offset);

    for (size_type i = offset + 1; i < m_nb_elements; i++) {
      construct_value(alloc, m_values + i - 1, std::move(m_values[i]));
      destroy_value(alloc, m_values + i);
    }
  }

  template <typename... Args, typename U = value_type,
            typename std::enable_if<!std::is_nothrow_move_constructible<
                U>::value>::type * = nullptr>
  void erase_at_offset(allocator_type &alloc, size_type offset) {
    tsl_sh_assert(offset < m_nb_elements);

    // Erasing the last element, don't need to reallocate. We keep the capacity.
    if (offset + 1 == m_nb_elements) {
      destroy_value(alloc, m_values + offset);
      return;
    }

    tsl_sh_assert(m_nb_elements > 1);
    const size_type new_capacity = m_nb_elements - 1;

    value_type *new_values = alloc.allocate(new_capacity);
    // Allocate should throw if there is a failure
    tsl_sh_assert(new_values != nullptr);

    size_type nb_new_values = 0;
    TSL_SH_TRY {
      for (size_type i = 0; i < m_nb_elements; i++) {
        if (i != offset) {
          construct_value(alloc, new_values + nb_new_values, m_values[i]);
          nb_new_values++;
        }
      }
    }
    TSL_SH_CATCH(...) {
      destroy_and_deallocate_values(alloc, new_values, nb_new_values,
                                    new_capacity);
      TSL_SH_RETRHOW;
    }

    tsl_sh_assert(nb_new_values == m_nb_elements - 1);

    destroy_and_deallocate_values(alloc, m_values, m_nb_elements, m_capacity);

    m_values = new_values;
    m_capacity = new_capacity;
  }

 private:
  value_type *m_values;

  bitmap_type m_bitmap_vals;
  bitmap_type m_bitmap_deleted_vals;

  size_type m_nb_elements;
  size_type m_capacity;
  bool m_last_array;
};

/**
 * Internal common class used by `sparse_map` and `sparse_set`.
 *
 * `ValueType` is what will be stored by `sparse_hash` (usually `std::pair<Key,
 * T>` for map and `Key` for set).
 *
 * `KeySelect` should be a `FunctionObject` which takes a `ValueType` in
 * parameter and returns a reference to the key.
 *
 * `ValueSelect` should be a `FunctionObject` which takes a `ValueType` in
 * parameter and returns a reference to the value. `ValueSelect` should be void
 * if there is no value (in a set for example).
 *
 * The strong exception guarantee only holds if `ExceptionSafety` is set to
 * `tsl::sh::exception_safety::strong`.
 *
 * `ValueType` must be nothrow move constructible and/or copy constructible.
 * Behaviour is undefined if the destructor of `ValueType` throws.
 *
 *
 * The class holds its buckets in a 2-dimensional fashion. Instead of having a
 * linear `std::vector<bucket>` for [0, bucket_count) where each bucket stores
 * one value, we have a `std::vector<sparse_array>` (m_sparse_buckets_data)
 * where each `sparse_array` stores multiple values (up to
 * `sparse_array::BITMAP_NB_BITS`). To convert a one dimensional `ibucket`
 * position to a position in `std::vector<sparse_array>` and a position in
 * `sparse_array`, use respectively the methods
 * `sparse_array::sparse_ibucket(ibucket)` and
 * `sparse_array::index_in_sparse_bucket(ibucket)`.
 */
template <class ValueType, class KeySelect, class ValueSelect, class Hash,
          class KeyEqual, class Allocator, class GrowthPolicy,
          tsl::sh::exception_safety ExceptionSafety, tsl::sh::sparsity Sparsity,
          tsl::sh::probing Probing>
class sparse_hash : private Allocator,
                    private Hash,
                    private KeyEqual,
                    private GrowthPolicy {
 private:
  template <typename U>
  using has_mapped_type =
      typename std::integral_constant<bool, !std::is_same<U, void>::value>;

  static_assert(
      noexcept(std::declval<GrowthPolicy>().bucket_for_hash(std::size_t(0))),
      "GrowthPolicy::bucket_for_hash must be noexcept.");
  static_assert(noexcept(std::declval<GrowthPolicy>().clear()),
                "GrowthPolicy::clear must be noexcept.");

 public:
  template <bool IsConst>
  class sparse_iterator;

  using key_type = typename KeySelect::key_type;
  using value_type = ValueType;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using hasher = Hash;
  using key_equal = KeyEqual;
  using allocator_type = Allocator;
  using reference = value_type &;
  using const_reference = const value_type &;
  using pointer = value_type *;
  using const_pointer = const value_type *;
  using iterator = sparse_iterator<false>;
  using const_iterator = sparse_iterator<true>;

 private:
  using sparse_array =
      tsl::detail_sparse_hash::sparse_array<ValueType, Allocator, Sparsity>;

  using sparse_buckets_allocator = typename std::allocator_traits<
      allocator_type>::template rebind_alloc<sparse_array>;
  using sparse_buckets_container =
      std::vector<sparse_array, sparse_buckets_allocator>;

 public:
  /**
   * The `operator*()` and `operator->()` methods return a const reference and
   * const pointer respectively to the stored value type (`Key` for a set,
   * `std::pair<Key, T>` for a map).
   *
   * In case of a map, to get a mutable reference to the value `T` associated to
   * a key (the `.second` in the stored pair), you have to call `value()`.
   */
  template <bool IsConst>
  class sparse_iterator {
    friend class sparse_hash;

   private:
    using sparse_bucket_iterator = typename std::conditional<
        IsConst, typename sparse_buckets_container::const_iterator,
        typename sparse_buckets_container::iterator>::type;

    using sparse_array_iterator =
        typename std::conditional<IsConst,
                                  typename sparse_array::const_iterator,
                                  typename sparse_array::iterator>::type;

    /**
     * sparse_array_it should be nullptr if sparse_bucket_it ==
     * m_sparse_buckets_data.end(). (TODO better way?)
     */
    sparse_iterator(sparse_bucket_iterator sparse_bucket_it,
                    sparse_array_iterator sparse_array_it)
        : m_sparse_buckets_it(sparse_bucket_it),
          m_sparse_array_it(sparse_array_it) {}

   public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = const typename sparse_hash::value_type;
    using difference_type = std::ptrdiff_t;
    using reference = value_type &;
    using pointer = value_type *;

    sparse_iterator() noexcept {}

    // Copy constructor from iterator to const_iterator.
    template <bool TIsConst = IsConst,
              typename std::enable_if<TIsConst>::type * = nullptr>
    sparse_iterator(const sparse_iterator<!TIsConst> &other) noexcept
        : m_sparse_buckets_it(other.m_sparse_buckets_it),
          m_sparse_array_it(other.m_sparse_array_it) {}

    sparse_iterator(const sparse_iterator &other) = default;
    sparse_iterator(sparse_iterator &&other) = default;
    sparse_iterator &operator=(const sparse_iterator &other) = default;
    sparse_iterator &operator=(sparse_iterator &&other) = default;

    const typename sparse_hash::key_type &key() const {
      return KeySelect()(*m_sparse_array_it);
    }

    template <class U = ValueSelect,
              typename std::enable_if<has_mapped_type<U>::value &&
                                      IsConst>::type * = nullptr>
    const typename U::value_type &value() const {
      return U()(*m_sparse_array_it);
    }

    template <class U = ValueSelect,
              typename std::enable_if<has_mapped_type<U>::value &&
                                      !IsConst>::type * = nullptr>
    typename U::value_type &value() {
      return U()(*m_sparse_array_it);
    }

    reference operator*() const { return *m_sparse_array_it; }

    pointer operator->() const { return std::addressof(*m_sparse_array_it); }

    sparse_iterator &operator++() {
      tsl_sh_assert(m_sparse_array_it != nullptr);
      ++m_sparse_array_it;

      if (m_sparse_array_it == m_sparse_buckets_it->end()) {
        do {
          if (m_sparse_buckets_it->last()) {
            ++m_sparse_buckets_it;
            m_sparse_array_it = nullptr;
            return *this;
          }

          ++m_sparse_buckets_it;
        } while (m_sparse_buckets_it->empty());

        m_sparse_array_it = m_sparse_buckets_it->begin();
      }

      return *this;
    }

    sparse_iterator operator++(int) {
      sparse_iterator tmp(*this);
      ++*this;

      return tmp;
    }

    friend bool operator==(const sparse_iterator &lhs,
                           const sparse_iterator &rhs) {
      return lhs.m_sparse_buckets_it == rhs.m_sparse_buckets_it &&
             lhs.m_sparse_array_it == rhs.m_sparse_array_it;
    }

    friend bool operator!=(const sparse_iterator &lhs,
                           const sparse_iterator &rhs) {
      return !(lhs == rhs);
    }

   private:
    sparse_bucket_iterator m_sparse_buckets_it;
    sparse_array_iterator m_sparse_array_it;
  };

 public:
  sparse_hash(size_type bucket_count, const Hash &hash, const KeyEqual &equal,
              const Allocator &alloc, float max_load_factor)
      : Allocator(alloc),
        Hash(hash),
        KeyEqual(equal),
        GrowthPolicy(bucket_count),
        m_sparse_buckets_data(alloc),
        m_sparse_buckets(static_empty_sparse_bucket_ptr()),
        m_bucket_count(bucket_count),
        m_nb_elements(0),
        m_nb_deleted_buckets(0) {
    if (m_bucket_count > max_bucket_count()) {
      TSL_SH_THROW_OR_ABORT(std::length_error,
                            "The map exceeds its maximum size.");
    }

    if (m_bucket_count > 0) {
      /*
       * We can't use the `vector(size_type count, const Allocator& alloc)`
       * constructor as it's only available in C++14 and we need to support
       * C++11. We thus must resize after using the `vector(const Allocator&
       * alloc)` constructor.
       *
       * We can't use `vector(size_type count, const T& value, const Allocator&
       * alloc)` as it requires the value T to be copyable.
       */
      m_sparse_buckets_data.resize(
          sparse_array::nb_sparse_buckets(bucket_count));
      m_sparse_buckets = m_sparse_buckets_data.data();

      tsl_sh_assert(!m_sparse_buckets_data.empty());
      m_sparse_buckets_data.back().set_as_last();
    }

    this->max_load_factor(max_load_factor);

    // Check in the constructor instead of outside of a function to avoid
    // compilation issues when value_type is not complete.
    static_assert(std::is_nothrow_move_constructible<value_type>::value ||
                      std::is_copy_constructible<value_type>::value,
                  "Key, and T if present, must be nothrow move constructible "
                  "and/or copy constructible.");
  }

  ~sparse_hash() { clear(); }

  sparse_hash(const sparse_hash &other)
      : Allocator(std::allocator_traits<
                  Allocator>::select_on_container_copy_construction(other)),
        Hash(other),
        KeyEqual(other),
        GrowthPolicy(other),
        m_sparse_buckets_data(
            std::allocator_traits<
                Allocator>::select_on_container_copy_construction(other)),
        m_bucket_count(other.m_bucket_count),
        m_nb_elements(other.m_nb_elements),
        m_nb_deleted_buckets(other.m_nb_deleted_buckets),
        m_load_threshold_rehash(other.m_load_threshold_rehash),
        m_load_threshold_clear_deleted(other.m_load_threshold_clear_deleted),
        m_max_load_factor(other.m_max_load_factor) {
    copy_buckets_from(other),
        m_sparse_buckets = m_sparse_buckets_data.empty()
                               ? static_empty_sparse_bucket_ptr()
                               : m_sparse_buckets_data.data();
  }

  sparse_hash(sparse_hash &&other) noexcept(
      std::is_nothrow_move_constructible<Allocator>::value
          &&std::is_nothrow_move_constructible<Hash>::value
              &&std::is_nothrow_move_constructible<KeyEqual>::value
                  &&std::is_nothrow_move_constructible<GrowthPolicy>::value
                      &&std::is_nothrow_move_constructible<
                          sparse_buckets_container>::value)
      : Allocator(std::move(other)),
        Hash(std::move(other)),
        KeyEqual(std::move(other)),
        GrowthPolicy(std::move(other)),
        m_sparse_buckets_data(std::move(other.m_sparse_buckets_data)),
        m_sparse_buckets(m_sparse_buckets_data.empty()
                             ? static_empty_sparse_bucket_ptr()
                             : m_sparse_buckets_data.data()),
        m_bucket_count(other.m_bucket_count),
        m_nb_elements(other.m_nb_elements),
        m_nb_deleted_buckets(other.m_nb_deleted_buckets),
        m_load_threshold_rehash(other.m_load_threshold_rehash),
        m_load_threshold_clear_deleted(other.m_load_threshold_clear_deleted),
        m_max_load_factor(other.m_max_load_factor) {
    other.GrowthPolicy::clear();
    other.m_sparse_buckets_data.clear();
    other.m_sparse_buckets = static_empty_sparse_bucket_ptr();
    other.m_bucket_count = 0;
    other.m_nb_elements = 0;
    other.m_nb_deleted_buckets = 0;
    other.m_load_threshold_rehash = 0;
    other.m_load_threshold_clear_deleted = 0;
  }

  sparse_hash &operator=(const sparse_hash &other) {
    if (this != &other) {
      clear();

      if (std::allocator_traits<
              Allocator>::propagate_on_container_copy_assignment::value) {
        Allocator::operator=(other);
      }

      Hash::operator=(other);
      KeyEqual::operator=(other);
      GrowthPolicy::operator=(other);

      if (std::allocator_traits<
              Allocator>::propagate_on_container_copy_assignment::value) {
        m_sparse_buckets_data =
            sparse_buckets_container(static_cast<const Allocator &>(other));
      } else {
        if (m_sparse_buckets_data.size() !=
            other.m_sparse_buckets_data.size()) {
          m_sparse_buckets_data =
              sparse_buckets_container(static_cast<const Allocator &>(*this));
        } else {
          m_sparse_buckets_data.clear();
        }
      }

      copy_buckets_from(other);
      m_sparse_buckets = m_sparse_buckets_data.empty()
                             ? static_empty_sparse_bucket_ptr()
                             : m_sparse_buckets_data.data();

      m_bucket_count = other.m_bucket_count;
      m_nb_elements = other.m_nb_elements;
      m_nb_deleted_buckets = other.m_nb_deleted_buckets;
      m_load_threshold_rehash = other.m_load_threshold_rehash;
      m_load_threshold_clear_deleted = other.m_load_threshold_clear_deleted;
      m_max_load_factor = other.m_max_load_factor;
    }

    return *this;
  }

  sparse_hash &operator=(sparse_hash &&other) {
    clear();

    if (std::allocator_traits<
            Allocator>::propagate_on_container_move_assignment::value) {
      static_cast<Allocator &>(*this) =
          std::move(static_cast<Allocator &>(other));
      m_sparse_buckets_data = std::move(other.m_sparse_buckets_data);
    } else if (static_cast<Allocator &>(*this) !=
               static_cast<Allocator &>(other)) {
      move_buckets_from(std::move(other));
    } else {
      static_cast<Allocator &>(*this) =
          std::move(static_cast<Allocator &>(other));
      m_sparse_buckets_data = std::move(other.m_sparse_buckets_data);
    }

    m_sparse_buckets = m_sparse_buckets_data.empty()
                           ? static_empty_sparse_bucket_ptr()
                           : m_sparse_buckets_data.data();

    static_cast<Hash &>(*this) = std::move(static_cast<Hash &>(other));
    static_cast<KeyEqual &>(*this) = std::move(static_cast<KeyEqual &>(other));
    static_cast<GrowthPolicy &>(*this) =
        std::move(static_cast<GrowthPolicy &>(other));
    m_bucket_count = other.m_bucket_count;
    m_nb_elements = other.m_nb_elements;
    m_nb_deleted_buckets = other.m_nb_deleted_buckets;
    m_load_threshold_rehash = other.m_load_threshold_rehash;
    m_load_threshold_clear_deleted = other.m_load_threshold_clear_deleted;
    m_max_load_factor = other.m_max_load_factor;

    other.GrowthPolicy::clear();
    other.m_sparse_buckets_data.clear();
    other.m_sparse_buckets = static_empty_sparse_bucket_ptr();
    other.m_bucket_count = 0;
    other.m_nb_elements = 0;
    other.m_nb_deleted_buckets = 0;
    other.m_load_threshold_rehash = 0;
    other.m_load_threshold_clear_deleted = 0;

    return *this;
  }

  allocator_type get_allocator() const {
    return static_cast<const Allocator &>(*this);
  }

  /*
   * Iterators
   */
  iterator begin() noexcept {
    auto begin = m_sparse_buckets_data.begin();
    while (begin != m_sparse_buckets_data.end() && begin->empty()) {
      ++begin;
    }

    return iterator(begin, (begin != m_sparse_buckets_data.end())
                               ? begin->begin()
                               : nullptr);
  }

  const_iterator begin() const noexcept { return cbegin(); }

  const_iterator cbegin() const noexcept {
    auto begin = m_sparse_buckets_data.cbegin();
    while (begin != m_sparse_buckets_data.cend() && begin->empty()) {
      ++begin;
    }

    return const_iterator(begin, (begin != m_sparse_buckets_data.cend())
                                     ? begin->cbegin()
                                     : nullptr);
  }

  iterator end() noexcept {
    return iterator(m_sparse_buckets_data.end(), nullptr);
  }

  const_iterator end() const noexcept { return cend(); }

  const_iterator cend() const noexcept {
    return const_iterator(m_sparse_buckets_data.cend(), nullptr);
  }

  /*
   * Capacity
   */
  bool empty() const noexcept { return m_nb_elements == 0; }

  size_type size() const noexcept { return m_nb_elements; }

  size_type max_size() const noexcept {
    return std::min(std::allocator_traits<Allocator>::max_size(),
                    m_sparse_buckets_data.max_size());
  }

  /*
   * Modifiers
   */
  void clear() noexcept {
    for (auto &bucket : m_sparse_buckets_data) {
      bucket.clear(*this);
    }

    m_nb_elements = 0;
    m_nb_deleted_buckets = 0;
  }

  template <typename P>
  std::pair<iterator, bool> insert(P &&value) {
    return insert_impl(KeySelect()(value), std::forward<P>(value));
  }

  template <typename P>
  iterator insert_hint(const_iterator hint, P &&value) {
    if (hint != cend() &&
        compare_keys(KeySelect()(*hint), KeySelect()(value))) {
      return mutable_iterator(hint);
    }

    return insert(std::forward<P>(value)).first;
  }

  template <class InputIt>
  void insert(InputIt first, InputIt last) {
    if (std::is_base_of<
            std::forward_iterator_tag,
            typename std::iterator_traits<InputIt>::iterator_category>::value) {
      const auto nb_elements_insert = std::distance(first, last);
      const size_type nb_free_buckets = m_load_threshold_rehash - size();
      tsl_sh_assert(m_load_threshold_rehash >= size());

      if (nb_elements_insert > 0 &&
          nb_free_buckets < size_type(nb_elements_insert)) {
        reserve(size() + size_type(nb_elements_insert));
      }
    }

    for (; first != last; ++first) {
      insert(*first);
    }
  }

  template <class K, class M>
  std::pair<iterator, bool> insert_or_assign(K &&key, M &&obj) {
    auto it = try_emplace(std::forward<K>(key), std::forward<M>(obj));
    if (!it.second) {
      it.first.value() = std::forward<M>(obj);
    }

    return it;
  }

  template <class K, class M>
  iterator insert_or_assign(const_iterator hint, K &&key, M &&obj) {
    if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
      auto it = mutable_iterator(hint);
      it.value() = std::forward<M>(obj);

      return it;
    }

    return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
  }

  template <class... Args>
  std::pair<iterator, bool> emplace(Args &&...args) {
    return insert(value_type(std::forward<Args>(args)...));
  }

  template <class... Args>
  iterator emplace_hint(const_iterator hint, Args &&...args) {
    return insert_hint(hint, value_type(std::forward<Args>(args)...));
  }

  template <class K, class... Args>
  std::pair<iterator, bool> try_emplace(K &&key, Args &&...args) {
    return insert_impl(key, std::piecewise_construct,
                       std::forward_as_tuple(std::forward<K>(key)),
                       std::forward_as_tuple(std::forward<Args>(args)...));
  }

  template <class K, class... Args>
  iterator try_emplace_hint(const_iterator hint, K &&key, Args &&...args) {
    if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
      return mutable_iterator(hint);
    }

    return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
  }

  /**
   * Here to avoid `template<class K> size_type erase(const K& key)` being used
   * when we use an iterator instead of a const_iterator.
   */
  iterator erase(iterator pos) {
    tsl_sh_assert(pos != end() && m_nb_elements > 0);
    auto it_sparse_array_next =
        pos.m_sparse_buckets_it->erase(*this, pos.m_sparse_array_it);
    m_nb_elements--;
    m_nb_deleted_buckets++;

    if (it_sparse_array_next == pos.m_sparse_buckets_it->end()) {
      auto it_sparse_buckets_next = pos.m_sparse_buckets_it;
      do {
        ++it_sparse_buckets_next;
      } while (it_sparse_buckets_next != m_sparse_buckets_data.end() &&
               it_sparse_buckets_next->empty());

      if (it_sparse_buckets_next == m_sparse_buckets_data.end()) {
        return end();
      } else {
        return iterator(it_sparse_buckets_next,
                        it_sparse_buckets_next->begin());
      }
    } else {
      return iterator(pos.m_sparse_buckets_it, it_sparse_array_next);
    }
  }

  iterator erase(const_iterator pos) { return erase(mutable_iterator(pos)); }

  iterator erase(const_iterator first, const_iterator last) {
    if (first == last) {
      return mutable_iterator(first);
    }

    // TODO Optimize, could avoid the call to std::distance.
    const size_type nb_elements_to_erase =
        static_cast<size_type>(std::distance(first, last));
    auto to_delete = mutable_iterator(first);
    for (size_type i = 0; i < nb_elements_to_erase; i++) {
      to_delete = erase(to_delete);
    }

    return to_delete;
  }

  template <class K>
  size_type erase(const K &key) {
    return erase(key, hash_key(key));
  }

  template <class K>
  size_type erase(const K &key, std::size_t hash) {
    return erase_impl(key, hash);
  }

  void swap(sparse_hash &other) {
    using std::swap;

    if (std::allocator_traits<Allocator>::propagate_on_container_swap::value) {
      swap(static_cast<Allocator &>(*this), static_cast<Allocator &>(other));
    } else {
      tsl_sh_assert(static_cast<Allocator &>(*this) ==
                    static_cast<Allocator &>(other));
    }

    swap(static_cast<Hash &>(*this), static_cast<Hash &>(other));
    swap(static_cast<KeyEqual &>(*this), static_cast<KeyEqual &>(other));
    swap(static_cast<GrowthPolicy &>(*this),
         static_cast<GrowthPolicy &>(other));
    swap(m_sparse_buckets_data, other.m_sparse_buckets_data);
    swap(m_sparse_buckets, other.m_sparse_buckets);
    swap(m_bucket_count, other.m_bucket_count);
    swap(m_nb_elements, other.m_nb_elements);
    swap(m_nb_deleted_buckets, other.m_nb_deleted_buckets);
    swap(m_load_threshold_rehash, other.m_load_threshold_rehash);
    swap(m_load_threshold_clear_deleted, other.m_load_threshold_clear_deleted);
    swap(m_max_load_factor, other.m_max_load_factor);
  }

  /*
   * Lookup
   */
  template <
      class K, class U = ValueSelect,
      typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
  typename U::value_type &at(const K &key) {
    return at(key, hash_key(key));
  }

  template <
      class K, class U = ValueSelect,
      typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
  typename U::value_type &at(const K &key, std::size_t hash) {
    return const_cast<typename U::value_type &>(
        static_cast<const sparse_hash *>(this)->at(key, hash));
  }

  template <
      class K, class U = ValueSelect,
      typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
  const typename U::value_type &at(const K &key) const {
    return at(key, hash_key(key));
  }

  template <
      class K, class U = ValueSelect,
      typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
  const typename U::value_type &at(const K &key, std::size_t hash) const {
    auto it = find(key, hash);
    if (it != cend()) {
      return it.value();
    } else {
      TSL_SH_THROW_OR_ABORT(std::out_of_range, "Couldn't find key.");
    }
  }

  template <
      class K, class U = ValueSelect,
      typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
  typename U::value_type &operator[](K &&key) {
    return try_emplace(std::forward<K>(key)).first.value();
  }

  template <class K>
  bool contains(const K &key) const {
    return contains(key, hash_key(key));
  }

  template <class K>
  bool contains(const K &key, std::size_t hash) const {
    return count(key, hash) != 0;
  }

  template <class K>
  size_type count(const K &key) const {
    return count(key, hash_key(key));
  }

  template <class K>
  size_type count(const K &key, std::size_t hash) const {
    if (find(key, hash) != cend()) {
      return 1;
    } else {
      return 0;
    }
  }

  template <class K>
  iterator find(const K &key) {
    return find_impl(key, hash_key(key));
  }

  template <class K>
  iterator find(const K &key, std::size_t hash) {
    return find_impl(key, hash);
  }

  template <class K>
  const_iterator find(const K &key) const {
    return find_impl(key, hash_key(key));
  }

  template <class K>
  const_iterator find(const K &key, std::size_t hash) const {
    return find_impl(key, hash);
  }

  template <class K>
  std::pair<iterator, iterator> equal_range(const K &key) {
    return equal_range(key, hash_key(key));
  }

  template <class K>
  std::pair<iterator, iterator> equal_range(const K &key, std::size_t hash) {
    iterator it = find(key, hash);
    return std::make_pair(it, (it == end()) ? it : std::next(it));
  }

  template <class K>
  std::pair<const_iterator, const_iterator> equal_range(const K &key) const {
    return equal_range(key, hash_key(key));
  }

  template <class K>
  std::pair<const_iterator, const_iterator> equal_range(
      const K &key, std::size_t hash) const {
    const_iterator it = find(key, hash);
    return std::make_pair(it, (it == cend()) ? it : std::next(it));
  }

  /*
   * Bucket interface
   */
  size_type bucket_count() const { return m_bucket_count; }

  size_type max_bucket_count() const {
    return m_sparse_buckets_data.max_size();
  }

  /*
   * Hash policy
   */
  float load_factor() const {
    if (bucket_count() == 0) {
      return 0;
    }

    return float(m_nb_elements) / float(bucket_count());
  }

  float max_load_factor() const { return m_max_load_factor; }

  void max_load_factor(float ml) {
    m_max_load_factor = std::max(0.1f, std::min(ml, 0.8f));
    m_load_threshold_rehash =
        size_type(float(bucket_count()) * m_max_load_factor);

    const float max_load_factor_with_deleted_buckets =
        m_max_load_factor + 0.5f * (1.0f - m_max_load_factor);
    tsl_sh_assert(max_load_factor_with_deleted_buckets > 0.0f &&
                  max_load_factor_with_deleted_buckets <= 1.0f);
    m_load_threshold_clear_deleted =
        size_type(float(bucket_count()) * max_load_factor_with_deleted_buckets);
  }

  void rehash(size_type count) {
    count = std::max(count,
                     size_type(std::ceil(float(size()) / max_load_factor())));
    rehash_impl(count);
  }

  void reserve(size_type count) {
    rehash(size_type(std::ceil(float(count) / max_load_factor())));
  }

  /*
   * Observers
   */
  hasher hash_function() const { return static_cast<const Hash &>(*this); }

  key_equal key_eq() const { return static_cast<const KeyEqual &>(*this); }

  /*
   * Other
   */
  iterator mutable_iterator(const_iterator pos) {
    auto it_sparse_buckets =
        m_sparse_buckets_data.begin() +
        std::distance(m_sparse_buckets_data.cbegin(), pos.m_sparse_buckets_it);

    return iterator(it_sparse_buckets,
                    sparse_array::mutable_iterator(pos.m_sparse_array_it));
  }

  template <class Serializer>
  void serialize(Serializer &serializer) const {
    serialize_impl(serializer);
  }

  template <class Deserializer>
  void deserialize(Deserializer &deserializer, bool hash_compatible) {
    deserialize_impl(deserializer, hash_compatible);
  }

 private:
  template <class K>
  std::size_t hash_key(const K &key) const {
    return Hash::operator()(key);
  }

  template <class K1, class K2>
  bool compare_keys(const K1 &key1, const K2 &key2) const {
    return KeyEqual::operator()(key1, key2);
  }

  size_type bucket_for_hash(std::size_t hash) const {
    const std::size_t bucket = GrowthPolicy::bucket_for_hash(hash);
    tsl_sh_assert(sparse_array::sparse_ibucket(bucket) <
                      m_sparse_buckets_data.size() ||
                  (bucket == 0 && m_sparse_buckets_data.empty()));

    return bucket;
  }

  template <class U = GrowthPolicy,
            typename std::enable_if<is_power_of_two_policy<U>::value>::type * =
                nullptr>
  size_type next_bucket(size_type ibucket, size_type iprobe) const {
    (void)iprobe;
    if (Probing == tsl::sh::probing::linear) {
      return (ibucket + 1) & this->m_mask;
    } else {
      tsl_sh_assert(Probing == tsl::sh::probing::quadratic);
      return (ibucket + iprobe) & this->m_mask;
    }
  }

  template <class U = GrowthPolicy,
            typename std::enable_if<!is_power_of_two_policy<U>::value>::type * =
                nullptr>
  size_type next_bucket(size_type ibucket, size_type iprobe) const {
    (void)iprobe;
    if (Probing == tsl::sh::probing::linear) {
      ibucket++;
      return (ibucket != bucket_count()) ? ibucket : 0;
    } else {
      tsl_sh_assert(Probing == tsl::sh::probing::quadratic);
      ibucket += iprobe;
      return (ibucket < bucket_count()) ? ibucket : ibucket % bucket_count();
    }
  }

  // TODO encapsulate m_sparse_buckets_data to avoid the managing the allocator
  void copy_buckets_from(const sparse_hash &other) {
    m_sparse_buckets_data.reserve(other.m_sparse_buckets_data.size());

    TSL_SH_TRY {
      for (const auto &bucket : other.m_sparse_buckets_data) {
        m_sparse_buckets_data.emplace_back(bucket,
                                           static_cast<Allocator &>(*this));
      }
    }
    TSL_SH_CATCH(...) {
      clear();
      TSL_SH_RETRHOW;
    }

    tsl_sh_assert(m_sparse_buckets_data.empty() ||
                  m_sparse_buckets_data.back().last());
  }

  void move_buckets_from(sparse_hash &&other) {
    m_sparse_buckets_data.reserve(other.m_sparse_buckets_data.size());

    TSL_SH_TRY {
      for (auto &&bucket : other.m_sparse_buckets_data) {
        m_sparse_buckets_data.emplace_back(std::move(bucket),
                                           static_cast<Allocator &>(*this));
      }
    }
    TSL_SH_CATCH(...) {
      clear();
      TSL_SH_RETRHOW;
    }

    tsl_sh_assert(m_sparse_buckets_data.empty() ||
                  m_sparse_buckets_data.back().last());
  }

  template <class K, class... Args>
  std::pair<iterator, bool> insert_impl(const K &key,
                                        Args &&...value_type_args) {
    /**
     * We must insert the value in the first empty or deleted bucket we find. If
     * we first find a deleted bucket, we still have to continue the search
     * until we find an empty bucket or until we have searched all the buckets
     * to be sure that the value is not in the hash table. We thus remember the
     * position, if any, of the first deleted bucket we have encountered so we
     * can insert it there if needed.
     */
    bool found_first_deleted_bucket = false;
    std::size_t sparse_ibucket_first_deleted = 0;
    typename sparse_array::size_type index_in_sparse_bucket_first_deleted = 0;

    const std::size_t hash = hash_key(key);
    std::size_t ibucket = bucket_for_hash(hash);

    std::size_t probe = 0;
    while (true) {
      std::size_t sparse_ibucket = sparse_array::sparse_ibucket(ibucket);
      auto index_in_sparse_bucket =
          sparse_array::index_in_sparse_bucket(ibucket);

      if (m_sparse_buckets[sparse_ibucket].has_value(index_in_sparse_bucket)) {
        auto value_it =
            m_sparse_buckets[sparse_ibucket].value(index_in_sparse_bucket);
        if (compare_keys(key, KeySelect()(*value_it))) {
          return std::make_pair(
              iterator(m_sparse_buckets_data.begin() + sparse_ibucket,
                       value_it),
              false);
        }
      } else if (m_sparse_buckets[sparse_ibucket].has_deleted_value(
                     index_in_sparse_bucket) &&
                 probe < m_bucket_count) {
        if (!found_first_deleted_bucket) {
          found_first_deleted_bucket = true;
          sparse_ibucket_first_deleted = sparse_ibucket;
          index_in_sparse_bucket_first_deleted = index_in_sparse_bucket;
        }
      } else {
        /**
         * At this point we are sure that the value does not exist
         * in the hash table.
         * First check if we satisfy load and delete thresholds, and if not,
         * rehash the hash table (and therefore start over). Otherwise, just
         * insert the value into the appropriate bucket.
         */
        if (size() >= m_load_threshold_rehash) {
          rehash_impl(GrowthPolicy::next_bucket_count());
          return insert_impl(key, std::forward<Args>(value_type_args)...);
        } else if (size() + m_nb_deleted_buckets >=
                   m_load_threshold_clear_deleted) {
          clear_deleted_buckets();
          return insert_impl(key, std::forward<Args>(value_type_args)...);
        }

        if (found_first_deleted_bucket) {
          auto it = insert_in_bucket(sparse_ibucket_first_deleted,
                                     index_in_sparse_bucket_first_deleted,
                                     std::forward<Args>(value_type_args)...);
          m_nb_deleted_buckets--;

          return it;
        }

        return insert_in_bucket(sparse_ibucket, index_in_sparse_bucket,
                                std::forward<Args>(value_type_args)...);
      }

      probe++;
      ibucket = next_bucket(ibucket, probe);
    }
  }

  template <class... Args>
  std::pair<iterator, bool> insert_in_bucket(
      std::size_t sparse_ibucket,
      typename sparse_array::size_type index_in_sparse_bucket,
      Args &&...value_type_args) {
    auto value_it = m_sparse_buckets[sparse_ibucket].set(
        *this, index_in_sparse_bucket, std::forward<Args>(value_type_args)...);
    m_nb_elements++;

    return std::make_pair(
        iterator(m_sparse_buckets_data.begin() + sparse_ibucket, value_it),
        true);
  }

  template <class K>
  size_type erase_impl(const K &key, std::size_t hash) {
    std::size_t ibucket = bucket_for_hash(hash);

    std::size_t probe = 0;
    while (true) {
      const std::size_t sparse_ibucket = sparse_array::sparse_ibucket(ibucket);
      const auto index_in_sparse_bucket =
          sparse_array::index_in_sparse_bucket(ibucket);

      if (m_sparse_buckets[sparse_ibucket].has_value(index_in_sparse_bucket)) {
        auto value_it =
            m_sparse_buckets[sparse_ibucket].value(index_in_sparse_bucket);
        if (compare_keys(key, KeySelect()(*value_it))) {
          m_sparse_buckets[sparse_ibucket].erase(*this, value_it,
                                                 index_in_sparse_bucket);
          m_nb_elements--;
          m_nb_deleted_buckets++;

          return 1;
        }
      } else if (!m_sparse_buckets[sparse_ibucket].has_deleted_value(
                     index_in_sparse_bucket) ||
                 probe >= m_bucket_count) {
        return 0;
      }

      probe++;
      ibucket = next_bucket(ibucket, probe);
    }
  }

  template <class K>
  iterator find_impl(const K &key, std::size_t hash) {
    return mutable_iterator(
        static_cast<const sparse_hash *>(this)->find(key, hash));
  }

  template <class K>
  const_iterator find_impl(const K &key, std::size_t hash) const {
    std::size_t ibucket = bucket_for_hash(hash);

    std::size_t probe = 0;
    while (true) {
      const std::size_t sparse_ibucket = sparse_array::sparse_ibucket(ibucket);
      const auto index_in_sparse_bucket =
          sparse_array::index_in_sparse_bucket(ibucket);

      if (m_sparse_buckets[sparse_ibucket].has_value(index_in_sparse_bucket)) {
        auto value_it =
            m_sparse_buckets[sparse_ibucket].value(index_in_sparse_bucket);
        if (compare_keys(key, KeySelect()(*value_it))) {
          return const_iterator(m_sparse_buckets_data.cbegin() + sparse_ibucket,
                                value_it);
        }
      } else if (!m_sparse_buckets[sparse_ibucket].has_deleted_value(
                     index_in_sparse_bucket) ||
                 probe >= m_bucket_count) {
        return cend();
      }

      probe++;
      ibucket = next_bucket(ibucket, probe);
    }
  }

  void clear_deleted_buckets() {
    // TODO could be optimized, we could do it in-place instead of allocating a
    // new bucket array.
    rehash_impl(m_bucket_count);
    tsl_sh_assert(m_nb_deleted_buckets == 0);
  }

  template <tsl::sh::exception_safety U = ExceptionSafety,
            typename std::enable_if<U == tsl::sh::exception_safety::basic>::type
                * = nullptr>
  void rehash_impl(size_type count) {
    sparse_hash new_table(count, static_cast<Hash &>(*this),
                          static_cast<KeyEqual &>(*this),
                          static_cast<Allocator &>(*this), m_max_load_factor);

    for (auto &bucket : m_sparse_buckets_data) {
      for (auto &val : bucket) {
        new_table.insert_on_rehash(std::move(val));
      }

      // TODO try to reuse some of the memory
      bucket.clear(*this);
    }

    new_table.swap(*this);
  }

  /**
   * TODO: For now we copy each element into the new map. We could move
   * them if they are nothrow_move_constructible without triggering
   * any exception if we reserve enough space in the sparse arrays beforehand.
   */
  template <tsl::sh::exception_safety U = ExceptionSafety,
            typename std::enable_if<
                U == tsl::sh::exception_safety::strong>::type * = nullptr>
  void rehash_impl(size_type count) {
    sparse_hash new_table(count, static_cast<Hash &>(*this),
                          static_cast<KeyEqual &>(*this),
                          static_cast<Allocator &>(*this), m_max_load_factor);

    for (const auto &bucket : m_sparse_buckets_data) {
      for (const auto &val : bucket) {
        new_table.insert_on_rehash(val);
      }
    }

    new_table.swap(*this);
  }

  template <typename K>
  void insert_on_rehash(K &&key_value) {
    const std::size_t hash = hash_key(KeySelect()(key_value));
    std::size_t ibucket = bucket_for_hash(hash);

    std::size_t probe = 0;
    while (true) {
      std::size_t sparse_ibucket = sparse_array::sparse_ibucket(ibucket);
      auto index_in_sparse_bucket =
          sparse_array::index_in_sparse_bucket(ibucket);

      if (!m_sparse_buckets[sparse_ibucket].has_value(index_in_sparse_bucket)) {
        m_sparse_buckets[sparse_ibucket].set(*this, index_in_sparse_bucket,
                                             std::forward<K>(key_value));
        m_nb_elements++;

        return;
      } else {
        tsl_sh_assert(
            !compare_keys(KeySelect()(key_value),
                          KeySelect()(*m_sparse_buckets[sparse_ibucket].value(
                              index_in_sparse_bucket))));
      }

      probe++;
      ibucket = next_bucket(ibucket, probe);
    }
  }

  template <class Serializer>
  void serialize_impl(Serializer &serializer) const {
    const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
    serializer(version);

    const slz_size_type bucket_count = m_bucket_count;
    serializer(bucket_count);

    const slz_size_type nb_sparse_buckets = m_sparse_buckets_data.size();
    serializer(nb_sparse_buckets);

    const slz_size_type nb_elements = m_nb_elements;
    serializer(nb_elements);

    const slz_size_type nb_deleted_buckets = m_nb_deleted_buckets;
    serializer(nb_deleted_buckets);

    const float max_load_factor = m_max_load_factor;
    serializer(max_load_factor);

    for (const auto &bucket : m_sparse_buckets_data) {
      bucket.serialize(serializer);
    }
  }

  template <class Deserializer>
  void deserialize_impl(Deserializer &deserializer, bool hash_compatible) {
    tsl_sh_assert(
        m_bucket_count == 0 &&
        m_sparse_buckets_data.empty());  // Current hash table must be empty

    const slz_size_type version =
        deserialize_value<slz_size_type>(deserializer);
    // For now we only have one version of the serialization protocol.
    // If it doesn't match there is a problem with the file.
    if (version != SERIALIZATION_PROTOCOL_VERSION) {
      TSL_SH_THROW_OR_ABORT(std::runtime_error,
                            "Can't deserialize the sparse_map/set. The "
                            "protocol version header is invalid.");
    }

    const slz_size_type bucket_count_ds =
        deserialize_value<slz_size_type>(deserializer);
    const slz_size_type nb_sparse_buckets =
        deserialize_value<slz_size_type>(deserializer);
    const slz_size_type nb_elements =
        deserialize_value<slz_size_type>(deserializer);
    const slz_size_type nb_deleted_buckets =
        deserialize_value<slz_size_type>(deserializer);
    const float max_load_factor = deserialize_value<float>(deserializer);

    if (!hash_compatible) {
      this->max_load_factor(max_load_factor);
      reserve(numeric_cast<size_type>(nb_elements,
                                      "Deserialized nb_elements is too big."));
      for (slz_size_type ibucket = 0; ibucket < nb_sparse_buckets; ibucket++) {
        sparse_array::deserialize_values_into_sparse_hash(deserializer, *this);
      }
    } else {
      m_bucket_count = numeric_cast<size_type>(
          bucket_count_ds, "Deserialized bucket_count is too big.");

      GrowthPolicy::operator=(GrowthPolicy(m_bucket_count));
      // GrowthPolicy should not modify the bucket count we got from
      // deserialization
      if (m_bucket_count != bucket_count_ds) {
        TSL_SH_THROW_OR_ABORT(std::runtime_error,
                              "The GrowthPolicy is not the same even though "
                              "hash_compatible is true.");
      }

      if (nb_sparse_buckets !=
          sparse_array::nb_sparse_buckets(m_bucket_count)) {
        TSL_SH_THROW_OR_ABORT(std::runtime_error,
                              "Deserialized nb_sparse_buckets is invalid.");
      }

      m_nb_elements = numeric_cast<size_type>(
          nb_elements, "Deserialized nb_elements is too big.");
      m_nb_deleted_buckets = numeric_cast<size_type>(
          nb_deleted_buckets, "Deserialized nb_deleted_buckets is too big.");

      m_sparse_buckets_data.reserve(numeric_cast<size_type>(
          nb_sparse_buckets, "Deserialized nb_sparse_buckets is too big."));
      for (slz_size_type ibucket = 0; ibucket < nb_sparse_buckets; ibucket++) {
        m_sparse_buckets_data.emplace_back(
            sparse_array::deserialize_hash_compatible(
                deserializer, static_cast<Allocator &>(*this)));
      }

      if (!m_sparse_buckets_data.empty()) {
        m_sparse_buckets_data.back().set_as_last();
        m_sparse_buckets = m_sparse_buckets_data.data();
      }

      this->max_load_factor(max_load_factor);
      if (load_factor() > this->max_load_factor()) {
        TSL_SH_THROW_OR_ABORT(
            std::runtime_error,
            "Invalid max_load_factor. Check that the serializer and "
            "deserializer support "
            "floats correctly as they can be converted implicitely to ints.");
      }
    }
  }

 public:
  static const size_type DEFAULT_INIT_BUCKET_COUNT = 0;
  static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.5f;

  /**
   * Protocol version currenlty used for serialization.
   */
  static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;

  /**
   * Return an always valid pointer to an static empty bucket_entry with
   * last_bucket() == true.
   */
  sparse_array *static_empty_sparse_bucket_ptr() {
    static sparse_array empty_sparse_bucket(true);
    return &empty_sparse_bucket;
  }

 private:
  sparse_buckets_container m_sparse_buckets_data;

  /**
   * Points to m_sparse_buckets_data.data() if !m_sparse_buckets_data.empty()
   * otherwise points to static_empty_sparse_bucket_ptr. This variable is useful
   * to avoid the cost of checking if m_sparse_buckets_data is empty when trying
   * to find an element.
   *
   * TODO Remove m_sparse_buckets_data and only use a pointer instead of a
   * pointer+vector to save some space in the sparse_hash object.
   */
  sparse_array *m_sparse_buckets;

  size_type m_bucket_count;
  size_type m_nb_elements;
  size_type m_nb_deleted_buckets;

  /**
   * Maximum that m_nb_elements can reach before a rehash occurs automatically
   * to grow the hash table.
   */
  size_type m_load_threshold_rehash;

  /**
   * Maximum that m_nb_elements + m_nb_deleted_buckets can reach before cleaning
   * up the buckets marked as deleted.
   */
  size_type m_load_threshold_clear_deleted;
  float m_max_load_factor;
};

}  // namespace detail_sparse_hash
}  // namespace tsl

#endif