//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//

// UNSUPPORTED: c++03, c++11, c++14, c++17

// <algorithm>

// template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
//        sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
//        indirect_equivalence_relation<projected<I1, Proj1>,
//                                      projected<I2, Proj2>> Pred = ranges::equal_to>
// constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
//                                       Pred pred = {},
//                                       Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20
//
// template<forward_range R1, forward_range R2,
//        class Proj1 = identity, class Proj2 = identity,
//        indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
//                                      projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
// constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
//                                       Proj1 proj1 = {}, Proj2 proj2 = {});                       // Since C++20

#include <algorithm>
#include <array>
#include <concepts>
#include <list>
#include <ranges>

#include "almost_satisfies_types.h"
#include "counting_predicates.h"
#include "counting_projection.h"
#include "test_iterators.h"

template <class Iter1, class Sent1 = int*, class Iter2 = int*, class Sent2 = int*>
concept HasIsPermutationIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
  std::ranges::is_permutation(first1, last1, first2, last2);
};

template <class Range1, class Range2 = UncheckedRange<int*>>
concept HasIsPermutationR = requires(Range1 range1, Range2 range2) {
  std::ranges::is_permutation(range1, range2);
};

static_assert(HasIsPermutationIt<int*>);
static_assert(!HasIsPermutationIt<ForwardIteratorNotDerivedFrom>);
static_assert(!HasIsPermutationIt<ForwardIteratorNotIncrementable>);
static_assert(!HasIsPermutationIt<int*, SentinelForNotSemiregular>);
static_assert(!HasIsPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotDerivedFrom>);
static_assert(!HasIsPermutationIt<int*, int*, ForwardIteratorNotIncrementable>);
static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotSemiregular>);
static_assert(!HasIsPermutationIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
// !indirect_equivalence_relation<Pred, projected<I1, Proj1>, projected<I2, Proj2>>;
static_assert(!HasIsPermutationIt<int*, int*, int**, int**>);

static_assert(HasIsPermutationR<UncheckedRange<int*>>);
static_assert(!HasIsPermutationR<ForwardRangeNotDerivedFrom>);
static_assert(!HasIsPermutationR<ForwardRangeNotIncrementable>);
static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelSemiregular>);
static_assert(!HasIsPermutationR<int*, ForwardRangeNotSentinelEqualityComparableWith>);
static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
static_assert(!HasIsPermutationR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
// !indirect_equivalence_relation<Pred, projected<iterator_t<I1>, Proj1>, projected<iterator_t<I2>, Proj2>>;
static_assert(!HasIsPermutationIt<UncheckedRange<int*>, UncheckedRange<int**>>);

template <int N, int M>
struct Data {
  std::array<int, N> input1;
  std::array<int, M> input2;
  bool expected;
};

template <class Iter1, class Sent1, class Iter2, class Sent2, int N, int M>
constexpr void test(Data<N, M> d) {
  {
    std::same_as<bool> decltype(auto) ret = std::ranges::is_permutation(Iter1(d.input1.data()),
                                                                        Sent1(Iter1(d.input1.data() + N)),
                                                                        Iter1(d.input2.data()),
                                                                        Sent1(Iter1(d.input2.data() + M)));
    assert(ret == d.expected);
  }
  {
    auto range1 = std::ranges::subrange(Iter1(d.input1.data()), Sent1(Iter1(d.input1.data() + N)));
    auto range2 = std::ranges::subrange(Iter1(d.input2.data()), Sent1(Iter1(d.input2.data() + M)));
    std::same_as<bool> decltype(auto) ret = std::ranges::is_permutation(range1, range2);
    assert(ret == d.expected);
  }
}

template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
constexpr void test_iterators() {
  // Ranges are identical.
  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {1, 2, 3, 4}, .expected = true});

  // Ranges are reversed.
  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 2, 3, 4}, .input2 = {4, 3, 2, 1}, .expected = true});

  // Two elements are swapped.
  test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {4, 2, 3, 1}, .input2 = {1, 2, 3, 4}, .expected = true});

  // The first range is shorter.
  test<Iter1, Sent1, Iter2, Sent2, 4, 5>({.input1 = {4, 2, 3, 1}, .input2 = {4, 3, 2, 1, 5}, .expected = false});

  // The first range is longer.
  test<Iter1, Sent1, Iter2, Sent2, 5, 4>({.input1 = {4, 2, 3, 1, 5}, .input2 = {4, 3, 2, 1}, .expected = false});

  // The first range is empty.
  test<Iter1, Sent1, Iter2, Sent2, 0, 4>({.input1 = {}, .input2 = {4, 3, 2, 1}, .expected = false});

  // The second range is empty.
  test<Iter1, Sent1, Iter2, Sent2, 5, 0>({.input1 = {4, 2, 3, 1, 5}, .input2 = {}, .expected = false});

  // Both ranges are empty.
  test<Iter1, Sent1, Iter2, Sent2, 0, 0>({.input1 = {}, .input2 = {}, .expected = true});

  // 1-element range, same value.
  test<Iter1, Sent1, Iter2, Sent2, 1, 1>({.input1 = {1}, .input2 = {1}, .expected = true});

  // 1-element range, different values.
  test<Iter1, Sent1, Iter2, Sent2, 1, 1>({.input1 = {1}, .input2 = {2}, .expected = false});
}

