shift.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_SHIFT_HPP__
#define NEFORCE_CORE_ALGORITHM_SHIFT_HPP__

 
#include "NeForce/core/algorithm/search.hpp"
#include "NeForce/core/functional/invoke.hpp"
#include "NeForce/core/numeric/math.hpp"
NEFORCE_BEGIN_NAMESPACE__



NEFORCE_BEGIN_INNER__

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<!(is_ranges_cot_iter_v<Iterator1> && is_ranges_cot_iter_v<Iterator2>), Iterator2>
__copy_aux(Iterator1 first, Iterator1 last,
           Iterator2 result) noexcept(is_nothrow_assignable_v<iter_value_t<Iterator2>, iter_value_t<Iterator1>>) {
    auto n = _NEFORCE distance(first, last);
    for (; n > 0; --n, ++first, ++result) {
        *result = *first;
    }
    return result;
}

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<is_ranges_cot_iter_v<Iterator1> && is_ranges_cot_iter_v<Iterator2>, Iterator2>
__copy_aux(Iterator1 first, Iterator1 last, Iterator2 result) noexcept {
    const auto n = static_cast<size_t>(last - first);
    const auto bytes = n * sizeof(iter_value_t<Iterator1>);
    _NEFORCE memory_move(_NEFORCE addressof(*result), _NEFORCE addressof(*first), bytes);
    return _NEFORCE next(result, n);
}
 
NEFORCE_END_INNER__

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 copy(Iterator1 first, Iterator1 last,
                         Iterator2 result) noexcept(noexcept(inner::__copy_aux(first, last, result))) {
    static_assert(is_ranges_input_iter_v<Iterator1>, "Iterator1 must be input_iterator");
    static_assert(is_iter_v<Iterator2>, "Iterator2 must be iterator");
    if (first == last) {
        return result;
    }
    return inner::__copy_aux(first, last, result);
}

NEFORCE_BEGIN_INNER__

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<is_ranges_rnd_iter_v<Iterator1>, Iterator2>
__copy_n_aux(Iterator1 first, iter_difference_t<Iterator1> count, Iterator2 result) {
    return _NEFORCE copy(first, _NEFORCE next(first, count), result);
}

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<!is_ranges_rnd_iter_v<Iterator1>, Iterator2>
__copy_n_aux(Iterator1 first, iter_difference_t<Iterator1> count, Iterator2 result) {
    for (; count > 0; --count, ++first, ++result) {
        *result = *first;
    }
    return result;
}
NEFORCE_END_INNER__

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 copy_n(Iterator1 first, iter_difference_t<Iterator1> count, Iterator2 result) {
    static_assert(is_ranges_input_iter_v<Iterator1>, "Iterator1 must be input_iterator");
    static_assert(is_iter_v<Iterator2>, "Iterator2 must be iterator");
    return inner::__copy_n_aux(first, count, result);
}

template <typename Iterator1, typename Iterator2, typename Pred>
constexpr Iterator2 copy_if(Iterator1 first, Iterator1 last, Iterator2 result, Pred pred) {
    static_assert(is_ranges_input_iter_v<Iterator1>, "Iterator1 must be input_iterator");
    static_assert(is_iter_v<Iterator2>, "Iterator2 must be iterator");
 
    for (; first != last; ++first) {
        if (pred(*first)) {
            *result++ = *first;
        }
    }
    return result;
}

NEFORCE_BEGIN_INNER__

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<!is_ranges_cot_iter_v<Iterator1>, Iterator2>
__copy_backward_aux(Iterator1 first, Iterator1 last,
                    Iterator2 result) noexcept(is_nothrow_copy_assignable_v<iter_value_t<Iterator1>>) {
    iter_difference_t<Iterator1> n = _NEFORCE distance(first, last);
    for (; n > 0; --n) {
        *--result = *--last;
    }
    return result;
}

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<is_ranges_cot_iter_v<Iterator1>, Iterator2> __copy_backward_aux(Iterator1 first, Iterator1 last,
                                                                                      Iterator2 result) noexcept {
    const auto n = static_cast<size_t>(last - first);
    auto dest = _NEFORCE prev(result, n);
    _NEFORCE memory_move(_NEFORCE addressof(*dest), _NEFORCE addressof(*first), n * sizeof(iter_value_t<Iterator1>));
    return dest;
}
 
