llvm/ADT/PriorityQueue.h

0001 //===- llvm/ADT/PriorityQueue.h - Priority queues ---------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file defines the PriorityQueue class.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_PRIORITYQUEUE_H
0015 #define LLVM_ADT_PRIORITYQUEUE_H
0016
0017 #include <algorithm>
0018 #include <queue>
0019
0020 namespace llvm {
0021
0022 /// PriorityQueue - This class behaves like std::priority_queue and
0023 /// provides a few additional convenience functions.
0024 ///
0025 template<class T,
0026          class Sequence = std::vector<T>,
0027          class Compare = std::less<typename Sequence::value_type> >
0028 class PriorityQueue : public std::priority_queue<T, Sequence, Compare> {
0029 public:
0030   explicit PriorityQueue(const Compare &compare = Compare(),
0031                          const Sequence &sequence = Sequence())
0032     : std::priority_queue<T, Sequence, Compare>(compare, sequence)
0033   {}
0034
0035   template<class Iterator>
0036   PriorityQueue(Iterator begin, Iterator end,
0037                 const Compare &compare = Compare(),
0038                 const Sequence &sequence = Sequence())
0039     : std::priority_queue<T, Sequence, Compare>(begin, end, compare, sequence)
0040   {}
0041
0042   /// erase_one - Erase one element from the queue, regardless of its
0043   /// position. This operation performs a linear search to find an element
0044   /// equal to t, but then uses all logarithmic-time algorithms to do
0045   /// the erase operation.
0046   ///
0047   void erase_one(const T &t) {
0048     // Linear-search to find the element.
0049     typename Sequence::size_type i = find(this->c, t) - this->c.begin();
0050
0051     // Logarithmic-time heap bubble-up.
0052     while (i != 0) {
0053       typename Sequence::size_type parent = (i - 1) / 2;
0054       this->c[i] = this->c[parent];
0055       i = parent;
0056     }
0057
0058     // The element we want to remove is now at the root, so we can use
0059     // priority_queue's plain pop to remove it.
0060     this->pop();
0061   }
0062
0063   /// reheapify - If an element in the queue has changed in a way that
0064   /// affects its standing in the comparison function, the queue's
0065   /// internal state becomes invalid. Calling reheapify() resets the
0066   /// queue's state, making it valid again. This operation has time
0067   /// complexity proportional to the number of elements in the queue,
0068   /// so don't plan to use it a lot.
0069   ///
0070   void reheapify() {
0071     std::make_heap(this->c.begin(), this->c.end(), this->comp);
0072   }
0073
0074   /// clear - Erase all elements from the queue.
0075   ///
0076   void clear() {
0077     this->c.clear();
0078   }
0079 };
0080
0081 } // End llvm namespace
0082
0083 #endif