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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
index	The offset, from first, of the element to be removed.
compare	A 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,last	A range of random-access iterators.
index	The offset, from first, of the element to be removed.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
compare	A 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,last	A range of random-access iterators.
index	The offset, from first, of the offending element.
compare	A 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,last	A range of random-access iterators.
index	The offset, from first, of the offending element.
compare	A 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.