//===----------------------------------------------------------------------===//
//
// 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<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
//          class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
//   requires indirectly_copyable<I, O>
//   constexpr remove_copy_if_result<I, O>
//     remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});                        // Since C++20
//
// template<input_range R, weakly_incrementable O, class Proj = identity,
//          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
//   requires indirectly_copyable<iterator_t<R>, O>
//   constexpr remove_copy_if_result<borrowed_iterator_t<R>, O>
//     remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});                                  // Since C++20

#include <algorithm>
#include <array>
#include <concepts>
#include <functional>
#include <ranges>
#include <type_traits>
#include <utility>

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

struct AlwaysTrue {
  constexpr bool operator()(auto&&...) const { return true; }
};

template <
    class I,
    class S    = sentinel_wrapper<std::decay_t<I>>,
    class O    = int*,
    class Pred = AlwaysTrue>
concept HasRemoveCopyIfIter =
  requires(I&& iter, S&& sent, O&& out, Pred&& pred) {
    std::ranges::remove_copy_if(std::forward<I>(iter), std::forward<S>(sent),
                                std::forward<O>(out), std::forward<Pred>(pred));
};

static_assert(HasRemoveCopyIfIter<int*, int*, int*>);

// !input_iterator<I>
static_assert(!HasRemoveCopyIfIter<InputIteratorNotDerivedFrom>);
static_assert(!HasRemoveCopyIfIter<cpp20_output_iterator<int*>>);

// !sentinel_for<S, I>
static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotSemiregular>);

// !weakly_incrementable<O>
static_assert(!HasRemoveCopyIfIter<int*, int*, WeaklyIncrementableNotMovable>);

// !indirect_unary_predicate<Pred, projected<I, Proj>>
static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);

// !indirectly_copyable<I, O>
static_assert(!HasRemoveCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
static_assert(!HasRemoveCopyIfIter<const int*, const int*, const int*>);

template < class R, class O = int*, class Pred = AlwaysTrue, class Proj = std::identity>
concept HasRemoveCopyIfRange =
    requires(R&& r, O&& out, Pred&& pred, Proj&& proj) {
      std::ranges::remove_copy_if(
          std::forward<R>(r), std::forward<O>(out), std::forward<Pred>(pred), std::forward<Proj>(proj));
    };

template <class T>
using R = UncheckedRange<T>;

static_assert(HasRemoveCopyIfRange<R<int*>>);

// !input_range<R>
static_assert(!HasRemoveCopyIfRange<R<InputIteratorNotDerivedFrom>>);
static_assert(!HasRemoveCopyIfRange<R<cpp20_output_iterator<int*>>>);

// !weakly_incrementable<O>
static_assert(!HasRemoveCopyIfRange<R<int*>, WeaklyIncrementableNotMovable>);

// !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>>
static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotPredicate>);
static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotCopyConstructible>);

// !indirectly_copyable<iterator_t<R>, O>
static_assert(!HasRemoveCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>);
static_assert(!HasRemoveCopyIfRange<R<const int*>, const int*>);

template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2, class Pred>
constexpr void testRemoveCopyIfImpl(std::array<int, N1> in, std::array<int, N2> expected, Pred pred) {
  using Sent = SentWrapper<InIter>;
  using Result = std::ranges::remove_copy_if_result<InIter, OutIter>;

  // iterator overload
  {
    std::array<int, N2> out;
    std::same_as<Result> decltype(auto) result =
        std::ranges::remove_copy_if(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()}, pred);
    assert(std::ranges::equal(out, expected));
    assert(base(result.in) == in.data() + in.size());
    assert(base(result.out) == out.data() + out.size());
  }

  // range overload
  {
    std::array<int, N2> out;
    std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};
    std::same_as<Result> decltype(auto) result =
        std::ranges::remove_copy_if(r, OutIter{out.data()}, pred);
    assert(std::ranges::equal(out, expected));
    assert(base(result.in) == in.data() + in.size());
    assert(base(result.out) == out.data() + out.size());
  }
}

