26 // A simple priority queue. The order of values is by priority and then FIFO.
28 // from the queue, and all operations are O(p) time for p priority levels.
29 // The queue is agnostic to priority ordering (whether 0 precedes 1).
30 // If the highest priority is 0, FirstMin() returns the first in order.
46   typedef uint32_t Priority;  typedef
84     Priority priority() const { return priority_; }  in priority()  function
110     static const Priority kNullPriority = static_cast<Priority>(-1);
114     Pointer(Priority priority, const ListIterator& iterator)  in Pointer()  argument
115         : priority_(priority), iterator_(iterator) {  in Pointer()
121     Priority priority_;
135   explicit PriorityQueue(Priority num_priorities) : lists_(num_priorities) {  in PriorityQueue()
145   // Adds |value| with |priority| to the queue. Returns a pointer to the
147   Pointer Insert(T value, Priority priority) {  in Insert()  argument
149     DCHECK_LT(priority, lists_.size());  in Insert()
151     List& list = lists_[priority];  in Insert()
160     return Pointer(priority, std::prev(list.end()));  in Insert()
163   // Adds |value| with |priority| to the queue. Returns a pointer to the
165   Pointer InsertAtFront(T value, Priority priority) {  in InsertAtFront()  argument
167     DCHECK_LT(priority, lists_.size());  in InsertAtFront()
169     List& list = lists_[priority];  in InsertAtFront()
178     return Pointer(priority, list.begin());  in InsertAtFront()
201   // Returns a pointer to the first value of minimum priority or a null-pointer
213   // Returns a pointer to the last value of minimum priority or a null-pointer
225   // Returns a pointer to the first value of maximum priority or a null-pointer
238   // Returns a pointer to the last value of maximum priority or a null-pointer
251   // Given an ordering of the values in this queue by decreasing priority and
254   // priority, then FIFO order. If the given pointer is already pointing at the
257   // (One could also implement GetNextTowardsFirstMin() [decreasing priority,
259   // priority, then {,reverse} FIFO].)
266     Priority priority = pointer.priority_;  in GetNextTowardsLastMin()  local
267     DCHECK(it != lists_[priority].end());  in GetNextTowardsLastMin()
269     while (it == lists_[priority].end()) {  in GetNextTowardsLastMin()
270       if (priority == 0u) {  in GetNextTowardsLastMin()
274       --priority;  in GetNextTowardsLastMin()
275       it = const_cast<List*>(&lists_[priority])->begin();  in GetNextTowardsLastMin()
277     return Pointer(priority, it);  in GetNextTowardsLastMin()
280   // Given an ordering of the values in this queue by decreasing priority and
283   // priority, then reverse FIFO order. If the given pointer is already pointing
291     Priority priority = pointer.priority_;  in GetPreviousTowardsFirstMax()  local
292     DCHECK(it != lists_[priority].end());  in GetPreviousTowardsFirstMax()
293     while (it == lists_[priority].begin()) {  in GetPreviousTowardsFirstMax()
294       if (priority == num_priorities() - 1) {  in GetPreviousTowardsFirstMax()
298       ++priority;  in GetPreviousTowardsFirstMax()
299       it = const_cast<List*>(&lists_[priority])->end();  in GetPreviousTowardsFirstMax()
301     return Pointer(priority, std::prev(it));  in GetPreviousTowardsFirstMax()
326   // Finds the first element (with respect to decreasing priority, then FIFO