heap.h

// Copyright (c) Electronic Arts Inc. All rights reserved.
 
// This file implements heap functionality much like the std C++ heap algorithms.
// Such heaps are not the same thing as memory heaps or pools, but rather are
// semi-sorted random access containers which have the primary purpose of 
// supporting the implementation of priority_queue and similar data structures.
// 
// The primary distinctions between this heap functionality and std::heap are:
//    - This heap exposes some extra functionality such as is_heap and change_heap.
//    - This heap is more efficient than versions found in typical STL 
//      implementations such as STLPort, Microsoft, and Metrowerks. This comes
//      about due to better use of array dereferencing and branch prediction.
//      You should expect of 5-30%, depending on the usage and platform.
 
// The publicly usable functions we define are:
//    push_heap     -- Adds an entry to a heap.                             Same as C++ std::push_heap.
//    pop_heap      -- Removes the top entry from a heap.                   Same as C++ std::pop_heap.
//    make_heap     -- Converts an array to a heap.                         Same as C++ std::make_heap.
//    sort_heap     -- Sorts a heap in place.                               Same as C++ std::sort_heap.
//    remove_heap   -- Removes an arbitrary entry from a heap.
//    change_heap   -- Changes the priority of an entry in the heap.
//    is_heap       -- Returns true if an array appears is in heap format.   Same as C++11 std::is_heap.
//    is_heap_until -- Returns largest part of the range which is a heap.    Same as C++11 std::is_heap_until.
 
 
 
#ifndef EASTL_HEAP_H
#define EASTL_HEAP_H
 
 
#include <EASTL/internal/config.h>
#include <EASTL/iterator.h>
#include <stddef.h>
 
#if defined(EA_PRAGMA_ONCE_SUPPORTED)
    #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result.
#endif
 
 
 
namespace eastl
{
 
    // promote_heap (internal function)
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename ValueType>
    inline void promote_heap_impl(RandomAccessIterator first, Distance topPosition, Distance position, T value)
    {
        for(Distance parentPosition = (position - 1) >> 1; // This formula assumes that (position > 0). // We use '>> 1' instead of '/ 2' because we have seen VC++ generate better code with >>.
            (position > topPosition) && eastl::less<ValueType>()(*(first + parentPosition), value);
            parentPosition = (position - 1) >> 1)
        {
            *(first + position) = eastl::forward<ValueType>(*(first + parentPosition)); // Swap the node with its parent.
            position = parentPosition;
        }
 
        *(first + position) = eastl::forward<ValueType>(value);
    }
 
    template <typename RandomAccessIterator, typename Distance, typename T>
    inline void promote_heap(RandomAccessIterator first, Distance topPosition, Distance position, const T& value)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        promote_heap_impl<RandomAccessIterator, Distance, const T&, const value_type>(first, topPosition, position, value);
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T>
    inline void promote_heap(RandomAccessIterator first, Distance topPosition, Distance position, T&& value)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        promote_heap_impl<RandomAccessIterator, Distance, T&&, value_type>(first, topPosition, position, eastl::forward<T>(value));
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename Compare, typename ValueType>
    inline void promote_heap_impl(RandomAccessIterator first, Distance topPosition, Distance position, T value, Compare compare)
    {
        for(Distance parentPosition = (position - 1) >> 1; // This formula assumes that (position > 0). // We use '>> 1' instead of '/ 2' because we have seen VC++ generate better code with >>.
            (position > topPosition) && compare(*(first + parentPosition), value);
            parentPosition = (position - 1) >> 1)
        {
            *(first + position) = eastl::forward<ValueType>(*(first + parentPosition)); // Swap the node with its parent.
            position = parentPosition;
        }
 
        *(first + position) = eastl::forward<ValueType>(value);
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename Compare>
    inline void promote_heap(RandomAccessIterator first, Distance topPosition, Distance position, const T& value, Compare compare)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        promote_heap_impl<RandomAccessIterator, Distance, const T&, Compare, const value_type>(first, topPosition, position, value, compare);
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename Compare>
    inline void promote_heap(RandomAccessIterator first, Distance topPosition, Distance position, T&& value, Compare compare)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        promote_heap_impl<RandomAccessIterator, Distance, T&&, Compare, value_type>(first, topPosition, position, eastl::forward<T>(value), compare);
    }
 
 
 
    // adjust_heap (internal function)
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename ValueType>
    void adjust_heap_impl(RandomAccessIterator first, Distance topPosition, Distance heapSize, Distance position, T value)
    {
        // We do the conventional approach of moving the position down to the 
        // bottom then inserting the value at the back and moving it up.
        Distance childPosition = (2 * position) + 2;
 
        for(; childPosition < heapSize; childPosition = (2 * childPosition) + 2)
        {
            if(eastl::less<ValueType>()(*(first + childPosition), *(first + (childPosition - 1)))) // Choose the larger of the two children.
                --childPosition;
            *(first + position) = eastl::forward<ValueType>(*(first + childPosition)); // Swap positions with this child.
            position = childPosition;
        }
 
        if(childPosition == heapSize) // If we are at the very last index of the bottom...
        {
            *(first + position) = eastl::forward<ValueType>(*(first + (childPosition - 1)));
            position = childPosition - 1;
        }
 
        eastl::promote_heap<RandomAccessIterator, Distance, T>(first, topPosition, position, eastl::forward<ValueType>(value));
    }
 
