include/llvm/ADT/PriorityQueue.h

   1 //===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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 =
  50       std::find(this->c.begin(), this->c.end(), t) - this->c.begin();
  51
  52     // Logarithmic-time heap bubble-up.
  53     while (i != 0) {
  54       typename Sequence::size_type parent = (i - 1) / 2;
  55       this->c[i] = this->c[parent];
  56       i = parent;
  57     }
  58
  59     // The element we want to remove is now at the root, so we can use
  60     // priority_queue's plain pop to remove it.
  61     this->pop();
  62   }
  63
  64   /// reheapify - If an element in the queue has changed in a way that
  65   /// affects its standing in the comparison function, the queue's
  66   /// internal state becomes invalid. Calling reheapify() resets the
  67   /// queue's state, making it valid again. This operation has time
  68   /// complexity proportional to the number of elements in the queue,
  69   /// so don't plan to use it a lot.
  70   ///
  71   void reheapify() {
  72     std::make_heap(this->c.begin(), this->c.end(), this->comp);
  73   }
  74
  75   /// clear - Erase all elements from the queue.
  76   ///
  77   void clear() {
  78     this->c.clear();
  79   }
  80 };
  81
  82 } // End llvm namespace
  83
  84 #endif