libcxx/test/std/algorithms/alg.modifying.operations/alg.shift/ranges_shift_right.pass.cpp

//===----------------------------------------------------------------------===//
//
// 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, c++20
// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=9000000

// <algorithm>

// template<permutable I, sentinel_for<I> S>
//   constexpr subrange<I> ranges::shift_right(I first, S last, iter_difference_t<I> n);

// template<forward_range R>
//   requires permutable<iterator_t<R>>
//   constexpr borrowed_subrange_t<R> ranges::shift_right(R&& r, range_difference_t<R> n)

#include <algorithm>
#include <array>
#include <cassert>
#include <ranges>
#include <vector>

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

struct InvalidDifferenceT {};

template <class Iter, class Sent = Iter, class N = std::iter_difference_t<Iter>>
concept HasShiftRightIt = requires(Iter iter, Sent sent, N n) { std::ranges::shift_right(iter, sent, n); };

static_assert(HasShiftRightIt<int*>);
static_assert(HasShiftRightIt<int*, sentinel_wrapper<int*>>);
static_assert(HasShiftRightIt<int*, sized_sentinel<int*>>);
static_assert(!HasShiftRightIt<int*, int*, InvalidDifferenceT>);
static_assert(!HasShiftRightIt<int*, int, int>);

static_assert(!HasShiftRightIt<ForwardIteratorNotDerivedFrom>);
static_assert(!HasShiftRightIt<PermutableNotForwardIterator>);
static_assert(!HasShiftRightIt<PermutableNotSwappable>);

template <class Range, class N = std::ranges::range_difference_t<Range>>
concept HasShiftRightR = requires(Range range, N n) { std::ranges::shift_right(range, n); };

static_assert(HasShiftRightR<UncheckedRange<int*>>);
static_assert(!HasShiftRightR<UncheckedRange<int*>, InvalidDifferenceT>);

static_assert(!HasShiftRightR<ForwardRangeNotDerivedFrom>);
static_assert(!HasShiftRightR<PermutableRangeNotForwardIterator>);
static_assert(!HasShiftRightR<PermutableRangeNotSwappable>);

struct TrackCopyMove {
  mutable int copy_count = 0;
  int move_count         = 0;

  constexpr TrackCopyMove() = default;
  constexpr TrackCopyMove(const TrackCopyMove& other) : copy_count(other.copy_count), move_count(other.move_count) {
    ++copy_count;
    ++other.copy_count;
  }

  constexpr TrackCopyMove(TrackCopyMove&& other) noexcept : copy_count(other.copy_count), move_count(other.move_count) {
    ++move_count;
    ++other.move_count;
  }
  constexpr TrackCopyMove& operator=(const TrackCopyMove& other) {
    ++copy_count;
    ++other.copy_count;
    return *this;
  }
  constexpr TrackCopyMove& operator=(TrackCopyMove&& other) noexcept {
    ++move_count;
    ++other.move_count;
    return *this;
  }
};

