search.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_SEARCH_HPP__
#define NEFORCE_CORE_ALGORITHM_SEARCH_HPP__

 
#include "NeForce/core/functional/functor.hpp"
#include "NeForce/core/iterator/reverse_iterator.hpp"
NEFORCE_BEGIN_NAMESPACE__



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

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

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

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

template <typename Iterator, typename T>
constexpr bool binary_search(Iterator first, Iterator last, const T& value) {
    Iterator i = _NEFORCE lower_bound(first, last, value);
    return i != last && !(value < *i);
}

template <typename Iterator, typename T, typename Compare>
constexpr bool binary_search(Iterator first, Iterator last, const T& value, Compare comp) {
    Iterator i = _NEFORCE lower_bound(first, last, value, comp);
    return i != last && !comp(value, *i);
}

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

template <typename Iterator1, typename Iterator2>
constexpr bool includes(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    return _NEFORCE includes(first1, last1, first2, last2, _NEFORCE less<iter_value_t<Iterator1>>());
}
 // BoundAlgorithms


template <typename Iterator, typename Predicate>
constexpr bool all_of(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    for (; first != last; ++first) {
        if (!pred(*first)) {
            return false;
        }
    }
    return true;
}

template <typename Iterator, typename Predicate>
constexpr bool any_of(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    for (; first != last; ++first) {
        if (pred(*first)) {
            return true;
        }
    }
    return false;
}

template <typename Iterator, typename Predicate>
constexpr bool none_of(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    for (; first != last; ++first) {
        if (pred(*first)) {
            return false;
        }
    }
    return true;
}
 // QuantifierAlgorithms


template <typename Iterator, typename BinaryPredicate>
constexpr Iterator adjacent_find(Iterator first, Iterator last, BinaryPredicate binary_pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    if (first == last) {
        return last;
    }
    Iterator next = first;
    while (++next != last) {
        if (binary_pred(*first, *next)) {
            return first;
        }
        first = next;
    }
    return last;
}

template <typename Iterator>
constexpr Iterator adjacent_find(Iterator first, Iterator last) {
    return _NEFORCE adjacent_find(first, last, _NEFORCE equal_to<iter_value_t<Iterator>>());
}
 // AdjacentAlgorithms


template <typename Iterator, typename T, typename BinaryPredicate,
          enable_if_t<is_ranges_input_iter_v<Iterator>, int> = 0>
constexpr iter_difference_t<Iterator> count_if(Iterator first, Iterator last, const T& value, BinaryPredicate pred) {
    iter_difference_t<Iterator> n = 0;
    for (; first != last; ++first) {
        if (pred(*first, value)) {
            ++n;
        }
    }
    return n;
}

template <typename Iterator, typename Predicate>
constexpr iter_difference_t<Iterator> count_if(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    iter_difference_t<Iterator> n = 0;
    for (; first != last; ++first) {
        if (pred(*first)) {
            ++n;
        }
    }
    return n;
}

template <typename Iterator, typename T>
constexpr iter_difference_t<Iterator> count(Iterator first, Iterator last, const T& value) {
    return _NEFORCE count_if(first, last, value, _NEFORCE equal_to<iter_value_t<Iterator>>());
}
 // CountingAlgorithms


template <typename Iterator, typename T>
NEFORCE_NODISCARD constexpr Iterator find(Iterator first, Iterator last, const T& value) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    while (first != last && *first != value) {
        ++first;
    }
    return first;
}

template <typename Iterator, typename Predicate>
constexpr Iterator find_if(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    while (first != last && !pred(*first)) {
        ++first;
    }
    return first;
}

template <typename Iterator, typename Predicate, enable_if_t<is_ranges_input_iter_v<Iterator>, int> = 0>
constexpr Iterator find_if_not(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
 
    while (first != last && pred(*first)) {
        ++first;
    }
    return first;
}
 // FindingAlgorithms


template <typename Iterator1, typename Iterator2, typename BinaryPredicate>
constexpr Iterator1 search(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2,
                           BinaryPredicate binary_pred) {
 
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterator must be forward_iterator");
 
    auto d1 = _NEFORCE distance(first1, last1);
    const auto d2 = _NEFORCE distance(first2, last2);
    if (d1 < d2) {
        return last1;
    }
 
    Iterator1 current1 = first1;
    Iterator2 current2 = first2;
 
    while (current2 != last2) {
        if (binary_pred(*current1, *current2)) {
            ++current1;
            ++current2;
        } else {
            if (d1 == d2) {
                return last1;
            }
 
            current1 = ++first1;
            current2 = first2;
            --d1;
        }
    }
    return first1;
}

template <typename Iterator1, typename Iterator2>
constexpr Iterator1 search(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    return _NEFORCE search(first1, last1, first2, last2, _NEFORCE equal_to<iter_value_t<Iterator1>>());
}