    template <typename RandomAccessIterator, typename Distance, typename T>
    void adjust_heap(RandomAccessIterator first, Distance topPosition, Distance heapSize, Distance position, const T& value)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        adjust_heap_impl<RandomAccessIterator, Distance, const T&, const value_type>(first, topPosition, heapSize, position, eastl::forward<const T&>(value));
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T>
    void adjust_heap(RandomAccessIterator first, Distance topPosition, Distance heapSize, Distance position, T&& value)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        adjust_heap_impl<RandomAccessIterator, Distance, T&&, value_type>(first, topPosition, heapSize, position, eastl::forward<T>(value));
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename Compare, typename ValueType>
    void adjust_heap_impl(RandomAccessIterator first, Distance topPosition, Distance heapSize, Distance position, T value, Compare compare)
    {
        // We do the conventional approach of moving the position down to the 
        // bottom then inserting the value at the back and moving it up.
        Distance childPosition = (2 * position) + 2;
 
        for(; childPosition < heapSize; childPosition = (2 * childPosition) + 2)
        {
            if(compare(*(first + childPosition), *(first + (childPosition - 1)))) // Choose the larger of the two children.
                --childPosition;
            *(first + position) = eastl::forward<ValueType>(*(first + childPosition)); // Swap positions with this child.
            position = childPosition;
        }
 
        if(childPosition == heapSize) // If we are at the bottom...
        {
            *(first + position) = eastl::forward<ValueType>(*(first + (childPosition - 1)));
            position = childPosition - 1;
        }
 
        eastl::promote_heap<RandomAccessIterator, Distance, T, Compare>(first, topPosition, position, eastl::forward<ValueType>(value), compare);
    }
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename Compare>
    void adjust_heap(RandomAccessIterator first, Distance topPosition, Distance heapSize, Distance position, const T& value, Compare compare)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        adjust_heap_impl<RandomAccessIterator, Distance, const T&, Compare, const value_type>(first, topPosition, heapSize, position, eastl::forward<const T&>(value), compare);
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename T, typename Compare>
    void adjust_heap(RandomAccessIterator first, Distance topPosition, Distance heapSize, Distance position, T&& value, Compare compare)
    {
        typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
        adjust_heap_impl<RandomAccessIterator, Distance, T&&, Compare, value_type>(first, topPosition, heapSize, position, eastl::forward<T>(value), compare);
    }
 
 
    // push_heap
 
    template <typename RandomAccessIterator>
    inline void push_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        const value_type tempBottom(eastl::forward<value_type>(*(last - 1)));
 
