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