leonardo_heap.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ALGORITHM_LEONARDO_HEAP_HPP__
#define NEFORCE_CORE_ALGORITHM_LEONARDO_HEAP_HPP__

 
#include "NeForce/core/container/vector.hpp"
#include "NeForce/core/numeric/math.hpp"
NEFORCE_BEGIN_NAMESPACE__



template <typename Iterator>
void adjust_leonardo_heap(Iterator first, size_t current_heap, int level_index, vector<int>& levels) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    size_t child_heap1 = 0;
    size_t child_heap2 = 0;
    while (level_index > 0) {
        size_t prev_heap = current_heap - leonardo(levels[level_index]);
        if (*(first + current_heap) < *(first + prev_heap)) {
            if (levels[level_index] > 1) {
                child_heap1 = current_heap - 1 - leonardo(levels[level_index] - 2);
                child_heap2 = current_heap - 1;
                if (*(first + prev_heap) < *(first + child_heap1)) {
                    break;
                }
                if (*(first + prev_heap) < *(first + child_heap2)) {
                    break;
                }
            }
            _NEFORCE iter_swap(first + current_heap, first + prev_heap);
            current_heap = prev_heap;
            --level_index;
        } else {
            break;
        }
    }
    int current_level = levels[level_index];
    while (current_level > 1) {
        size_t max_child = current_heap;
        child_heap1 = current_heap - 1 - leonardo(current_level - 2);
        child_heap2 = current_heap - 1;
 
        if (*(first + max_child) < *(first + child_heap1)) {
            max_child = child_heap1;
        }
        if (*(first + max_child) < *(first + child_heap2)) {
            max_child = child_heap2;
        }
 
        if (max_child == child_heap1) {
            _NEFORCE iter_swap(first + current_heap, first + child_heap1);
            current_heap = child_heap1;
            --current_level;
        } else if (max_child == child_heap2) {
            _NEFORCE iter_swap(first + current_heap, first + child_heap2);
            current_heap = child_heap2;
            current_level -= 2;
        } else {
            break;
        }
    }
}

template <typename Iterator>
void push_leonardo_heap(Iterator first, Iterator last) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    if (first == last) {
        return;
    }
    const size_t size = _NEFORCE distance(first, last);
    if (size < 2) {
        return;
    }
 
    vector<int> levels = {1};
    int toplevel = 0;
    for (size_t i = 1; i < size - 1; ++i) {
        if (toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1) {
            --toplevel;
            ++levels[toplevel];
        } else if (levels[toplevel] != 1) {
            ++toplevel;
            levels.push_back(1);
        } else {
            ++toplevel;
            levels.push_back(0);
        }
    }
    if (toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1) {
        --toplevel;
        ++levels[toplevel];
    } else if (levels[toplevel] != 1) {
        ++toplevel;
        levels.push_back(1);
    } else {
        ++toplevel;
        levels.push_back(0);
    }
    _NEFORCE adjust_leonardo_heap(first, size - 1, toplevel, levels);
}

template <typename Iterator>
void pop_leonardo_heap(Iterator first, Iterator last) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    if (first == last) {
        return;
    }
    const size_t size = _NEFORCE distance(first, last);
    vector<int> levels = {1};
    int toplevel = 0;
    for (size_t i = 1; i < size; ++i) {
        if (toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1) {
            --toplevel;
            ++levels[toplevel];
        } else if (levels[toplevel] != 1) {
            ++toplevel;
            levels.push_back(1);
        } else {
            ++toplevel;
            levels.push_back(0);
        }
        _NEFORCE adjust_leonardo_heap(first, i, toplevel, levels);
    }
    if (levels[toplevel] <= 1) {
        --toplevel;
    } else {
        --levels[toplevel];
        levels.push_back(levels[toplevel] - 1);
        ++toplevel;
        _NEFORCE adjust_leonardo_heap(first, size - 2 - leonardo(levels[toplevel]), toplevel - 1, levels);
        _NEFORCE adjust_leonardo_heap(first, size - 2, toplevel, levels);
    }
}

template <typename Iterator>
void sort_leonardo_heap(Iterator first, Iterator last) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    if (first == last) {
        return;
    }
    const size_t size = _NEFORCE distance(first, last);
    if (size < 2) {
        return;
    }
 
    vector<int> levels = {1};
    int toplevel = 0;
    for (size_t i = 1; i < size; ++i) {
        if (toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1) {
            --toplevel;
            ++levels[toplevel];
        } else if (levels[toplevel] != 1) {
            ++toplevel;
            levels.push_back(1);
        } else {
            ++toplevel;
            levels.push_back(0);
        }
        _NEFORCE adjust_leonardo_heap(first, i, toplevel, levels);
    }
    for (size_t i = size - 2; i > 0; --i) {
        if (levels[toplevel] <= 1) {
            --toplevel;
        } else {
            --levels[toplevel];
            levels.push_back(levels[toplevel] - 1);
            ++toplevel;
 
            _NEFORCE adjust_leonardo_heap(first, i - leonardo(levels[toplevel]), toplevel - 1, levels);
            _NEFORCE adjust_leonardo_heap(first, i, toplevel, levels);
        }
    }
}

template <typename Iterator>
void make_leonardo_heap(Iterator first, Iterator last) {
    static_assert(is_ranges_rnd_iter_v<Iterator>, "Iterator must be random_access_iterator");
 
    if (first == last) {
        return;
    }
    const size_t size = _NEFORCE distance(first, last);
    vector<int> levels = {1};
    int toplevel = 0;
 
    for (size_t i = 1; i < size; ++i) {
        if (toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1) {
            --toplevel;
            ++levels[toplevel];
        } else if (levels[toplevel] != 1) {
            ++toplevel;
            levels.push_back(1);
        } else {
            ++toplevel;
            levels.push_back(0);
        }
        _NEFORCE adjust_leonardo_heap(first, i, toplevel, levels);
    }
}
 // LeonardoHeap


template <typename Iterator>
NEFORCE_CONSTEXPR20 void smooth_sort(Iterator first, Iterator last) {
    _NEFORCE make_leonardo_heap(first, last);
    _NEFORCE sort_leonardo_heap(first, last);
}
 // SortAlgorithms
 // StandardAlgorithms
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ALGORITHM_LEONARDO_HEAP_HPP__