//===----------------------------------------------------------------------===//
//
// 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_ASSOCIATIVE_CONTAINERS_H
#define SUPPORT_FROM_RANGE_ASSOCIATIVE_CONTAINERS_H

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

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

template <class Container, class Range>
concept HasFromRangeCtr = requires (Range&& range) {
  Container(std::from_range, std::forward<Range>(range));
  Container(std::from_range, std::forward<Range>(range), std::less<typename Container::key_type>());
  Container(std::from_range, std::forward<Range>(range), std::less<typename Container::key_type>(),
      std::allocator<typename Container::value_type>());
  Container(std::from_range, std::forward<Range>(range), 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 Comp,
          class Alloc,
          class ValueType = std::pair<const K, V>>
void test_associative_map_with_input(std::vector<ValueType>&& input) {
  auto in = wrap_input<Iter, Sent>(input);

  { // (range)
    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));
  }

  { // (range, comp)
    Comp comp;
    Container<K, V, Comp> c(std::from_range, in, comp);

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

  { // (range, allocator)
    Alloc alloc;
    Container<K, V, std::less<K>, Alloc> c(std::from_range, in, 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));
  }

  { // (range, comp, allocator)
    Comp comp;
    Alloc alloc;
    Container<K, V, Comp, Alloc> c(std::from_range, in, comp, alloc);

    assert(c.key_comp() == comp);
    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));
  }
}

template <template <class ...> class Container,
          class K,
          class V,
          class Iter,
          class Sent,
          class Comp,
          class Alloc>
void test_associative_map() {
  auto test_with_input = &test_associative_map_with_input<Container, K, V, Iter, Sent, Comp, 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_associative_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_less<K>, ThrowingAllocator<ValueType>> c(std::from_range, in, alloc);
    assert(false); // The constructor call above should throw.

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

template <class Container, class Range>
concept SetHasFromRangeCtr = requires (Range&& range) {
  Container(std::from_range, std::forward<Range>(range));
  Container(std::from_range, std::forward<Range>(range), std::less<typename Container::value_type>());
  Container(std::from_range, std::forward<Range>(range), std::less<typename Container::value_type>(),
      std::allocator<typename Container::value_type>());
  Container(std::from_range, std::forward<Range>(range), 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(SetHasFromRangeCtr<Container<T>, InputRange<T>>);
  // Input range with a convertible value type.
  static_assert(SetHasFromRangeCtr<Container<T>, InputRange<U>>);
  // Input range with a non-convertible value type.
  static_assert(!SetHasFromRangeCtr<Container<T>, InputRange<Empty>>);
  // Not an input range.
  static_assert(!SetHasFromRangeCtr<Container<T>, InputRangeNotDerivedFromGeneric<T>>);

  return true;
}

template <template <class ...> class Container,
          class T,
          class Iter,
          class Sent,
          class Comp,
          class Alloc>
void test_associative_set_with_input(std::vector<T>&& input) {
  auto b = Iter(input.data());
  auto e = Iter(input.data() + input.size());
  std::ranges::subrange in(std::move(b), Sent(std::move(e)));

  { // (range)
    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));
  }

  { // (range, comp)
    Comp comp;
    Container<T, Comp> c(std::from_range, in, comp);

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

  { // (range, allocator)
    Alloc alloc;
    Container<T, std::less<T>, Alloc> c(std::from_range, in, 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));
  }

  { // (range, comp, allocator)
    Comp comp;
    Alloc alloc;
    Container<T, Comp, Alloc> c(std::from_range, in, comp, alloc);

    assert(c.key_comp() == comp);
    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));
  }
}

template <template <class ...> class Container,
          class T,
          class Iter,
          class Sent,
          class Comp,
          class Alloc>
void test_associative_set() {
  auto test_with_input = &test_associative_set_with_input<Container, T, Iter, Sent, Comp, 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_associative_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> 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};

  try {
    ThrowingAllocator<T> alloc;

    globalMemCounter.reset();
    Container<T, test_less<T>, ThrowingAllocator<T>> c(std::from_range, in, alloc);
    assert(false); // The constructor call above should throw.

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

#endif // SUPPORT_FROM_RANGE_ASSOCIATIVE_CONTAINERS_H