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 priority than the second. 16 * 17 * Optionally objects may know their index into the priority queue. The queue will update the 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(). 20 * Additionally, the * priority is allowed to change as long as priorityDidChange() 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&))nullptr> 27 class SkTDPQueue : public SkNoncopyable { 28 public: SkTDPQueue()29 SkTDPQueue() {} 30 31 /** Number of items in the queue. */ count()32 int count() const { return fArray.count(); } 33 34 /** Gets the next item in the queue without popping it. */ peek()35 const T& peek() const { return fArray[0]; } peek()36 T& peek() { return fArray[0]; } 37 38 /** Removes the next item. */ pop()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. */ insert(T entry)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-nullptr. */ remove(T entry)66 void remove(T entry) { 67 SkASSERT(nullptr != 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 called after an 84 item's priority is changed to maintain correct ordering. Changing the priority is only 85 allowed if an INDEX function is provided. */ priorityDidChange(T entry)86 void priorityDidChange(T entry) { 87 SkASSERT(nullptr != 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 /** 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 in the queue. */ at(int i)97 T at(int i) const { return fArray[i]; } 98 99 private: LeftOf(int x)100 static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; } ParentOf(int x)101 static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; } 102 percolateUpOrDown(int index)103 void percolateUpOrDown(int index) { 104 SkASSERT(index >= 0); 105 if (!percolateUpIfNecessary(index)) { 106 this->validate(index); 107 this->percolateDownIfNecessary(index); 108 } 109 } 110 percolateUpIfNecessary(int index)111 bool percolateUpIfNecessary(int index) { 112 SkASSERT(index >= 0); 113 bool percolated = false; 114 do { 115 if (0 == index) { 116 this->setIndex(index); 117 return percolated; 118 } 119 int p = ParentOf(index); 120 if (LESS(fArray[index], fArray[p])) { 121 SkTSwap(fArray[index], fArray[p]); 122 this->setIndex(index); 123 index = p; 124 percolated = true; 125 } else { 126 this->setIndex(index); 127 return percolated; 128 } 129 this->validate(index); 130 } while (true); 131 } 132 percolateDownIfNecessary(int index)133 void percolateDownIfNecessary(int index) { 134 SkASSERT(index >= 0); 135 do { 136 int child = LeftOf(index); 137 138 if (child >= fArray.count()) { 139 // We're a leaf. 140 this->setIndex(index); 141 return; 142 } 143 144 if (child + 1 >= fArray.count()) { 145 // We only have a left child. 146 if (LESS(fArray[child], fArray[index])) { 147 SkTSwap(fArray[child], fArray[index]); 148 this->setIndex(child); 149 this->setIndex(index); 150 return; 151 } 152 } else if (LESS(fArray[child + 1], fArray[child])) { 153 // The right child is the one we should swap with, if we swap. 154 child++; 155 } 156 157 // Check if we need to swap. 158 if (LESS(fArray[child], fArray[index])) { 159 SkTSwap(fArray[child], fArray[index]); 160 this->setIndex(index); 161 index = child; 162 } else { 163 // We're less than both our children. 164 this->setIndex(index); 165 return; 166 } 167 this->validate(index); 168 } while (true); 169 } 170 setIndex(int index)171 void setIndex(int index) { 172 SkASSERT(index < fArray.count()); 173 if (SkToBool(INDEX)) { 174 *INDEX(fArray[index]) = index; 175 } 176 } 177 178 void validate(int excludedIndex = -1) const { 179 #ifdef SK_DEBUG 180 for (int i = 1; i < fArray.count(); ++i) { 181 int p = ParentOf(i); 182 if (excludedIndex != p && excludedIndex != i) { 183 SkASSERT(!(LESS(fArray[i], fArray[p]))); 184 SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i); 185 } 186 } 187 #endif 188 } 189 190 SkTDArray<T> fArray; 191 192 typedef SkNoncopyable INHERITED; 193 }; 194 195 #endif 196