NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Functions
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_itAn 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,lastInput 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
compComparison class.
seqContainer 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,lastRange of elements.
compInstance of comparison class.
seqInstance 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
valueElement 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
otherPriority 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,deque2Priority 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_itA valid iterator in the range [begin, end).
valueThe 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.