//===----------------------------------------------------------------------===//
//
// 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 bool is_heap(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 bool is_heap(R&& r, Comp comp = {}, Proj proj = {});                             // Since C++20

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

#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 HasIsHeapIter =
    requires(Iter&& iter, Sent&& sent, Comp&& comp) {
      std::ranges::is_heap(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp));
    };

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

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

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

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

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

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

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

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

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

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

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

  { // (iterator, sentinel) overload.
    std::same_as<bool> decltype(auto) result = std::ranges::is_heap(begin, end);
    assert(result == expected);
  }

  { // (range) overload.
    auto range = std::ranges::subrange(begin, end);
    std::same_as<bool> decltype(auto) result = std::ranges::is_heap(range);
    assert(result == expected);
  }
}

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

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.
      assert(!std::ranges::is_heap(in.begin(), in.end(), ls));
      assert(std::ranges::is_heap(in.begin(), in.end(), gt));
    }

    { // (range) overload.
      assert(!std::ranges::is_heap(in, ls));
      assert(std::ranges::is_heap(in, gt));
    }
  }

  { // 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.
      assert(!std::ranges::is_heap(in.begin(), in.end(), {}));
      assert(std::ranges::is_heap(in.begin(), in.end(), {}, negate));
    }

    { // (range) overload.
      assert(!std::ranges::is_heap(in, {}));
      assert(std::ranges::is_heap(in, {}, negate));
    }
  }


  return true;
}

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

  return 0;
}