heap.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_HEAP_HPP__
#define NEFORCE_CORE_ALGORITHM_HEAP_HPP__

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



template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 Iterator is_heap_until(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");
 
    auto n = last - first;
    for (iter_difference_t<Iterator> child = 1; child < n; ++child) {
        auto parent = (child - 1) / 2;
        if (comp(*(first + parent), *(first + child))) {
            return first + child;
        }
    }
    return last;
}

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

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 bool is_heap(Iterator first, Iterator last, Compare comp) {
    return _NEFORCE is_heap_until(first, last, comp) == last;
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 bool is_heap(Iterator first, Iterator last) {
    return _NEFORCE is_heap_until(first, last) == last;
}
 

NEFORCE_BEGIN_INNER__

template <typename Iterator, typename T, typename Compare>
NEFORCE_CONSTEXPR20 void push_heap_aux(Iterator first, iter_difference_t<Iterator> hole_index,
                                       iter_difference_t<Iterator> top_index, T value, 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");
 
    auto parent = (hole_index - 1) / 2;
    while (hole_index > top_index && comp(*(first + parent), value)) {
        *(first + hole_index) = *(first + parent);
        hole_index = parent;
        parent = (hole_index - 1) / 2;
    }
    *(first + hole_index) = value;
}

template <typename Iterator, typename T>
NEFORCE_CONSTEXPR20 void push_heap_aux(Iterator first, iter_difference_t<Iterator> hole_index,
                                       iter_difference_t<Iterator> top_index, T value) {
    inner::push_heap_aux(first, hole_index, top_index, value, less<iter_value_t<Iterator>>());
}
 
NEFORCE_END_INNER__
 

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void push_heap(Iterator first, Iterator last, Compare comp) {
    if (last - first < 2) {
        return;
    }
    inner::push_heap_aux(first, last - first - 1, 0, *(last - 1), comp);
}

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

template <typename Iterator, typename T, typename Compare>
NEFORCE_CONSTEXPR20 void adjust_heap(Iterator first, iter_difference_t<Iterator> hole_index,
                                     iter_difference_t<Iterator> len, T value, Compare comp) {
    auto top_index = hole_index;
    auto child = 2 * hole_index + 1;
    while (child < len) {
        if (child + 1 < len && comp(*(first + child), *(first + child + 1))) {
            ++child;
        }
        if (!comp(value, *(first + child))) {
            break;
        }
        *(first + hole_index) = *(first + child);
        hole_index = child;
        child = 2 * hole_index + 1;
    }
    inner::push_heap_aux(first, hole_index, top_index, value, comp);
}

template <typename Iterator, typename T>
NEFORCE_CONSTEXPR20 void adjust_heap(Iterator first, iter_difference_t<Iterator> hole_index,
                                     iter_difference_t<Iterator> len, T value) {
    _NEFORCE adjust_heap(first, hole_index, len, value, less<iter_value_t<Iterator>>());
}
 

NEFORCE_BEGIN_INNER__

template <typename Iterator, typename T, typename Compare>
NEFORCE_CONSTEXPR20 void pop_heap_aux(Iterator first, Iterator last, Iterator result, T value, Compare comp) {
    *result = *first;
    _NEFORCE adjust_heap(first, 0, last - first, value, comp);
}

template <typename Iterator, typename T>
NEFORCE_CONSTEXPR20 void pop_heap_aux(Iterator first, Iterator last, Iterator result, T value) {
    inner::pop_heap_aux(first, last, result, value, less<iter_value_t<Iterator>>());
}
 
NEFORCE_END_INNER__
 

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void pop_heap(Iterator first, Iterator last, Compare comp) {
    if (last - first < 2) {
        return;
    }
    --last;
    inner::pop_heap_aux(first, last, last, *last, comp);
}

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

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void sort_heap(Iterator first, Iterator last, Compare comp) {
    while (last - first > 1) {
        _NEFORCE pop_heap(first, last--, comp);
    }
}

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

template <typename Iterator, typename Compare>
NEFORCE_CONSTEXPR20 void make_heap(Iterator first, Iterator last, Compare comp) {
    if (last - first < 2) {
        return;
    }
    const auto len = last - first;
    if (len < 2) {
        return;
    }
 
    auto parent = (len - 2) / 2;
    while (true) {
        _NEFORCE adjust_heap(first, parent, len, *(first + parent), comp);
        if (parent == 0) {
            return;
        }
        --parent;
    }
}

template <typename Iterator>
NEFORCE_CONSTEXPR20 void make_heap(Iterator first, Iterator last) {
    _NEFORCE make_heap(first, last, less<iter_value_t<Iterator>>());
}
 // HeapAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_HEAP_HPP__