Blender  V3.3
Public Member Functions | List of all members
blender::InplacePriorityQueue< T, FirstHasHigherPriority > Class Template Reference

#include <BLI_inplace_priority_queue.hh>

Public Member Functions

 InplacePriorityQueue (Span< T > data)
 
void rebuild ()
 
int64_t size () const
 
bool is_empty () const
 
const Tpeek () const
 
const Tpop ()
 
int64_t peek_index () const
 
int64_t pop_index ()
 
void priority_decreased (const int64_t index)
 
void priority_increased (const int64_t index)
 
void priority_changed (const int64_t index)
 
Span< int64_tactive_indices () const
 
Span< int64_tinactive_indices () const
 
Span< int64_tall_indices () const
 
std::string to_dot () const
 

Detailed Description

template<typename T, typename FirstHasHigherPriority = std::greater<T>>
class blender::InplacePriorityQueue< T, FirstHasHigherPriority >

An InplacePriorityQueue adds priority queue functionality to an existing array. The underlying array is not changed. Instead, the priority queue maintains indices into the original array.

The priority queue provides efficient access to the element in order of their priorities.

When a priority changes, the priority queue has to be informed using one of the following methods: priority_decreased, priority_increased or priority_changed.

Definition at line 25 of file BLI_inplace_priority_queue.hh.

Constructor & Destructor Documentation

◆ InplacePriorityQueue()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
blender::InplacePriorityQueue< T, FirstHasHigherPriority >::InplacePriorityQueue ( Span< T data)
inline

Construct the priority queue on top of the data in the given span.

Definition at line 44 of file BLI_inplace_priority_queue.hh.

References data_, and blender::InplacePriorityQueue< T, FirstHasHigherPriority >::rebuild().

Member Function Documentation

◆ active_indices()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
Span<int64_t> blender::InplacePriorityQueue< T, FirstHasHigherPriority >::active_indices ( ) const
inline

Returns the indices of all elements that are in the priority queue. There are no guarantees about the order of indices.

Definition at line 183 of file BLI_inplace_priority_queue.hh.

References blender::Array< T, InlineBufferCapacity, Allocator >::as_span(), and blender::Span< T >::take_front().

Referenced by blender::tests::TEST().

◆ all_indices()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
Span<int64_t> blender::InplacePriorityQueue< T, FirstHasHigherPriority >::all_indices ( ) const
inline

Returns the concatenation of the active and inactive indices.

Definition at line 201 of file BLI_inplace_priority_queue.hh.

Referenced by blender::tests::TEST().

◆ inactive_indices()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
Span<int64_t> blender::InplacePriorityQueue< T, FirstHasHigherPriority >::inactive_indices ( ) const
inline

Returns the indices of all elements that are not in the priority queue. The indices are in reverse order of their removal from the queue. I.e. the index that has been removed last, comes first.

Definition at line 193 of file BLI_inplace_priority_queue.hh.

References blender::Array< T, InlineBufferCapacity, Allocator >::as_span(), and blender::Span< T >::drop_front().

Referenced by blender::tests::TEST().

◆ is_empty()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
bool blender::InplacePriorityQueue< T, FirstHasHigherPriority >::is_empty ( ) const
inline

Returns true, when the priority queue contains no elements. If this returns true, peek and pop must not be used.

Definition at line 82 of file BLI_inplace_priority_queue.hh.

Referenced by blender::InplacePriorityQueue< T, FirstHasHigherPriority >::peek_index(), blender::InplacePriorityQueue< T, FirstHasHigherPriority >::pop_index(), and blender::tests::TEST().

◆ peek()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
const T& blender::InplacePriorityQueue< T, FirstHasHigherPriority >::peek ( ) const
inline

Get the element with the highest priority in the priority queue. The returned reference is const, because the priority queue has read-only access to the underlying data. If you need a mutable reference, use peek_index instead.

Definition at line 92 of file BLI_inplace_priority_queue.hh.

References data_, and blender::InplacePriorityQueue< T, FirstHasHigherPriority >::peek_index().

Referenced by blender::tests::TEST().

◆ peek_index()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
int64_t blender::InplacePriorityQueue< T, FirstHasHigherPriority >::peek_index ( ) const
inline

Get the index of the element with the highest priority in the priority queue.

Definition at line 110 of file BLI_inplace_priority_queue.hh.

References BLI_assert, and blender::InplacePriorityQueue< T, FirstHasHigherPriority >::is_empty().

Referenced by blender::InplacePriorityQueue< T, FirstHasHigherPriority >::peek().

◆ pop()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
const T& blender::InplacePriorityQueue< T, FirstHasHigherPriority >::pop ( )
inline

Get the element with the highest priority in the priority queue and remove it. The returned reference is const, because the priority queue has read-only access to the underlying data. If you need a mutable reference, use pop_index instead.

Definition at line 102 of file BLI_inplace_priority_queue.hh.

References blender::InplacePriorityQueue< T, FirstHasHigherPriority >::pop_index().

Referenced by blender::tests::TEST().

◆ pop_index()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
int64_t blender::InplacePriorityQueue< T, FirstHasHigherPriority >::pop_index ( )
inline

Get the index of the element with the highest priority in the priority queue and remove it.

Definition at line 119 of file BLI_inplace_priority_queue.hh.

References BLI_assert, and blender::InplacePriorityQueue< T, FirstHasHigherPriority >::is_empty().

Referenced by blender::InplacePriorityQueue< T, FirstHasHigherPriority >::pop().

◆ priority_changed()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
void blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_changed ( const int64_t  index)
inline

Inform the priority queue that the priority of the element at the given index has been changed.

Definition at line 173 of file BLI_inplace_priority_queue.hh.

References blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_decreased(), and blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_increased().

Referenced by blender::tests::TEST().

◆ priority_decreased()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
void blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_decreased ( const int64_t  index)
inline

Inform the priority queue that the priority of the element at the given index has been decreased.

Definition at line 135 of file BLI_inplace_priority_queue.hh.

Referenced by blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_changed(), and blender::tests::TEST().

◆ priority_increased()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
void blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_increased ( const int64_t  index)
inline

Inform the priority queue that the priority of the element at the given index has been increased.

Definition at line 149 of file BLI_inplace_priority_queue.hh.

Referenced by blender::InplacePriorityQueue< T, FirstHasHigherPriority >::priority_changed(), and blender::tests::TEST().

◆ rebuild()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
void blender::InplacePriorityQueue< T, FirstHasHigherPriority >::rebuild ( )
inline

Rebuilds the priority queue from the array that has been passed to the constructor.

Definition at line 58 of file BLI_inplace_priority_queue.hh.

References data_.

Referenced by blender::InplacePriorityQueue< T, FirstHasHigherPriority >::InplacePriorityQueue().

◆ size()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
int64_t blender::InplacePriorityQueue< T, FirstHasHigherPriority >::size ( ) const
inline

Returns the number of elements in the priority queue. This is less or equal than the size of the underlying array.

Definition at line 73 of file BLI_inplace_priority_queue.hh.

◆ to_dot()

template<typename T , typename FirstHasHigherPriority = std::greater<T>>
std::string blender::InplacePriorityQueue< T, FirstHasHigherPriority >::to_dot ( ) const
inline

Return the heap used by the priority queue as dot graph string. This exists for debugging purposes.

Definition at line 210 of file BLI_inplace_priority_queue.hh.


The documentation for this class was generated from the following file: