include/llvm/ADT/PriorityQueue.h

   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