Line data    Source code

       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        3321 : class PriorityQueue : public std::priority_queue<T, Sequence, Compare> {
      29             : public:
      30       22202 :   explicit PriorityQueue(const Compare &compare = Compare(),
      31             :                          const Sequence &sequence = Sequence())
      32       22196 :     : std::priority_queue<T, Sequence, Compare>(compare, sequence)
      33           0 :   {}
      34           0 : 
      35             :   template<class Iterator>
      36           0 :   PriorityQueue(Iterator begin, Iterator end,
      37           0 :                 const Compare &compare = Compare(),
      38           0 :                 const Sequence &sequence = Sequence())
      39             :     : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence)
      40           0 :   {}
      41           0 : 
      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