//===----------------------------------------------------------------------===//
//
// 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<forward_iterator I, sentinel_for<I> S, class T,
//          class Pred = ranges::equal_to, class Proj = identity>
//   requires indirectly_comparable<I, const T*, Pred, Proj>
//   constexpr subrange<I>
//     ranges::search_n(I first, S last, iter_difference_t<I> count,
//                      const T& value, Pred pred = {}, Proj proj = {});
// template<forward_range R, class T, class Pred = ranges::equal_to,
//          class Proj = identity>
//   requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
//   constexpr borrowed_subrange_t<R>
//     ranges::search_n(R&& r, range_difference_t<R> count,
//                      const T& value, Pred pred = {}, Proj proj = {});

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

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

template <class Iter1, class Sent1 = Iter1>
concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) {
  std::ranges::search_n(first1, last1, 0, 0);
};

static_assert(HasSearchNIt<int*>);
static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>);
static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>);
static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>);
static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable

template <class Range1, class Range2 = UncheckedRange<int*>>
concept HasSearchNR = requires (Range1 range) {
  std::ranges::search_n(range, 0, 0);
};

static_assert(HasSearchNR<UncheckedRange<int*>>);
static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>);
static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>);
static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>);
static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>);
static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable

template <class Iter, class Sent = Iter>
constexpr void test_iterators() {
  { // simple test
    {
      int a[] = {1, 2, 3, 4, 5, 6};
      std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret =
          std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 1, 3);
      assert(base(ret.begin()) == a + 2);
      assert(base(ret.end()) == a + 3);
    }
    {
      int a[] = {1, 2, 3, 4, 5, 6};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
      std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret = std::ranges::search_n(range, 1, 3);
      assert(base(ret.begin()) == a + 2);
      assert(base(ret.end()) == a + 3);
    }
  }

  { // matching part begins at the front
    {
      int a[] = {7, 7, 3, 7, 3, 6};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 2, 7);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 2);
    }
    {
      int a[] = {7, 7, 3, 7, 3, 6};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
      auto ret = std::ranges::search_n(range, 2, 7);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 2);
    }
  }

  { // matching part ends at the back
    {
      int a[] = {9, 3, 6, 4, 4};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 2, 4);
      assert(base(ret.begin()) == a + 3);
      assert(base(ret.end()) == a + 5);
    }
    {
      int a[] = {9, 3, 6, 4, 4};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
      auto ret = std::ranges::search_n(range, 2, 4);
      assert(base(ret.begin()) == a + 3);
      assert(base(ret.end()) == a + 5);
    }
  }

  { // pattern does not match
    {
      int a[] = {9, 3, 6, 4, 8};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 1, 1);
      assert(base(ret.begin()) == a + 5);
      assert(base(ret.end()) == a + 5);
    }
    {
      int a[] = {9, 3, 6, 4, 8};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
      auto ret = std::ranges::search_n(range, 1, 1);
      assert(base(ret.begin()) == a + 5);
      assert(base(ret.end()) == a + 5);
    }
  }

  { // range and pattern are identical
    {
      int a[] = {1, 1, 1, 1};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 4)), 4, 1);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 4);
    }
    {
      int a[] = {1, 1, 1, 1};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
      auto ret = std::ranges::search_n(range, 4, 1);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 4);
    }
  }

  { // pattern is longer than range
    {
      int a[] = {3, 3, 3};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 4, 3);
      assert(base(ret.begin()) == a + 3);
      assert(base(ret.end()) == a + 3);
    }
    {
      int a[] = {3, 3, 3};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
      auto ret = std::ranges::search_n(range, 4, 3);
      assert(base(ret.begin()) == a + 3);
      assert(base(ret.end()) == a + 3);
    }
  }

  { // pattern has zero length
    {
      int a[] = {6, 7, 8};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 0, 7);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a);
    }
    {
      int a[] = {6, 7, 8};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
      auto ret = std::ranges::search_n(range, 0, 7);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a);
    }
  }

  { // range has zero length
    {
      int a[] = {};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a)), 1, 1);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a);
    }
    {
      int a[] = {};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a)));
      auto ret = std::ranges::search_n(range, 1, 1);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a);
    }
  }

  { // check that the first match is returned
    {
      int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 9)), 2, 6);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 2);
    }
    {
      int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 9)));
      auto ret = std::ranges::search_n(range, 2, 6);
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 2);
    }
  }

  { // check that the predicate is used
    {
      int a[] = {1, 4, 4, 3, 6, 1};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
                                       3,
                                       4,
                                       [](int l, int r) { return l == r || l == 1; });
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 3);
    }
    {
      int a[] = {1, 4, 4, 3, 6, 1};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
      auto ret = std::ranges::search_n(range, 3, 4, [](int l, int r) { return l == r || l == 1; });
      assert(base(ret.begin()) == a);
      assert(base(ret.end()) == a + 3);
    }
  }

  { // check that the projections are used
    {
      int a[] = {1, 3, 1, 6, 5, 6};
      auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
                                       3,
                                       6,
                                       {},
                                       [](int i) { return i % 2 == 0 ? i : i + 1; });
      assert(base(ret.begin()) == a + 3);
      assert(base(ret.end()) == a + 6);
    }
    {
      int a[] = {1, 3, 1, 6, 5, 6};
      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
      auto ret = std::ranges::search_n(range,
                                       3,
                                       6,
                                       {},
                                       [](int i) { return i % 2 == 0 ? i : i + 1; });
      assert(base(ret.begin()) == a + 3);
      assert(base(ret.end()) == a + 6);
    }
  }
}
constexpr bool test() {
  test_iterators<forward_iterator<int*>>();
  test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
  test_iterators<bidirectional_iterator<int*>>();
  test_iterators<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
  test_iterators<random_access_iterator<int*>>();
  test_iterators<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
  test_iterators<contiguous_iterator<int*>>();
  test_iterators<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
  test_iterators<int*>();

  { // check that std::invoke is used
    struct S {
      int i;

      constexpr S identity() {
        return *this;
      }

      constexpr bool compare(int o) {
        return i == o;
      }
    };
    {
      S a[] = {{1}, {2}, {3}, {4}};
      auto ret = std::ranges::search_n(a, a + 4, 1, 2, &S::compare, &S::identity);
      assert(ret.begin() == a + 1);
      assert(ret.end() == a + 2);
    }
    {
      S a[] = {{1}, {2}, {3}, {4}};
      auto ret = std::ranges::search_n(a, 1, 2, &S::compare, &S::identity);
      assert(ret.begin() == a + 1);
      assert(ret.end() == a + 2);
    }
  }

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

  return true;
}

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

  return 0;
}