partition.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_PARTITION_HPP__
#define NEFORCE_CORE_ALGORITHM_PARTITION_HPP__

 
#include "NeForce/core/algorithm/shift.hpp"
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator, typename Predicate>
constexpr Iterator partition(Iterator first, Iterator last, Predicate pred) {
    static_assert(is_ranges_bid_iter_v<Iterator>, "Iterator must be bidirectional_iterator");
    static_assert(is_invocable_v<Predicate, decltype(*first)>, "Predicate must be invocable");
 
    while (true) {
        while (true) {
            if (first == last) {
                return first;
            }
 
            if (pred(*first)) {
                ++first;
            } else {
                break;
            }
        }
        --last;
        while (true) {
            if (first == last) {
                return first;
            }
 
            if (!pred(*last)) {
                --last;
            } else {
                break;
            }
        }
        _NEFORCE iter_swap(first, last);
        ++first;
    }
}

NEFORCE_BEGIN_INNER__
 
template <typename Iterator, typename Compare>
constexpr Iterator median_iter(Iterator a, Iterator b, Iterator c, Compare comp) {
    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;
        }
    }
}
 
NEFORCE_END_INNER__

template <typename Iterator, typename Compare>
constexpr Iterator lomuto_partition(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    if (last - first < 2) {
        return first;
    }
 
    Iterator mid = first + (last - first) / 2;
    Iterator piv_iter = inner::median_iter(first, mid, last - 1, comp);
    _NEFORCE iter_swap(first, piv_iter);
    auto pivot = *first;
 
    Iterator i = first + 1;
    Iterator j = first;
 
    while (i != last) {
        if (comp(*i, pivot)) {
            ++j;
            if (i != j) {
                _NEFORCE iter_swap(i, j);
            }
        }
        ++i;
    }
    _NEFORCE iter_swap(first, j);
    return j;
}

template <typename Iterator>
constexpr Iterator lomuto_partition(Iterator first, Iterator last) {
    return _NEFORCE lomuto_partition(first, last, less<>{});
}
 // PartitionAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_PARTITION_HPP__