diff options
Diffstat (limited to 'gfx/skia/skia/src/base/SkTDPQueue.h')
-rw-r--r-- | gfx/skia/skia/src/base/SkTDPQueue.h | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/gfx/skia/skia/src/base/SkTDPQueue.h b/gfx/skia/skia/src/base/SkTDPQueue.h new file mode 100644 index 0000000000..3a897130f2 --- /dev/null +++ b/gfx/skia/skia/src/base/SkTDPQueue.h @@ -0,0 +1,222 @@ +/* + * Copyright 2015 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkTDPQueue_DEFINED +#define SkTDPQueue_DEFINED + +#include "include/private/base/SkAssert.h" +#include "include/private/base/SkDebug.h" +#include "include/private/base/SkTDArray.h" +#include "include/private/base/SkTo.h" +#include "src/base/SkTSort.h" + +#include <utility> + +/** + * This class implements a priority queue. T is the type of the elements in the queue. LESS is a + * function that compares two Ts and returns true if the first is higher priority than the second. + * + * Optionally objects may know their index into the priority queue. The queue will update the index + * as the objects move through the queue. This is enabled by using a non-nullptr function for INDEX. + * When an INDEX function is provided random deletes from the queue are allowed using remove(). + * Additionally, the * priority is allowed to change as long as priorityDidChange() is called + * afterwards. In debug builds the index will be set to -1 before an element is removed from the + * queue. + */ +template <typename T, + bool (*LESS)(const T&, const T&), + int* (*INDEX)(const T&) = (int* (*)(const T&))nullptr> +class SkTDPQueue { +public: + SkTDPQueue() {} + SkTDPQueue(int reserve) { fArray.reserve(reserve); } + + SkTDPQueue(SkTDPQueue&&) = default; + SkTDPQueue& operator =(SkTDPQueue&&) = default; + + SkTDPQueue(const SkTDPQueue&) = delete; + SkTDPQueue& operator=(const SkTDPQueue&) = delete; + + /** Number of items in the queue. */ + int count() const { return fArray.size(); } + + /** Gets the next item in the queue without popping it. */ + const T& peek() const { return fArray[0]; } + T& peek() { return fArray[0]; } + + /** Removes the next item. */ + void pop() { + this->validate(); + SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; }) + if (1 == fArray.size()) { + fArray.pop_back(); + return; + } + + fArray[0] = fArray[fArray.size() - 1]; + this->setIndex(0); + fArray.pop_back(); + this->percolateDownIfNecessary(0); + + this->validate(); + } + + /** Inserts a new item in the queue based on its priority. */ + void insert(T entry) { + this->validate(); + int index = fArray.size(); + *fArray.append() = entry; + this->setIndex(fArray.size() - 1); + this->percolateUpIfNecessary(index); + this->validate(); + } + + /** Random access removal. This requires that the INDEX function is non-nullptr. */ + void remove(T entry) { + SkASSERT(nullptr != INDEX); + int index = *INDEX(entry); + SkASSERT(index >= 0 && index < fArray.size()); + this->validate(); + SkDEBUGCODE(*INDEX(fArray[index]) = -1;) + if (index == fArray.size() - 1) { + fArray.pop_back(); + return; + } + fArray[index] = fArray[fArray.size() - 1]; + fArray.pop_back(); + this->setIndex(index); + this->percolateUpOrDown(index); + this->validate(); + } + + /** Notification that the priority of an entry has changed. This must be called after an + item's priority is changed to maintain correct ordering. Changing the priority is only + allowed if an INDEX function is provided. */ + void priorityDidChange(T entry) { + SkASSERT(nullptr != INDEX); + int index = *INDEX(entry); + SkASSERT(index >= 0 && index < fArray.size()); + this->validate(index); + this->percolateUpOrDown(index); + this->validate(); + } + + /** Gets the item at index i in the priority queue (for i < this->count()). at(0) is equivalent + to peek(). Otherwise, there is no guarantee about ordering of elements in the queue. */ + T at(int i) const { return fArray[i]; } + + /** Sorts the queue into priority order. The queue is only guarenteed to remain in sorted order + * until any other operation, other than at(), is performed. + */ + void sort() { + if (fArray.size() > 1) { + SkTQSort<T>(fArray.begin(), fArray.end(), LESS); + for (int i = 0; i < fArray.size(); i++) { + this->setIndex(i); + } + this->validate(); + } + } + +private: + static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; } + static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; } + + void percolateUpOrDown(int index) { + SkASSERT(index >= 0); + if (!percolateUpIfNecessary(index)) { + this->validate(index); + this->percolateDownIfNecessary(index); + } + } + + bool percolateUpIfNecessary(int index) { + SkASSERT(index >= 0); + bool percolated = false; + do { + if (0 == index) { + this->setIndex(index); + return percolated; + } + int p = ParentOf(index); + if (LESS(fArray[index], fArray[p])) { + using std::swap; + swap(fArray[index], fArray[p]); + this->setIndex(index); + index = p; + percolated = true; + } else { + this->setIndex(index); + return percolated; + } + this->validate(index); + } while (true); + } + + void percolateDownIfNecessary(int index) { + SkASSERT(index >= 0); + do { + int child = LeftOf(index); + + if (child >= fArray.size()) { + // We're a leaf. + this->setIndex(index); + return; + } + + if (child + 1 >= fArray.size()) { + // We only have a left child. + if (LESS(fArray[child], fArray[index])) { + using std::swap; + swap(fArray[child], fArray[index]); + this->setIndex(child); + this->setIndex(index); + return; + } + } else if (LESS(fArray[child + 1], fArray[child])) { + // The right child is the one we should swap with, if we swap. + child++; + } + + // Check if we need to swap. + if (LESS(fArray[child], fArray[index])) { + using std::swap; + swap(fArray[child], fArray[index]); + this->setIndex(index); + index = child; + } else { + // We're less than both our children. + this->setIndex(index); + return; + } + this->validate(index); + } while (true); + } + + void setIndex(int index) { + SkASSERT(index < fArray.size()); + if (SkToBool(INDEX)) { + *INDEX(fArray[index]) = index; + } + } + + void validate(int excludedIndex = -1) const { +#ifdef SK_DEBUG + for (int i = 1; i < fArray.size(); ++i) { + int p = ParentOf(i); + if (excludedIndex != p && excludedIndex != i) { + SkASSERT(!(LESS(fArray[i], fArray[p]))); + SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i); + } + } +#endif + } + + SkTDArray<T> fArray; +}; + +#endif |