LLVM  10.0.0svn
PriorityQueue.h
Go to the documentation of this file.
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  ///
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  ///
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  ///
75  void clear() {
76  this->c.clear();
77  }
78 };
79 
80 } // End llvm namespace
81 
82 #endif
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Definition: BitVector.h:937
void reheapify()
reheapify - If an element in the queue has changed in a way that affects its standing in the comparis...
Definition: PriorityQueue.h:69
void erase_one(const T &t)
erase_one - Erase one element from the queue, regardless of its position.
Definition: PriorityQueue.h:46
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1198
PriorityQueue(Iterator begin, Iterator end, const Compare &compare=Compare(), const Sequence &sequence=Sequence())
Definition: PriorityQueue.h:35
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:40
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:251
void clear()
clear - Erase all elements from the queue.
Definition: PriorityQueue.h:75
PriorityQueue(const Compare &compare=Compare(), const Sequence &sequence=Sequence())
Definition: PriorityQueue.h:29
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
Definition: PriorityQueue.h:27