Priority Deques

Detailed Description

This module implements a priority deque adaptor, allowing to push/pop from both ends of the container.

Classes
class	nvbio::priority_deque< Type, Sequence, Compare >
	Efficient double-ended priority queue. More...

Functions
template<typename Type , typename Sequence , typename Compare >
void	nvbio::swap (priority_deque< Type, Sequence, Compare > &deque1, priority_deque< Type, Sequence, Compare > &deque2)
	Swaps the elements of two priority deques. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	nvbio::priority_deque< Type, Sequence, Compare >::priority_deque (const Compare &=Compare(), const Sequence &=Sequence())
	Constructs a new priority deque. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	nvbio::priority_deque< Type, Sequence, Compare >::priority_deque (const Sequence &seq, const bool constructed=false)
template<typename InputIterator >
	boost::container::priority_deque< Type, Sequence, Compare >::priority_deque (InputIterator first, InputIterator last, const C &comp, const S &seq)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::push (const value_type &)
	Copies an element into the priority deque. More...
template<typename InputIterator >
void	boost::container::priority_deque< Type, Sequence, Compare >::merge (InputIterator first, InputIterator last)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::swap (priority_deque< Type, Sequence, Compare > &)
	Moves the elements from this deque into another, and vice-versa. More...
template<typename T , typename S , typename C >
void	swap (priority_deque< T, S, C > &deque1, priority_deque< T, S, C > &deque2)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	nvbio::priority_deque< Type, Sequence, Compare >::maximum (void) const
	Accesses a maximal element in the deque. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	nvbio::priority_deque< Type, Sequence, Compare >::minimum (void) const
	Accesses a minimal element in the deque. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	nvbio::priority_deque< Type, Sequence, Compare >::top (void) const
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference	nvbio::priority_deque< Type, Sequence, Compare >::bottom (void) const
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::pop_bottom (void)
	Removes a minimal element from the deque. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::pop_top (void)
	Removes a maximal element from the deque. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::pop (void)
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::update (const_iterator, const value_type &)
	Modifies a specified element of the deque. More...
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	nvbio::priority_deque< Type, Sequence, Compare >::erase (const_iterator)
	Removes a specified element from the deque. More...

Function Documentation

template<typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference nvbio::priority_deque< Type, Sequence, Compare >::bottom ( void  ) const

inline

Identical to std::priority_queue top().

See Also

maximum

Definition at line 214 of file priority_deque.h.

template<typename T , typename Sequence , typename Compare >

void nvbio::priority_deque< T, Sequence, Compare >::erase

(

const_iterator

random_it)

Removes a specified element from the deque.

Parameters

random_it

An iterator in the range [begin, end)

Precondition

Priority deque contains one or more elements.

Postcondition

The deque no longer contains the element previously at random_it.

All iterators and references are invalidated.

See Also

set

Remarks

Complexity: O(log n)

Definition at line 498 of file priority_deque.h.

template<typename T , typename Sequence , typename Compare >

priority_deque< T, Sequence, Compare >::const_reference nvbio::priority_deque< T, Sequence, Compare >::maximum

(

void

)

const

Accesses a maximal element in the deque.

Returns

Const reference to a maximal element in the priority deque.

Precondition

Priority deque contains one or more elements.

See Also

minimum, pop_maximum

Remarks

Complexity: O(1)

Definition at line 369 of file priority_deque.h.

template<typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>

template<typename InputIterator >

void boost::container::priority_deque< Type, Sequence, Compare >::merge	(	InputIterator	first,
		InputIterator	last
	)

Parameters

first,last

Input iterators bounding the range [ first, last)

Postcondition

Priority deque contains its original elements, and copies of those in the range.

All iterators and references are invalidated.

Remarks

Complexity: O(n)

Exception safety: Basic.

Definition at line 432 of file priority_deque.h.

template<typename T , typename Sequence , typename Compare >

priority_deque< T, Sequence, Compare >::const_reference nvbio::priority_deque< T, Sequence, Compare >::minimum

(

void

)

const

Accesses a minimal element in the deque.

Returns

Const reference to a minimal element in the priority deque.

Precondition

Priority deque contains one or more elements.

See Also

maximum, pop_minimum

Remarks

Complexity: O(1)

Definition at line 384 of file priority_deque.h.

template<typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::priority_deque< Type, Sequence, Compare >::pop ( void  )

inline

Identical to std::priority_queue pop().

See Also

pop_maximum

Definition at line 225 of file priority_deque.h.

template<typename T , typename Sequence , typename Compare >

