| 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 |