NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Namespaces | Functions
nvbio::heap Namespace Reference

Namespaces

 interval_heap_internal
 

Functions

template<typename Iterator , typename Compare >
NVBIO_FORCEINLINE
NVBIO_HOST_DEVICE void 
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 
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 
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 
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 
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 
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 
swap (T &a, T &b)
 
template<typename Iterator , typename Compare >
void 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 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 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 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 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 sort_interval_heap (Iterator first, Iterator last, Compare compare)
 Sorts an interval heap in ascending order. More...
 
template<typename Iterator , typename Compare >
Iterator 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 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 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 
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 
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 
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...
 

Function Documentation

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.

Checks whether the range is a valid interval heap.

Remarks
Exception safety: Non-throwing

Checks whether the range is an interval heap.

Remarks
Exception safety: Non-throwing

Definition at line 309 of file interval_heap.hpp.

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.

Checks whether the range is an interval heap.

Remarks
Exception safety: Non-throwing

Definition at line 339 of file interval_heap.h.

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.

Finds the largest subrange that forms a valid interval heap.

Remarks
Exception safety: Non-throwing

Finds the largest subrange that qualifies as an interval heap.

Remarks
Exception safety: Non-throwing

Definition at line 271 of file interval_heap.hpp.

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.

Finds the largest subrange that qualifies as an interval heap.

Remarks
Exception safety: Non-throwing

Definition at line 301 of file interval_heap.h.

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.

This function moves elements in a range to from an interval-heap.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Postcondition
[ first, last) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(n) !
Exception safety: Basic

Definition at line 327 of file interval_heap.hpp.

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.

This function moves elements in a range to from an interval-heap.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Postcondition
[ first, last) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(n) !
Exception safety: Basic

Definition at line 357 of file interval_heap.h.

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.

This function moves a specified element to the end of the range of iterators. This is typically done so that the element can be efficiently removed (by pop_back, for example).

Parameters
first,lastA range of random-access iterators.
indexThe offset, from first, of the element to be removed.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
index is in the range [ 0, last - first)
Postcondition
[ first, last - 1) is a valid interval heap.
The element originally at first + index has been moved to last - 1.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 171 of file interval_heap.hpp.

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.

This function moves a specified element to the end of the range of iterators. This is typically done so that the element can be efficiently removed (by pop_back, for example).

Parameters
first,lastA range of random-access iterators.
indexThe offset, from first, of the element to be removed.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
index is in the range [ 0, last - first)
Postcondition
[ first, last - 1) is a valid interval heap.
The element originally at first + index has been moved to last - 1.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 216 of file interval_heap.h.

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.

This function moves a maximal element to the end of the range of iterators. This is typically done so that the element can be efficiently removed (by pop_back, for example), but can also be used to sort the range in ascending order.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
Postcondition
A maximal element from the range has been moved to last - 1.
[ first, last - 1) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 230 of file interval_heap.hpp.

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.

This function moves a maximal element to the end of the range of iterators. This is typically done so that the element can be efficiently removed (by pop_back, for example), but can also be used to sort the range in ascending order.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
Postcondition
A maximal element from the range has been moved to last - 1.
[ first, last - 1) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 265 of file interval_heap.h.

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.

This function moves a minimal element to the end of the range of iterators. This is typically done so that the element can be efficiently removed (by pop_back, for example), but can also be used to sort the range in descending order.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
Postcondition
A minimal element from the range has been moved to last - 1.
[ first, last - 1) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 201 of file interval_heap.hpp.

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.

This function moves a minimal element to the end of the range of iterators. This is typically done so that the element can be efficiently removed (by pop_back, for example), but can also be used to sort the range in descending order.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
Postcondition
A minimal element from the range has been moved to last - 1.
[ first, last - 1) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 241 of file interval_heap.h.

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.

This function expands an interval heap from [ first, last - 1) to [ first, last), maintaining the interval-heap property. This is typically used to add a new element to the interval heap.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last - 1) is a valid interval heap.
Postcondition
[ first, last) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 150 of file interval_heap.hpp.

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.

This function expands an interval heap from [ first, last - 1) to [ first, last), maintaining the interval-heap property. This is typically used to add a new element to the interval heap.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last - 1) is a valid interval heap.
Postcondition
[ first, last) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: As strong as sift_interval_heap.

Definition at line 195 of file interval_heap.h.

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.

This function takes an interval heap and sorts its elements in ascending order.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
Postcondition
[ first, last) is sorted in ascending order.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(n log n)
Exception safety: Basic

Definition at line 259 of file interval_heap.hpp.

template<typename Iterator , typename Compare >
void nvbio::heap::sort_interval_heap ( Iterator  first,
Iterator  last,
Compare  compare 
)

Sorts an interval heap in ascending order.

This function takes an interval heap and sorts its elements in ascending order.

Parameters
first,lastA range of random-access iterators.
compareA comparison object.
Precondition
[ first, last) is a valid interval heap.
Postcondition
[ first, last) is sorted in ascending order.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(n log n)
Exception safety: Basic

Definition at line 289 of file interval_heap.h.

template<typename T >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::heap::swap ( T &  a,
T &  b 
)

Definition at line 119 of file interval_heap.h.

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.

This function restores the interval-heap property violated by the specified element.

Parameters
first,lastA range of random-access iterators.
indexThe offset, from first, of the offending element.
compareA comparison object.
Precondition
index is in the range [ 0, last - first).
[ first, last) is a valid interval heap, if the element at first + index is ignored.
Postcondition
[ first, last) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: Basic if move/copy/swap provide the basic guarantee. Strong if they do not throw exceptions.

Definition at line 125 of file interval_heap.hpp.

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.

This function restores the interval-heap property violated by the specified element.

Parameters
first,lastA range of random-access iterators.
indexThe offset, from first, of the offending element.
compareA comparison object.
Precondition
index is in the range [ 0, last - first).
[ first, last) is a valid interval heap, if the element at first + index is ignored.
Postcondition
[ first, last) is a valid interval heap.
Invariant
No element is added to or removed from the range.
Remarks
Complexity: O(log n)
Exception safety: Basic if move/copy/swap provide the basic guarantee. Strong if they do not throw exceptions.

Definition at line 170 of file interval_heap.h.