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

// Making this test file support C++03 is difficult; the lack of support for initializer lists is a major issue.
// UNSUPPORTED: c++03

// <algorithm>

#include <algorithm>
#include <array>
#include <cassert>
#include <random>
#include <set>

#include "test_macros.h"

// This file contains checks for lifetime issues across all the classic algorithms. It uses two complementary
// approaches:
// - runtime checks using a proxy iterator that tracks the lifetime of itself and its objects to catch potential
//   lifetime issues;
// - `constexpr` checks using a `constexpr`-friendly proxy iterator that catch undefined behavior.

// A random-access proxy iterator that tracks the lifetime of itself and its `value_type` and `reference` objects to
// prevent potential lifetime issues in algorithms.
//
// This class cannot be `constexpr` because its cache is a static variable. The cache cannot be provided as
// a constructor parameter because `LifetimeIterator` has to be default-constructible.
class LifetimeIterator {
  // The cache simply tracks addresses of the local variables.
  class LifetimeCache {
    std::set<const void*> cache_;

  public:
    bool contains(const void* ptr) const { return cache_.find(ptr) != cache_.end(); }

    void insert(const void* ptr) {
      assert(!contains(ptr));
      cache_.insert(ptr);
    }

    void erase(const void* ptr) {
      assert(contains(ptr));
      cache_.erase(ptr);
    }
  };

 public:
  struct Value {
    int i_;
    bool moved_from_ = false; // Check for double moves and reads after moving.

    Value() { lifetime_cache.insert(this); }
    Value(int i) : i_(i) { lifetime_cache.insert(this); }
    ~Value() { lifetime_cache.erase(this); }

    Value(const Value& rhs) : i_(rhs.i_) {
      assert(lifetime_cache.contains(&rhs));
      assert(!rhs.moved_from_);

      lifetime_cache.insert(this);
    }

    Value(Value&& rhs) noexcept : i_(rhs.i_) {
      assert(lifetime_cache.contains(&rhs));

      assert(!rhs.moved_from_);
      rhs.moved_from_ = true;

      // It's ok if it throws -- since it's a test, terminating the program is acceptable.
      lifetime_cache.insert(this);
    }

    Value& operator=(const Value& rhs) {
      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
      assert(!rhs.moved_from_);

      i_ = rhs.i_;
      moved_from_ = false;

      return *this;
    }

    Value& operator=(Value&& rhs) noexcept {
      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));

      assert(!rhs.moved_from_);
      rhs.moved_from_ = true;

      i_ = rhs.i_;
      moved_from_ = false;

