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

// <algorithm>

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

// template<permutable I, sentinel_for<I> S, class Proj = identity,
//          indirect_unary_predicate<projected<I, Proj>> Pred>
//   constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
// template<forward_range R, class Proj = identity,
//          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
//   requires permutable<iterator_t<R>>
//   constexpr borrowed_subrange_t<R>
//     ranges::remove_if(R&& r, Pred pred, Proj proj = {});

#include <algorithm>
#include <array>
#include <cassert>
#include <ranges>

#include "almost_satisfies_types.h"
#include "boolean_testable.h"
#include "test_iterators.h"

struct FalsePredicate {
  bool operator()(int) { return false; }
};

template <class Iter, class Sent = sentinel_wrapper<Iter>>
concept HasRemoveIfIt = requires(Iter first, Sent last) { std::ranges::remove_if(first, last, FalsePredicate{}); };

static_assert(HasRemoveIfIt<int*>);
static_assert(!HasRemoveIfIt<PermutableNotForwardIterator>);
static_assert(!HasRemoveIfIt<PermutableNotSwappable>);
static_assert(!HasRemoveIfIt<int*, SentinelForNotSemiregular>);
static_assert(!HasRemoveIfIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
static_assert(!HasRemoveIfIt<int**>); // not indirect_unary_predicate

template <class Range>
concept HasRemoveIfR = requires(Range range) { std::ranges::remove_if(range, FalsePredicate{}); };

static_assert(HasRemoveIfR<UncheckedRange<int*>>);
static_assert(!HasRemoveIfR<PermutableRangeNotForwardIterator>);
static_assert(!HasRemoveIfR<PermutableRangeNotSwappable>);
static_assert(!HasRemoveIfR<SentinelForNotSemiregular>);
static_assert(!HasRemoveIfR<SentinelForNotWeaklyEqualityComparableWith>);
static_assert(!HasRemoveIfR<UncheckedRange<int**>>); // not indirect_unary_predicate

template <int N, int M>
struct Data {
  std::array<int, N> input;
  std::array<int, M> expected;
  int cutoff;
};

template <class Iter, class Sent, int N, int M>
constexpr void test(Data<N, M> d) {
  { // iterator overload
    auto input = d.input;

    auto first = Iter(input.data());
    auto last  = Sent(Iter(input.data() + input.size()));

    std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =
        std::ranges::remove_if(std::move(first), std::move(last), [&](int i) { return i < d.cutoff; });

    assert(base(ret.begin()) == input.data() + M);
    assert(base(ret.end()) == input.data() + N);
    assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));
  }

  { // range overload
    auto input = d.input;
    auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));

    std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove_if(range, [&](int i) {
      return i < d.cutoff;
    });

    assert(base(ret.begin()) == input.data() + M);
    assert(base(ret.end()) == input.data() + N);
    assert(std::ranges::equal(base(input.begin()), base(ret.begin()), d.expected.begin(), d.expected.end()));
  }
}

template <class Iter, class Sent>
constexpr void tests() {
  // simple test
  test<Iter, Sent, 6, 2>({.input = {1, 2, 3, 4, 5, 6}, .expected = {5, 6}, .cutoff = 5});
  // empty range
  test<Iter, Sent, 0, 0>({});
  // single element range - no match
  test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .cutoff = 1});
  // single element range - match
  test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .cutoff = 2});
  // two element range
  test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .cutoff = 2});
  // all elements match
  test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .cutoff = 2});
  // no elements match
  test<Iter, Sent, 5, 5>({.input = {1, 1, 1, 1, 1}, .expected = {1, 1, 1, 1, 1}, .cutoff = 0});
  // the relative order of elements isn't changed
  test<Iter, Sent, 8, 7>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {2, 3, 2, 3, 4, 2, 5}, .cutoff = 2});
  // multiple matches in a row
  test<Iter, Sent, 5, 3>({.input = {1, 2, 2, 2, 1}, .expected = {2, 2, 2}, .cutoff = 2});
  // only the last element matches
  test<Iter, Sent, 3, 2>({.input = {2, 2, 1}, .expected = {2, 2}, .cutoff = 2});
  // only the last element doesn't match
  test<Iter, Sent, 3, 1>({.input = {1, 1, 2}, .expected = {2}, .cutoff = 2});
}

template <class Iter>
constexpr void test_sentinels() {
  tests<Iter, Iter>();
  tests<Iter, sentinel_wrapper<Iter>>();
  tests<Iter, sized_sentinel<Iter>>();
}

constexpr void test_iterators() {
  test_sentinels<forward_iterator<int*>>();
  test_sentinels<bidirectional_iterator<int*>>();
  test_sentinels<random_access_iterator<int*>>();
  test_sentinels<contiguous_iterator<int*>>();
  test_sentinels<int*>();
}

constexpr bool test() {
  test_iterators();

  { // check that ranges::dangling is returned
    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
        std::ranges::remove_if(std::array{1, 2, 3, 4}, [](int i) { return i < 0; });
  }

  {// check complexity requirements

   // This is https://llvm.org/PR56382 - clang-format behaves weird if function-local structs are used
   // clang-format off
    {
      int comp_count = 0;
      auto comp = [&](int i) {
        ++comp_count;
        return i == 0;
      };
      int proj_count = 0;
      auto proj      = [&](int i) {
        ++proj_count;
        return i;
      };
      int a[]  = {1, 2, 3, 4};
      auto ret = std::ranges::remove_if(std::begin(a), std::end(a), comp, proj);
      assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
      assert(comp_count == 4);
      assert(proj_count == 4);
    }
    {
      int comp_count = 0;
      auto comp      = [&](int i) {
        ++comp_count;
        return i == 0;
      };
      int proj_count = 0;
      auto proj      = [&](int i) {
        ++proj_count;
        return i;
      };
      int a[]  = {1, 2, 3, 4};
      auto ret = std::ranges::remove_if(a, comp, proj);
      assert(ret.begin() == std::end(a) && ret.end() == std::end(a));
      assert(comp_count == 4);
      assert(proj_count == 4);
    }
  }

  { // check that std::invoke is used
    struct S {
      constexpr S& identity() { return *this; }
      constexpr bool predicate() const { return true; }
    };
    {
      S a[4]   = {};
      auto ret = std::ranges::remove_if(std::begin(a), std::end(a), &S::predicate, &S::identity);
      assert(ret.begin() == std::begin(a));
      assert(ret.end() == std::end(a));
    }
    {
      S a[4]   = {};
      auto ret = std::ranges::remove_if(a, &S::predicate, &S::identity);
      assert(ret.begin() == std::begin(a));
      assert(ret.end() == std::end(a));
    }
  }

  {
    // check that the implicit conversion to bool works
    {
      int a[]  = {1, 2, 3, 4};
      auto ret = std::ranges::remove_if(a, a + 4, [](const int& i) { return BooleanTestable{i == 3}; });
      assert(ret.begin() == a + 3);
    }
    {
      int a[]  = {1, 2, 3, 4};
      auto ret = std::ranges::remove_if(a, [](const int& b) { return BooleanTestable{b == 3}; });
      assert(ret.begin() == a + 3);
    }
  }

  return true;
}
// clang-format on

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

  return 0;
}