NEFORCE_END_INNER__

template <typename Iterator1, typename Iterator2>
constexpr Iterator2
copy_backward(Iterator1 first, Iterator1 last,
              Iterator2 result) noexcept(noexcept(inner::__copy_backward_aux(first, last, result))) {
    static_assert(is_ranges_bid_iter_v<Iterator1> && is_ranges_bid_iter_v<Iterator2>,
                  "Iterators must be bidirectional_iterator");
 
    if (first == last) {
        return result;
    }
    return inner::__copy_backward_aux(first, last, result);
}

NEFORCE_BEGIN_INNER__

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<!(is_ranges_cot_iter_v<Iterator1> && is_trivially_copyable_v<iter_value_t<Iterator1>>), Iterator2>
__move_aux(Iterator1 first, Iterator1 last,
           Iterator2 result) noexcept(is_nothrow_move_assignable_v<iter_value_t<Iterator1>>) {
    iter_difference_t<Iterator1> n = _NEFORCE distance(first, last);
    for (; n > 0; --n, ++first, ++result) {
        *result = _NEFORCE move(*first);
    }
    return result;
}

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<is_ranges_cot_iter_v<Iterator1> && is_trivially_copyable_v<iter_value_t<Iterator1>>, Iterator2>
__move_aux(Iterator1 first, Iterator1 last, Iterator2 result) noexcept {
    const auto n = static_cast<size_t>(last - first);
    _NEFORCE memory_move(_NEFORCE addressof(*result), _NEFORCE addressof(*first), n * sizeof(iter_value_t<Iterator1>));
    return result + n;
}
 
NEFORCE_END_INNER__

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 move(Iterator1 first, Iterator1 last,
                         Iterator2 result) noexcept(noexcept(inner::__move_aux(first, last, result))) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterators must be input_iterator");
 
    if (first == last) {
        return result;
    }
    return inner::__move_aux(first, last, result);
}

NEFORCE_BEGIN_INNER__

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<!(is_ranges_cot_iter_v<Iterator1> && is_trivially_copyable_v<iter_value_t<Iterator1>>), Iterator2>
__move_backward_aux(Iterator1 first, Iterator1 last, Iterator2 result) {
    for (size_t n = _NEFORCE distance(first, last); n > 0; --n) {
        *--result = _NEFORCE move(*--last);
    }
    return result;
}

template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<is_ranges_cot_iter_v<Iterator1> && is_trivially_copyable_v<iter_value_t<Iterator1>>, Iterator2>
__move_backward_aux(Iterator1 first, Iterator1 last, Iterator2 result) noexcept {
    const auto n = static_cast<size_t>(last - first);
    auto dest = result - n;
    _NEFORCE memory_move(_NEFORCE addressof(*dest), _NEFORCE addressof(*first), n * sizeof(iter_value_t<Iterator1>));
    return dest;
}
NEFORCE_END_INNER__

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 move_backward(Iterator1 first, Iterator1 last, Iterator2 result) {
    static_assert(is_ranges_bid_iter_v<Iterator1> && is_ranges_bid_iter_v<Iterator2>,
                  "Iterators must be bidirectional_iterator");
    if (first == last) {
        return result;
    }
    return inner::__move_backward_aux(first, last, result);
}
 

template <typename Iterator, typename T>
constexpr void fill(Iterator first, Iterator last,
                    const T& value) noexcept(is_nothrow_assignable_v<iter_value_t<Iterator>, T>) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterators must be input_iterator");
    static_assert(is_assignable_v<decltype(*first), T>, "Iterators must be assignable from T");
 
    for (; first != last; ++first) {
        *first = value;
    }
}

template <typename Iterator, typename T>
constexpr Iterator fill_n(Iterator first, iter_difference_t<Iterator> n,
                          const T& value) noexcept(is_nothrow_assignable_v<iter_value_t<Iterator>, T>) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterators must be input_iterator");
    static_assert(is_assignable_v<decltype(*first), T>, "Iterators must be assignable from T");
 
    for (; n > 0; --n, ++first) {
        *first = value;
    }
    return first;
}
 