template <class InIter, class OutIter, template <class> class SentWrapper>
constexpr void testImpl() {
  // remove multiple elements
  {
    std::array in{1, 2, 3, 2, 1};
    std::array expected{1, 3, 1};
    auto pred = [](int i) { return i == 2; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // remove single elements
  {
    std::array in{1, 2, 3, 2, 1};
    std::array expected{1, 2, 2, 1};
    auto pred = [](int i) { return i == 3; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // nothing removed
  {
    std::array in{1, 2, 3, 2, 1};
    std::array expected{1, 2, 3, 2, 1};
    auto pred = [](int) { return false; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // all removed
  {
    std::array in{1, 2, 3, 2, 1};
    std::array<int, 0> expected{};
    auto pred = [](int) { return true; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // remove first
  {
    std::array in{1, 2, 3, 2};
    std::array expected{2, 3, 2};
    auto pred = [](int i) { return i < 2; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // remove last
  {
    std::array in{1, 2, 3, 2, 5};
    std::array expected{1, 2, 3, 2};
    auto pred = [](int i) { return i > 3; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // stable
  {
    std::array in{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::array expected{6, 7, 8, 9, 10};
    auto pred = [](int i) { return i < 6; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // empty range
  {
    std::array<int, 0> in{};
    std::array<int, 0> expected{};
    auto pred = [](int) { return false; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }

  // one element range
  {
    std::array in{1};
    std::array<int, 0> expected{};
    auto pred = [](int i) { return i == 1; };
    testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
  }
}

template <class OutIter, template <class> class SentWrapper>
constexpr void withAllPermutationsOfInIter() {
  testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>();
  testImpl<forward_iterator<int*>, OutIter, SentWrapper>();
  testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>();
  testImpl<random_access_iterator<int*>, OutIter, SentWrapper>();
  testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>();
  testImpl<int*, OutIter, SentWrapper>();
}

template <template <class> class SentWrapper>
constexpr void withAllPermutationsOfInIterOutIter() {
  withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
  withAllPermutationsOfInIter<int*, SentWrapper>();
}

constexpr bool test() {
  withAllPermutationsOfInIterOutIter<std::type_identity_t>();
  withAllPermutationsOfInIterOutIter<sentinel_wrapper>();

  // Test custom projection
  {
    struct Data {
      int data;
    };

    std::array in{Data{4}, Data{8}, Data{12}, Data{12}};
    std::array expected{Data{4}, Data{12}, Data{12}};

    const auto proj = &Data::data;
    const auto pred = [](int i) { return i == 8; };

    const auto equals = [](const Data& x, const Data& y) { return x.data == y.data; };
    // iterator overload
    {
      std::array<Data, 3> out;
      auto result = std::ranges::remove_copy_if(in.begin(), in.end(), out.begin(), pred, proj);
      assert(std::ranges::equal(out, expected, equals));
      assert(result.in == in.end());
      assert(result.out == out.end());
    }

    // range overload
    {
      std::array<Data, 3> out;
      auto result = std::ranges::remove_copy_if(in, out.begin(), pred, proj);
      assert(std::ranges::equal(out, expected, equals));
      assert(result.in == in.end());
      assert(result.out == out.end());
    }
  }

  // Complexity: Exactly last - first applications of the corresponding predicate and any projection.
  {
    std::array in{4, 4, 5, 6};
    std::array expected{5, 6};

    const auto pred = [](int i) { return i == 4; };

    // iterator overload
    {
      int numberOfPred = 0;
      int numberOfProj = 0;
      std::array<int, 2> out;
      std::ranges::remove_copy_if(
          in.begin(), in.end(), out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj));

      assert(numberOfPred == static_cast<int>(in.size()));
      assert(numberOfProj == static_cast<int>(in.size()));

      assert(std::ranges::equal(out, expected));
    }

    // range overload
    {
      int numberOfPred = 0;
      int numberOfProj = 0;
      std::array<int, 2> out;
      std::ranges::remove_copy_if(
          in, out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj));
      assert(numberOfPred == static_cast<int>(in.size()));
      assert(numberOfProj == static_cast<int>(in.size()));
      assert(std::ranges::equal(out, expected));
    }
  }

  return true;
}

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

  return 0;
}