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-NULL 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&))NULL>
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-NULL. */
remove(T entry)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 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(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     /** 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