NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Namespaces | Functions
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.