| //===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// This file defines the PriorityQueue class. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_ADT_PRIORITYQUEUE_H |
| #define LLVM_ADT_PRIORITYQUEUE_H |
| |
| #include <algorithm> |
| #include <queue> |
| |
| namespace llvm { |
| |
| /// PriorityQueue - This class behaves like std::priority_queue and |
| /// provides a few additional convenience functions. |
| /// |
| template<class T, |
| class Sequence = std::vector<T>, |
| class Compare = std::less<typename Sequence::value_type> > |
| class PriorityQueue : public std::priority_queue<T, Sequence, Compare> { |
| public: |
| explicit PriorityQueue(const Compare &compare = Compare(), |
| const Sequence &sequence = Sequence()) |
| : std::priority_queue<T, Sequence, Compare>(compare, sequence) |
| {} |
| |
| template<class Iterator> |
| PriorityQueue(Iterator begin, Iterator end, |
| const Compare &compare = Compare(), |
| const Sequence &sequence = Sequence()) |
| : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence) |
| {} |
| |
| /// erase_one - Erase one element from the queue, regardless of its |
| /// position. This operation performs a linear search to find an element |
| /// equal to t, but then uses all logarithmic-time algorithms to do |
| /// the erase operation. |
| /// |
| void erase_one(const T &t) { |
| // Linear-search to find the element. |
| typename Sequence::size_type i = find(this->c, t) - this->c.begin(); |
| |
| // Logarithmic-time heap bubble-up. |
| while (i != 0) { |
| typename Sequence::size_type parent = (i - 1) / 2; |
| this->c[i] = this->c[parent]; |
| i = parent; |
| } |
| |
| // The element we want to remove is now at the root, so we can use |
| // priority_queue's plain pop to remove it. |
| this->pop(); |
| } |
| |
| /// reheapify - If an element in the queue has changed in a way that |
| /// affects its standing in the comparison function, the queue's |
| /// internal state becomes invalid. Calling reheapify() resets the |
| /// queue's state, making it valid again. This operation has time |
| /// complexity proportional to the number of elements in the queue, |
| /// so don't plan to use it a lot. |
| /// |
| void reheapify() { |
| std::make_heap(this->c.begin(), this->c.end(), this->comp); |
| } |
| |
| /// clear - Erase all elements from the queue. |
| /// |
| void clear() { |
| this->c.clear(); |
| } |
| }; |
| |
| } // End llvm namespace |
| |
| #endif |