template <typename Iterator1, typename Iterator2>
constexpr void iter_swap(Iterator1 a, Iterator2 b) noexcept(noexcept(_NEFORCE swap(*a, *b))) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterators must be input_iterator");
    _NEFORCE swap(*a, *b);
}

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 swap_ranges(Iterator1 first1, Iterator1 last1, Iterator2 first2) {
    for (; first1 != last1; ++first1, ++first2) {
        _NEFORCE iter_swap(first1, first2);
    }
    return first2;
}
 

template <typename Iterator, typename Function>
constexpr Function for_each(Iterator first, Iterator last, Function f) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Function, decltype(*first)>, "Function must be invocable");
 
    for (; first != last; ++first) {
        f(*first);
    }
    return f;
}

template <typename Iterator, typename Function>
constexpr Iterator for_each_n(Iterator first, iter_difference_t<Iterator> n, Function f) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Function, decltype(*first)>, "Function must be invocable");
 
    for (iter_difference_t<Iterator> i = 0; i < n; ++i) {
        f(*first);
        ++first;
    }
    return first;
}
 

template <typename Iterator, typename Generator>
constexpr void generate(Iterator first, Iterator last, Generator gen) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Generator>, "Generator must be invocable");
    static_assert(is_assignable_v<decltype(*first), invoke_result_t<Generator>>,
                  "Generator must be assignable from invoke_result");
 
    for (; first != last; ++first) {
        *first = gen();
    }
}

template <typename Iterator, typename Generator>
constexpr Iterator generate_n(Iterator first, iter_difference_t<Iterator> n, Generator gen) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Generator>, "Generator must be invocable");
    static_assert(is_assignable_v<decltype(*first), invoke_result_t<Generator>>,
                  "Generator must be assignable from invoke_result");
 
    for (; n > 0; --n, ++first) {
        *first = gen();
    }
    return first;
}
 

template <typename Iterator1, typename Iterator2, typename T>
constexpr Iterator2 replace_copy(Iterator1 first, Iterator1 last, Iterator2 result, const T& old_value,
                                 const T& new_value) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterators must be forward_iterator");
    static_assert(is_assignable_v<decltype(*result), const T&>, "*result must be assignable from const T");
 
    for (; first != last; ++first, ++result) {
        *result = *first == old_value ? new_value : *first;
    }
    return result;
}

template <typename Iterator1, typename Iterator2, typename Predicate, typename T>
constexpr Iterator2 replace_copy_if(Iterator1 first, Iterator1 last, Iterator2 result, Predicate pred,
                                    const T& new_value) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterators must be forward_iterator");
    static_assert(is_invocable_v<Predicate, decltype(*first)>, "Predicate must be invocable");
    static_assert(is_assignable_v<decltype(*result), const T&>, "*result must be assignable from const T");
 
    for (; first != last; ++first, ++result) {
        *result = pred(*first) ? new_value : *first;
    }
    return result;
}

template <typename Iterator, typename T>
constexpr void replace(Iterator first, Iterator last, const T& old_value, const T& new_value) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterators must be forward_iterator");
    static_assert(is_assignable_v<decltype(*first), const T&>, "*result must be assignable from const T");
 
    for (; first != last; ++first) {
        if (*first == old_value) {
            *first = new_value;
        }
    }
}

template <typename Iterator, typename Predicate, typename T>
constexpr void replace_if(Iterator first, Iterator last, Predicate pred, const T& new_value) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterators must be forward_iterator");
    static_assert(is_invocable_v<Predicate, decltype(*first)>, "Predicate must be invocable");
    static_assert(is_assignable_v<decltype(*first), const T&>, "*result must be assignable from const T");
 
    for (; first != last; ++first) {
        if (pred(*first)) {
            *first = new_value;
        }
    }
}
 
#ifndef NEFORCE_STANDARD_17
NEFORCE_BEGIN_INNER__

template <typename Iterator>
enable_if_t<is_ranges_rnd_iter_v<Iterator>> __reverse_aux(Iterator first, Iterator last) {
    while (first < last) {
        --last;
        _NEFORCE iter_swap(first, last);
        ++first;
    }
    return;
}

