Program Listing for File heap.h¶
↰ Return to documentation for file (necsim/eastl/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 <stddef.h>
#include <utility>
#include <iterator>
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) && (*(first + parentPosition) < value);
parentPosition = (position - 1) >> 1)
{
*(first + position) = std::forward<ValueType>(*(first + parentPosition)); // Swap the node with its parent.
position = parentPosition;
}
*(first + position) = std::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, std::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) = std::forward<ValueType>(*(first + parentPosition)); // Swap the node with its parent.
position = parentPosition;
}
*(first + position) = std::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, std::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(*(first + childPosition) < *(first + (childPosition - 1))) // Choose the larger of the two children.
--childPosition;
*(first + position) = std::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) = std::forward<ValueType>(*(first + (childPosition - 1)));
position = childPosition - 1;
}
eastl::promote_heap<RandomAccessIterator, Distance, T>(first, topPosition, position, std::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, std::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, std::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) = std::forward<ValueType>(*(first + childPosition)); // Swap positions with this child.
position = childPosition;
}
if(childPosition == heapSize) // If we are at the bottom...
{
*(first + position) = std::forward<ValueType>(*(first + (childPosition - 1)));
position = childPosition - 1;
}
eastl::promote_heap<RandomAccessIterator, Distance, T, Compare>(first, topPosition, position, std::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, std::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, std::forward<T>(value), compare);
}
// push_heap
template <typename RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last)
{
typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
const value_type tempBottom(std::forward<value_type>(*(last - 1)));
eastl::promote_heap<RandomAccessIterator, difference_type, value_type>
(first, (difference_type)0, (difference_type)(last - first - 1), std::forward<const value_type>(tempBottom));
}
template <typename RandomAccessIterator, typename Compare>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
{
typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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 std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
value_type tempBottom(std::forward<value_type>(*(last - 1)));
*(last - 1) = std::forward<value_type>(*first);
eastl::adjust_heap<RandomAccessIterator, difference_type, value_type>
(first, (difference_type)0, (difference_type)(last - first - 1), 0, std::forward<value_type>(tempBottom));
}
template <typename RandomAccessIterator, typename Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
{
typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
value_type tempBottom(std::forward<value_type>(*(last - 1)));
*(last - 1) = std::forward<value_type>(*first);
eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare>
(first, (difference_type)0, (difference_type)(last - first - 1), 0, std::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 std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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(std::forward<value_type>(*(first + parentPosition)));
eastl::adjust_heap<RandomAccessIterator, difference_type, value_type>
(first, parentPosition, heapSize, parentPosition, std::forward<value_type>(temp));
} while(parentPosition != 0);
}
}
template <typename RandomAccessIterator, typename Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare compare)
{
typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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(std::forward<value_type>(*(first + parentPosition)));
eastl::adjust_heap<RandomAccessIterator, difference_type, value_type, Compare>
(first, parentPosition, heapSize, parentPosition, std::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 std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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 std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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 std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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 std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename std::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