Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
Public Member Functions | List of all members
SkTDPQueue< T, LESS, INDEX > Class Template Reference

#include <SkTDPQueue.h>

Public Member Functions

 SkTDPQueue ()
 
 SkTDPQueue (int reserve)
 
 SkTDPQueue (SkTDPQueue &&)=default
 
SkTDPQueue & operator= (SkTDPQueue &&)=default
 
 SkTDPQueue (const SkTDPQueue &)=delete
 
SkTDPQueue & operator= (const SkTDPQueue &)=delete
 
int count () const
 
const T & peek () const
 
T & peek ()
 
void pop ()
 
void insert (T entry)
 
void remove (T entry)
 
void priorityDidChange (T entry)
 
T at (int i) const
 
void sort ()
 

Detailed Description

template<typename T, bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
class SkTDPQueue< T, LESS, INDEX >

This class implements a priority queue. T is the type of the elements in the queue. LESS is a function that compares two Ts and returns true if the first is higher priority than the second.

Optionally objects may know their index into the priority queue. The queue will update the index as the objects move through the queue. This is enabled by using a non-nullptr function for INDEX. When an INDEX function is provided random deletes from the queue are allowed using remove(). Additionally, the * priority is allowed to change as long as priorityDidChange() is called afterwards. In debug builds the index will be set to -1 before an element is removed from the queue.

Definition at line 33 of file SkTDPQueue.h.

Constructor & Destructor Documentation

◆ SkTDPQueue() [1/4]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
SkTDPQueue< T, LESS, INDEX >::SkTDPQueue ( )
inline

Definition at line 35 of file SkTDPQueue.h.

35{}

◆ SkTDPQueue() [2/4]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
SkTDPQueue< T, LESS, INDEX >::SkTDPQueue ( int  reserve)
inline

Definition at line 36 of file SkTDPQueue.h.

36{ fArray.reserve(reserve); }

◆ SkTDPQueue() [3/4]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
SkTDPQueue< T, LESS, INDEX >::SkTDPQueue ( SkTDPQueue< T, LESS, INDEX > &&  )
default

◆ SkTDPQueue() [4/4]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
SkTDPQueue< T, LESS, INDEX >::SkTDPQueue ( const SkTDPQueue< T, LESS, INDEX > &  )
delete

Member Function Documentation

◆ at()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
T SkTDPQueue< T, LESS, INDEX >::at ( int  i) const
inline

Gets the item at index i in the priority queue (for i < this->count()). at(0) is equivalent to peek(). Otherwise, there is no guarantee about ordering of elements in the queue.

Definition at line 110 of file SkTDPQueue.h.

110{ return fArray[i]; }

◆ count()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
int SkTDPQueue< T, LESS, INDEX >::count ( ) const
inline

Number of items in the queue.

Definition at line 45 of file SkTDPQueue.h.

45{ return fArray.size(); }

◆ insert()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
void SkTDPQueue< T, LESS, INDEX >::insert ( T  entry)
inline

Inserts a new item in the queue based on its priority.

Definition at line 69 of file SkTDPQueue.h.

69 {
70 this->validate();
71 int index = fArray.size();
72 *fArray.append() = entry;
73 this->setIndex(fArray.size() - 1);
74 this->percolateUpIfNecessary(index);
75 this->validate();
76 }

◆ operator=() [1/2]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
SkTDPQueue & SkTDPQueue< T, LESS, INDEX >::operator= ( const SkTDPQueue< T, LESS, INDEX > &  )
delete

◆ operator=() [2/2]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
SkTDPQueue & SkTDPQueue< T, LESS, INDEX >::operator= ( SkTDPQueue< T, LESS, INDEX > &&  )
default

◆ peek() [1/2]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
T & SkTDPQueue< T, LESS, INDEX >::peek ( )
inline

Definition at line 49 of file SkTDPQueue.h.

49{ return fArray[0]; }

◆ peek() [2/2]

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
const T & SkTDPQueue< T, LESS, INDEX >::peek ( ) const
inline

Gets the next item in the queue without popping it.

Definition at line 48 of file SkTDPQueue.h.

48{ return fArray[0]; }

◆ pop()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
void SkTDPQueue< T, LESS, INDEX >::pop ( )
inline

Removes the next item.

Definition at line 52 of file SkTDPQueue.h.

52 {
53 this->validate();
54 SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; })
55 if (1 == fArray.size()) {
56 fArray.pop_back();
57 return;
58 }
59
60 fArray[0] = fArray[fArray.size() - 1];
61 this->setIndex(0);
62 fArray.pop_back();
63 this->percolateDownIfNecessary(0);
64
65 this->validate();
66 }
SkDEBUGCODE
#define SkDEBUGCODE(...)
Definition SkDebug.h:23
SkToBool
static constexpr bool SkToBool(const T &x)
Definition SkTo.h:35

◆ priorityDidChange()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
void SkTDPQueue< T, LESS, INDEX >::priorityDidChange ( T  entry)
inline

Notification that the priority of an entry has changed. This must be called after an item's priority is changed to maintain correct ordering. Changing the priority is only allowed if an INDEX function is provided.

Definition at line 99 of file SkTDPQueue.h.

99 {
100 SkASSERT(nullptr != INDEX);
101 int index = *INDEX(entry);
102 SkASSERT(index >= 0 && index < fArray.size());
103 this->validate(index);
104 this->percolateUpOrDown(index);
105 this->validate();
106 }
SkASSERT
#define SkASSERT(cond)
Definition SkAssert.h:116

◆ remove()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
void SkTDPQueue< T, LESS, INDEX >::remove ( T  entry)
inline

Random access removal. This requires that the INDEX function is non-nullptr.

Definition at line 79 of file SkTDPQueue.h.

79 {
80 SkASSERT(nullptr != INDEX);
81 int index = *INDEX(entry);
82 SkASSERT(index >= 0 && index < fArray.size());
83 this->validate();
84 SkDEBUGCODE(*INDEX(fArray[index]) = -1;)
85 if (index == fArray.size() - 1) {
86 fArray.pop_back();
87 return;
88 }
89 fArray[index] = fArray[fArray.size() - 1];
90 fArray.pop_back();
91 this->setIndex(index);
92 this->percolateUpOrDown(index);
93 this->validate();
94 }

◆ sort()

template<typename T , bool(*)(const T &, const T &) LESS, int *(*)(const T &) INDEX = (int* (*)(const T&))nullptr>
void SkTDPQueue< T, LESS, INDEX >::sort ( )
inline

Sorts the queue into priority order. The queue is only guarenteed to remain in sorted order until any other operation, other than at(), is performed.

Definition at line 115 of file SkTDPQueue.h.

115 {
116 if (fArray.size() > 1) {
117 SkTQSort<T>(fArray.begin(), fArray.end(), LESS);
118 for (int i = 0; i < fArray.size(); i++) {
119 this->setIndex(i);
120 }
121 this->validate();
122 }
123 }
The documentation for this class was generated from the following file:
Generated on Fri Apr 26 2024 06:20:22 for Flutter Engine by doxygen 1.9.8