Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(519)

Side by Side Diff: src/core/SkTDPQueue.h

Issue 914003004: Add a templated priority queue class. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Attempt to silence warning Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « gyp/tests.gypi ('k') | tests/TDPQueueTest.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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 priorit y than the second.
16 *
17 * Optionally objects may know their index into the priority queue. The queue wi ll update the index
18 * as the objects move through the queue. This is enabled by using a non-NULL fu nction 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 priorityDidChang e() 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&))NULL>
27 class SkTDPQueue : public SkNoncopyable {
28 public:
29 SkTDPQueue() {}
30
31 /** Number of items in the queue. */
32 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 T& peek() { return fArray[0]; }
37
38 /** Removes the next item. */
39 void pop() {
40 this->validate();
41 SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; })
42 if (1 == fArray.count()) {
43 fArray.pop();
44 return;
45 }
46
47 fArray[0] = fArray[fArray.count() - 1];
48 this->setIndex(0);
49 fArray.pop();
50 this->percolateDownIfNecessary(0);
51
52 this->validate();
53 }
54
55 /** Inserts a new item in the queue based on its priority. */
56 void insert(T entry) {
57 this->validate();
58 int index = fArray.count();
59 *fArray.append() = entry;
60 this->setIndex(fArray.count() - 1);
61 this->percolateUpIfNecessary(index);
62 this->validate();
63 }
64
65 /** Random access removal. This requires that the INDEX function is non-NULL . */
66 void remove(T entry) {
67 SkASSERT(NULL != INDEX);
68 int index = *INDEX(entry);
69 SkASSERT(index >= 0 && index < fArray.count());
70 this->validate();
71 SkDEBUGCODE(*INDEX(fArray[index]) = -1;)
72 if (index == fArray.count() - 1) {
73 fArray.pop();
74 return;
75 }
76 fArray[index] = fArray[fArray.count() - 1];
77 fArray.pop();
78 this->setIndex(index);
79 this->percolateUpOrDown(index);
80 this->validate();
81 }
82
83 /** Notification that the priority of an entry has changed. This must be cal led after an
84 item's priority is changed to maintain correct ordering. Changing the pr iority is only
85 allowed if an INDEX function is provided. */
86 void priorityDidChange(T entry) {
87 SkASSERT(NULL != 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 private:
96 static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; }
97 static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; }
98
99 void percolateUpOrDown(int index) {
100 SkASSERT(index >= 0);
101 if (!percolateUpIfNecessary(index)) {
102 this->validate(index);
103 this->percolateDownIfNecessary(index);
104 }
105 }
106
107 bool percolateUpIfNecessary(int index) {
108 SkASSERT(index >= 0);
109 bool percolated = false;
110 do {
111 if (0 == index) {
112 this->setIndex(index);
113 return percolated;
114 }
115 int p = ParentOf(index);
116 if (LESS(fArray[index], fArray[p])) {
117 SkTSwap(fArray[index], fArray[p]);
118 this->setIndex(index);
119 index = p;
120 percolated = true;
121 } else {
122 this->setIndex(index);
123 return percolated;
124 }
125 this->validate(index);
126 } while (true);
127 }
128
129 void percolateDownIfNecessary(int index) {
130 SkASSERT(index >= 0);
131 do {
132 int child = LeftOf(index);
133
134 if (child >= fArray.count()) {
135 // We're a leaf.
136 this->setIndex(index);
137 return;
138 }
139
140 if (child + 1 >= fArray.count()) {
141 // We only have a left child.
142 if (LESS(fArray[child], fArray[index])) {
143 SkTSwap(fArray[child], fArray[index]);
144 this->setIndex(child);
145 this->setIndex(index);
146 return;
147 }
148 } else if (LESS(fArray[child + 1], fArray[child])) {
149 // The right child is the one we should swap with, if we swap.
150 child++;
151 }
152
153 // Check if we need to swap.
154 if (LESS(fArray[child], fArray[index])) {
155 SkTSwap(fArray[child], fArray[index]);
156 this->setIndex(index);
157 index = child;
158 } else {
159 // We're less than both our children.
160 this->setIndex(index);
161 return;
162 }
163 this->validate(index);
164 } while (true);
165 }
166
167 void setIndex(int index) {
168 SkASSERT(index < fArray.count());
169 if (SkToBool(INDEX)) {
170 *INDEX(fArray[index]) = index;
171 }
172 }
173
174 void validate(int excludedIndex = -1) const {
175 #ifdef SK_DEBUG
176 for (int i = 1; i < fArray.count(); ++i) {
177 int p = ParentOf(i);
178 if (excludedIndex != p && excludedIndex != i) {
179 SkASSERT(!(LESS(fArray[i], fArray[p])));
180 SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i);
181 }
182 }
183 #endif
184 }
185
186 SkTDArray<T> fArray;
187
188 typedef SkNoncopyable INHERITED;
189 };
190
191 #endif
OLDNEW
« no previous file with comments | « gyp/tests.gypi ('k') | tests/TDPQueueTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698