1 /* Copyright (c) 2014, 2019, Oracle and/or its affiliates. All rights reserved. 2 3 This program is free software; you can redistribute it and/or modify 4 it under the terms of the GNU General Public License, version 2.0, 5 as published by the Free Software Foundation. 6 7 This program is also distributed with certain software (including 8 but not limited to OpenSSL) that is licensed under separate terms, 9 as designated in a particular file or component or in included license 10 documentation. The authors of MySQL hereby grant you an additional 11 permission to link the program and your derivative works with the 12 separately licensed software that they have included with MySQL. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License, version 2.0, for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program; if not, write to the Free Software 21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ 22 23 #ifndef PRIORITY_QUEUE_INCLUDED 24 #define PRIORITY_QUEUE_INCLUDED 25 26 /** 27 @file include/priority_queue.h 28 */ 29 30 #include <functional> 31 #include <new> 32 #include <utility> 33 #include <vector> 34 35 #include "my_compiler.h" 36 #include "my_dbug.h" 37 #include "template_utils.h" 38 39 #if defined(EXTRA_CODE_FOR_UNIT_TESTING) 40 #include <iostream> 41 #include <sstream> 42 #endif 43 44 namespace priority_queue_unittest { 45 class PriorityQueueTest; 46 } // namespace priority_queue_unittest 47 48 /** 49 Implements a priority queue using a vector-based max-heap. 50 51 A priority queue is a container specifically designed such that its first 52 element is always the greatest of the elements it contains, according to 53 some strict weak ordering criterion. 54 55 For object locality, the implementation is vector-based, rather than 56 node-based. 57 58 The priority queue is mutable, which means that the priority of an element 59 can be changed. See increase/decrease/update member functions. 60 The typical use case is to change the value/priority of the root node. 61 62 We provide iterators, which can be used to visit all elements. 63 Iterators do not visit queue elements in priority order. 64 Iterators should not be used to change the priority of elements. 65 66 The underlying container must be 67 constructible from an iterator range, should provide const and 68 non-const random access iterators to access its elements, as well as 69 the following operations: 70 - size() 71 - empty() 72 - push_back() 73 - pop_back() 74 - swap() 75 - clear() 76 - capacity() 77 - reserve() 78 - max_size() 79 80 @tparam T Type of the elements of the priority queue. 81 @tparam Container Type of the underlying container object where elements 82 are stored. Its value_type shall be T. 83 @tparam Less A binary predicate that takes two elements (of type T) 84 and returns a bool. The expression less(a,b), where 85 less is an object of this type and a and b are elements 86 in the container, shall return true if a is considered 87 to go before b in the strict weak ordering the 88 function defines. 89 */ 90 template <typename T, typename Container = std::vector<T>, 91 typename Less = std::less<typename Container::value_type>> 92 class Priority_queue : public Less { 93 public: 94 typedef Container container_type; 95 typedef Less less_type; 96 typedef typename container_type::value_type value_type; 97 typedef typename container_type::size_type size_type; 98 typedef typename container_type::iterator iterator; 99 typedef typename container_type::const_iterator const_iterator; 100 typedef typename container_type::allocator_type allocator_type; 101 102 friend class priority_queue_unittest::PriorityQueueTest; 103 104 private: 105 // Deriving from Less allows empty base-class optimization in some cases. 106 typedef Less Base; 107 108 // Returns the index of the parent node of node i. parent(size_type i)109 static size_type parent(size_type i) { 110 DBUG_ASSERT(i != 0); 111 return (--i) >> 1; // (i - 1) / 2 112 } 113 114 // Returns the index of the left child of node i. left(size_type i)115 static size_type left(size_type i) { 116 return (i << 1) | 1; // 2 * i + 1 117 } 118 119 // Returns the index of the right child of node i. right(size_type i)120 static size_type right(size_type i) { 121 return (++i) << 1; // 2 * i + 2 122 } 123 heapify(size_type i,size_type last)124 void heapify(size_type i, size_type last) { 125 DBUG_ASSERT(i < size()); 126 size_type largest = i; 127 128 do { 129 i = largest; 130 size_type l = left(i); 131 size_type r = right(i); 132 133 if (l < last && Base::operator()(m_container[i], m_container[l])) { 134 largest = l; 135 } 136 137 if (r < last && Base::operator()(m_container[largest], m_container[r])) { 138 largest = r; 139 } 140 141 if (largest != i) { 142 std::swap(m_container[i], m_container[largest]); 143 } 144 } while (largest != i); 145 } 146 heapify(size_type i)147 void heapify(size_type i) { heapify(i, m_container.size()); } 148 reverse_heapify(size_type i)149 void reverse_heapify(size_type i) { 150 DBUG_ASSERT(i < size()); 151 while (i > 0 && !Base::operator()(m_container[i], m_container[parent(i)])) { 152 std::swap(m_container[parent(i)], m_container[i]); 153 i = parent(i); 154 } 155 } 156 157 // Sets the value of element i, and rebuilds the priority queue. decrease_key(size_type i,value_type const & x)158 void decrease_key(size_type i, value_type const &x) { 159 m_container[i] = x; 160 heapify(i); 161 } 162 163 // Sets the value of element i, and rebuilds the priority queue. increase_key(size_type i,value_type const & x)164 void increase_key(size_type i, value_type const &x) { 165 m_container[i] = x; 166 reverse_heapify(i); 167 } 168 169 public: 170 /// Constructs an empty priority queue. 171 Priority_queue(Less const &less = Less(), 172 const allocator_type &alloc = allocator_type()) Base(less)173 : Base(less), m_container(alloc) {} 174 175 /// Constructs a heap of the objects between first and beyond. 176 template <typename Input_iterator> 177 Priority_queue(Input_iterator first, Input_iterator beyond, 178 Less const &less = Less(), 179 const allocator_type &alloc = allocator_type()) Base(less)180 : Base(less), m_container(first, beyond, alloc) { 181 build_heap(); 182 } 183 184 /// Constructs a heap based on input argument. assign(const container_type & container)185 void assign(const container_type &container) { 186 m_container = container; 187 build_heap(); 188 } 189 190 /** 191 Constructs a heap based on container contents. 192 Can also be used when many elements have changed. 193 */ build_heap()194 void build_heap() { 195 if (m_container.size() > 1) { 196 for (size_type i = parent(m_container.size() - 1); i > 0; --i) { 197 heapify(i); 198 } 199 heapify(0); 200 } 201 } 202 203 /// Returns a const reference to the top element of the priority queue. top()204 value_type const &top() const { 205 DBUG_ASSERT(!empty()); 206 return m_container[0]; 207 } 208 209 /// Returns a reference to the top element of the priority queue. top()210 value_type &top() { 211 DBUG_ASSERT(!empty()); 212 return m_container[0]; 213 } 214 215 /** 216 Inserts an element in the priority queue. 217 218 @param x value to be pushed. 219 @retval true if out-of-memory, false otherwise. 220 */ push(value_type const & x)221 bool push(value_type const &x) { 222 try { 223 m_container.push_back(x); 224 } catch (std::bad_alloc const &) { 225 return true; 226 } 227 228 reverse_heapify(m_container.size() - 1); 229 return false; 230 } 231 232 /// Pops the top-most element in the priority queue. pop()233 void pop() { remove(0); } 234 235 /// Removes the element at position i from the priority queue. remove(size_type i)236 void remove(size_type i) { 237 DBUG_ASSERT(i < size()); 238 239 if (i == m_container.size() - 1) { 240 m_container.pop_back(); 241 return; 242 } 243 244 m_container[i] = m_container[m_container.size() - 1]; 245 m_container.pop_back(); 246 update(i); 247 } 248 249 /** 250 Decreases the priority of the element at position i, where the 251 new priority is x. 252 */ decrease(size_type i,value_type const & x)253 void decrease(size_type i, value_type const &x) { 254 DBUG_ASSERT(i < size()); 255 DBUG_ASSERT(!Base::operator()(m_container[i], x)); 256 decrease_key(i, x); 257 } 258 259 /** 260 Increases the priority of the element at position i, where the 261 new priority is x. 262 */ increase(size_type i,value_type const & x)263 void increase(size_type i, value_type const &x) { 264 DBUG_ASSERT(i < size()); 265 DBUG_ASSERT(!Base::operator()(x, m_container[i])); 266 increase_key(i, x); 267 } 268 269 /** 270 Changes the priority of the element at position i, where the 271 new priority is x. 272 */ update(size_type i,value_type const & x)273 void update(size_type i, value_type const &x) { 274 DBUG_ASSERT(i < size()); 275 if (Base::operator()(x, m_container[i])) { 276 decrease_key(i, x); 277 } else { 278 increase_key(i, x); 279 } 280 } 281 282 /** 283 Assumes that the i-th element's value has increased 284 and rebuilds the priority queue. 285 */ increase(size_type i)286 void increase(size_type i) { reverse_heapify(i); } 287 288 /** 289 Assumes that the i-th element's value has decreased 290 and rebuilds the priority queue. 291 */ decrease(size_type i)292 void decrease(size_type i) { heapify(i); } 293 294 /** 295 Assumes that the i-th element's value has changed 296 and rebuilds the priority queue. 297 */ update(size_type i)298 void update(size_type i) { 299 DBUG_ASSERT(i < size()); 300 if (i == 0 || Base::operator()(m_container[i], m_container[parent(i)])) { 301 heapify(i); 302 } else { 303 reverse_heapify(i); 304 } 305 } 306 307 /** 308 Assumes that the top element's value has changed 309 and rebuilds the priority queue. 310 */ update_top()311 void update_top() { 312 DBUG_ASSERT(!empty()); 313 heapify(0); 314 } 315 316 /// Returns the number of elements of the priority queue size()317 size_type size() const { return m_container.size(); } 318 319 /// Returns true if the priority queue is empty empty()320 bool empty() const { return m_container.empty(); } 321 322 /// Returns a const reference to the i-th element in the underlying container. 323 value_type const &operator[](size_type i) const { 324 DBUG_ASSERT(i < size()); 325 return m_container[i]; 326 } 327 328 /// Returns a reference to the i-th element in the underlying container. 329 value_type &operator[](size_type i) { 330 DBUG_ASSERT(i < size()); 331 return m_container[i]; 332 } 333 334 /// Returns a const iterator to the first element of the underlying container. begin()335 const_iterator begin() const { return m_container.begin(); } 336 337 /// Returns a const iterator to the end element of the underlying container. end()338 const_iterator end() const { return m_container.end(); } 339 340 /// Returns an iterator to the first element of the underlying container. begin()341 iterator begin() { return m_container.begin(); } 342 343 /// Returns an iterator to the end element of the underlying container. end()344 iterator end() { return m_container.end(); } 345 346 /// Swaps the contents of two priority queues. swap(Priority_queue & other)347 void swap(Priority_queue &other) { 348 std::swap(static_cast<Base &>(*this), static_cast<Base &>(other)); 349 m_container.swap(other.m_container); 350 } 351 352 /// Returns true if the priority queue has the heap property. is_valid()353 bool is_valid() const { 354 for (size_type i = 1; i < m_container.size(); ++i) { 355 if (Base::operator()(m_container[parent(i)], m_container[i])) { 356 return false; 357 } 358 } 359 return true; 360 } 361 362 /** 363 Sorts the elements of the priority queue according to the strict 364 partial ordering defined by the object of type Less passed to 365 the priority queue. 366 367 The heap property of the priority queue is invalidated by this 368 operation. 369 */ sort()370 void sort() { 371 if (!m_container.empty()) { 372 for (size_type i = m_container.size() - 1; i > 0; --i) { 373 std::swap(m_container[i], m_container[0]); 374 heapify(0, i); 375 } 376 } 377 } 378 379 /// Clears the priority queue. clear()380 void clear() { m_container.clear(); } 381 382 /// Clears the priority queue, but deletes all elements first. delete_elements()383 void delete_elements() { delete_container_pointers(m_container); } 384 385 /// Returns the capacity of the internal container. capacity()386 size_type capacity() const { return m_container.capacity(); } 387 388 /** 389 Reserves space for array elements. 390 391 @param n number of elements. 392 @retval true if out-of-memory, false otherwise. 393 */ 394 MY_ATTRIBUTE((warn_unused_result)) reserve(size_type n)395 bool reserve(size_type n) { 396 DBUG_ASSERT(n <= m_container.max_size()); 397 try { 398 m_container.reserve(n); 399 } catch (std::bad_alloc const &) { 400 return true; 401 } 402 return false; 403 } 404 405 private: 406 container_type m_container; 407 }; 408 409 #if defined(EXTRA_CODE_FOR_UNIT_TESTING) 410 template <class T, class Container, class Less> 411 inline std::ostream &operator<<(std::ostream &os, 412 Priority_queue<T, Container, Less> const &pq) { 413 typedef typename Priority_queue<T, Container, Less>::size_type size_type; 414 415 for (size_type i = 0; i < pq.size(); i++) { 416 os << pq[i] << " " << std::flush; 417 } 418 419 return os; 420 } 421 422 template <class T, class Container, class Less> 423 inline std::stringstream &operator<<( 424 std::stringstream &ss, Priority_queue<T, Container, Less> const &pq) { 425 typedef typename Priority_queue<T, Container, Less>::size_type size_type; 426 427 for (size_type i = 0; i < pq.size(); i++) { 428 ss << pq[i] << " "; 429 ; 430 } 431 432 return ss; 433 } 434 #endif // EXTRA_CODE_FOR_UNIT_TESTING 435 436 #endif // PRIORITY_QUEUE_INCLUDED 437