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