Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 1 | //===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===// |
| 2 | // |
||
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
||
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
||
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
||
| 6 | // |
||
| 7 | //===----------------------------------------------------------------------===// |
||
| 8 | /// |
||
| 9 | /// \file |
||
| 10 | /// This file defines the PriorityQueue class. |
||
| 11 | /// |
||
| 12 | //===----------------------------------------------------------------------===// |
||
| 13 | |||
| 14 | #ifndef LLVM_ADT_PRIORITYQUEUE_H |
||
| 15 | #define LLVM_ADT_PRIORITYQUEUE_H |
||
| 16 | |||
| 17 | #include <algorithm> |
||
| 18 | #include <queue> |
||
| 19 | |||
| 20 | namespace llvm { |
||
| 21 | |||
| 22 | /// PriorityQueue - This class behaves like std::priority_queue and |
||
| 23 | /// provides a few additional convenience functions. |
||
| 24 | /// |
||
| 25 | template<class T, |
||
| 26 | class Sequence = std::vector<T>, |
||
| 27 | class Compare = std::less<typename Sequence::value_type> > |
||
| 28 | class PriorityQueue : public std::priority_queue<T, Sequence, Compare> { |
||
| 29 | public: |
||
| 30 | explicit PriorityQueue(const Compare &compare = Compare(), |
||
| 31 | const Sequence &sequence = Sequence()) |
||
| 32 | : std::priority_queue<T, Sequence, Compare>(compare, sequence) |
||
| 33 | {} |
||
| 34 | |||
| 35 | template<class Iterator> |
||
| 36 | PriorityQueue(Iterator begin, Iterator end, |
||
| 37 | const Compare &compare = Compare(), |
||
| 38 | const Sequence &sequence = Sequence()) |
||
| 39 | : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence) |
||
| 40 | {} |
||
| 41 | |||
| 42 | /// erase_one - Erase one element from the queue, regardless of its |
||
| 43 | /// position. This operation performs a linear search to find an element |
||
| 44 | /// equal to t, but then uses all logarithmic-time algorithms to do |
||
| 45 | /// the erase operation. |
||
| 46 | /// |
||
| 47 | void erase_one(const T &t) { |
||
| 48 | // Linear-search to find the element. |
||
| 49 | typename Sequence::size_type i = find(this->c, t) - this->c.begin(); |
||
| 50 | |||
| 51 | // Logarithmic-time heap bubble-up. |
||
| 52 | while (i != 0) { |
||
| 53 | typename Sequence::size_type parent = (i - 1) / 2; |
||
| 54 | this->c[i] = this->c[parent]; |
||
| 55 | i = parent; |
||
| 56 | } |
||
| 57 | |||
| 58 | // The element we want to remove is now at the root, so we can use |
||
| 59 | // priority_queue's plain pop to remove it. |
||
| 60 | this->pop(); |
||
| 61 | } |
||
| 62 | |||
| 63 | /// reheapify - If an element in the queue has changed in a way that |
||
| 64 | /// affects its standing in the comparison function, the queue's |
||
| 65 | /// internal state becomes invalid. Calling reheapify() resets the |
||
| 66 | /// queue's state, making it valid again. This operation has time |
||
| 67 | /// complexity proportional to the number of elements in the queue, |
||
| 68 | /// so don't plan to use it a lot. |
||
| 69 | /// |
||
| 70 | void reheapify() { |
||
| 71 | std::make_heap(this->c.begin(), this->c.end(), this->comp); |
||
| 72 | } |
||
| 73 | |||
| 74 | /// clear - Erase all elements from the queue. |
||
| 75 | /// |
||
| 76 | void clear() { |
||
| 77 | this->c.clear(); |
||
| 78 | } |
||
| 79 | }; |
||
| 80 | |||
| 81 | } // End llvm namespace |
||
| 82 | |||
| 83 | #endif |