interval_heap.h File Reference

#include <iterator>

Go to the source code of this file.

Namespaces
	nvbio
	Define a vector_view POD type and plain_view() for std::vector.
	nvbio::heap
	nvbio::heap::interval_heap_internal

Functions
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::make_interval_heap (Iterator first, Iterator last, Compare compare)
	Moves elements in [first,last) to form an interval heap. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::push_interval_heap (Iterator first, Iterator last, Compare compare)
	Expands the interval heap to include the element at last-1. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::update_interval_heap (Iterator first, Iterator last, typename std::iterator_traits< Iterator >::difference_type index, Compare compare)
	Restores the interval-heap property if one element violates it. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::sort_interval_heap (Iterator first, Iterator last, Compare compare)
	Sorts an interval heap in ascending order. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE Iterator	nvbio::heap::is_interval_heap_until (Iterator first, Iterator last, Compare compare)
	Finds the largest subrange that qualifies as an interval heap. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bool	nvbio::heap::is_interval_heap (Iterator first, Iterator last, Compare compare)
	Checks whether the range is an interval heap. More...
template<typename T >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::swap (T &a, T &b)
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::interval_heap_internal::sift_leaf (Iterator first, Iterator last, typename std::iterator_traits< Iterator >::difference_type index, Compare compare)
	Restores the interval-heap property if one leaf element violates it. More...
template<bool left_bound, typename Iterator , typename Offset , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::interval_heap_internal::sift_up (Iterator first, Offset index, Compare compare, Offset limit_child)
	Moves an element up the interval heap. More...
template<typename Iterator , typename Offset , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::interval_heap_internal::sift_leaf_max (Iterator first, Iterator last, Offset index, Compare compare, Offset limit_child)
	Moves an element between min/max bounds, and up the interval heap. More...
template<typename Iterator , typename Offset , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::interval_heap_internal::sift_leaf_min (Iterator first, Iterator last, Offset index, Compare compare, Offset limit_child)
	Moves an element between min/max bounds, and up the interval heap. More...
template<bool left_bound, typename Iterator , typename Offset , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::interval_heap_internal::sift_down (Iterator first, Iterator last, Offset index, Compare compare, Offset limit_child)
	Restores the interval-heap property if one element violates it. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::update_interval_heap (Iterator first, Iterator last, typename std::iterator_traits< Iterator >::difference_type index, Compare compare)
	Restores the interval-heap property if one element violates it. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::push_interval_heap (Iterator first, Iterator last, Compare compare)
	Expands the interval heap to include the element at last-1. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::pop_interval_heap (Iterator first, Iterator last, typename std::iterator_traits< Iterator >::difference_type index, Compare compare)
	Moves an element to the back of the range for popping. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::pop_interval_heap_min (Iterator first, Iterator last, Compare compare)
	Moves a minimal element to the back of the range for popping. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::pop_interval_heap_max (Iterator first, Iterator last, Compare compare)
	Moves a maximal element to the back of the range for popping. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::sort_interval_heap (Iterator first, Iterator last, Compare compare)
	Sorts an interval heap in ascending order. More...
template<typename Iterator , typename Compare >
Iterator	nvbio::heap::is_interval_heap_until (Iterator first, Iterator last, Compare compare)
	Finds the largest subrange that forms a valid interval heap. More...
template<typename Iterator , typename Compare >
bool	nvbio::heap::is_interval_heap (Iterator first, Iterator last, Compare compare)
	Checks whether the range is a valid interval heap. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::make_interval_heap (Iterator first, Iterator last, Compare compare)
	Moves elements in [first,last) to form an interval heap. More...
template<bool left_bound, typename Iterator , typename Offset , typename Compare >
void	nvbio::heap::interval_heap_internal::sift_up (Iterator first, Offset origin, Compare compare, Offset limit_child)
	Moves an element up the interval heap. More...
template<typename Iterator , typename Offset , typename Compare >
void	nvbio::heap::interval_heap_internal::sift_leaf_max (Iterator first, Iterator last, Offset index, Compare compare, Offset limit_child)
	Moves an element between min/max bounds, and up the interval heap. More...
template<typename Iterator , typename Offset , typename Compare >
void	nvbio::heap::interval_heap_internal::sift_leaf_min (Iterator first, Iterator last, Offset index, Compare compare, Offset limit_child)
	Moves an element between min/max bounds, and up the interval heap. More...
template<bool left_bound, typename Iterator , typename Offset , typename Compare >
void	nvbio::heap::interval_heap_internal::sift_down (Iterator first, Iterator last, Offset origin, Compare compare, Offset limit_child)
	Restores the interval-heap property if one element violates it. More...
template<typename Iterator , typename Compare >
void	nvbio::heap::interval_heap_internal::sift_leaf (Iterator first, Iterator last, typename std::iterator_traits< Iterator >::difference_type index, Compare compare)
	Restores the interval-heap property if one leaf element violates it. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::pop_interval_heap_min (Iterator first, Iterator last, Compare compare)
	Moves a minimal element to the back of the range for popping. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::pop_interval_heap_max (Iterator first, Iterator last, Compare compare)
	Moves a maximal element to the back of the range for popping. More...
template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::heap::pop_interval_heap (Iterator first, Iterator last, typename std::iterator_traits< Iterator >::difference_type index, Compare compare)
	Moves an element to the back of the range for popping. More...

Detailed Description

interval_heap.hpp provides functions for creating interval heaps by rearranging a range of elements. A valid interval heap has the following properties: Given elements A and B, A is less than B iff compare(A,B), where compare is a binary functor describing a strict weak ordering. Left and right bounds are those with even and odd indices, respectively. A right bound is never less than its corresponding left bound. A left bound is never less than the left bound of its parent. A right bound is never less than the right bounds of its children.

Remarks

Exception-safety: All functions in interval_heap.hpp provide at least the basic exception-safety guarantee. That is, no element will be lost in the event of an exception. Elements may, however, no longer form an interval heap.

Exception-safety: Pre-C++11: If the comparison and swap don't throw, neither do any of the interval-heap functions.

Exception-safety: C++11: If the comparison, move-assign, and move-construct, do not throw, neither do any of the interval-heap functions.

Definition in file interval_heap.h.