OLD | NEW |
(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 |
OLD | NEW |