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

// Test std::partial_sort stability randomization

// UNSUPPORTED: c++03
// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY

#include <algorithm>
#include <array>
#include <cassert>
#include <functional>
#include <iterator>
#include <vector>

#include "test_macros.h"

struct MyType {
  int value = 0;
  constexpr bool operator<(const MyType& other) const { return value < other.value; }
};

std::vector<MyType> deterministic() {
  static constexpr int kSize = 100;
  std::vector<MyType> v;
  v.resize(kSize);
  for (int i = 0; i < kSize; ++i) {
    v[i].value = (i % 2 ? 1 : kSize / 2 + i);
  }
  auto comp = std::less<MyType>();
  std::__partial_sort_impl<std::_ClassicAlgPolicy>(v.begin(), v.begin() + kSize / 2, v.end(), comp);
  return v;
}

void test_randomization() {
  static constexpr int kSize = 100;
  std::vector<MyType> v;
  v.resize(kSize);
  for (int i = 0; i < kSize; ++i) {
    v[i].value = (i % 2 ? 1 : kSize / 2 + i);
  }
  auto deterministic_v = deterministic();
  std::partial_sort(v.begin(), v.begin() + kSize / 2, v.end());
  bool all_equal = true;
  for (int i = 0; i < kSize; ++i) {
    if (v[i].value != deterministic_v[i].value) {
      all_equal = false;
    }
  }
  assert(!all_equal);
}

void test_same() {
  static constexpr int kSize = 100;
  std::vector<MyType> v;
  v.resize(kSize);
  for (int i = 0; i < kSize; ++i) {
    v[i].value = (i % 2 ? 1 : kSize / 2 + i);
  }
  auto snapshot_v = v;
  auto snapshot_custom_v = v;
  std::partial_sort(v.begin(), v.begin() + kSize / 2, v.end());
  std::partial_sort(snapshot_v.begin(), snapshot_v.begin() + kSize / 2, snapshot_v.end());
  std::partial_sort(snapshot_custom_v.begin(), snapshot_custom_v.begin() + kSize / 2, snapshot_custom_v.end(), std::less<MyType>());
  bool all_equal = true;
  for (int i = 0; i < kSize; ++i) {
    if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) {
      all_equal = false;
    }
    if (i < kSize / 2) {
      assert(v[i].value == 1);
    }
  }
  assert(all_equal);
}

#if TEST_STD_VER > 17
constexpr bool test_constexpr() {
  std::array<MyType, 10> v;
  for (int i = 9; i >= 0; --i) {
    v[9 - i].value = i;
  }
  std::partial_sort(v.begin(), v.begin() + 5, v.end());
  return std::is_sorted(v.begin(), v.begin() + 5);
}
#endif

int main(int, char**) {
  test_randomization();
  test_same();
#if TEST_STD_VER > 17
  static_assert(test_constexpr(), "");
#endif
  return 0;
}