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
84