compare.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_COMPARE_HPP__
#define NEFORCE_CORE_ALGORITHM_COMPARE_HPP__

 
#include <initializer_list>
#include "NeForce/core/algorithm/search.hpp"
#include "NeForce/core/memory/memory.hpp"
#include "NeForce/core/utility/pair.hpp"
#ifdef NEFORCE_PLATFORM_WINDOWS
#    ifdef max
#        undef max
#    endif
#    ifdef min
#        undef min
#    endif
#endif
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator1, typename Iterator2, typename BinaryPredicate>
NEFORCE_NODISCARD constexpr bool equal(Iterator1 first1, Iterator1 last1, Iterator2 first2,
                                       BinaryPredicate binary_pred) noexcept(noexcept(++first1) && noexcept(++first2) &&
                                                                             noexcept(binary_pred(*first1, *first2))) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterator must be input_iterator");
    for (; first1 != last1; ++first1, ++first2) {
        if (!binary_pred(*first1, *first2)) {
            return false;
        }
    }
    return true;
}

template <typename Iterator1, typename Iterator2>
NEFORCE_NODISCARD constexpr bool equal(Iterator1 first1, Iterator1 last1, Iterator2 first2) noexcept(
        noexcept(_NEFORCE equal(first1, last1, first2, _NEFORCE equal_to<iter_value_t<Iterator1>>()))) {
    return _NEFORCE equal(first1, last1, first2, _NEFORCE equal_to<iter_value_t<Iterator1>>());
}

template <typename Iterator, typename T, typename Compare>
constexpr pair<Iterator, Iterator> equal_range(Iterator first, Iterator last, const T& value, Compare comp) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterator must be forward_iterator");
 
    auto len = _NEFORCE distance(first, last);
    auto half = len;
    Iterator middle, left, right;
 
    while (len > 0) {
        half = len >> 1;
        middle = first;
        _NEFORCE advance(middle, half);
 
        if (comp(*middle, value)) {
            first = middle;
            ++first;
            len = len - half - 1;
        } else if (comp(value, *middle)) {
            len = half;
        } else {
            left = _NEFORCE lower_bound(first, middle, value, comp);
            _NEFORCE advance(first, len);
            right = _NEFORCE upper_bound(++middle, first, value, comp);
            return pair<Iterator, Iterator>(left, right);
        }
    }
    return pair<Iterator, Iterator>(first, first);
}

template <typename Iterator, typename T>
constexpr pair<Iterator, Iterator> equal_range(Iterator first, Iterator last, const T& value) {
    return _NEFORCE equal_range(first, last, value, _NEFORCE less<iter_value_t<Iterator>>());
}
 

template <typename T, typename Compare>
constexpr const T& max(const T& a, const T& b, Compare comp) noexcept(noexcept(comp(a, b))) {
    return comp(a, b) ? b : a;
}

template <typename T>
constexpr const T& max(const T& a, const T& b) noexcept(noexcept(a < b)) {
    return a < b ? b : a;
}

template <typename T, typename Compare>
constexpr const T& min(const T& a, const T& b, Compare comp) noexcept(noexcept(comp(b, a))) {
    return comp(b, a) ? b : a;
}

template <typename T>
constexpr const T& min(const T& a, const T& b) noexcept(noexcept(b < a)) {
    return b < a ? b : a;
}

template <typename T, typename Compare>
constexpr const T& median(const T& a, const T& b, const T& c, Compare comp) noexcept(noexcept(comp(a, b))) {
    if (comp(a, b)) {
        if (comp(b, c)) {
            return b;
        } else if (comp(a, c)) {
            return c;
        } else {
            return a;
        }
    } else if (comp(a, c)) {
        return a;
    } else if (comp(b, c)) {
        return c;
    } else {
        return b;
    }
}

template <typename T>
constexpr const T& median(const T& a, const T& b,
                          const T& c) noexcept(noexcept(_NEFORCE median(a, b, c, _NEFORCE less<T>()))) {
    return _NEFORCE median(a, b, c, _NEFORCE less<T>());
}
 

template <typename Iterator, typename Compare>
pair<iter_value_t<Iterator>, iter_value_t<Iterator>> constexpr minmax(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    using T = iter_value_t<Iterator>;
    if (first == last) {
        return _NEFORCE make_pair(T(), T());
    }
    T min_val = *first;
    T max_val = *first;
 
    ++first;
    for (; first != last; ++first) {
        if (comp(*first, min_val)) {
            min_val = *first;
        } else if (!comp(*first, max_val)) {
            max_val = *first;
        }
    }
    return _NEFORCE make_pair(min_val, max_val);
}