      return *this;
    }

    friend bool operator<(const Value& lhs, const Value& rhs) {
      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
      assert(!lhs.moved_from_ && !rhs.moved_from_);

      return lhs.i_ < rhs.i_;
    }

    friend bool operator==(const Value& lhs, const Value& rhs) {
      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
      assert(!lhs.moved_from_ && !rhs.moved_from_);

      return lhs.i_ == rhs.i_;
    }

  };

  struct Reference {
    Value* v_;
    bool moved_from_ = false; // Check for double moves and reads after moving.

    Reference(Value& v) : v_(&v) {
      lifetime_cache.insert(this);
    }

    ~Reference() {
      lifetime_cache.erase(this);
    }

    Reference(const Reference& rhs) : v_(rhs.v_) {
      assert(lifetime_cache.contains(&rhs));
      assert(!rhs.moved_from_);

      lifetime_cache.insert(this);
    }

    Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
      assert(lifetime_cache.contains(&rhs));

      assert(!rhs.moved_from_);
      rhs.moved_from_ = true;

      lifetime_cache.insert(this);
    }

    Reference& operator=(const Reference& rhs) {
      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
      assert(!rhs.moved_from_);

      *v_ = *rhs.v_;
      moved_from_ = false;

      return *this;
    }

    Reference& operator=(Reference&& rhs) noexcept {
      assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));

      assert(!rhs.moved_from_);
      rhs.moved_from_ = true;

      *v_ = *rhs.v_;
      moved_from_ = false;

      return *this;
    }

    operator Value() const {
      assert(lifetime_cache.contains(this));
      assert(!moved_from_);

      return *v_;
    }

    Reference& operator=(Value v) {
      assert(lifetime_cache.contains(this));
      assert(!moved_from_);

      *v_ = v;
      moved_from_ = false;

      return *this;
    }

    friend bool operator<(const Reference& lhs, const Reference& rhs) {
      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
      assert(!lhs.moved_from_ && !rhs.moved_from_);

      return *lhs.v_ < *rhs.v_;
    }

    friend bool operator==(const Reference& lhs, const Reference& rhs) {
      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
      assert(!lhs.moved_from_ && !rhs.moved_from_);

      return *lhs.v_ == *rhs.v_;
    }

    friend void swap(Reference lhs, Reference rhs) {
      assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
      assert(!lhs.moved_from_ && !rhs.moved_from_);

      std::swap(*(lhs.v_), *(rhs.v_));
    }
  };

  using difference_type   = int;
  using value_type        = Value;
  using reference         = Reference;
  using pointer           = void;
  using iterator_category = std::random_access_iterator_tag;

  Value* ptr_ = nullptr;
  bool moved_from_ = false; // Check for double moves and reads after moving.

  LifetimeIterator() = default;
  LifetimeIterator(Value* ptr) : ptr_(ptr) {}

  LifetimeIterator(const LifetimeIterator& rhs) : ptr_(rhs.ptr_) {
    assert(!rhs.moved_from_);
  }

  LifetimeIterator& operator=(const LifetimeIterator& rhs) {
    assert(!rhs.moved_from_);

    ptr_ = rhs.ptr_;
    moved_from_ = false;

    return *this;
  }

  LifetimeIterator(LifetimeIterator&& rhs) noexcept : ptr_(rhs.ptr_) {
    assert(!rhs.moved_from_);
    rhs.moved_from_ = true;
    rhs.ptr_ = nullptr;
  }

  LifetimeIterator& operator=(LifetimeIterator&& rhs) noexcept {
    assert(!rhs.moved_from_);
    rhs.moved_from_ = true;
    moved_from_ = false;

    ptr_ = rhs.ptr_;
    rhs.ptr_ = nullptr;

    return *this;
  }

  Reference operator*() const {
    assert(!moved_from_);
    return Reference(*ptr_);
  }

  LifetimeIterator& operator++() {
    assert(!moved_from_);

    ++ptr_;
    return *this;
  }

  LifetimeIterator operator++(int) {
    assert(!moved_from_);

    auto tmp = *this;
    ++*this;
    return tmp;
  }

  friend bool operator==(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ == rhs.ptr_;
  }
  friend bool operator!=(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ != rhs.ptr_;
  }

  LifetimeIterator& operator--() {
    assert(!moved_from_);

    --ptr_;
    return *this;
  }

  LifetimeIterator operator--(int) {
    assert(!moved_from_);

    auto tmp = *this;
    --*this;
    return tmp;
  }

  LifetimeIterator& operator+=(difference_type n) {
    assert(!moved_from_);

    ptr_ += n;
    return *this;
  }

  LifetimeIterator& operator-=(difference_type n) {
    assert(!moved_from_);

    ptr_ -= n;
    return *this;
  }

  Reference operator[](difference_type i) const {
    assert(!moved_from_);
    return Reference(*(ptr_ + i));
  }

  friend bool operator<(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ < rhs.ptr_;
  }

  friend bool operator>(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ > rhs.ptr_;
  }

  friend bool operator<=(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ <= rhs.ptr_;
  }

  friend bool operator>=(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ >= rhs.ptr_;
  }

  friend LifetimeIterator operator+(const LifetimeIterator& lhs, difference_type n) {
    assert(!lhs.moved_from_);
    return LifetimeIterator(lhs.ptr_ + n);
  }

  friend LifetimeIterator operator+(difference_type n, const LifetimeIterator& lhs) {
    assert(!lhs.moved_from_);
    return LifetimeIterator(n + lhs.ptr_);
  }

  friend LifetimeIterator operator-(const LifetimeIterator& lhs, difference_type n) {
    assert(!lhs.moved_from_);
    return LifetimeIterator(lhs.ptr_ - n);
  }

  friend difference_type operator-(LifetimeIterator lhs, LifetimeIterator rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return static_cast<int>(lhs.ptr_ - rhs.ptr_);
  }

  static LifetimeCache lifetime_cache;
};

