//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H
#define SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <limits>
#include <ranges>
#include <vector>
#include <utility>

#include "../exception_safety_helpers.h"
#include "../from_range_helpers.h"
#include "../test_compare.h"
#include "../test_hash.h"
#include "MoveOnly.h"
#include "almost_satisfies_types.h"
#include "count_new.h"
#include "test_macros.h"

// template<container-compatible-range<value_type> R>
//   unordered-container(from_range_t, R&& rg, size_type n = see below,
//     const hasher& hf = hasher(), const key_equal& eql = key_equal(),
//     const allocator_type& a = allocator_type()); // C++23
//
// template<container-compatible-range<value_type> R>
//   unordered-container(from_range_t, R&& rg, size_type n, const allocator_type& a)
//     : unordered-container(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
//
// template<container-compatible-range<value_type> R>
//   unordered-container(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
//     : unordered-container(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23

template <class Container, class Range>
concept HasFromRangeCtr = requires (Range&& range) {
  // (from_range, range)
  Container(std::from_range, std::forward<Range>(range));
  // (from_range, range, n)
  Container(std::from_range, std::forward<Range>(range), 0);
  // (from_range, range, n, hash)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>());
  // (from_range, range, n, hash, equal)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(),
            std::equal_to<typename Container::key_type>());
  // (from_range, range, n, hash, equal, alloc)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(),
            std::equal_to<typename Container::key_type>(), std::allocator<typename Container::value_type>());
  // (from_range, range, n, alloc)
  Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>());
  // (from_range, range, n, hash, alloc)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(),
            std::allocator<typename Container::value_type>());
};

template <template <class...> class Container, class K, class V, class K2, class V2>
constexpr bool test_map_constraints() {
  using ValueType = std::pair<const K, V>;

  // Input range with the same value type.
  static_assert(HasFromRangeCtr<Container<K, V>, InputRange<ValueType>>);
  // Input range with a convertible value type.
  static_assert(HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K2, V2>>>);
  // Input range with a non-convertible value type.
  static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const Empty, V>>>);
  static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K, Empty>>>);
  // Not an input range.
  static_assert(!HasFromRangeCtr<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>);

  return true;
}

template <template <class ...> class Container,
          class K,
          class V,
          class Iter,
          class Sent,
          class Hash,
          class Equal,
          class Alloc,
          class ValueType = std::pair<const K, V>>
void test_unordered_map_with_input(std::vector<ValueType>&& input) {
  using DefaultHash = std::hash<int>;
  using DefaultEqual = std::equal_to<int>;

  auto validate = [](auto&& c) {
    if (!c.empty()) {
      auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count());
      assert(std::fabs(diff) < std::numeric_limits<float>::epsilon());
    }
    assert(c.max_load_factor() == 1);
  };

  { // (range)
    auto in = wrap_input<Iter, Sent>(input);
    Container<K, V> c(std::from_range, in);

    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n)
    auto in = wrap_input<Iter, Sent>(input);
    Container<K, V> c(std::from_range, in, 123);

    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher)
    auto in = wrap_input<Iter, Sent>(input);
    Container<K, V, Hash> c(std::from_range, in, 123, Hash());

    assert(c.hash_function() == Hash());
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher, key_equal)
    auto in = wrap_input<Iter, Sent>(input);
    Container<K, V, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal());

    assert(c.hash_function() == Hash());
    assert(c.key_eq() == Equal());
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher, key_equal, allocator)
    auto in = wrap_input<Iter, Sent>(input);
    Alloc alloc;
    Container<K, V, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc);

    assert(c.hash_function() == Hash());
    assert(c.key_eq() == Equal());
    assert(c.get_allocator() == alloc);
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, allocator)
    auto in = wrap_input<Iter, Sent>(input);
    Alloc alloc;
    Container<K, V, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc);

    assert(c.get_allocator() == alloc);
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher, allocator)
    auto in = wrap_input<Iter, Sent>(input);
    Alloc alloc;
    Container<K, V, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc);

    assert(c.hash_function() == Hash());
    assert(c.get_allocator() == alloc);
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }
}

template <template <class ...> class Container,
          class K,
          class V,
          class Iter,
          class Sent,
          class Hash,
          class Equal,
          class Alloc>
void test_unordered_map() {
  auto test_with_input = &test_unordered_map_with_input<Container, K, V, Iter, Sent, Hash, Equal, Alloc>;

  // Normal input.
  test_with_input({{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}});
  // Empty input.
  test_with_input({});
  // Single-element input.
  test_with_input({{1, 2}});
}

template <template <class ...> class Container>
void test_unordered_map_move_only() {
  std::pair<const int, MoveOnly> input[5];
  std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});

  [[maybe_unused]] Container<int, MoveOnly> c(std::from_range, in);
}

template <template <class ...> class Container>
void test_map_exception_safety_throwing_copy() {
#if !defined(TEST_HAS_NO_EXCEPTIONS)
  using K = int;
  using V = ThrowingCopy<3>;

  V::throwing_enabled = false;
  std::pair<const K, V> in[5] = {
    {1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}}
  };
  V::throwing_enabled = true;
  V::reset();

  try {
    Container<K, V> c(std::from_range, in);
    assert(false); // The constructor call above should throw.

  } catch (int) {
    assert(V::created_by_copying == 3);
    assert(V::destroyed == 2); // No destructor call for the partially-constructed element.
  }
