OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef SkTDPQueue_DEFINED | 8 #ifndef SkTDPQueue_DEFINED |
9 #define SkTDPQueue_DEFINED | 9 #define SkTDPQueue_DEFINED |
10 | 10 |
11 #include "SkTDArray.h" | 11 #include "SkTDArray.h" |
12 | 12 |
13 /** | 13 /** |
14 * This class implements a priority queue. T is the type of the elements in the
queue. LESS is a | 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. | 15 * function that compares two Ts and returns true if the first is higher priorit
y than the second. |
16 * | 16 * |
17 * Optionally objects may know their index into the priority queue. The queue wi
ll update the index | 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. | 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(). | 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 | 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 | 21 * afterwards. In debug builds the index will be set to -1 before an element is
removed from the |
22 * queue. | 22 * queue. |
23 */ | 23 */ |
24 template <typename T, | 24 template <typename T, |
25 bool (*LESS)(const T&, const T&), | 25 bool (*LESS)(const T&, const T&), |
26 int* (*INDEX)(const T&) = (int* (*)(const T&))NULL> | 26 int* (*INDEX)(const T&) = (int* (*)(const T&))nullptr> |
27 class SkTDPQueue : public SkNoncopyable { | 27 class SkTDPQueue : public SkNoncopyable { |
28 public: | 28 public: |
29 SkTDPQueue() {} | 29 SkTDPQueue() {} |
30 | 30 |
31 /** Number of items in the queue. */ | 31 /** Number of items in the queue. */ |
32 int count() const { return fArray.count(); } | 32 int count() const { return fArray.count(); } |
33 | 33 |
34 /** Gets the next item in the queue without popping it. */ | 34 /** Gets the next item in the queue without popping it. */ |
35 const T& peek() const { return fArray[0]; } | 35 const T& peek() const { return fArray[0]; } |
36 T& peek() { return fArray[0]; } | 36 T& peek() { return fArray[0]; } |
(...skipping 18 matching lines...) Expand all Loading... |
55 /** Inserts a new item in the queue based on its priority. */ | 55 /** Inserts a new item in the queue based on its priority. */ |
56 void insert(T entry) { | 56 void insert(T entry) { |
57 this->validate(); | 57 this->validate(); |
58 int index = fArray.count(); | 58 int index = fArray.count(); |
59 *fArray.append() = entry; | 59 *fArray.append() = entry; |
60 this->setIndex(fArray.count() - 1); | 60 this->setIndex(fArray.count() - 1); |
61 this->percolateUpIfNecessary(index); | 61 this->percolateUpIfNecessary(index); |
62 this->validate(); | 62 this->validate(); |
63 } | 63 } |
64 | 64 |
65 /** Random access removal. This requires that the INDEX function is non-NULL
. */ | 65 /** Random access removal. This requires that the INDEX function is non-null
ptr. */ |
66 void remove(T entry) { | 66 void remove(T entry) { |
67 SkASSERT(NULL != INDEX); | 67 SkASSERT(nullptr != INDEX); |
68 int index = *INDEX(entry); | 68 int index = *INDEX(entry); |
69 SkASSERT(index >= 0 && index < fArray.count()); | 69 SkASSERT(index >= 0 && index < fArray.count()); |
70 this->validate(); | 70 this->validate(); |
71 SkDEBUGCODE(*INDEX(fArray[index]) = -1;) | 71 SkDEBUGCODE(*INDEX(fArray[index]) = -1;) |
72 if (index == fArray.count() - 1) { | 72 if (index == fArray.count() - 1) { |
73 fArray.pop(); | 73 fArray.pop(); |
74 return; | 74 return; |
75 } | 75 } |
76 fArray[index] = fArray[fArray.count() - 1]; | 76 fArray[index] = fArray[fArray.count() - 1]; |
77 fArray.pop(); | 77 fArray.pop(); |
78 this->setIndex(index); | 78 this->setIndex(index); |
79 this->percolateUpOrDown(index); | 79 this->percolateUpOrDown(index); |
80 this->validate(); | 80 this->validate(); |
81 } | 81 } |
82 | 82 |
83 /** Notification that the priority of an entry has changed. This must be cal
led after an | 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 | 84 item's priority is changed to maintain correct ordering. Changing the pr
iority is only |
85 allowed if an INDEX function is provided. */ | 85 allowed if an INDEX function is provided. */ |
86 void priorityDidChange(T entry) { | 86 void priorityDidChange(T entry) { |
87 SkASSERT(NULL != INDEX); | 87 SkASSERT(nullptr != INDEX); |
88 int index = *INDEX(entry); | 88 int index = *INDEX(entry); |
89 SkASSERT(index >= 0 && index < fArray.count()); | 89 SkASSERT(index >= 0 && index < fArray.count()); |
90 this->validate(index); | 90 this->validate(index); |
91 this->percolateUpOrDown(index); | 91 this->percolateUpOrDown(index); |
92 this->validate(); | 92 this->validate(); |
93 } | 93 } |
94 | 94 |
95 /** Gets the item at index i in the priority queue (for i < this->count()).
at(0) is equivalent | 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 i
n the queue. */ | 96 to peek(). Otherwise, there is no guarantee about ordering of elements i
n the queue. */ |
97 T at(int i) const { return fArray[i]; } | 97 T at(int i) const { return fArray[i]; } |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
186 } | 186 } |
187 #endif | 187 #endif |
188 } | 188 } |
189 | 189 |
190 SkTDArray<T> fArray; | 190 SkTDArray<T> fArray; |
191 | 191 |
192 typedef SkNoncopyable INHERITED; | 192 typedef SkNoncopyable INHERITED; |
193 }; | 193 }; |
194 | 194 |
195 #endif | 195 #endif |
OLD | NEW |