LifetimeIterator::LifetimeCache LifetimeIterator::lifetime_cache;

#if TEST_STD_VER > 17
// A constexpr-friendly proxy iterator to check for undefined behavior in algorithms (since undefined behavior is
// statically caught in `constexpr` context).
class ConstexprIterator {
 public:
  struct Reference {
    int* v_;
    bool moved_from_ = false; // Check for double moves and reads after moving.

    constexpr Reference(int& v) : v_(&v) { }

    constexpr Reference(const Reference& rhs) = default;
    constexpr Reference& operator=(const Reference& rhs) {
      assert(!rhs.moved_from_);
      v_ = rhs.v_;
      moved_from_ = false;

      return *this;
    }

    constexpr Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
      assert(!rhs.moved_from_);
      rhs.moved_from_ = true;
    }

    constexpr Reference& operator=(Reference&& rhs) noexcept {
      assert(!rhs.moved_from_);
      rhs.moved_from_ = true;
      moved_from_ = false;

      v_ = rhs.v_;
      return *this;
    }

    constexpr operator int() const {
      assert(!moved_from_);
      return *v_;
    }

    constexpr Reference& operator=(int v) {
      *v_ = v;
      moved_from_ = false;

      return *this;
    }

    friend constexpr bool operator<(const Reference& lhs, const Reference& rhs) {
      assert(!lhs.moved_from_ && !rhs.moved_from_);
      return *lhs.v_ < *rhs.v_;
    }

    friend constexpr bool operator==(const Reference& lhs, const Reference& rhs) {
      assert(!lhs.moved_from_ && !rhs.moved_from_);
      return *lhs.v_ == *rhs.v_;
    }

    friend constexpr void swap(Reference lhs, Reference rhs) {
      assert(!lhs.moved_from_ && !rhs.moved_from_);
      std::swap(*(lhs.v_), *(rhs.v_));
    }
  };

  using difference_type   = int;
  using value_type        = int;
  using reference         = Reference;
  using pointer           = void;
  using iterator_category = std::random_access_iterator_tag;

  int* ptr_ = nullptr;
  bool moved_from_ = false; // Check for double moves and reads after moving.

  constexpr ConstexprIterator() = default;
  constexpr ConstexprIterator(int* ptr) : ptr_(ptr) {}

  constexpr ConstexprIterator(const ConstexprIterator& rhs) : ptr_(rhs.ptr_) {
    assert(!rhs.moved_from_);
  }

  constexpr ConstexprIterator& operator=(const ConstexprIterator& rhs) {
    assert(!rhs.moved_from_);

    ptr_ = rhs.ptr_;
    moved_from_ = false;

    return *this;
  }

  constexpr ConstexprIterator(ConstexprIterator&& rhs) noexcept : ptr_(rhs.ptr_) {
    assert(!rhs.moved_from_);
    rhs.moved_from_ = true;
    rhs.ptr_ = nullptr;
  }

  constexpr ConstexprIterator& operator=(ConstexprIterator&& rhs) noexcept {
    assert(!rhs.moved_from_);
    rhs.moved_from_ = true;
    moved_from_ = false;

    ptr_ = rhs.ptr_;
    rhs.ptr_ = nullptr;

    return *this;
  }

  constexpr Reference operator*() const {
    assert(!moved_from_);
    return Reference(*ptr_);
  }

  constexpr ConstexprIterator& operator++() {
    assert(!moved_from_);

    ++ptr_;
    return *this;
  }

  constexpr ConstexprIterator operator++(int) {
    assert(!moved_from_);

    auto tmp = *this;
    ++*this;
    return tmp;
  }

  friend constexpr bool operator==(const ConstexprIterator& lhs, const ConstexprIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ == rhs.ptr_;
  }

  friend constexpr bool operator!=(const ConstexprIterator& lhs, const ConstexprIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ != rhs.ptr_;
  }

  constexpr ConstexprIterator& operator--() {
    assert(!moved_from_);

    --ptr_;
    return *this;
  }

  constexpr ConstexprIterator operator--(int) {
    assert(!moved_from_);

    auto tmp = *this;
    --*this;
    return tmp;
  }

  constexpr ConstexprIterator& operator+=(difference_type n) {
    assert(!moved_from_);

    ptr_ += n;
    return *this;
  }

  constexpr ConstexprIterator& operator-=(difference_type n) {
    assert(!moved_from_);

    ptr_ -= n;
    return *this;
  }

  constexpr Reference operator[](difference_type i) const {
    return Reference(*(ptr_ + i));
  }

  friend constexpr auto operator<=>(const ConstexprIterator& lhs, const ConstexprIterator& rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return lhs.ptr_ <=> rhs.ptr_;
  }

  friend constexpr ConstexprIterator operator+(const ConstexprIterator& lhs, difference_type n) {
    assert(!lhs.moved_from_);
    return ConstexprIterator(lhs.ptr_ + n);
  }

  friend constexpr ConstexprIterator operator+(difference_type n, const ConstexprIterator& lhs) {
    assert(!lhs.moved_from_);
    return ConstexprIterator(n + lhs.ptr_);
  }

  friend constexpr ConstexprIterator operator-(const ConstexprIterator& lhs, difference_type n) {
    assert(!lhs.moved_from_);
    return ConstexprIterator(lhs.ptr_ - n);
  }

  friend constexpr difference_type operator-(ConstexprIterator lhs, ConstexprIterator rhs) {
    assert(!lhs.moved_from_ && !rhs.moved_from_);
    return static_cast<int>(lhs.ptr_ - rhs.ptr_);
  }
};