template <class Iter, class Sent>
constexpr void test_iter_sent() {
  {
    const std::array<int, 8> original = {3, 1, 4, 1, 5, 9, 2, 6};

    // (iterator, sentinel) overload
    for (size_t n = 0; n <= original.size(); ++n) {
      for (size_t k = 0; k <= n + 2; ++k) {
        std::vector<int> scratch(n);
        auto begin = Iter(scratch.data());
        auto end   = Sent(Iter(scratch.data() + n));
        std::ranges::copy(original.begin(), original.begin() + n, begin);
        std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::shift_right(begin, end, k);

        assert(result.end() == end);
        if (k < n) {
          assert(result.begin() == Iter(scratch.data() + k));
          assert(std::ranges::equal(original.begin(), original.begin() + n - k, result.begin(), result.end()));
        } else {
          assert(result.begin() == end);
          assert(std::ranges::equal(original.begin(), original.begin() + n, begin, end));
        }
      }
    }

    // (range) overload
    for (size_t n = 0; n <= original.size(); ++n) {
      for (size_t k = 0; k <= n + 2; ++k) {
        std::vector<int> scratch(n);
        auto begin = Iter(scratch.data());
        auto end   = Sent(Iter(scratch.data() + n));
        std::ranges::copy(original.begin(), original.begin() + n, begin);
        auto range                                                      = std::ranges::subrange(begin, end);
        std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::shift_right(range, k);

        assert(result.end() == end);
        if (k < n) {
          assert(result.begin() == Iter(scratch.data() + k));
          assert(std::ranges::equal(original.begin(), original.begin() + n - k, result.begin(), result.end()));
        } else {
          assert(result.begin() == end);
          assert(std::ranges::equal(original.begin(), original.begin() + n, begin, end));
        }
      }
    }
  }
  // n == 0
  {
    std::array<int, 3> input          = {0, 1, 2};
    const std::array<int, 3> expected = {0, 1, 2};

    { // (iterator, sentinel) overload
      auto in                                                         = input;
      auto begin                                                      = Iter(in.data());
      auto end                                                        = Sent(Iter(in.data() + in.size()));
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::shift_right(begin, end, 0);
      assert(std::ranges::equal(expected, result));
      assert(result.begin() == begin);
      assert(result.end() == end);
    }

    { // (range) overload
      auto in                                                         = input;
      auto begin                                                      = Iter(in.data());
      auto end                                                        = Sent(Iter(in.data() + in.size()));
      auto range                                                      = std::ranges::subrange(begin, end);
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::shift_right(range, 0);
      assert(std::ranges::equal(expected, result));
      assert(result.begin() == begin);
      assert(result.end() == end);
    }
  }

  // n == len
  {
    std::array<int, 3> input          = {0, 1, 2};
    const std::array<int, 3> expected = {0, 1, 2};

    { // (iterator, sentinel) overload
      auto in    = input;
      auto begin = Iter(in.data());
      auto end   = Sent(Iter(in.data() + in.size()));
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
          std::ranges::shift_right(begin, end, input.size());
      assert(std::ranges::equal(expected, input));
      assert(result.begin() == end);
      assert(result.end() == end);
    }

    { // (range) overload
      auto in                                                         = input;
      auto begin                                                      = Iter(in.data());
      auto end                                                        = Sent(Iter(in.data() + in.size()));
      auto range                                                      = std::ranges::subrange(begin, end);
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::shift_right(range, input.size());
      assert(std::ranges::equal(expected, input));
      assert(result.begin() == end);
      assert(result.end() == end);
    }
  }

  // n > len
  {
    std::array<int, 3> input          = {0, 1, 2};
    const std::array<int, 3> expected = {0, 1, 2};

    { // (iterator, sentinel) overload
      auto in    = input;
      auto begin = Iter(in.data());
      auto end   = Sent(Iter(in.data() + in.size()));
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
          std::ranges::shift_right(begin, end, input.size() + 1);
      assert(std::ranges::equal(expected, input));
      assert(result.begin() == end);
      assert(result.end() == end);
    }

    { // (range) overload
      auto in    = input;
      auto begin = Iter(in.data());
      auto end   = Sent(Iter(in.data() + in.size()));
      auto range = std::ranges::subrange(begin, end);
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
          std::ranges::shift_right(range, input.size() + 1);
      assert(std::ranges::equal(expected, input));
      assert(result.begin() == end);
      assert(result.end() == end);
    }
  }

  // empty range
  {
    std::vector<int> input          = {};
    const std::vector<int> expected = {};
    { // (iterator, sentinel) overload
      auto in    = input;
      auto begin = Iter(in.data());
      auto end   = Sent(Iter(in.data() + in.size()));
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
          std::ranges::shift_right(begin, end, input.size() + 1);
      assert(std::ranges::equal(expected, input));
      assert(result.begin() == begin);
      assert(result.end() == begin);
    }

    { // (range) overload
      auto in    = input;
      auto begin = Iter(in.data());
      auto end   = Sent(Iter(in.data() + in.size()));
      auto range = std::ranges::subrange(begin, end);
      std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
          std::ranges::shift_right(range, input.size() + 1);
      assert(std::ranges::equal(expected, input));
      assert(result.begin() == begin);
      assert(result.end() == begin);
    }
  }
}

constexpr bool test() {
  types::for_each(types::forward_iterator_list<int*>{}, []<class Iter> {
    test_iter_sent<Iter, Iter>();
    test_iter_sent<Iter, sentinel_wrapper<Iter>>();
    test_iter_sent<Iter, sized_sentinel<Iter>>();
  });

  // Complexity: At most (last - first) - n assignments or swaps.
  {
    constexpr int length = 100;
    constexpr int n      = length / 2;
    auto make_vec        = []() {
      std::vector<TrackCopyMove> vec;
      vec.reserve(length);
      for (int i = 0; i < length; ++i) {
        vec.emplace_back();
      }
      return vec;
    };

    { // (iterator, sentinel) overload
      auto input  = make_vec();
      auto result = std::ranges::shift_right(input.begin(), input.end(), n);
      assert(result.begin() == input.begin() + length - n);
      assert(result.end() == input.end());

      auto total_copies = 0;
      auto total_moves  = 0;
      for (auto it = result.begin(); it != result.end(); ++it) {
        const auto& item = *it;
        total_copies += item.copy_count;
        total_moves += item.move_count;
      }

      assert(total_copies == 0);
      assert(total_moves <= length - n);
    }

    { // (range) overload
      auto input  = make_vec();
      auto result = std::ranges::shift_right(input, n);
      assert(result.begin() == input.begin() + length - n);
      assert(result.end() == input.end());

      auto total_copies = 0;
      auto total_moves  = 0;
      for (auto it = result.begin(); it != result.end(); ++it) {
        const auto& item = *it;
        total_copies += item.copy_count;
        total_moves += item.move_count;
      }

      assert(total_copies == 0);
      assert(total_moves <= length - n);
    }
  }

  return true;
}

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

  return 0;
}