Blender
V3.3
|
#include <BLI_inplace_priority_queue.hh>
Public Member Functions | |
InplacePriorityQueue (Span< T > data) | |
void | rebuild () |
int64_t | size () const |
bool | is_empty () const |
const T & | peek () const |
const T & | pop () |
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_t > | active_indices () const |
Span< int64_t > | inactive_indices () const |
Span< int64_t > | all_indices () const |
std::string | to_dot () const |
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.
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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().
|
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.
|
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.