#endif // TEST_STD_VER > 17

template <class T, std::size_t N = 32>
class Input {
  using Array = std::array<T, N>;

  std::size_t size_ = 0;
  Array values_ = {};

public:
  template <std::size_t N2>
  TEST_CONSTEXPR_CXX20 Input(std::array<T, N2> from) {
    static_assert(N2 <= N, "");

    std::copy(from.begin(), from.end(), begin());
    size_ = N2;
  }

  TEST_CONSTEXPR_CXX20 typename Array::iterator begin() { return values_.begin(); }
  TEST_CONSTEXPR_CXX20 typename Array::iterator end() { return values_.begin() + size_; }
  TEST_CONSTEXPR_CXX20 std::size_t size() const { return size_; }
};

// TODO: extend `Value` and `Reference` so that it's possible to pass plain integers to all the algorithms.

// Several generic inputs that are useful for many algorithms. Provides two unsorted sequences with and without
// duplicates, with positive and negative values; and a few corner cases, like an empty sequence, a sequence of all
// duplicates, and so on.
template <class Iter>
TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_simple_in() {
  using T = typename Iter::value_type;
  std::array<Input<T>, 8> result = {
    Input<T>({std::array<T, 0>{ }}),
    Input<T>({std::array<T, 1>{ T{1} }}),
    Input<T>({std::array<T, 1>{ T{-1} }}),
    Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
    Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
    Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
    Input<T>({std::array<T, 9>{ T{-8}, {6}, {3}, {2}, {1}, {5}, {-4}, {-9}, {3} }}),
    Input<T>({std::array<T, 9>{ T{-8}, {3}, {3}, {2}, {5}, {-4}, {-4}, {-4}, {1} }}),
  };
  return result;
}

// Sorted inputs of varying lengths.
template <class Iter>
TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_sorted_in() {
  using T = typename Iter::value_type;
  std::array<Input<T>, 8> result = {
    Input<T>({std::array<T, 0>{ }}),
    Input<T>({std::array<T, 1>{ T{1} }}),
    Input<T>({std::array<T, 1>{ T{-1} }}),
    Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
    Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
    Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
    Input<T>({std::array<T, 8>{ T{-8}, {-5}, {-3}, {-1}, {1}, {4}, {5}, {9} }}),
    Input<T>({std::array<T, 11>{ T{-8}, {-5}, {-3}, {-3}, {-1}, {1}, {4}, {5}, {5}, {9}, {9} }}),
  };
  return result;
}

// Inputs for testing `std::sort`. These have been manually verified to exercise all internal functions in `std::sort`
// except the branchless sort ones (which can't be triggered with proxy arrays).
template <class Iter>
TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_sort_test_in() {
  using T = typename Iter::value_type;
  std::array<Input<T>, 8> result = {
    Input<T>({std::array<T, 0>{ }}),
    Input<T>({std::array<T, 1>{ T{1} }}),
    Input<T>({std::array<T, 1>{ T{-1} }}),
    Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
    Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
    Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
    Input<T>({std::array<T, 8>{ T{-8}, {-5}, {-3}, {-1}, {1}, {4}, {5}, {9} }}),
    Input<T>({std::array<T, 11>{ T{-8}, {-5}, {-3}, {-3}, {-1}, {1}, {4}, {5}, {5}, {9}, {9} }}),
  };
  return result;
}

template <class Input, std::size_t N, class Func>
TEST_CONSTEXPR_CXX20 void test(std::array<Input, N> inputs, Func func) {
  for (auto&& in : inputs) {
    func(in.begin(), in.end());
  }
}

template <class Input, std::size_t N, class Func>
TEST_CONSTEXPR_CXX20 void test_n(std::array<Input, N> inputs, Func func) {
  for (auto&& in : inputs) {
    func(in.begin(), in.size());
  }
}

constexpr int to_int(int x) { return x; }
int to_int(LifetimeIterator::Value x) { return x.i_; }

std::mt19937 rand_gen() { return std::mt19937(); }

