//===----------------------------------------------------------------------===//
//
// 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<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
//          indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
//   constexpr I is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});                // Since C++20
//
// template<random_access_range R, class Proj = identity,
//          indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
//   constexpr borrowed_iterator_t<R>
//     is_heap_until(R&& r, Comp comp = {}, Proj proj = {});                                    // Since C++20

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

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

// Test constraints of the (iterator, sentinel) overload.
// ======================================================

template <class Iter = int*, class Sent = int*, class Comp = std::ranges::less>
concept HasIsHeapUntilIter =
    requires(Iter&& iter, Sent&& sent, Comp&& comp) {
      std::ranges::is_heap_until(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp));
    };

static_assert(HasIsHeapUntilIter<int*, int*, std::ranges::less>);

// !random_access_iterator<I>
static_assert(!HasIsHeapUntilIter<RandomAccessIteratorNotDerivedFrom>);
static_assert(!HasIsHeapUntilIter<RandomAccessIteratorBadIndex>);

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

struct NoComparator {};
// !indirect_strict_weak_order<Comp, projected<I, Proj>>
static_assert(!HasIsHeapUntilIter<NoComparator*, NoComparator*>);

// Test constraints of the (range) overload.
// =========================================

template <class Range, class Comp = std::ranges::less>
concept HasIsHeapUntilRange =
    requires(Range&& range, Comp&& comp) {
      std::ranges::is_heap_until(std::forward<Range>(range), std::forward<Comp>(comp));
    };

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

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

// !random_access_range<R>
static_assert(!HasIsHeapUntilRange<RandomAccessRangeNotDerivedFrom>);
static_assert(!HasIsHeapUntilRange<RandomAccessRangeBadIndex>);

// !indirect_strict_weak_order<Comp, projected<iterator_t<R>, Proj>>
static_assert(!HasIsHeapUntilRange<R<NoComparator*>>);

template <class Iter, class Sent, std::size_t N>
constexpr void test_one(std::array<int, N> input, std::size_t until_index) {
  auto begin = Iter(input.data());
  auto end = Sent(Iter(input.data() + input.size()));

  { // (iterator, sentinel) overload.
    std::same_as<Iter> decltype(auto) result = std::ranges::is_heap_until(begin, end);
    assert(base(result) == input.data() + until_index);
  }

  { // (range) overload.
    auto range = std::ranges::subrange(begin, end);
    std::same_as<Iter> decltype(auto) result = std::ranges::is_heap_until(range);
    assert(base(result) == input.data() + until_index);
  }
}

template <class Iter, class Sent>
constexpr void test_iter_sent() {
  // Empty sequence.
  test_one<Iter, Sent, 0>({}, 0);
  // 1-element sequence.
  test_one<Iter, Sent>(std::array{1}, 1);
  // 2-element sequence, a heap.
  test_one<Iter, Sent>(std::array{2, 1}, 2);
  // 2-element sequence, not a heap.
  test_one<Iter, Sent>(std::array{1, 2}, 1);
  // Longer sequence, a heap.
  test_one<Iter, Sent>(std::array{8, 6, 7, 3, 4, 1, 5, 2}, 8);
  // Longer sequence, not a heap.
  test_one<Iter, Sent>(std::array{8, 6, 7, 3, 4, 1, 2, 5}, 7);
  // Longer sequence with duplicates, a heap.
  test_one<Iter, Sent>(std::array{8, 7, 5, 5, 6, 4, 1, 2, 3, 2}, 10);
  // Longer sequence with duplicates, not a heap.
  test_one<Iter, Sent>(std::array{7, 5, 5, 6, 4, 1, 2, 3, 2, 8}, 3);
  // All elements are the same.
  test_one<Iter, Sent>(std::array{1, 1, 1}, 3);
}

template <class Iter>
constexpr void test_iter() {
  test_iter_sent<Iter, Iter>();
  test_iter_sent<Iter, sentinel_wrapper<Iter>>();
}

constexpr void test_iterators() {
  test_iter<random_access_iterator<int*>>();
  test_iter<contiguous_iterator<int*>>();
  test_iter<int*>();
  test_iter<const int*>();
}

constexpr bool test() {
  test_iterators();

  { // A custom comparator works.
    std::ranges::less ls;
    std::ranges::greater gt;
    std::array in = {1, 3, 2, 5, 4, 7, 8, 6};

    { // (iterator, sentinel) overload.
      auto result_default_comp = std::ranges::is_heap_until(in.begin(), in.end(), ls);
      assert(result_default_comp == in.begin() + 1);
      auto result_custom_comp = std::ranges::is_heap_until(in.begin(), in.end(), gt);
      assert(result_custom_comp == in.end());
    }

    { // (range) overload.
      auto result_default_comp = std::ranges::is_heap_until(in, ls);
      assert(result_default_comp == in.begin() + 1);
      auto result_custom_comp = std::ranges::is_heap_until(in, gt);
      assert(result_custom_comp == in.end());
    }
  }

  { // A custom projection works.
    struct A {
      int x;
      constexpr auto operator<=>(const A&) const = default;
    };

    std::array in = {A{-8}, A{-6}, A{-7}, A{-3}, A{-4}, A{-1}, A{-5}, A{-2}};
    auto negate = [](A a) { return a.x * -1; };

    { // (iterator, sentinel) overload.
      auto result_default_comp = std::ranges::is_heap_until(in.begin(), in.end(), {});
      assert(result_default_comp == in.begin() + 1);
      auto result_custom_comp = std::ranges::is_heap_until(in.begin(), in.end(), {}, negate);
      assert(result_custom_comp == in.end());
    }

    { // (range) overload.
      auto result_default_comp = std::ranges::is_heap_until(in, {});
      assert(result_default_comp == in.begin() + 1);
      auto result_custom_comp = std::ranges::is_heap_until(in, {}, negate);
      assert(result_custom_comp == in.end());
    }
  }


  return true;
}

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

  return 0;
}