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 */
25template <typename T,
26          bool (*LESS)(const T&, const T&),
27          int* (*INDEX)(const T&) = (int* (*)(const T&))nullptr>
28class SkTDPQueue {
29public:
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. */
39    int count() const { return fArray.count(); }
40
41    /** Gets the next item in the queue without popping it. */
42    const T& peek() const { return fArray[0]; }
43    T& peek() { return fArray[0]; }
44
45    /** Removes the next item. */
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. */
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. */
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. */
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. */
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     */
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
119private:
120    static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; }
121    static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; }
122
123    void percolateUpOrDown(int index) {
124        SkASSERT(index >= 0);
125        if (!percolateUpIfNecessary(index)) {
126            this->validate(index);
127            this->percolateDownIfNecessary(index);
128        }
129    }
130
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
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
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