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