#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 33 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 52 of file BLI_inplace_priority_queue.hh.

References data, i, and size().

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 191 of file BLI_inplace_priority_queue.hh.

References 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 209 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 201 of file BLI_inplace_priority_queue.hh.

References 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 90 of file BLI_inplace_priority_queue.hh.

Referenced by blender::ed::transform::curves::curve_connected_point_distances(), blender::ed::transform::curves::cyclic_curve_connected_point_distances(), peek_index(), pop_index(), blender::tests::TEST(), 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 100 of file BLI_inplace_priority_queue.hh.

References peek_index(), and T.

Referenced by blender::tests::TEST(), blender::tests::TEST(), and 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 118 of file BLI_inplace_priority_queue.hh.

References BLI_assert, and is_empty().

Referenced by 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 110 of file BLI_inplace_priority_queue.hh.

References pop_index(), and T.

Referenced by blender::tests::TEST(), blender::tests::TEST(), blender::tests::TEST(), and 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 127 of file BLI_inplace_priority_queue.hh.

References BLI_assert, and is_empty().

Referenced by blender::ed::transform::curves::curve_connected_point_distances(), blender::ed::transform::curves::cyclic_curve_connected_point_distances(), and 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 181 of file BLI_inplace_priority_queue.hh.

References priority_decreased(), and 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 143 of file BLI_inplace_priority_queue.hh.

Referenced by 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 157 of file BLI_inplace_priority_queue.hh.

Referenced by blender::ed::transform::curves::curve_connected_point_distances(), blender::ed::transform::curves::cyclic_curve_connected_point_distances(), 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 66 of file BLI_inplace_priority_queue.hh.

References i.

◆ 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 81 of file BLI_inplace_priority_queue.hh.

Referenced by InplacePriorityQueue().

◆ 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 218 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

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()