#endif
}

template <template <class ...> class Container, class K, class V>
void test_map_exception_safety_throwing_allocator() {
#if !defined(TEST_HAS_NO_EXCEPTIONS)
  using ValueType = std::pair<const K, V>;
  ValueType in[] = {
    ValueType{K{1}, V{1}}
  };

  try {
    ThrowingAllocator<ValueType> alloc;

    globalMemCounter.reset();
    Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>>
        c(std::from_range, in, /*n=*/0, alloc);
    assert(false); // The constructor call should throw.

  } catch (int) {
    assert(globalMemCounter.new_called == globalMemCounter.delete_called);
  }
#endif
}

template <class Container, class Range>
concept SetHasFromRangeCtr = requires (Range&& range) {
  // (from_range, range)
  Container(std::from_range, std::forward<Range>(range));
  // (from_range, range, n)
  Container(std::from_range, std::forward<Range>(range), 0);
  // (from_range, range, n, hash)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>());
  // (from_range, range, n, hash, equal)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(),
            std::equal_to<typename Container::value_type>());
  // (from_range, range, n, hash, equal, alloc)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(),
            std::equal_to<typename Container::value_type>(), std::allocator<typename Container::value_type>());
  // (from_range, range, n, alloc)
  Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>());
  // (from_range, range, n, hash, alloc)
  Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(),
            std::allocator<typename Container::value_type>());
};

template <template <class...> class Container, class T, class U>
constexpr bool test_set_constraints() {
  // Input range with the same value type.
  static_assert(HasFromRangeCtr<Container<T>, InputRange<T>>);
  // Input range with a convertible value type.
  static_assert(HasFromRangeCtr<Container<T>, InputRange<U>>);
  // Input range with a non-convertible value type.
  static_assert(!HasFromRangeCtr<Container<T>, InputRange<Empty>>);
  // Not an input range.
  static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotDerivedFromGeneric<T>>);

  return true;
}

template <template <class ...> class Container,
          class T,
          class Iter,
          class Sent,
          class Hash,
          class Equal,
          class Alloc>
void test_unordered_set_with_input(std::vector<T>&& input) {
  using DefaultHash = std::hash<int>;
  using DefaultEqual = std::equal_to<int>;

  auto validate = [](auto&& c) {
    if (!c.empty()) {
      auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count());
      assert(std::fabs(diff) < std::numeric_limits<float>::epsilon());
    }
    assert(c.max_load_factor() == 1);
  };

  { // (range)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Container<T> c(std::from_range, in);

    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Container<T> c(std::from_range, in, 123);

    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Container<T, Hash> c(std::from_range, in, 123, Hash());

    assert(c.hash_function() == Hash());
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher, key_equal)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Container<T, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal());

    assert(c.hash_function() == Hash());
    assert(c.key_eq() == Equal());
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher, key_equal, allocator)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Alloc alloc;
    Container<T, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc);

    assert(c.hash_function() == Hash());
    assert(c.key_eq() == Equal());
    assert(c.get_allocator() == alloc);
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, allocator)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Alloc alloc;
    Container<T, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc);

    assert(c.get_allocator() == alloc);
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }

  { // (range, n, hasher, allocator)
    std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size())));
    Alloc alloc;
    Container<T, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc);

    assert(c.hash_function() == Hash());
    assert(c.get_allocator() == alloc);
    assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end())));
    assert(std::ranges::is_permutation(input, c));
    validate(c);
  }
}

template <template <class ...> class Container,
          class T,
          class Iter,
          class Sent,
          class Hash,
          class Equal,
          class Alloc>
void test_unordered_set() {
  auto test_with_input = &test_unordered_set_with_input<Container, T, Iter, Sent, Hash, Equal, Alloc>;

  // Normal input.
  test_with_input({0, 5, 12, 7, -1, 8, 26});
  // Empty input.
  test_with_input({});
  // Single-element input.
  test_with_input({5});
}

template <template <class ...> class Container>
void test_unordered_set_move_only() {
  MoveOnly input[5];
  std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});

  [[maybe_unused]] Container<MoveOnly> c(std::from_range, in);
}

template <template <class ...> class Container>
void test_set_exception_safety_throwing_copy() {
#if !defined(TEST_HAS_NO_EXCEPTIONS)
  using T = ThrowingCopy<3>;
  T::reset();
  T in[5] = {{1}, {2}, {3}, {4}, {5}};

  try {
    Container<T, test_hash<T>> c(std::from_range, in);
    assert(false); // The constructor call above should throw.

  } catch (int) {
    assert(T::created_by_copying == 3);
    assert(T::destroyed == 2); // No destructor call for the partially-constructed element.
  }
#endif
}

template <template <class ...> class Container, class T>
void test_set_exception_safety_throwing_allocator() {
#if !defined(TEST_HAS_NO_EXCEPTIONS)
  T in[] = {1, 2, 3};

  try {
    ThrowingAllocator<T> alloc;

    globalMemCounter.reset();
    Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(std::from_range, in, /*n=*/0, alloc);
    assert(false); // The constructor call should throw.

  } catch (int) {
    assert(globalMemCounter.new_called == globalMemCounter.delete_called);
  }
#endif
}

#endif // SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H