template <typename Iterator>
constexpr pair<iter_value_t<Iterator>, iter_value_t<Iterator>> minmax(Iterator first, Iterator last) {
    return _NEFORCE minmax(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}
 

template <typename Iterator, typename Compare>
constexpr Iterator max_element(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    if (first == last) {
        return first;
    }
    Iterator result = first;
    while (++first != last) {
        if (comp(*result, *first)) {
            result = first;
        }
    }
    return result;
}

template <typename Iterator>
constexpr Iterator max_element(Iterator first, Iterator last) {
    return _NEFORCE max_element(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename T>
constexpr const T& max(std::initializer_list<T> list) {
    auto iter = _NEFORCE max_element(list.begin(), list.end());
    return *iter;
}

template <typename Iterator, typename Compare>
constexpr Iterator min_element(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    if (first == last) {
        return first;
    }
    Iterator result = first;
    while (++first != last) {
        if (comp(*first, *result)) {
            result = first;
        }
    }
    return result;
}

template <typename Iterator>
constexpr Iterator min_element(Iterator first, Iterator last) {
    return _NEFORCE min_element(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename T>
constexpr const T& min(std::initializer_list<T> list) {
    return *_NEFORCE min_element(list.begin(), list.end());
}

template <typename Iterator, typename Compare>
constexpr pair<Iterator, Iterator> minmax_element(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    Iterator min = _NEFORCE min_element(first, last, comp);
    Iterator max = _NEFORCE max_element(first, last, comp);
    return _NEFORCE make_pair(min, max);
}

template <typename Iterator>
constexpr pair<Iterator, Iterator> minmax_element(Iterator first, Iterator last) {
    return _NEFORCE minmax_element(first, last, _NEFORCE less<iter_value_t<Iterator>>());
}
 

template <typename T, typename Compare>
constexpr const T& clamp(const T& value, const T& lower, const T& upper,
                         Compare comp) noexcept(noexcept(comp(value, lower))) {
    if (comp(value, lower)) {
        return lower;
    } else if (comp(upper, value)) {
        return upper;
    }
    return value;
}

template <typename T>
constexpr const T& clamp(const T& value, const T& lower,
                         const T& upper) noexcept(noexcept(_NEFORCE clamp(value, lower, upper, _NEFORCE less<T>()))) {
    return _NEFORCE clamp(value, lower, upper, _NEFORCE less<T>());
}
 

template <typename Iterator1, typename Iterator2, typename Compare>
NEFORCE_NODISCARD constexpr bool
lexicographical_compare(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2,
                        Compare comp) noexcept(noexcept(++first1) && noexcept(++first2) &&
                                               noexcept(comp(*first1, *first2)) &&
                                               noexcept(first1 == last1 && first2 != last2)) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterator must be input_iterator");
    for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
        if (comp(*first1, *first2)) {
            return true;
        }
        if (comp(*first2, *first1)) {
            return false;
        }
    }
    return first1 == last1 && first2 != last2;
}

NEFORCE_BEGIN_INNER__

template <typename Iterator1, typename Iterator2>
NEFORCE_NODISCARD constexpr enable_if_t<is_ranges_cot_iter_v<Iterator1> && is_ranges_cot_iter_v<Iterator2>, bool>
__lexicographical_compare_aux(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) noexcept {
    const auto len1 = static_cast<size_t>(last1 - first1);
    const auto len2 = static_cast<size_t>(last2 - first2);
    const size_t clp = _NEFORCE min(len1, len2);
 
    const int result = _NEFORCE memory_compare(_NEFORCE addressof(*first1), _NEFORCE addressof(*first2),
                                               clp * sizeof(iter_value_t<Iterator1>));
    return result != 0 ? result < 0 : len1 < len2;
}

template <typename Iterator1, typename Iterator2>
NEFORCE_NODISCARD constexpr enable_if_t<!(is_ranges_cot_iter_v<Iterator1> && is_ranges_cot_iter_v<Iterator2>), bool>
__lexicographical_compare_aux(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) noexcept(noexcept(
        _NEFORCE lexicographical_compare(first1, last1, first2, last2, _NEFORCE less<iter_value_t<Iterator1>>()))) {
    return _NEFORCE lexicographical_compare(first1, last1, first2, last2, _NEFORCE less<iter_value_t<Iterator1>>());
}
 
NEFORCE_END_INNER__

template <typename Iterator1, typename Iterator2>
NEFORCE_NODISCARD constexpr bool lexicographical_compare(
        Iterator1 first1, Iterator1 last1, Iterator2 first2,
        Iterator2 last2) noexcept(noexcept(inner::__lexicographical_compare_aux(first1, last1, first2, last2))) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterator must be input_iterator");
    return inner::__lexicographical_compare_aux(first1, last1, first2, last2);
}
 

template <typename Iterator1, typename Iterator2, typename Compare>
pair<Iterator1, Iterator2> constexpr mismatch(Iterator1 first1, Iterator1 last1, Iterator2 first2, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterator must be input_iterator");
    while (first1 != last1 && comp(*first1, *first2)) {
        ++first1;
        ++first2;
    }
    return _NEFORCE make_pair<Iterator1, Iterator2>(first1, first2);
}

template <typename Iterator1, typename Iterator2>
constexpr pair<Iterator1, Iterator2> mismatch(Iterator1 first1, Iterator1 last1, Iterator2 first2) {
    return _NEFORCE mismatch(first1, last1, first2, _NEFORCE equal_to<iter_value_t<Iterator1>>());
}
 // CompareAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_COMPARE_HPP__