void nvbio::priority_deque< T, Sequence, Compare >::pop_bottom

(

void

)

Removes a minimal element from the deque.

Precondition

Priority deque contains one or more elements.

Postcondition

A maximal element has been removed from the priority deque.

All iterators and references are invalidated.

See Also

maximum, pop, pop_minimum

Remarks

Complexity: O(log n)

Definition at line 399 of file priority_deque.h.

template<typename T , typename Sequence , typename Compare >

void nvbio::priority_deque< T, Sequence, Compare >::pop_top

(

void

)

Removes a maximal element from the deque.

Precondition

Priority deque contains one or more elements.

Postcondition

A minimal element has been removed from the priority deque.

All iterators and references are invalidated.

See Also

minimum, pop_maximum

Remarks

Complexity: O(log n)

Definition at line 413 of file priority_deque.h.

template<typename T , typename S, typename C>

nvbio::priority_deque< T, S, C >::priority_deque ( const C &  comp = Compare(), const S &  seq = Sequence()  )

explicit

Constructs a new priority deque.

Parameters

comp	Comparison class.
seq	Container class.

Postcondition

Deque contains copies of all elements from sequence.

Remarks

Complexity: O(n)

Definition at line 312 of file priority_deque.h.

template<typename T , typename S, typename C >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE nvbio::priority_deque< T, S, C >::priority_deque	(	const S &	seq,
		const bool	constructed = false
	)

O(1) Creates a new priority deque from an already heapified container

Definition at line 320 of file priority_deque.h.

template<typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>

template<typename InputIterator >

boost::container::priority_deque< Type, Sequence, Compare >::priority_deque	(	InputIterator	first,
		InputIterator	last,
		const C &	comp,
		const S &	seq
	)

Parameters

first,last	Range of elements.
comp	Instance of comparison class.
seq	Instance of container class.

Postcondition

Deque contains copies of all elements in sequence (if specified) and in the range [ first, last).

Remarks

Complexity: O(n)

Definition at line 338 of file priority_deque.h.

template<typename T , typename Sequence , typename Compare >

void nvbio::priority_deque< T, Sequence, Compare >::push

(

const value_type &

value)

Copies an element into the priority deque.

Parameters

value

Element to add the the priority deque.

Postcondition

Priority deque contains value or a copy of value.

All iterators and references are invalidated.

Remarks

Complexity: O(log n)

Definition at line 355 of file priority_deque.h.

template<typename Type , typename Sequence , typename Compare >

void nvbio::swap	(	priority_deque< Type, Sequence, Compare > &	deque1,
		priority_deque< Type, Sequence, Compare > &	deque2
	)

Swaps the elements of two priority deques.

template<typename T, typename S, typename C>

void nvbio::priority_deque< T, S, C >::swap

(

priority_deque< T, S, C > &

other)

Moves the elements from this deque into another, and vice-versa.

Parameters

other

Priority deque with which to swap.

Postcondition

Deque contains the elements from source, and source contains the elements from this deque.

All iterators and references are invalidated.

Note

Sequence containers are required to have swap functions.

Remarks

Complexity: O(1)

Definition at line 446 of file priority_deque.h.

template<typename T , typename S , typename C >

void swap ( priority_deque< T, S, C > &  deque1, priority_deque< T, S, C > &  deque2  )

related

Parameters

deque1,deque2

Priority deques.

Postcondition

deque1 contains the elements originally in deque2, and deque2 contains the elements originally in deque1

All iterators and references are invalidated.

Remarks

Complexity: O(1)

Definition at line 459 of file priority_deque.h.

template<typename Type, typename Sequence = std::vector<Type>, typename Compare = ::std::less<typename Sequence::value_type>>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const_reference nvbio::priority_deque< Type, Sequence, Compare >::top ( void  ) const

inline

Identical to std::priority_queue top().

See Also

maximum

Definition at line 211 of file priority_deque.h.

template<typename T , typename S , typename C >

void nvbio::priority_deque< T, S, C >::update	(	const_iterator	random_it,
		const value_type &	value
	)

Modifies a specified element of the deque.

Parameters

random_it	A valid iterator in the range [begin, end).
value	The new value.

Precondition

Priority deque contains one or more elements.

Postcondition

The element at random_it is set to value.

All iterators and references are invalidated.

See Also

erase

Elements within the deque may be unordered.

Remarks

Complexity: O(log n)

Exception safety: Basic. Exceptions won't lose elements, but may corrupt the heap.

Definition at line 479 of file priority_deque.h.