1193323Sed//===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===//
2193323Sed//
3193323Sed//                     The LLVM Compiler Infrastructure
4193323Sed//
5193323Sed// This file is distributed under the University of Illinois Open Source
6193323Sed// License. See LICENSE.TXT for details.
7193323Sed//
8193323Sed//===----------------------------------------------------------------------===//
9193323Sed//
10193323Sed// This file defines the PriorityQueue class.
11193323Sed//
12193323Sed//===----------------------------------------------------------------------===//
13193323Sed
14249423Sdim#ifndef LLVM_ADT_PRIORITYQUEUE_H
15249423Sdim#define LLVM_ADT_PRIORITYQUEUE_H
16193323Sed
17199481Srdivacky#include <algorithm>
18193323Sed#include <queue>
19193323Sed
20193323Sednamespace llvm {
21193323Sed
22193323Sed/// PriorityQueue - This class behaves like std::priority_queue and
23193323Sed/// provides a few additional convenience functions.
24193323Sed///
25193323Sedtemplate<class T,
26193323Sed         class Sequence = std::vector<T>,
27193323Sed         class Compare = std::less<typename Sequence::value_type> >
28193323Sedclass PriorityQueue : public std::priority_queue<T, Sequence, Compare> {
29193323Sedpublic:
30193323Sed  explicit PriorityQueue(const Compare &compare = Compare(),
31193323Sed                         const Sequence &sequence = Sequence())
32193323Sed    : std::priority_queue<T, Sequence, Compare>(compare, sequence)
33193323Sed  {}
34193323Sed
35193323Sed  template<class Iterator>
36193323Sed  PriorityQueue(Iterator begin, Iterator end,
37193323Sed                const Compare &compare = Compare(),
38193323Sed                const Sequence &sequence = Sequence())
39193323Sed    : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence)
40193323Sed  {}
41193323Sed
42193323Sed  /// erase_one - Erase one element from the queue, regardless of its
43193323Sed  /// position. This operation performs a linear search to find an element
44193323Sed  /// equal to t, but then uses all logarithmic-time algorithms to do
45193323Sed  /// the erase operation.
46193323Sed  ///
47193323Sed  void erase_one(const T &t) {
48193323Sed    // Linear-search to find the element.
49193323Sed    typename Sequence::size_type i =
50193323Sed      std::find(this->c.begin(), this->c.end(), t) - this->c.begin();
51193323Sed
52193323Sed    // Logarithmic-time heap bubble-up.
53193323Sed    while (i != 0) {
54193323Sed      typename Sequence::size_type parent = (i - 1) / 2;
55193323Sed      this->c[i] = this->c[parent];
56193323Sed      i = parent;
57193323Sed    }
58193323Sed
59193323Sed    // The element we want to remove is now at the root, so we can use
60193323Sed    // priority_queue's plain pop to remove it.
61193323Sed    this->pop();
62193323Sed  }
63193323Sed
64193323Sed  /// reheapify - If an element in the queue has changed in a way that
65193323Sed  /// affects its standing in the comparison function, the queue's
66193323Sed  /// internal state becomes invalid. Calling reheapify() resets the
67193323Sed  /// queue's state, making it valid again. This operation has time
68193323Sed  /// complexity proportional to the number of elements in the queue,
69193323Sed  /// so don't plan to use it a lot.
70193323Sed  ///
71193323Sed  void reheapify() {
72193323Sed    std::make_heap(this->c.begin(), this->c.end(), this->comp);
73193323Sed  }
74193323Sed
75193323Sed  /// clear - Erase all elements from the queue.
76193323Sed  ///
77193323Sed  void clear() {
78193323Sed    this->c.clear();
79193323Sed  }
80193323Sed};
81193323Sed
82193323Sed} // End llvm namespace
83193323Sed
84193323Sed#endif
85