//===----------------------------------------------------------------------===//
//
// 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 Gen>
//   requires permutable<I> &&
//            uniform_random_bit_generator<remove_reference_t<Gen>>
//   I shuffle(I first, S last, Gen&& g);                                                           // Since C++20
//
// template<random_access_range R, class Gen>
//   requires permutable<iterator_t<R>> &&
//            uniform_random_bit_generator<remove_reference_t<Gen>>
//   borrowed_iterator_t<R> shuffle(R&& r, Gen&& g);                                                // Since C++20

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

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

class RandGen {
public:
  constexpr static std::size_t min() { return 0; }
  constexpr static std::size_t max() { return 255; }

  constexpr std::size_t operator()() {
    flip = !flip;
    return flip;
  }

private:
  bool flip = false;
};

static_assert(std::uniform_random_bit_generator<RandGen>);
// `std::uniform_random_bit_generator` is a subset of requirements of `__libcpp_random_is_valid_urng`. Make sure that
// a type satisfying the required minimum is still accepted by `ranges::shuffle`.
LIBCPP_STATIC_ASSERT(!std::__libcpp_random_is_valid_urng<RandGen>::value);

struct BadGen {
  constexpr static std::size_t min() { return 255; }
  constexpr static std::size_t max() { return 0; }
  constexpr std::size_t operator()() const;
};
static_assert(!std::uniform_random_bit_generator<BadGen>);

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

template <class Iter = int*, class Sent = int*, class Gen = RandGen>
concept HasShuffleIter =
    requires(Iter&& iter, Sent&& sent, Gen&& gen) {
      std::ranges::shuffle(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Gen>(gen));
    };

static_assert(HasShuffleIter<int*, int*, RandGen>);

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

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

// !permutable<I>
static_assert(!HasShuffleIter<PermutableNotForwardIterator>);
static_assert(!HasShuffleIter<PermutableNotSwappable>);

// !uniform_random_bit_generator<remove_reference_t<Gen>>
static_assert(!HasShuffleIter<int*, int*, BadGen>);

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

template <class Range, class Gen = RandGen>
concept HasShuffleRange =
    requires(Range&& range, Gen&& gen) {
      std::ranges::shuffle(std::forward<Range>(range), std::forward<Gen>(gen));
    };

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

static_assert(HasShuffleRange<R<int*>, RandGen>);

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

// !permutable<iterator_t<R>>
static_assert(!HasShuffleRange<PermutableNotForwardIterator>);
static_assert(!HasShuffleRange<PermutableNotSwappable>);

// !uniform_random_bit_generator<remove_reference_t<Gen>>
static_assert(!HasShuffleRange<R<int*>, BadGen>);

template <class Iter, class Sent, std::size_t N, class Gen>
void test_one(const std::array<int, N> input, Gen gen) {
  { // (iterator, sentinel) overload.
    auto shuffled = input;
    auto begin = Iter(shuffled.data());
    auto end = Sent(Iter(shuffled.data() + shuffled.size()));

    std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(begin, end, gen);

    assert(result == Iter(shuffled.data() + shuffled.size()));
    // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
    //assert(std::ranges::is_permutation(shuffled, input);
    {
      auto shuffled_sorted = shuffled;
      std::ranges::sort(shuffled_sorted);
      auto original_sorted = input;
      std::ranges::sort(original_sorted);
      assert(shuffled_sorted == original_sorted);
    }
  }

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

    std::same_as<Iter> decltype(auto) result = std::ranges::shuffle(range, gen);

    assert(result == Iter(shuffled.data() + shuffled.size()));
    // TODO(ranges): uncomment `ranges::is_permutation` once https://reviews.llvm.org/D127194 lands and remove sorting.
    //assert(std::ranges::is_permutation(shuffled, input);
    {
      auto shuffled_sorted = shuffled;
      std::ranges::sort(shuffled_sorted);
      auto original_sorted = input;
      std::ranges::sort(original_sorted);
      assert(shuffled_sorted == original_sorted);
    }
  }
}

template <class Iter, class Sent>
void test_iterators_iter_sent() {
  RandGen gen;

  // Empty sequence.
  test_one<Iter, Sent, 0>({}, gen);
  // 1-element sequence.
  test_one<Iter, Sent, 1>({1}, gen);
  // 2-element sequence.
  test_one<Iter, Sent, 2>({2, 1}, gen);
  // 3-element sequence.
  test_one<Iter, Sent, 3>({2, 1, 3}, gen);
  // Longer sequence.
  test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, gen);
  // Longer sequence with duplicates.
  test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, gen);
  // All elements are the same.
  test_one<Iter, Sent, 3>({1, 1, 1}, gen);
}

template <class Iter>
void test_iterators_iter() {
  test_iterators_iter_sent<Iter, Iter>();
  test_iterators_iter_sent<Iter, sentinel_wrapper<Iter>>();
}

void test_iterators() {
  test_iterators_iter<random_access_iterator<int*>>();
  test_iterators_iter<contiguous_iterator<int*>>();
  test_iterators_iter<int*>();
}

// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of the value category of
// the given generator object.
template <class Gen, bool CheckConst = true>
void test_generator() {
  std::array in = {1, 2, 3, 4, 5, 6, 7, 8};
  auto begin = in.begin();
  auto end = in.end();

  { // Lvalue.
    Gen g;
    std::ranges::shuffle(begin, end, g);
    std::ranges::shuffle(in, g);
  }

  if constexpr (CheckConst) { // Const lvalue.
    const Gen g;
    std::ranges::shuffle(begin, end, g);
    std::ranges::shuffle(in, g);
  }

  { // Prvalue.
    std::ranges::shuffle(begin, end, Gen());
    std::ranges::shuffle(in, Gen());
  }

  { // Xvalue.
    Gen g1, g2;
    std::ranges::shuffle(begin, end, std::move(g1));
    std::ranges::shuffle(in, std::move(g2));
  }
}

// Checks the logic for wrapping the given iterator to make sure it works correctly regardless of whether the given
// generator class has a const or non-const invocation operator (or both).
void test_generators() {
  struct GenBase {
    constexpr static std::size_t min() { return 0; }
    constexpr static std::size_t max() { return 255; }
  };
  struct NonconstGen : GenBase {
    std::size_t operator()() { return 1; }
  };
  struct ConstGen : GenBase {
    std::size_t operator()() const { return 1; }
  };
  struct ConstAndNonconstGen : GenBase {
    std::size_t operator()() { return 1; }
    std::size_t operator()() const { return 1; }
  };

  test_generator<ConstGen>();
  test_generator<NonconstGen, /*CheckConst=*/false>();
  test_generator<ConstAndNonconstGen>();
}

void test() {
  test_iterators();
  test_generators();

  { // Complexity: Exactly `(last - first) - 1` swaps.
    {
      std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; //14

      int swaps = 0;
      auto begin = adl::Iterator::TrackSwaps(in.data(), swaps);
      auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps);

      std::ranges::shuffle(begin, end, RandGen());
      int expected = in.size() - 1;
      // Note: our implementation doesn't perform a swap when the distribution returns 0, so the actual number of swaps
      // might be less than specified in the standard.
      assert(swaps <= expected);
      swaps = 0;
    }
  }
}

int main(int, char**) {
  test();
  // Note: `ranges::shuffle` is not `constexpr`.

  return 0;
}