#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

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 39 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 58 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 197 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 215 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 207 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 96 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 106 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 124 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 116 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 133 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 187 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 149 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 163 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 72 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 87 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 224 of file BLI_inplace_priority_queue.hh.

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

BLI_inplace_priority_queue.hh

Public Member Functions

Detailed Description

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

Constructor & Destructor Documentation

◆ InplacePriorityQueue()

Member Function Documentation

◆ active_indices()

◆ all_indices()

◆ inactive_indices()

◆ is_empty()

◆ peek()

◆ peek_index()

◆ pop()

◆ pop_index()

◆ priority_changed()

◆ priority_decreased()

◆ priority_increased()

◆ rebuild()

◆ size()

◆ to_dot()

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