template <typename Iterator>
enable_if_t<!is_ranges_rnd_iter_v<Iterator>> __reverse_aux(Iterator first, Iterator last) {
    while (true) {
        if (first == last || first == --last) {
            return;
        }
        --last;
        _NEFORCE iter_swap(first, last);
        ++first;
    }
    return;
}
 
NEFORCE_END_INNER__
#endif // NEFORCE_STANDARD_17

template <typename Iterator>
constexpr void reverse(Iterator first, Iterator last) {
    static_assert(is_ranges_bid_iter_v<Iterator>, "Iterators must be bidirectional_iterator");
 
#ifdef NEFORCE_STANDARD_17
    if constexpr (is_ranges_rnd_iter_v<Iterator>) {
        while (first < last) {
            --last;
            _NEFORCE iter_swap(first, last);
            ++first;
        }
    } else {
        while (first != last) {
            --last;
            if (first == last) {
                break;
            }
            _NEFORCE iter_swap(first, last);
            ++first;
        }
    }
#else
    inner::__reverse_aux(first, last);
#endif
}

NEFORCE_BEGIN_INNER__
 
template <typename Iterator>
constexpr enable_if_t<!is_ranges_bid_iter_v<Iterator>> __rotate_aux_dispatch(Iterator first, Iterator middle,
                                                                             Iterator last) {
    for (Iterator i = middle;;) {
        _NEFORCE iter_swap(first, i);
        ++first;
        ++i;
        if (first == middle) {
            if (i == last) {
                return;
            }
            middle = i;
        } else if (i == last) {
            i = middle;
        }
    }
}
 
template <typename Iterator>
constexpr enable_if_t<is_ranges_bid_iter_v<Iterator>> __rotate_aux_dispatch(Iterator first, Iterator middle,
                                                                            Iterator last) {
    _NEFORCE reverse(first, middle);
    _NEFORCE reverse(middle, last);
    _NEFORCE reverse(first, last);
}

template <typename Iterator>
constexpr enable_if_t<!is_ranges_rnd_iter_v<Iterator>> __rotate_aux(Iterator first, Iterator middle, Iterator last) {
    if (first == middle || middle == last) {
        return;
    }
    inner::__rotate_aux_dispatch(first, middle, last);
}

template <typename Iterator>
constexpr void __rotate_cycle_aux(Iterator first, Iterator last, Iterator initial, iter_difference_t<Iterator> shift) {
    iter_value_t<Iterator> value = *initial;
    Iterator ptr1 = initial;
    Iterator ptr2 = ptr1 + shift;
    while (ptr2 != initial) {
        *ptr1 = *ptr2;
        ptr1 = ptr2;
        if (last - ptr2 > shift) {
            ptr2 += shift;
        } else {
            ptr2 = first + (shift - (last - ptr2));
        }
    }
    *ptr1 = _NEFORCE move(value);
}

template <typename Iterator>
constexpr enable_if_t<is_ranges_rnd_iter_v<Iterator>> __rotate_aux(Iterator first, Iterator middle, Iterator last) {
    auto n = _NEFORCE gcd(last - first, middle - first);
    while (n--) {
        inner::__rotate_cycle_aux(first, last, first + n, middle - first);
    }
    return;
}
 
NEFORCE_END_INNER__

template <typename Iterator>
constexpr Iterator rotate(Iterator first, Iterator middle, Iterator last) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterators must be forward_iterator");
 
    if (first == middle) {
        return last;
    }
    if (middle == last) {
        return first;
    }
 
    auto dist = _NEFORCE distance(middle, last);
    inner::__rotate_aux(first, middle, last);
    return _NEFORCE next(first, dist);
}

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 rotate_copy(Iterator1 first, Iterator1 middle, Iterator1 last, Iterator2 result) {
    return _NEFORCE copy(first, middle, _NEFORCE copy(middle, last, result));
}
 

