iOS/Pods/Realm/include/core/realm/util/priority_queue.hpp

   1 /*************************************************************************
   2  *
   3  * Copyright 2016 Realm Inc.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  **************************************************************************/
  18
  19
  20 #pragma once
  21 #ifndef REALM_UTIL_PRIORITY_QUEUE_HPP
  22 #define REALM_UTIL_PRIORITY_QUEUE_HPP
  23
  24 #include <vector>
  25 #include <functional>
  26 #include <algorithm>
  27
  28 namespace realm {
  29 namespace util {
  30
  31
  32 /// PriorityQueue corresponds exactly to `std::priority_queue`, but has the extra feature
  33 /// of allowing iteration and erasure of elements in the queue.
  34 ///
  35 /// PriorityQueue only allows const access to its elements, because non-const access
  36 /// would open up the risk of changing the ordering of the elements.
  37 ///
  38 /// Note: As opposed to `std::priority_queue`, this does not store elements in a heap
  39 /// internally. Instead, elements are stored in sorted order. Users of this class are
  40 /// allowed to operate on this assumption.
  41 template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
  42 class PriorityQueue : private Compare {
  43 public:
  44     using container_type = Container;
  45     using value_type = typename Container::value_type;
  46     using size_type = typename Container::size_type;
  47     using reference = typename Container::reference;
  48     using const_reference = typename Container::const_reference;
  49     using const_reverse_iterator = typename Container::const_reverse_iterator;
  50     using const_iterator = typename Container::const_iterator;
  51
  52     //@{
  53     /// Construct a PriorityQueue, optionally providing a comparator object.
  54     PriorityQueue(const Compare& comparator, const Container& cont);
  55
  56     explicit PriorityQueue(const Compare& comparator = Compare{}, Container&& cont = Container{});
  57
  58     template <class InputIt>
  59     PriorityQueue(InputIt first, InputIt last, const Compare& comparator, const Container& cont);
  60
  61     template <class InputIt>
  62     PriorityQueue(InputIt first, InputIt last, const Compare& comparator = Compare{}, Container&& cont = Container{});
  63     //@}
  64     // Skipping Allocator-specific template constructors.
  65
  66     PriorityQueue(const PriorityQueue&) = default;
  67     PriorityQueue(PriorityQueue&&) = default;
  68     PriorityQueue& operator=(const PriorityQueue&) = default;
  69     PriorityQueue& operator=(PriorityQueue&&) = default;
  70
  71     bool empty() const;
  72     size_type size() const;
  73
  74     //@{
  75     /// Push an element to the priority queue.
  76     ///
  77     /// If insertion to the underlying `Container` invalidates
  78     /// iterators and references, any iterators and references into this
  79     /// priority queue are also invalidated. By default, this is the case.
  80     void push(const T& value);
  81     void push(T&& value);
  82     //@}
  83
  84     /// Pop the largest element from the priority queue.
  85     ///
  86     /// If `pop_back` on the underlying `Container` invalidates
  87     /// iterators and references, any iterators and reference into this
  88     /// priority queue are also invalidated. By default, this is *NOT* the case.
  89     ///
  90     /// Calling `pop()` on an empty priority queue is undefined.
  91     void pop();
  92
  93     /// Return a reference to the largest element of the priority queue.
  94     ///
  95     /// Calling `top()` on an empty priority queue is undefined.
  96     const_reference top() const;
  97
  98     /// Pop the top of the queue and return it by moving it out of the queue.
  99     ///
 100     /// Note: This method does not exist in `std::priority_queue`.
 101     ///
 102     /// Calling `pop_top()` on an empty priorty queue is undefined.
 103     value_type pop_top();
 104
 105     // FIXME: emplace() deliberately omitted for simplicity.
 106
 107     /// Swap the contents of this priority queue with the contents of \a other.
 108     void swap(PriorityQueue& other);
 109
 110     // Not in std::priority_queue:
 111
 112     /// Return an iterator to the beginning of the queue (smallest element first).
 113     const_iterator begin() const;
 114
 115     /// Return an iterator to the end of the queue (largest element last);
 116     const_iterator end() const;
 117
 118     /// Return a reverse iterator into the priority queue (largest element first).
 119     const_reverse_iterator rbegin() const;
 120
 121     /// Return a reverse iterator representing the end of the priority queue (smallest element last).
 122     const_reverse_iterator rend() const;
 123
 124     /// Erase element pointed to by \a it.
 125     ///
 126     /// Note: This function differs from `std::priority_queue` by returning the erased
 127     /// element using move semantics.
 128     ///
 129     /// Calling `erase()` with a beyond-end iterator (such as what is returned by `end()`)
 130     /// is undefined.
 131     value_type erase(const_iterator it);
 132
 133     /// Remove all elements from the priority queue.
 134     void clear();
 135
 136     /// Calls `reserve()` on the underlying `Container`.
 137     void reserve(size_type);
 138
 139 private:
 140     Container m_queue;
 141
 142     const Compare& compare() const;
 143     Compare& compare();
 144 };
 145
 146
 147 /// Implementation
 148
 149 template <class T, class Container, class Compare>
 150 PriorityQueue<T, Container, Compare>::PriorityQueue(const Compare& comparator, const Container& cont)
 151     : Compare(comparator)
 152     , m_queue(cont)
 153 {
 154 }
 155
 156 template <class T, class Container, class Compare>
 157 PriorityQueue<T, Container, Compare>::PriorityQueue(const Compare& comparator, Container&& cont)
 158     : Compare(comparator)
 159     , m_queue(std::move(cont))
 160 {
 161 }
 162
 163 template <class T, class Container, class Compare>
 164 template <class InputIt>
 165 PriorityQueue<T, Container, Compare>::PriorityQueue(InputIt first, InputIt last, const Compare& comparator,
 166                                                     const Container& cont)
 167     : Compare(comparator)
 168     , m_queue(cont)
 169 {
 170     for (auto it = first; it != last; ++it) {
 171         push(*it);
 172     }
 173 }
 174
 175 template <class T, class Container, class Compare>
 176 template <class InputIt>
 177 PriorityQueue<T, Container, Compare>::PriorityQueue(InputIt first, InputIt last, const Compare& comparator,
 178                                                     Container&& cont)
 179     : Compare(comparator)
 180     , m_queue(std::move(cont))
 181 {
 182     for (auto it = first; it != last; ++it) {
 183         push(*it);
 184     }
 185 }
 186
 187 template <class T, class Container, class Compare>
 188 typename PriorityQueue<T, Container, Compare>::size_type PriorityQueue<T, Container, Compare>::size() const
 189 {
 190     return m_queue.size();
 191 }
 192
 193 template <class T, class Container, class Compare>
 194 bool PriorityQueue<T, Container, Compare>::empty() const
 195 {
 196     return m_queue.empty();
 197 }
 198
 199 template <class T, class Container, class Compare>
 200 void PriorityQueue<T, Container, Compare>::push(const T& element)
 201 {
 202     auto it = std::lower_bound(m_queue.begin(), m_queue.end(), element, compare());
 203     m_queue.insert(it, element);
 204 }
 205
 206 template <class T, class Container, class Compare>
 207 void PriorityQueue<T, Container, Compare>::push(T&& element)
 208 {
 209     auto it = std::lower_bound(m_queue.begin(), m_queue.end(), element, compare());
 210     m_queue.insert(it, std::move(element));
 211 }
 212
 213 template <class T, class Container, class Compare>
 214 void PriorityQueue<T, Container, Compare>::pop()
 215 {
 216     m_queue.pop_back();
 217 }
 218
 219 template <class T, class Container, class Compare>
 220 typename PriorityQueue<T, Container, Compare>::const_reference PriorityQueue<T, Container, Compare>::top() const
 221 {
 222     return m_queue.back();
 223 }
 224
 225 template <class T, class Container, class Compare>
 226 typename PriorityQueue<T, Container, Compare>::value_type PriorityQueue<T, Container, Compare>::pop_top()
 227 {
 228     value_type value = std::move(m_queue.back());
 229     m_queue.pop_back();
 230     return value;
 231 }
 232
 233 template <class T, class Container, class Compare>
 234 Compare& PriorityQueue<T, Container, Compare>::compare()
 235 {
 236     return *this;
 237 }
 238
 239 template <class T, class Container, class Compare>
 240 const Compare& PriorityQueue<T, Container, Compare>::compare() const
 241 {
 242     return *this;
 243 }
 244
 245 template <class T, class Container, class Compare>
 246 typename PriorityQueue<T, Container, Compare>::const_iterator PriorityQueue<T, Container, Compare>::begin() const
 247 {
 248     return m_queue.begin();
 249 }
 250
 251 template <class T, class Container, class Compare>
 252 typename PriorityQueue<T, Container, Compare>::const_iterator PriorityQueue<T, Container, Compare>::end() const
 253 {
 254     return m_queue.end();
 255 }
 256
 257 template <class T, class Container, class Compare>
 258 typename PriorityQueue<T, Container, Compare>::const_reverse_iterator
 259 PriorityQueue<T, Container, Compare>::rbegin() const
 260 {
 261     return m_queue.rbegin();
 262 }
 263
 264 template <class T, class Container, class Compare>
 265 typename PriorityQueue<T, Container, Compare>::const_reverse_iterator
 266 PriorityQueue<T, Container, Compare>::rend() const
 267 {
 268     return m_queue.rend();
 269 }
 270
 271 template <class T, class Container, class Compare>
 272 typename PriorityQueue<T, Container, Compare>::value_type
 273 PriorityQueue<T, Container, Compare>::erase(const_iterator it)
 274 {
 275     // Convert to non-const iterator:
 276     auto non_const_iterator = m_queue.begin() + (it - m_queue.begin());
 277     value_type value = std::move(*non_const_iterator);
 278     m_queue.erase(non_const_iterator);
 279     return value;
 280 }
 281
 282 template <class T, class Container, class Compare>
 283 void PriorityQueue<T, Container, Compare>::clear()
 284 {
 285     m_queue.clear();
 286 }
 287
 288 template <class T, class Container, class Compare>
 289 void PriorityQueue<T, Container, Compare>::reserve(size_type sz)
 290 {
 291     m_queue.reserve(sz);
 292 }
 293
 294 template <class T, class Container, class Compare>
 295 void PriorityQueue<T, Container, Compare>::swap(PriorityQueue& other)
 296 {
 297     using std::swap;
 298     swap(m_queue, other.m_queue);
 299     swap(compare(), other.compare());
 300 }
 301 }
 302 }
 303
 304 #endif // REALM_UTIL_PRIORITY_QUEUE_HPP