        eastl::promote_heap<RandomAccessIterator, difference_type, value_type>
                           (first, (difference_type)0, (difference_type)(last - first - 1), eastl::forward<const value_type>(tempBottom));
    }
 
 
    template <typename RandomAccessIterator, typename Compare>
    inline void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        const value_type tempBottom(*(last - 1));
 
        eastl::promote_heap<RandomAccessIterator, difference_type, value_type, Compare>
                           (first, (difference_type)0, (difference_type)(last - first - 1), tempBottom, compare);
    }
 
 
 
 
    // pop_heap
 
    template <typename RandomAccessIterator>
    inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        value_type tempBottom(eastl::forward<value_type>(*(last - 1)));
        *(last - 1) = eastl::forward<value_type>(*first);
        eastl::adjust_heap<RandomAccessIterator, difference_type, value_type>
                          (first, (difference_type)0, (difference_type)(last - first - 1), 0, eastl::forward<value_type>(tempBottom));
    }
 
 
 
    template <typename RandomAccessIterator, typename Compare>
    inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        value_type tempBottom(eastl::forward<value_type>(*(last - 1)));
        *(last - 1) = eastl::forward<value_type>(*first);
        eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare>
                          (first, (difference_type)0, (difference_type)(last - first - 1), 0, eastl::forward<value_type>(tempBottom), compare);
    }
 
 
    // make_heap
 
 
    template <typename RandomAccessIterator>
    void make_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        // We do bottom-up heap construction as per Sedgewick. Such construction is O(n).
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        const difference_type heapSize = last - first;
 
        if(heapSize >= 2) // If there is anything to do... (we need this check because otherwise the math fails below).
        {
            difference_type parentPosition = ((heapSize - 2) >> 1) + 1; // We use '>> 1' instead of '/ 2' because we have seen VC++ generate better code with >>.
 
            do{
                --parentPosition;
                value_type temp(eastl::forward<value_type>(*(first + parentPosition)));
                eastl::adjust_heap<RandomAccessIterator, difference_type, value_type>
                                  (first, parentPosition, heapSize, parentPosition, eastl::forward<value_type>(temp));
            } while(parentPosition != 0);
        }
    }
 
 
    template <typename RandomAccessIterator, typename Compare>
    void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        const difference_type heapSize = last - first;
 
        if(heapSize >= 2) // If there is anything to do... (we need this check because otherwise the math fails below).
        {
            difference_type parentPosition = ((heapSize - 2) >> 1) + 1; // We use '>> 1' instead of '/ 2' because we have seen VC++ generate better code with >>.
 
            do{
                --parentPosition;
                value_type temp(eastl::forward<value_type>(*(first + parentPosition)));
                eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare>
                                  (first, parentPosition, heapSize, parentPosition, eastl::forward<value_type>(temp), compare);
            } while(parentPosition != 0);
        }
    }
 
 
    // sort_heap
 
    template <typename RandomAccessIterator>
    inline void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        for(; (last - first) > 1; --last) // We simply use the heap to sort itself.
            eastl::pop_heap<RandomAccessIterator>(first, last);
    }
 
 
    template <typename RandomAccessIterator, typename Compare>
    inline void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    {
        for(; (last - first) > 1; --last) // We simply use the heap to sort itself.
            eastl::pop_heap<RandomAccessIterator, Compare>(first, last, compare);
    }
 
 
 
    // remove_heap
 
    template <typename RandomAccessIterator, typename Distance>
    inline void remove_heap(RandomAccessIterator first, Distance heapSize, Distance position)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        const value_type tempBottom(*(first + heapSize - 1));
        *(first + heapSize - 1) = *(first + position);
        eastl::adjust_heap<RandomAccessIterator, difference_type, value_type>
                          (first, (difference_type)0, (difference_type)(heapSize - 1), (difference_type)position, tempBottom);
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename Compare>
    inline void remove_heap(RandomAccessIterator first, Distance heapSize, Distance position, Compare compare)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        const value_type tempBottom(*(first + heapSize - 1));
        *(first + heapSize - 1) = *(first + position);
        eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare>
                          (first, (difference_type)0, (difference_type)(heapSize - 1), (difference_type)position, tempBottom, compare);
    }
 
 
 
    // change_heap
 
    template <typename RandomAccessIterator, typename Distance>
    inline void change_heap(RandomAccessIterator first, Distance heapSize, Distance position)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        eastl::remove_heap<RandomAccessIterator, Distance>(first, heapSize, position);
 
        value_type tempBottom(*(first + heapSize - 1));
 
        eastl::promote_heap<RandomAccessIterator, difference_type, value_type>
                           (first, (difference_type)0, (difference_type)(heapSize - 1), tempBottom);
    }
 
 
    template <typename RandomAccessIterator, typename Distance, typename Compare>
    inline void change_heap(RandomAccessIterator first, Distance heapSize, Distance position, Compare compare)
    {
        typedef typename eastl::iterator_traits<RandomAccessIterator>::difference_type difference_type;
        typedef typename eastl::iterator_traits<RandomAccessIterator>::value_type      value_type;
 
        eastl::remove_heap<RandomAccessIterator, Distance, Compare>(first, heapSize, position, compare);
 
        value_type tempBottom(*(first + heapSize - 1));
 
        eastl::promote_heap<RandomAccessIterator, difference_type, value_type, Compare>
                           (first, (difference_type)0, (difference_type)(heapSize - 1), tempBottom, compare);
    }
 
 
 
    // is_heap_until
 
    template <typename RandomAccessIterator>
    inline RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last)
    {
        int counter = 0;
 
        for(RandomAccessIterator child = first + 1; child < last; ++child, counter ^= 1)
        {
            if(*first < *child)  // We must use operator <, and are not allowed to use > or >= here.
                return child;
            first += counter; // counter switches between 0 and 1 every time through.
        }
 
        return last;
    }
 
 
    template <typename RandomAccessIterator, typename Compare>
    inline RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    {
        int counter = 0;
 
        for(RandomAccessIterator child = first + 1; child < last; ++child, counter ^= 1)
        {
            if(compare(*first, *child))
                return child;
            first += counter; // counter switches between 0 and 1 every time through.
        }
 
        return last;
    }
 
 
 
    // is_heap
 
    template <typename RandomAccessIterator>
    inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        return (eastl::is_heap_until(first, last) == last);
    }
 
 
    template <typename RandomAccessIterator, typename Compare>
    inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
    {
        return (eastl::is_heap_until(first, last, compare) == last);
    }
 
 
    // To consider: The following may be a faster implementation for most cases.
    //
    // template <typename RandomAccessIterator>
    // inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
    // {
    //     if(((uintptr_t)(last - first) & 1) == 0) // If the range has an even number of elements...
    //         --last;
    // 
    //     RandomAccessIterator parent = first, child = (first + 1);
    // 
    //     for(; child < last; child += 2, ++parent)
    //     {
    //         if((*parent < *child) || (*parent < *(child + 1)))
    //             return false;
    //     }
    // 
    //     if((((uintptr_t)(last - first) & 1) == 0) && (*parent < *child))
    //         return false;
    // 
    //     return true;
    // }
 
 
} // namespace eastl
 
 
#endif // Header include guard