template <class Iter1, class Sent1 = Iter1>
constexpr void test_iterators1() {
  test_iterators<Iter1, Sent1, forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
  test_iterators<Iter1, Sent1, forward_iterator<int*>>();
  test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
  test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
  test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
  test_iterators<Iter1, Sent1, int*>();
  test_iterators<Iter1, Sent1, const int*>();
}

constexpr bool test() {
  test_iterators1<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
  test_iterators1<forward_iterator<int*>>();
  test_iterators1<bidirectional_iterator<int*>>();
  test_iterators1<random_access_iterator<int*>>();
  test_iterators1<contiguous_iterator<int*>>();
  test_iterators1<int*>();
  test_iterators1<const int*>();

  { // A custom comparator works.
    struct A {
      int a;
      constexpr bool pred(const A& rhs) const { return a == rhs.a; }
    };

    std::array in1 = {A{2}, A{3}, A{1}};
    std::array in2 = {A{1}, A{2}, A{3}};

    {
      auto ret = std::ranges::is_permutation(in1.begin(), in1.end(), in2.begin(), in2.end(), &A::pred);
      assert(ret);
    }

    {
      auto ret = std::ranges::is_permutation(in1, in2, &A::pred);
      assert(ret);
    }
  }

  { // A custom projection works.
    struct A {
      int a;

      constexpr bool operator==(const A&) const = default;

      constexpr A x2() const { return A{a * 2}; }
      constexpr A div2() const { return A{a / 2}; }
    };

    std::array in1 = {A{1}, A{2}, A{3}};  // [2, 4, 6] after applying `x2`.
    std::array in2 = {A{4}, A{8}, A{12}}; // [2, 4, 6] after applying `div2`.

    {
      auto ret = std::ranges::is_permutation(
          in1.begin(), in1.end(), in2.begin(), in2.end(), {}, &A::x2, &A::div2);
      assert(ret);
    }

    {
      auto ret = std::ranges::is_permutation(in1, in2, {}, &A::x2, &A::div2);
      assert(ret);
    }
  }


  { // Check that complexity requirements are met.
    int predCount = 0;
    int proj1Count = 0;
    int proj2Count = 0;
    auto reset_counters = [&] {
      predCount = proj1Count = proj2Count = 0;
    };

    counting_predicate pred(std::ranges::equal_to{}, predCount);
    counting_projection<> proj1(proj1Count);
    counting_projection<> proj2(proj2Count);

    {
      // 1. No applications of the corresponding predicate if `ForwardIterator1` and `ForwardIterator2` meet the
      //    requirements of random access iterators and `last1 - first1 != last2 - first2`.
      int a[] = {1, 2, 3, 4, 5};
      int b[] = {1, 2, 3, 4};
      // Make sure that the iterators have different types.
      auto b_begin = random_access_iterator<int*>(std::begin(b));
      auto b_end = random_access_iterator<int*>(std::end(b));

      {
        auto ret = std::ranges::is_permutation(a, a + 5, b_begin, b_end, pred, proj1, proj2);
        assert(!ret);

        assert(predCount == 0);
        assert(proj1Count == 0);
        assert(proj2Count == 0);
        reset_counters();
      }

      {
        auto ret = std::ranges::is_permutation(a, std::ranges::subrange(b_begin, b_end), pred, proj1, proj2);
        assert(!ret);

        assert(predCount == 0);
        assert(proj1Count == 0);
        assert(proj2Count == 0);
        reset_counters();
      }
    }

    // 2. Otherwise, exactly last1 - first1 applications of the corresponding predicate if
    // `equal(first1, last1, first2, last2, pred)` would return true.
    {
      int a[] = {1, 2, 3, 4, 5};
      int b[] = {1, 2, 3, 4, 5};
      int expected = 5;

      {
        auto ret = std::ranges::is_permutation(a, a + 5, b, b + 5, pred, proj1, proj2);
        assert(ret);

        assert(predCount == expected);
        assert(proj1Count == expected);
        assert(proj2Count == expected);
        reset_counters();
      }

      {
        auto ret = std::ranges::is_permutation(a, b, pred, proj1, proj2);
        assert(ret);

        assert(predCount == expected);
        assert(proj1Count == expected);
        assert(proj2Count == expected);
        reset_counters();
      }
    }

    // Note: we currently don't have the setup to test big-O complexity, but copying the requirement for completeness'
    // sake.
    // 3. Otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`.
  }


  return true;
}

int main(int, char**) {
  test();
  static_assert(test());

  return 0;
}