Line data Source code
1 : /*
2 : * Copyright 2015 Google Inc.
3 : *
4 : * Use of this source code is governed by a BSD-style license that can be
5 : * found in the LICENSE file.
6 : */
7 :
8 : #ifndef SkTDPQueue_DEFINED
9 : #define SkTDPQueue_DEFINED
10 :
11 : #include "SkTDArray.h"
12 :
13 : /**
14 : * This class implements a priority queue. T is the type of the elements in the queue. LESS is a
15 : * function that compares two Ts and returns true if the first is higher priority than the second.
16 : *
17 : * Optionally objects may know their index into the priority queue. The queue will update the index
18 : * as the objects move through the queue. This is enabled by using a non-nullptr function for INDEX.
19 : * When an INDEX function is provided random deletes from the queue are allowed using remove().
20 : * Additionally, the * priority is allowed to change as long as priorityDidChange() is called
21 : * afterwards. In debug builds the index will be set to -1 before an element is removed from the
22 : * queue.
23 : */
24 : template <typename T,
25 : bool (*LESS)(const T&, const T&),
26 : int* (*INDEX)(const T&) = (int* (*)(const T&))nullptr>
27 0 : class SkTDPQueue : public SkNoncopyable {
28 : public:
29 0 : SkTDPQueue() {}
30 :
31 : /** Number of items in the queue. */
32 0 : int count() const { return fArray.count(); }
33 :
34 : /** Gets the next item in the queue without popping it. */
35 : const T& peek() const { return fArray[0]; }
36 0 : T& peek() { return fArray[0]; }
37 :
38 : /** Removes the next item. */
39 0 : void pop() {
40 0 : this->validate();
41 0 : SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; })
42 0 : if (1 == fArray.count()) {
43 0 : fArray.pop();
44 0 : return;
45 : }
46 :
47 0 : fArray[0] = fArray[fArray.count() - 1];
48 0 : this->setIndex(0);
49 0 : fArray.pop();
50 0 : this->percolateDownIfNecessary(0);
51 :
52 0 : this->validate();
53 : }
54 :
55 : /** Inserts a new item in the queue based on its priority. */
56 0 : void insert(T entry) {
57 0 : this->validate();
58 0 : int index = fArray.count();
59 0 : *fArray.append() = entry;
60 0 : this->setIndex(fArray.count() - 1);
61 0 : this->percolateUpIfNecessary(index);
62 0 : this->validate();
63 0 : }
64 :
65 : /** Random access removal. This requires that the INDEX function is non-nullptr. */
66 0 : void remove(T entry) {
67 : SkASSERT(nullptr != INDEX);
68 0 : int index = *INDEX(entry);
69 0 : SkASSERT(index >= 0 && index < fArray.count());
70 0 : this->validate();
71 0 : SkDEBUGCODE(*INDEX(fArray[index]) = -1;)
72 0 : if (index == fArray.count() - 1) {
73 0 : fArray.pop();
74 0 : return;
75 : }
76 0 : fArray[index] = fArray[fArray.count() - 1];
77 0 : fArray.pop();
78 0 : this->setIndex(index);
79 0 : this->percolateUpOrDown(index);
80 0 : this->validate();
81 : }
82 :
83 : /** Notification that the priority of an entry has changed. This must be called after an
84 : item's priority is changed to maintain correct ordering. Changing the priority is only
85 : allowed if an INDEX function is provided. */
86 : void priorityDidChange(T entry) {
87 : SkASSERT(nullptr != INDEX);
88 : int index = *INDEX(entry);
89 : SkASSERT(index >= 0 && index < fArray.count());
90 : this->validate(index);
91 : this->percolateUpOrDown(index);
92 : this->validate();
93 : }
94 :
95 : /** Gets the item at index i in the priority queue (for i < this->count()). at(0) is equivalent
96 : to peek(). Otherwise, there is no guarantee about ordering of elements in the queue. */
97 0 : T at(int i) const { return fArray[i]; }
98 :
99 : private:
100 0 : static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; }
101 0 : static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; }
102 :
103 0 : void percolateUpOrDown(int index) {
104 0 : SkASSERT(index >= 0);
105 0 : if (!percolateUpIfNecessary(index)) {
106 0 : this->validate(index);
107 0 : this->percolateDownIfNecessary(index);
108 : }
109 0 : }
110 :
111 0 : bool percolateUpIfNecessary(int index) {
112 0 : SkASSERT(index >= 0);
113 0 : bool percolated = false;
114 : do {
115 0 : if (0 == index) {
116 0 : this->setIndex(index);
117 0 : return percolated;
118 : }
119 0 : int p = ParentOf(index);
120 0 : if (LESS(fArray[index], fArray[p])) {
121 0 : SkTSwap(fArray[index], fArray[p]);
122 0 : this->setIndex(index);
123 0 : index = p;
124 0 : percolated = true;
125 : } else {
126 0 : this->setIndex(index);
127 0 : return percolated;
128 : }
129 0 : this->validate(index);
130 : } while (true);
131 : }
132 :
133 0 : void percolateDownIfNecessary(int index) {
134 0 : SkASSERT(index >= 0);
135 : do {
136 0 : int child = LeftOf(index);
137 :
138 0 : if (child >= fArray.count()) {
139 : // We're a leaf.
140 0 : this->setIndex(index);
141 0 : return;
142 : }
143 :
144 0 : if (child + 1 >= fArray.count()) {
145 : // We only have a left child.
146 0 : if (LESS(fArray[child], fArray[index])) {
147 0 : SkTSwap(fArray[child], fArray[index]);
148 0 : this->setIndex(child);
149 0 : this->setIndex(index);
150 0 : return;
151 : }
152 0 : } else if (LESS(fArray[child + 1], fArray[child])) {
153 : // The right child is the one we should swap with, if we swap.
154 0 : child++;
155 : }
156 :
157 : // Check if we need to swap.
158 0 : if (LESS(fArray[child], fArray[index])) {
159 0 : SkTSwap(fArray[child], fArray[index]);
160 0 : this->setIndex(index);
161 0 : index = child;
162 : } else {
163 : // We're less than both our children.
164 0 : this->setIndex(index);
165 0 : return;
166 : }
167 0 : this->validate(index);
168 : } while (true);
169 : }
170 :
171 0 : void setIndex(int index) {
172 0 : SkASSERT(index < fArray.count());
173 : if (SkToBool(INDEX)) {
174 0 : *INDEX(fArray[index]) = index;
175 : }
176 0 : }
177 :
178 0 : void validate(int excludedIndex = -1) const {
179 : #ifdef SK_DEBUG
180 0 : for (int i = 1; i < fArray.count(); ++i) {
181 0 : int p = ParentOf(i);
182 0 : if (excludedIndex != p && excludedIndex != i) {
183 0 : SkASSERT(!(LESS(fArray[i], fArray[p])));
184 0 : SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i);
185 : }
186 : }
187 : #endif
188 0 : }
189 :
190 : SkTDArray<T> fArray;
191 :
192 : typedef SkNoncopyable INHERITED;
193 : };
194 :
195 : #endif
|
