sort.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_SORT_HPP__
#define NEFORCE_CORE_ALGORITHM_SORT_HPP__

 
#include "NeForce/core/algorithm/compare.hpp"
#include "NeForce/core/algorithm/heap.hpp"
#include "NeForce/core/algorithm/merge.hpp"
#include "NeForce/core/algorithm/partition.hpp"
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator, typename Compare>
bool is_sorted(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return true;
    }
    Iterator next = _NEFORCE next(first);
    for (; next != last; ++first, ++next) {
        if (comp(*next, *first)) {
            return false;
        }
    }
    return true;
}

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

template <typename Iterator, typename Compare>
Iterator is_sorted_until(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator>, "Iterator must be input_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return last;
    }
    Iterator next = _NEFORCE next(first);
    for (; next != last; ++first, ++next) {
        if (comp(*next, *first)) {
            return next;
        }
    }
    return last;
}

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

template <typename Iterator, typename Compare>
void merge_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    const auto n = _NEFORCE distance(first, last);
    if (n < 2) {
        return;
    }
    Iterator mid = first + n / 2;
    _NEFORCE merge_sort(first, mid);
    _NEFORCE merge_sort(mid, last);
    _NEFORCE inplace_merge(first, mid, last, comp);
}

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

template <typename Iterator, typename Compare>
void partial_sort(Iterator first, Iterator middle, Iterator last, Compare comp) {
    if (first == middle) {
        return;
    }
    _NEFORCE make_heap(first, middle, comp);
    for (Iterator i = middle; i < last; ++i) {
        if (comp(*i, *first)) {
            inner::pop_heap_aux(first, middle, i, *i, comp);
        }
    }
    _NEFORCE sort_heap(first, middle, comp);
}

template <typename Iterator>
void partial_sort(Iterator first, Iterator middle, Iterator last) {
    return _NEFORCE partial_sort(first, middle, last, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator1, typename Iterator2, typename Compare>
Iterator2 partial_sort_copy(Iterator1 first, Iterator1 last, Iterator2 result_first, Iterator2 result_last,
                            Compare comp) {
    static_assert(is_ranges_input_iter_v<Iterator1>, "Iterator must be input_iterator");
 
    if (result_first == result_last) {
        return result_last;
    }
    Iterator2 result_real_last = result_first;
    while (first != last && result_real_last != result_last) {
        *result_real_last = *first;
        ++result_real_last;
        ++first;
    }
    _NEFORCE make_heap(result_first, result_real_last, comp);
    while (first != last) {
        if (comp(*first, *result_first)) {
            _NEFORCE adjust_heap(result_first, 0, result_real_last - result_first, *first, comp);
        }
        ++first;
    }
    _NEFORCE sort_heap(result_first, result_real_last, comp);
    return result_real_last;
}

template <typename Iterator1, typename Iterator2>
Iterator2 partial_sort_copy(Iterator1 first, Iterator1 last, Iterator2 result_first, Iterator2 result_last) {
    return _NEFORCE partial_sort_copy(first, result_first, result_last, _NEFORCE less<iter_value_t<Iterator1>>());
}

NEFORCE_BEGIN_INNER__

template <typename Iterator, typename T, typename Compare>
void __insertion_sort_aux(Iterator last, T value, Compare comp) {
    Iterator next = last;
    --next;
    while (comp(value, *next)) {
        *last = *next;
        last = next;
        --next;
    }
    *last = value;
}
 
NEFORCE_END_INNER__

template <typename Iterator, typename Compare>
void insertion_sort(Iterator first, Iterator last, Compare comp) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    if (first == last) {
        return;
    }
    for (Iterator i = first + 1; i != last; ++i) {
        iter_value_t<Iterator> value = *i;
        if (comp(value, *first)) {
            _NEFORCE copy_backward(first, i, i + 1);
            *first = value;
        } else {
            inner::__insertion_sort_aux(i, value, comp);
        }
    }
}

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

template <typename Iterator, typename Compare>
void introspective_sort(Iterator first, Iterator last, int depth_limit, Compare comp) {
    static_assert(is_invocable_v<Compare, decltype(*first), decltype(*first)>, "Compare must be invocable");
 
    while (first < last) {
        if (depth_limit == 0) {
            _NEFORCE partial_sort(first, last, last, comp);
            return;
        }
        --depth_limit;
        Iterator cut = _NEFORCE lomuto_partition(
                first, last, _NEFORCE median(*first, *(first + (last - first) / 2), *(last - 1), comp), comp);
        _NEFORCE introspective_sort(cut, last, depth_limit, comp);
        last = cut;
    }
}

template <typename Iterator>
void introspective_sort(Iterator first, Iterator last, int depth_limit) {
    return _NEFORCE introspective_sort(first, last, depth_limit, _NEFORCE less<iter_value_t<Iterator>>());
}

template <typename Iterator, typename Compare>
void quick_sort(Iterator first, Iterator last, Compare comp) {
    if (first < last) {
        Iterator pov = last - 1;
        Iterator cut = _NEFORCE lomuto_partition(first, last, *pov, comp);
        _NEFORCE iter_swap(cut, pov);
        _NEFORCE quick_sort(first, cut, comp);
        _NEFORCE quick_sort(cut + 1, last, comp);
    }
}

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

NEFORCE_BEGIN_INNER__

template <typename Iterator, typename Compare>
void __intro_sort_dispatch(Iterator first, Iterator last, int depth_limit, Compare comp) {
    while (last - first > MEMORY_ALIGN_THRESHHOLD) {
        if (depth_limit == 0) {
            _NEFORCE partial_sort(first, last, last, comp);
            return;
        }
        --depth_limit;
        Iterator cut = _NEFORCE lomuto_partition(
                first, last, _NEFORCE median(*first, *(first + (last - first) / 2), *(last - 1), comp), comp);
        inner::__intro_sort_dispatch(cut, last, depth_limit, comp);
        last = cut;
    }
}

NEFORCE_CONST_FUNCTION constexpr int __log2_int(int x) noexcept {
    int k = 0;
    for (; x > 1; x >>= 1) {
        ++k;
    }
    return k;
}
 
NEFORCE_END_INNER__

template <typename Iterator, typename Compare>
void sort(Iterator first, Iterator last, Compare comp) {
    if (first == last) {
        return;
    }
 
    inner::__intro_sort_dispatch(first, last, inner::__log2_int(last - first) * 2, comp);
    constexpr size_t threshhold = MEMORY_ALIGN_THRESHHOLD;
 
    if (last - first > threshhold) {
        _NEFORCE insertion_sort(first, first + threshhold, comp);
        for (Iterator i = first + threshhold; i != last; ++i) {
            inner::__insertion_sort_aux(i, *i, comp);
        }
    } else {
        _NEFORCE insertion_sort(first, last, comp);
    }
}

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

template <typename Iterator, typename Compare>
void nth_element(Iterator first, Iterator nth, Iterator last, Compare comp) {
    while (last - first > 3) {
        Iterator cut = _NEFORCE lomuto_partition(
                first, last, _NEFORCE median(*first, *(first + (last - first) / 2), *(last - 1), comp), comp);
        if (cut <= nth) {
            first = cut;
        } else {
            last = cut;
        }
    }
    _NEFORCE insertion_sort(first, last, comp);
}

template <typename Iterator>
void nth_element(Iterator first, Iterator nth, Iterator last) {
    return _NEFORCE nth_element(first, nth, last, _NEFORCE less<iter_value_t<Iterator>>());
}
 // SortAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_SORT_HPP__