template <typename Iterator, typename T>
constexpr Iterator search_n(Iterator first, Iterator last, const size_t count, const T& value) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterator must be forward_iterator");
 
    if (count == 0) {
        return first;
    }
 
    first = _NEFORCE find(first, last, value);
    while (first != last) {
        size_t n = count - 1;
        Iterator i = first;
        ++i;
        while (i != last && n != 0 && *i == value) {
            ++i;
            --n;
        }
        if (n == 0) {
            return first;
        }
 
        first = _NEFORCE find(i, last, value);
    }
    return last;
}

template <typename Iterator, typename T, typename BinaryPredicate>
constexpr Iterator search_n(Iterator first, Iterator last, const size_t count, const T& value,
                            BinaryPredicate binary_pred) {
    static_assert(is_ranges_fwd_iter_v<Iterator>, "Iterator must be forward_iterator");
 
    if (count == 0) {
        return first;
    }
 
    while (first != last) {
        if (binary_pred(*first, value)) {
            break;
        }
        ++first;
    }
 
    while (first != last) {
        size_t n = count - 1;
        Iterator i = first;
        ++i;
 
        while (i != last && n != 0 && binary_pred(*i, value)) {
            ++i;
            --n;
        }
        if (n == 0) {
            return first;
        }
 
        while (i != last) {
            if (binary_pred(*i, value)) {
                break;
            }
            ++i;
        }
        first = i;
    }
    return last;
}
 
#ifndef NEFORCE_STANDARD_17
NEFORCE_BEGIN_INNER__
 
template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<is_ranges_bid_iter_v<Iterator1> && is_ranges_bid_iter_v<Iterator2>, Iterator1>
__find_end_aux(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    using reviter1 = _NEFORCE reverse_iterator<Iterator1>;
    using reviter2 = _NEFORCE reverse_iterator<Iterator2>;
    reviter1 rlast1(first1);
    reviter2 rlast2(first2);
    reviter1 rresult = _NEFORCE search(reviter1(last1), rlast1, reviter2(last2), rlast2);
    if (rresult == rlast1) {
        return last1;
    }
    Iterator1 result = rresult.base();
    _NEFORCE advance(result, -distance(first2, last2));
    return result;
}
 
template <typename Iterator1, typename Iterator2>
constexpr enable_if_t<!(is_ranges_bid_iter_v<Iterator1> && is_ranges_bid_iter_v<Iterator2>), Iterator1>
__find_end_aux(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    Iterator1 result = last1;
    while (true) {
        Iterator1 new_result = _NEFORCE search(first1, last1, first2, last2);
        if (new_result == last1) {
            return result;
        }
        result = new_result;
        first1 = new_result;
        ++first1;
    }
}
 
NEFORCE_END_INNER__
#endif // NEFORCE_STANDARD_17

template <typename Iterator1, typename Iterator2>
constexpr Iterator1 find_end(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    static_assert(is_ranges_fwd_iter_v<Iterator1> && is_ranges_fwd_iter_v<Iterator2>,
                  "Iterator must be forward_iterator");
 
    if (first2 == last2) {
        return last1;
    }
#ifdef NEFORCE_STANDARD_17
    if constexpr (is_ranges_bid_iter_v<Iterator1> && is_ranges_bid_iter_v<Iterator2>) {
        using reviter1 = _NEFORCE reverse_iterator<Iterator1>;
        using reviter2 = _NEFORCE reverse_iterator<Iterator2>;
 
        reviter1 rlast1(first1);
        reviter2 rlast2(first2);
        reviter1 rresult = _NEFORCE search(reviter1(last1), rlast1, reviter2(last2), rlast2);
        if (rresult == rlast1) {
            return last1;
        }
 
        Iterator1 result = rresult.base();
        _NEFORCE advance(result, -distance(first2, last2));
        return result;
    } else {
        Iterator1 result = last1;
        while (true) {
            Iterator1 new_result = _NEFORCE search(first1, last1, first2, last2);
            if (new_result == last1) {
                return result;
            }
            result = new_result;
            first1 = new_result;
            ++first1;
        }
    }
#else
    return inner::__find_end_aux(first1, last1, first2, last2);
#endif
}

template <typename Iterator1, typename Iterator2, typename BinaryPredicate>
constexpr Iterator1 find_first_of(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2,
                                  BinaryPredicate comp) {
    static_assert(is_ranges_input_iter_v<Iterator1> && is_ranges_input_iter_v<Iterator2>,
                  "Iterator must be input_iterator");
 
    for (; first1 != last1; ++first1) {
        for (Iterator2 iter = first2; iter != last2; ++iter) {
            if (comp(*first1, *iter)) {
                return first1;
            }
        }
    }
    return last1;
}

template <typename Iterator1, typename Iterator2>
constexpr Iterator1 find_first_of(Iterator1 first1, Iterator1 last1, Iterator2 first2, Iterator2 last2) {
    return _NEFORCE find_first_of(first1, last1, first2, last2, _NEFORCE equal_to<iter_value_t<Iterator1>>());
}
 // PatternMatchingAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_SEARCH_HPP__