13555bd88a6513d219a084eabd41e9dff9e513605bsalomon/* 23555bd88a6513d219a084eabd41e9dff9e513605bsalomon * Copyright 2015 Google Inc. 33555bd88a6513d219a084eabd41e9dff9e513605bsalomon * 43555bd88a6513d219a084eabd41e9dff9e513605bsalomon * Use of this source code is governed by a BSD-style license that can be 53555bd88a6513d219a084eabd41e9dff9e513605bsalomon * found in the LICENSE file. 63555bd88a6513d219a084eabd41e9dff9e513605bsalomon */ 73555bd88a6513d219a084eabd41e9dff9e513605bsalomon 83555bd88a6513d219a084eabd41e9dff9e513605bsalomon#ifndef SkTDPQueue_DEFINED 93555bd88a6513d219a084eabd41e9dff9e513605bsalomon#define SkTDPQueue_DEFINED 103555bd88a6513d219a084eabd41e9dff9e513605bsalomon 113555bd88a6513d219a084eabd41e9dff9e513605bsalomon#include "SkTDArray.h" 125480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger#include "SkTSort.h" 133555bd88a6513d219a084eabd41e9dff9e513605bsalomon 143555bd88a6513d219a084eabd41e9dff9e513605bsalomon/** 153555bd88a6513d219a084eabd41e9dff9e513605bsalomon * This class implements a priority queue. T is the type of the elements in the queue. LESS is a 163555bd88a6513d219a084eabd41e9dff9e513605bsalomon * function that compares two Ts and returns true if the first is higher priority than the second. 173555bd88a6513d219a084eabd41e9dff9e513605bsalomon * 183555bd88a6513d219a084eabd41e9dff9e513605bsalomon * Optionally objects may know their index into the priority queue. The queue will update the index 1996fcdcc219d2a0d3579719b84b28bede76efba64halcanary * as the objects move through the queue. This is enabled by using a non-nullptr function for INDEX. 203555bd88a6513d219a084eabd41e9dff9e513605bsalomon * When an INDEX function is provided random deletes from the queue are allowed using remove(). 213555bd88a6513d219a084eabd41e9dff9e513605bsalomon * Additionally, the * priority is allowed to change as long as priorityDidChange() is called 223555bd88a6513d219a084eabd41e9dff9e513605bsalomon * afterwards. In debug builds the index will be set to -1 before an element is removed from the 233555bd88a6513d219a084eabd41e9dff9e513605bsalomon * queue. 243555bd88a6513d219a084eabd41e9dff9e513605bsalomon */ 253555bd88a6513d219a084eabd41e9dff9e513605bsalomontemplate <typename T, 263555bd88a6513d219a084eabd41e9dff9e513605bsalomon bool (*LESS)(const T&, const T&), 2796fcdcc219d2a0d3579719b84b28bede76efba64halcanary int* (*INDEX)(const T&) = (int* (*)(const T&))nullptr> 28bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Kleinclass SkTDPQueue { 293555bd88a6513d219a084eabd41e9dff9e513605bsalomonpublic: 303555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTDPQueue() {} 313555bd88a6513d219a084eabd41e9dff9e513605bsalomon 32bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Klein SkTDPQueue(SkTDPQueue&&) = default; 33bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Klein SkTDPQueue& operator =(SkTDPQueue&&) = default; 34bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Klein 35bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Klein SkTDPQueue(const SkTDPQueue&) = delete; 36bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Klein SkTDPQueue& operator=(const SkTDPQueue&) = delete; 37bc4c96bc65ab6ee0acc62d5d8a6613156991ac6cMike Klein 383555bd88a6513d219a084eabd41e9dff9e513605bsalomon /** Number of items in the queue. */ 393555bd88a6513d219a084eabd41e9dff9e513605bsalomon int count() const { return fArray.count(); } 403555bd88a6513d219a084eabd41e9dff9e513605bsalomon 413555bd88a6513d219a084eabd41e9dff9e513605bsalomon /** Gets the next item in the queue without popping it. */ 423555bd88a6513d219a084eabd41e9dff9e513605bsalomon const T& peek() const { return fArray[0]; } 433555bd88a6513d219a084eabd41e9dff9e513605bsalomon T& peek() { return fArray[0]; } 449d524f22bfde5dc3dc8f48e1be39bdebd3bb0304halcanary 453555bd88a6513d219a084eabd41e9dff9e513605bsalomon /** Removes the next item. */ 463555bd88a6513d219a084eabd41e9dff9e513605bsalomon void pop() { 473555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 483555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkDEBUGCODE(if (SkToBool(INDEX)) { *INDEX(fArray[0]) = -1; }) 493555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (1 == fArray.count()) { 503555bd88a6513d219a084eabd41e9dff9e513605bsalomon fArray.pop(); 513555bd88a6513d219a084eabd41e9dff9e513605bsalomon return; 523555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 533555bd88a6513d219a084eabd41e9dff9e513605bsalomon 543555bd88a6513d219a084eabd41e9dff9e513605bsalomon fArray[0] = fArray[fArray.count() - 1]; 553555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(0); 563555bd88a6513d219a084eabd41e9dff9e513605bsalomon fArray.pop(); 573555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->percolateDownIfNecessary(0); 583555bd88a6513d219a084eabd41e9dff9e513605bsalomon 593555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 603555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 613555bd88a6513d219a084eabd41e9dff9e513605bsalomon 623555bd88a6513d219a084eabd41e9dff9e513605bsalomon /** Inserts a new item in the queue based on its priority. */ 633555bd88a6513d219a084eabd41e9dff9e513605bsalomon void insert(T entry) { 643555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 653555bd88a6513d219a084eabd41e9dff9e513605bsalomon int index = fArray.count(); 663555bd88a6513d219a084eabd41e9dff9e513605bsalomon *fArray.append() = entry; 673555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(fArray.count() - 1); 683555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->percolateUpIfNecessary(index); 693555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 703555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 713555bd88a6513d219a084eabd41e9dff9e513605bsalomon 7296fcdcc219d2a0d3579719b84b28bede76efba64halcanary /** Random access removal. This requires that the INDEX function is non-nullptr. */ 733555bd88a6513d219a084eabd41e9dff9e513605bsalomon void remove(T entry) { 7496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr != INDEX); 753555bd88a6513d219a084eabd41e9dff9e513605bsalomon int index = *INDEX(entry); 763555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(index >= 0 && index < fArray.count()); 773555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 783555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkDEBUGCODE(*INDEX(fArray[index]) = -1;) 793555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (index == fArray.count() - 1) { 803555bd88a6513d219a084eabd41e9dff9e513605bsalomon fArray.pop(); 813555bd88a6513d219a084eabd41e9dff9e513605bsalomon return; 823555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 833555bd88a6513d219a084eabd41e9dff9e513605bsalomon fArray[index] = fArray[fArray.count() - 1]; 843555bd88a6513d219a084eabd41e9dff9e513605bsalomon fArray.pop(); 853555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 863555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->percolateUpOrDown(index); 873555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 883555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 893555bd88a6513d219a084eabd41e9dff9e513605bsalomon 903555bd88a6513d219a084eabd41e9dff9e513605bsalomon /** Notification that the priority of an entry has changed. This must be called after an 913555bd88a6513d219a084eabd41e9dff9e513605bsalomon item's priority is changed to maintain correct ordering. Changing the priority is only 923555bd88a6513d219a084eabd41e9dff9e513605bsalomon allowed if an INDEX function is provided. */ 933555bd88a6513d219a084eabd41e9dff9e513605bsalomon void priorityDidChange(T entry) { 9496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr != INDEX); 953555bd88a6513d219a084eabd41e9dff9e513605bsalomon int index = *INDEX(entry); 963555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(index >= 0 && index < fArray.count()); 973555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(index); 983555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->percolateUpOrDown(index); 993555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(); 1003555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1013555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1021a9600f2537ad62e85529801a634167f2913bc24bsalomon /** Gets the item at index i in the priority queue (for i < this->count()). at(0) is equivalent 1031a9600f2537ad62e85529801a634167f2913bc24bsalomon to peek(). Otherwise, there is no guarantee about ordering of elements in the queue. */ 1049f2d1571ed1f0ed579e5d7779c46a90e20f30f22bsalomon T at(int i) const { return fArray[i]; } 1059f2d1571ed1f0ed579e5d7779c46a90e20f30f22bsalomon 1065480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger /** Sorts the queue into priority order. The queue is only guarenteed to remain in sorted order 1075480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger * until any other operation, other than at(), is performed. 1085480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger */ 1095480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger void sort() { 1105480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger if (fArray.count() > 1) { 1115480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger SkTQSort<T>(fArray.begin(), fArray.end() - 1, LESS); 1125480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger for (int i = 0; i < fArray.count(); i++) { 1135480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger this->setIndex(i); 1145480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1155480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger this->validate(); 1165480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1175480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger } 1185480a18d8799511034d0da219c72932cd8f25274Derek Sollenberger 1193555bd88a6513d219a084eabd41e9dff9e513605bsalomonprivate: 1203555bd88a6513d219a084eabd41e9dff9e513605bsalomon static int LeftOf(int x) { SkASSERT(x >= 0); return 2 * x + 1; } 1213555bd88a6513d219a084eabd41e9dff9e513605bsalomon static int ParentOf(int x) { SkASSERT(x > 0); return (x - 1) >> 1; } 1223555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1233555bd88a6513d219a084eabd41e9dff9e513605bsalomon void percolateUpOrDown(int index) { 1243555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(index >= 0); 1253555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (!percolateUpIfNecessary(index)) { 1263555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(index); 1273555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->percolateDownIfNecessary(index); 1283555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1293555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1303555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1313555bd88a6513d219a084eabd41e9dff9e513605bsalomon bool percolateUpIfNecessary(int index) { 1323555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(index >= 0); 1333555bd88a6513d219a084eabd41e9dff9e513605bsalomon bool percolated = false; 1343555bd88a6513d219a084eabd41e9dff9e513605bsalomon do { 1353555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (0 == index) { 1363555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1373555bd88a6513d219a084eabd41e9dff9e513605bsalomon return percolated; 1383555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1393555bd88a6513d219a084eabd41e9dff9e513605bsalomon int p = ParentOf(index); 1403555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (LESS(fArray[index], fArray[p])) { 1413555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTSwap(fArray[index], fArray[p]); 1423555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1433555bd88a6513d219a084eabd41e9dff9e513605bsalomon index = p; 1443555bd88a6513d219a084eabd41e9dff9e513605bsalomon percolated = true; 1453555bd88a6513d219a084eabd41e9dff9e513605bsalomon } else { 1463555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1473555bd88a6513d219a084eabd41e9dff9e513605bsalomon return percolated; 1483555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1493555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(index); 1503555bd88a6513d219a084eabd41e9dff9e513605bsalomon } while (true); 1513555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1523555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1533555bd88a6513d219a084eabd41e9dff9e513605bsalomon void percolateDownIfNecessary(int index) { 1543555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(index >= 0); 1553555bd88a6513d219a084eabd41e9dff9e513605bsalomon do { 1563555bd88a6513d219a084eabd41e9dff9e513605bsalomon int child = LeftOf(index); 1579d524f22bfde5dc3dc8f48e1be39bdebd3bb0304halcanary 1583555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (child >= fArray.count()) { 1593555bd88a6513d219a084eabd41e9dff9e513605bsalomon // We're a leaf. 1603555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1613555bd88a6513d219a084eabd41e9dff9e513605bsalomon return; 1623555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1633555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1643555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (child + 1 >= fArray.count()) { 1653555bd88a6513d219a084eabd41e9dff9e513605bsalomon // We only have a left child. 1663555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (LESS(fArray[child], fArray[index])) { 1673555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTSwap(fArray[child], fArray[index]); 1683555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(child); 1693555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1703555bd88a6513d219a084eabd41e9dff9e513605bsalomon return; 1713555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1723555bd88a6513d219a084eabd41e9dff9e513605bsalomon } else if (LESS(fArray[child + 1], fArray[child])) { 1733555bd88a6513d219a084eabd41e9dff9e513605bsalomon // The right child is the one we should swap with, if we swap. 1743555bd88a6513d219a084eabd41e9dff9e513605bsalomon child++; 1753555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1763555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1773555bd88a6513d219a084eabd41e9dff9e513605bsalomon // Check if we need to swap. 1783555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (LESS(fArray[child], fArray[index])) { 1793555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTSwap(fArray[child], fArray[index]); 1803555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1813555bd88a6513d219a084eabd41e9dff9e513605bsalomon index = child; 1823555bd88a6513d219a084eabd41e9dff9e513605bsalomon } else { 1833555bd88a6513d219a084eabd41e9dff9e513605bsalomon // We're less than both our children. 1843555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->setIndex(index); 1853555bd88a6513d219a084eabd41e9dff9e513605bsalomon return; 1863555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1873555bd88a6513d219a084eabd41e9dff9e513605bsalomon this->validate(index); 1883555bd88a6513d219a084eabd41e9dff9e513605bsalomon } while (true); 1893555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1903555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1913555bd88a6513d219a084eabd41e9dff9e513605bsalomon void setIndex(int index) { 1923555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(index < fArray.count()); 1933555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (SkToBool(INDEX)) { 1943555bd88a6513d219a084eabd41e9dff9e513605bsalomon *INDEX(fArray[index]) = index; 1953555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1963555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 1973555bd88a6513d219a084eabd41e9dff9e513605bsalomon 1983555bd88a6513d219a084eabd41e9dff9e513605bsalomon void validate(int excludedIndex = -1) const { 1993555bd88a6513d219a084eabd41e9dff9e513605bsalomon#ifdef SK_DEBUG 2003555bd88a6513d219a084eabd41e9dff9e513605bsalomon for (int i = 1; i < fArray.count(); ++i) { 2013555bd88a6513d219a084eabd41e9dff9e513605bsalomon int p = ParentOf(i); 2023555bd88a6513d219a084eabd41e9dff9e513605bsalomon if (excludedIndex != p && excludedIndex != i) { 2033555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(!(LESS(fArray[i], fArray[p]))); 2043555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkASSERT(!SkToBool(INDEX) || *INDEX(fArray[i]) == i); 2053555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 2063555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 2073555bd88a6513d219a084eabd41e9dff9e513605bsalomon#endif 2083555bd88a6513d219a084eabd41e9dff9e513605bsalomon } 2093555bd88a6513d219a084eabd41e9dff9e513605bsalomon 2103555bd88a6513d219a084eabd41e9dff9e513605bsalomon SkTDArray<T> fArray; 2113555bd88a6513d219a084eabd41e9dff9e513605bsalomon}; 2123555bd88a6513d219a084eabd41e9dff9e513605bsalomon 2133555bd88a6513d219a084eabd41e9dff9e513605bsalomon#endif 214