• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #include "SkTSort.h"
13 
14 /**
15  * This class implements a priority queue. T is the type of the elements in the queue. LESS is a
16  * function that compares two Ts and returns true if the first is higher priority than the second.
17  *
18  * Optionally objects may know their index into the priority queue. The queue will update the index
19  * as the objects move through the queue. This is enabled by using a non-nullptr function for INDEX.
20  * When an INDEX function is provided random deletes from the queue are allowed using remove().
21  * Additionally, the * priority is allowed to change as long as priorityDidChange() is called
22  * afterwards. In debug builds the index will be set to -1 before an element is removed from the
23  * queue.
24  */
25 template <typename T,
26           bool (*LESS)(const T&, const T&),
27           int* (*INDEX)(const T&) = (int* (*)(const T&))nullptr>
28 class SkTDPQueue {
29 public:
SkTDPQueue()30     SkTDPQueue() {}
31 
32     SkTDPQueue(SkTDPQueue&&) = default;
33     SkTDPQueue& operator =(SkTDPQueue&&) = default;
34 
35     SkTDPQueue(const SkTDPQueue&) = delete;
36     SkTDPQueue& operator=(const SkTDPQueue&) = delete;
37 
38     /** Number of items in the queue. */
count()39     int count() const { return fArray.count(); }
40 
41     /** Gets the next item in the queue without popping it. */
peek()42     const T& peek() const { return fArray[0]; }
peek()43     T& peek() { return fArray[0]; }
44 
45     /** Removes the next item. */
pop()46     void pop() {
47         this->validate();
48         SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; })
49         if (1 == fArray.count()) {
50             fArray.pop();
51             return;
52         }
53 
54         fArray[0] = fArray[fArray.count() - 1];
55         this->setIndex(0);
56         fArray.pop();
57         this->percolateDownIfNecessary(0);
58 
59         this->validate();
60     }
61 
62     /** Inserts a new item in the queue based on its priority. */
insert(T entry)63     void insert(T entry) {
64         this->validate();
65         int index = fArray.count();
66         *fArray.append() = entry;
67         this->setIndex(fArray.count() - 1);
68         this->percolateUpIfNecessary(index);
69         this->validate();
70     }
71 
72     /** Random access removal. This requires that the INDEX function is non-nullptr. */
remove(T entry)73     void remove(T entry) {
74         SkASSERT(nullptr != INDEX);
75         int index = *INDEX(entry);
76         SkASSERT(index >= 0 && index < fArray.count());
77         this->validate();
78         SkDEBUGCODE(*INDEX(fArray[index]) = -1;)
79         if (index == fArray.count() - 1) {
80             fArray.pop();
81             return;
82         }
83         fArray[index] = fArray[fArray.count() - 1];
84         fArray.pop();
85         this->setIndex(index);
86         this->percolateUpOrDown(index);
87         this->validate();
88     }
89 
90     /** Notification that the priority of an entry has changed. This must be called after an
91         item's priority is changed to maintain correct ordering. Changing the priority is only
92         allowed if an INDEX function is provided. */
priorityDidChange(T entry)93     void priorityDidChange(T entry) {
94         SkASSERT(nullptr != INDEX);
95         int index = *INDEX(entry);
96         SkASSERT(index >= 0 && index < fArray.count());
97         this->validate(index);
98         this->percolateUpOrDown(index);
99         this->validate();
100     }
101 
102     /** Gets the item at index i in the priority queue (for i < this->count()). at(0) is equivalent
103         to peek(). Otherwise, there is no guarantee about ordering of elements in the queue. */
at(int i)104     T at(int i) const { return fArray[i]; }
105 
106     /** Sorts the queue into priority order.  The queue is only guarenteed to remain in sorted order
107      *  until any other operation, other than at(), is performed.
108      */
sort()109     void sort() {
110         if (fArray.count() > 1) {
111             SkTQSort<T>(fArray.begin(), fArray.end() - 1, LESS);
112             for (int i = 0; i < fArray.count(); i++) {
113                 this->setIndex(i);
114             }
115             this->validate();
116         }
117     }
118 
119 private:
LeftOf(int x)120     static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; }
ParentOf(int x)121     static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; }
122 
percolateUpOrDown(int index)123     void percolateUpOrDown(int index) {
124         SkASSERT(index >= 0);
125         if (!percolateUpIfNecessary(index)) {
126             this->validate(index);
127             this->percolateDownIfNecessary(index);
128         }
129     }
130 
percolateUpIfNecessary(int index)131     bool percolateUpIfNecessary(int index) {
132         SkASSERT(index >= 0);
133         bool percolated = false;
134         do {
135             if (0 == index) {
136                 this->setIndex(index);
137                 return percolated;
138             }
139             int p = ParentOf(index);
140             if (LESS(fArray[index], fArray[p])) {
141                 SkTSwap(fArray[index], fArray[p]);
142                 this->setIndex(index);
143                 index = p;
144                 percolated = true;
145             } else {
146                 this->setIndex(index);
147                 return percolated;
148             }
149             this->validate(index);
150         } while (true);
151     }
152 
percolateDownIfNecessary(int index)153     void percolateDownIfNecessary(int index) {
154         SkASSERT(index >= 0);
155         do {
156             int child = LeftOf(index);
157 
158             if (child >= fArray.count()) {
159                 // We're a leaf.
160                 this->setIndex(index);
161                 return;
162             }
163 
164             if (child + 1 >= fArray.count()) {
165                 // We only have a left child.
166                 if (LESS(fArray[child], fArray[index])) {
167                     SkTSwap(fArray[child], fArray[index]);
168                     this->setIndex(child);
169                     this->setIndex(index);
170                     return;
171                 }
172             } else if (LESS(fArray[child + 1], fArray[child])) {
173                 // The right child is the one we should swap with, if we swap.
174                 child++;
175             }
176 
177             // Check if we need to swap.
178             if (LESS(fArray[child], fArray[index])) {
179                 SkTSwap(fArray[child], fArray[index]);
180                 this->setIndex(index);
181                 index = child;
182             } else {
183                 // We're less than both our children.
184                 this->setIndex(index);
185                 return;
186             }
187             this->validate(index);
188         } while (true);
189     }
190 
setIndex(int index)191     void setIndex(int index) {
192         SkASSERT(index < fArray.count());
193         if (SkToBool(INDEX)) {
194             *INDEX(fArray[index]) = index;
195         }
196     }
197 
198     void validate(int excludedIndex = -1) const {
199 #ifdef SK_DEBUG
200         for (int i = 1; i < fArray.count(); ++i) {
201             int p = ParentOf(i);
202             if (excludedIndex != p && excludedIndex != i) {
203                 SkASSERT(!(LESS(fArray[i], fArray[p])));
204                 SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i);
205             }
206         }
207 #endif
208     }
209 
210     SkTDArray<T> fArray;
211 };
212 
213 #endif
214