template <class Iter>
TEST_CONSTEXPR_CXX20 bool test() {
  using T = typename Iter::value_type;

  auto is_neg = [](const T& val) { return to_int(val) < 0; };
  auto gen = [] { return T{42}; };
  auto identity = [] (T val) -> T { return val; };

  constexpr int N = 32;
  std::array<T, N> output;
  auto out = output.begin();
  T x{1};
  T y{3};

  auto simple_in = get_simple_in<Iter>();
  auto sorted_in = get_sorted_in<Iter>();
  auto sort_test_in = get_sort_test_in<Iter>();

  using I = Iter;

  test(simple_in, [&](I b, I e) { (void) std::any_of(b, e, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::all_of(b, e, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::none_of(b, e, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::find(b, e, T{1}); });
  test(simple_in, [&](I b, I e) { (void) std::find_if(b, e, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::find_if_not(b, e, is_neg); });
  // TODO: find_first_of
  test(simple_in, [&](I b, I e) { (void) std::adjacent_find(b, e); });
  // TODO: mismatch
  // TODO: equal
  // TODO: lexicographical_compare
  // TODO: partition_point
  test(sorted_in, [&](I b, I e) { (void) std::lower_bound(b, e, x); });
  test(sorted_in, [&](I b, I e) { (void) std::upper_bound(b, e, x); });
  test(sorted_in, [&](I b, I e) { (void) std::equal_range(b, e, x); });
  test(sorted_in, [&](I b, I e) { (void) std::binary_search(b, e, x); });
  // `min`, `max` and `minmax` don't use iterators.
  test(simple_in, [&](I b, I e) { (void) std::min_element(b, e); });
  test(simple_in, [&](I b, I e) { (void) std::max_element(b, e); });
  test(simple_in, [&](I b, I e) { (void) std::minmax_element(b, e); });
  test(simple_in, [&](I b, I e) { (void) std::count(b, e, x); });
  test(simple_in, [&](I b, I e) { (void) std::count_if(b, e, is_neg); });
  // TODO: search
  // TODO: search_n
  // TODO: find_end
  // TODO: is_partitioned
  // TODO: is_sorted
  // TODO: is_sorted_until
  // TODO: includes
  // TODO: is_heap
  // TODO: is_heap_until
  // `clamp` doesn't use iterators.
  // TODO: is_permutation
  test(simple_in, [&](I b, I e) { (void) std::for_each(b, e, is_neg); });
#if TEST_STD_VER > 14
  test_n(simple_in, [&](I b, std::size_t n) { (void) std::for_each_n(b, n, is_neg); });
#endif
  test(simple_in, [&](I b, I e) { (void) std::copy(b, e, out); });
  test_n(simple_in, [&](I b, std::size_t n) { (void) std::copy_n(b, n, out); });
  test(simple_in, [&](I b, I e) { (void) std::copy_backward(b, e, out + N); });
  test(simple_in, [&](I b, I e) { (void) std::copy_if(b, e, out, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::move(b, e, out); });
  test(simple_in, [&](I b, I e) { (void) std::move_backward(b, e, out + N); });
  test(simple_in, [&](I b, I e) { (void) std::transform(b, e, out, identity); });
  test(simple_in, [&](I b, I e) { (void) std::generate(b, e, gen); });
  test_n(simple_in, [&](I b, std::size_t n) { (void) std::generate_n(b, n, gen); });
  test(simple_in, [&](I b, I e) { (void) std::remove_copy(b, e, out, x); });
  test(simple_in, [&](I b, I e) { (void) std::remove_copy_if(b, e, out, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::replace(b, e, x, y); });
  test(simple_in, [&](I b, I e) { (void) std::replace_if(b, e, is_neg, y); });
  test(simple_in, [&](I b, I e) { (void) std::replace_copy(b, e, out, x, y); });
  test(simple_in, [&](I b, I e) { (void) std::replace_copy_if(b, e, out, is_neg, y); });
  // TODO: swap_ranges
  test(simple_in, [&](I b, I e) { (void) std::reverse_copy(b, e, out); });
  // TODO: rotate_copy
  // TODO: sample
  // TODO: unique_copy
  // TODO: partition_copy
  // TODO: partial_sort_copy
  // TODO: merge
  // TODO: set_difference
  // TODO: set_intersection
  // TODO: set_symmetric_difference
  // TODO: set_union
  test(simple_in, [&](I b, I e) { (void) std::remove(b, e, x); });
  test(simple_in, [&](I b, I e) { (void) std::remove_if(b, e, is_neg); });
  test(simple_in, [&](I b, I e) { (void) std::reverse(b, e); });
  // TODO: rotate
  if (!TEST_IS_CONSTANT_EVALUATED)
    test(simple_in, [&](I b, I e) { (void) std::shuffle(b, e, rand_gen()); });
  // TODO: unique
  test(simple_in, [&](I b, I e) { (void) std::partition(b, e, is_neg); });
  if (!TEST_IS_CONSTANT_EVALUATED)
    test(simple_in, [&](I b, I e) { (void) std::stable_partition(b, e, is_neg); });
  if (!TEST_IS_CONSTANT_EVALUATED)
    test(sort_test_in, [&](I b, I e) { (void) std::sort(b, e); });
  if (!TEST_IS_CONSTANT_EVALUATED)
    test(sort_test_in, [&](I b, I e) { (void) std::stable_sort(b, e); });
  // TODO: partial_sort
  // TODO: nth_element
  // TODO: inplace_merge
  test(simple_in, [&](I b, I e) { (void) std::make_heap(b, e); });
  // TODO: push_heap
  // TODO: pop_heap
  // TODO: sort_heap
  test(simple_in, [&](I b, I e) { (void) std::prev_permutation(b, e); });
  test(simple_in, [&](I b, I e) { (void) std::next_permutation(b, e); });

  // TODO: algorithms in `<numeric>`
  // TODO: algorithms in `<memory>`

  return true;
}

void test_all() {
  test<LifetimeIterator>();
#if TEST_STD_VER > 17 // Most algorithms are only `constexpr` starting from C++20.
  static_assert(test<ConstexprIterator>());
#endif
}

int main(int, char**) {
  test_all();

  return 0;
}