template <typename Iterator>
constexpr Iterator shift_left(Iterator first, Iterator last, iter_difference_t<Iterator> n) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterators must be forward_iterator");
 
    if (n <= 0) {
        return last;
    }
 
    auto dist = _NEFORCE distance(first, last);
    if (static_cast<decltype(dist)>(n) >= dist) {
        return first;
    }
 
    Iterator new_last = _NEFORCE next(first, dist - n);
    _NEFORCE move(_NEFORCE next(first, n), last, first);
    return new_last;
}
 

template <typename Iterator>
constexpr Iterator shift_right(Iterator first, Iterator last, iter_difference_t<Iterator> n) {
    static_assert(is_ranges_bid_iter_v<Iterator>, "Iterators must be bidirectional_iterator");
 
    if (n <= 0) {
        return first;
    }
 
    auto dist = _NEFORCE distance(first, last);
    if (static_cast<decltype(dist)>(n) >= dist) {
        return last;
    }
 
    Iterator new_first = _NEFORCE next(first, n);
    _NEFORCE move_backward(first, _NEFORCE next(first, dist - n), last);
    return new_first;
}
 

template <typename Iterator1, typename Iterator2, typename UnaryOperation>
constexpr Iterator2 transform(Iterator1 first, Iterator1 last, Iterator2 result,
                              UnaryOperation op) noexcept(noexcept(++first) && noexcept(++result) &&
                                                          noexcept(*result = op(*first))) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterators must be forward_iterator");
    static_assert(is_invocable_v<UnaryOperation, decltype(*first)>, "UnaryOperation must be invocable");
    static_assert(is_assignable_v<decltype(*result), invoke_result_t<UnaryOperation, decltype(*first)>>,
                  "*result must be assignable");
 
    for (; first != last; ++first, ++result) {
        *result = op(*first);
    }
    return result;
}

template <typename Iterator1, typename Iterator2, typename Iterator3, typename BinaryOperation>
constexpr Iterator3 transform(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator3 result,
                              BinaryOperation binary_op) noexcept(noexcept(++first1) && noexcept(first2) &&
                                                                  noexcept(++result) &&
                                                                  noexcept(*result = binary_op(*first1, *first2))) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2> && is_ranges_fwd_iter_v<Iterator3>,
                  "Iterators must be forward_iterator");
    static_assert(is_invocable_v<BinaryOperation, decltype(*first1), decltype(*first2)>,
                  "UnaryOperation must be invocable");
    static_assert(
            is_assignable_v<decltype(*result), invoke_result_t<BinaryOperation, decltype(*first1), decltype(*first2)>>,
            "*result must be assignable");
 
    for (; first1 != last1; ++first1, ++first2, ++result) {
        *result = binary_op(*first1, *first2);
    }
    return result;
}
 

template <typename Iterator1, typename Iterator2, typename BinaryPredicate>
constexpr Iterator2 unique_copy(Iterator1 first, Iterator1 last, Iterator2 result, BinaryPredicate binary_pred) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterators must be forward_iterator");
    static_assert(is_invocable_v<BinaryPredicate, decltype(*result), decltype(*first)>,
                  "BinaryPredicate must be invocable");
 
    if (first == last) {
        return result;
    }
 
    *result = *first;
 
    while (++first != last) {
        if (!binary_pred(*result, *first)) {
            *++result = *first;
        }
    }
    return ++result;
}

template <typename Iterator1, typename Iterator2>
constexpr Iterator2 unique_copy(Iterator1 first, Iterator1 last, Iterator2 result) {
    return _NEFORCE unique_copy(first, last, result, _NEFORCE equal_to<iter_value_t<Iterator1>>());
}

template <typename Iterator, typename BinaryPredicate>
constexpr Iterator unique(Iterator first, Iterator last, BinaryPredicate binary_pred) {
    first = _NEFORCE adjacent_find(first, last, binary_pred);
    if (first == last) {
        return last;
    }
 
    Iterator result = first;
    while (++first != last) {
        if (!binary_pred(*result, *first)) {
            *++result = _NEFORCE move(*first);
        }
    }
    return ++result;
}

template <typename Iterator>
constexpr Iterator unique(Iterator first, Iterator last) {
    return _NEFORCE unique(first, last, _NEFORCE equal_to<iter_value_t<Iterator>>{});
}
 // ShiftAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_SHIFT_HPP__