1 /* Copyright (c) 2014, 2021, Oracle and/or its affiliates. 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 #include "my_dbug.h" 27 28 #include <functional> 29 #include <utility> 30 #include <vector> 31 #include "template_utils.h" 32 33 #if defined(EXTRA_CODE_FOR_UNIT_TESTING) 34 #include <iostream> 35 #include <sstream> 36 #endif 37 38 namespace priority_queue_unittest { class PriorityQueueTest; }; 39 40 41 /** 42 Implements a priority queue using a vector-based max-heap. 43 44 A priority queue is a container specifically designed such that its first 45 element is always the greatest of the elements it contains, according to 46 some strict weak ordering criterion. 47 48 For object locality, the implementation is vector-based, rather than 49 node-based. 50 51 The priority queue is mutable, which means that the priority of an element 52 can be changed. See increase/decrease/update member functions. 53 The typical use case is to change the value/priority of the root node. 54 55 We provide iterators, which can be used to visit all elements. 56 Iterators do not visit queue elements in priority order. 57 Iterators should not be used to change the priority of elements. 58 59 The underlying container must be 60 constructible from an iterator range, should provide const and 61 non-const random access iterators to access its elements, as well as 62 the following operations: 63 - size() 64 - empty() 65 - push_back() 66 - pop_back() 67 - swap() 68 - clear() 69 - capacity() 70 - reserve() 71 - max_size() 72 73 @tparam T Type of the elements of the priority queue. 74 @tparam Container Type of the underlying container object where elements 75 are stored. Its value_type shall be T. 76 @tparam Less A binary predicate that takes two elements (of type T) 77 and returns a bool. The expression less(a,b), where 78 less is an object of this type and a and b are elements 79 in the container, shall return true if a is considered 80 to go before b in the strict weak ordering the 81 function defines. 82 */ 83 template 84 < 85 typename T, 86 typename Container = std::vector<T>, 87 typename Less = std::less<typename Container::value_type> 88 > 89 class Priority_queue : public Less 90 { 91 public: 92 typedef Container container_type; 93 typedef Less less_type; 94 typedef typename container_type::value_type value_type; 95 typedef typename container_type::size_type size_type; 96 typedef typename container_type::iterator iterator; 97 typedef typename container_type::const_iterator const_iterator; 98 typedef typename container_type::allocator_type allocator_type; 99 100 friend class priority_queue_unittest::PriorityQueueTest; 101 private: 102 // Deriving from Less allows empty base-class optimization in some cases. 103 typedef Less Base; 104 105 // Returns the index of the parent node of node i. parent(size_type i)106 static size_type parent(size_type i) 107 { 108 assert(i != 0); 109 return (--i) >> 1; // (i - 1) / 2 110 } 111 112 // Returns the index of the left child of node i. left(size_type i)113 static size_type left(size_type i) 114 { 115 return (i << 1) | 1; // 2 * i + 1 116 } 117 118 // Returns the index of the right child of node i. right(size_type i)119 static size_type right(size_type i) 120 { 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 { 126 assert(i < size()); 127 size_type largest = i; 128 129 do 130 { 131 i = largest; 132 size_type l = left(i); 133 size_type r = right(i); 134 135 if (l < last && Base::operator()(m_container[i], m_container[l])) 136 { 137 largest = l; 138 } 139 140 if (r < last && Base::operator()(m_container[largest], m_container[r])) 141 { 142 largest = r; 143 } 144 145 if (largest != i) 146 { 147 std::swap(m_container[i], m_container[largest]); 148 } 149 } while (largest != i); 150 } 151 heapify(size_type i)152 void heapify(size_type i) 153 { 154 heapify(i, m_container.size()); 155 } 156 reverse_heapify(size_type i)157 void reverse_heapify(size_type i) 158 { 159 assert(i < size()); 160 while (i > 0 && !Base::operator()(m_container[i], m_container[parent(i)])) 161 { 162 std::swap(m_container[parent(i)], m_container[i]); 163 i = parent(i); 164 } 165 } 166 167 // Sets the value of element i, and rebuilds the priority queue. decrease_key(size_type i,value_type const & x)168 void decrease_key(size_type i, value_type const &x) 169 { 170 m_container[i] = x; 171 heapify(i); 172 } 173 174 // Sets the value of element i, and rebuilds the priority queue. increase_key(size_type i,value_type const & x)175 void increase_key(size_type i, value_type const &x) 176 { 177 m_container[i] = x; 178 reverse_heapify(i); 179 } 180 181 public: 182 /// Constructs an empty priority queue. 183 Priority_queue(Less const &less = Less(), 184 const allocator_type& alloc = allocator_type()) Base(less)185 : Base(less), 186 m_container(alloc) 187 {} 188 189 /// Constructs a heap of the objects between first and beyond. 190 template <typename Input_iterator> 191 Priority_queue(Input_iterator first, Input_iterator beyond, 192 Less const &less = Less(), 193 const allocator_type& alloc = allocator_type()) Base(less)194 : Base(less), 195 m_container(first, beyond, alloc) 196 { 197 build_heap(); 198 } 199 200 /// Constructs a heap based on input argument. assign(const container_type & container)201 void assign(const container_type &container) 202 { 203 m_container= container; 204 build_heap(); 205 } 206 207 /** 208 Constructs a heap based on container contents. 209 Can also be used when many elements have changed. 210 */ build_heap()211 void build_heap() 212 { 213 if (m_container.size() > 1) 214 { 215 for (size_type i = parent(m_container.size() - 1); i > 0; --i) 216 { 217 heapify(i); 218 } 219 heapify(0); 220 } 221 } 222 223 /// Returns a const reference to the top element of the priority queue. top()224 value_type const &top() const 225 { 226 assert(!empty()); 227 return m_container[0]; 228 } 229 230 /// Returns a reference to the top element of the priority queue. top()231 value_type& top() 232 { 233 assert(!empty()); 234 return m_container[0]; 235 } 236 237 /** 238 Inserts an element in the priority queue. 239 240 @param x value to be pushed. 241 @retval true if out-of-memory, false otherwise. 242 */ push(value_type const & x)243 bool push(value_type const &x) 244 { 245 try 246 { 247 m_container.push_back(x); 248 } 249 catch(std::bad_alloc const &) 250 { 251 return true; 252 } 253 254 reverse_heapify(m_container.size() - 1); 255 return false; 256 } 257 258 /// Pops the top-most element in the priority queue. pop()259 void pop() 260 { 261 remove(0); 262 } 263 264 /// Removes the element at position i from the priority queue. remove(size_type i)265 void remove(size_type i) 266 { 267 assert(i < size()); 268 269 if (i == m_container.size() - 1) 270 { 271 m_container.pop_back(); 272 return; 273 } 274 275 m_container[i] = m_container[m_container.size() - 1]; 276 m_container.pop_back(); 277 update(i); 278 } 279 280 /** 281 Decreases the priority of the element at position i, where the 282 new priority is x. 283 */ decrease(size_type i,value_type const & x)284 void decrease(size_type i, value_type const &x) 285 { 286 assert(i < size()); 287 assert(!Base::operator()(m_container[i], x)); 288 decrease_key(i, x); 289 } 290 291 /** 292 Increases the priority of the element at position i, where the 293 new priority is x. 294 */ increase(size_type i,value_type const & x)295 void increase(size_type i, value_type const &x) 296 { 297 assert(i < size()); 298 assert(!Base::operator()(x, m_container[i])); 299 increase_key(i, x); 300 } 301 302 /** 303 Changes the priority of the element at position i, where the 304 new priority is x. 305 */ update(size_type i,value_type const & x)306 void update(size_type i, value_type const &x) 307 { 308 assert(i < size()); 309 if (Base::operator()(x, m_container[i])) 310 { 311 decrease_key(i, x); 312 } 313 else 314 { 315 increase_key(i, x); 316 } 317 } 318 319 /** 320 Assumes that the i-th element's value has increased 321 and rebuilds the priority queue. 322 */ increase(size_type i)323 void increase(size_type i) 324 { 325 reverse_heapify(i); 326 } 327 328 /** 329 Assumes that the i-th element's value has decreased 330 and rebuilds the priority queue. 331 */ decrease(size_type i)332 void decrease(size_type i) 333 { 334 heapify(i); 335 } 336 337 /** 338 Assumes that the i-th element's value has changed 339 and rebuilds the priority queue. 340 */ update(size_type i)341 void update(size_type i) 342 { 343 assert(i < size()); 344 if (i == 0 || Base::operator()(m_container[i], m_container[parent(i)])) 345 { 346 heapify(i); 347 } 348 else 349 { 350 reverse_heapify(i); 351 } 352 } 353 354 /** 355 Assumes that the top element's value has changed 356 and rebuilds the priority queue. 357 */ update_top()358 void update_top() 359 { 360 assert(!empty()); 361 heapify(0); 362 } 363 364 /// Returns the number of elements of the priority queue size()365 size_type size() const { return m_container.size(); } 366 367 /// Returns true if the priority queue is empty empty()368 bool empty() const { return m_container.empty(); } 369 370 /// Returns a const reference to the i-th element in the underlying container. 371 value_type const& operator[](size_type i) const 372 { 373 assert(i < size()); 374 return m_container[i]; 375 } 376 377 /// Returns a reference to the i-th element in the underlying container. 378 value_type& operator[](size_type i) 379 { 380 assert(i < size()); 381 return m_container[i]; 382 } 383 384 /// Returns a const iterator to the first element of the underlying container. begin()385 const_iterator begin() const 386 { 387 return m_container.begin(); 388 } 389 390 /// Returns a const iterator to the end element of the underlying container. end()391 const_iterator end() const 392 { 393 return m_container.end(); 394 } 395 396 /// Returns an iterator to the first element of the underlying container. begin()397 iterator begin() 398 { 399 return m_container.begin(); 400 } 401 402 /// Returns an iterator to the end element of the underlying container. end()403 iterator end() 404 { 405 return m_container.end(); 406 } 407 408 /// Swaps the contents of two priority queues. swap(Priority_queue & other)409 void swap(Priority_queue& other) 410 { 411 std::swap(static_cast<Base&>(*this), static_cast<Base&>(other)); 412 m_container.swap(other.m_container); 413 } 414 415 /// Returns true if the priority queue has the heap property. is_valid()416 bool is_valid() const 417 { 418 for (size_type i = 1; i < m_container.size(); ++i) 419 { 420 if (Base::operator()(m_container[parent(i)], m_container[i])) 421 { 422 return false; 423 } 424 } 425 return true; 426 } 427 428 /** 429 Sorts the elements of the priority queue according to the strict 430 partial ordering defined by the object of type Less passed to 431 the priority queue. 432 433 The heap property of the priority queue is invalidated by this 434 operation. 435 */ sort()436 void sort() 437 { 438 if (!m_container.empty()) 439 { 440 for (size_type i = m_container.size() - 1; i > 0; --i) 441 { 442 std::swap(m_container[i], m_container[0]); 443 heapify(0, i); 444 } 445 } 446 } 447 448 /// Clears the priority queue. clear()449 void clear() 450 { 451 m_container.clear(); 452 } 453 454 /// Clears the priority queue, but deletes all elements first. delete_elements()455 void delete_elements() 456 { 457 delete_container_pointers(m_container); 458 } 459 460 /// Returns the capacity of the internal container. capacity()461 size_type capacity() const 462 { 463 return m_container.capacity(); 464 } 465 466 /** 467 Reserves space for array elements. 468 469 @param n number of elements. 470 @retval true if out-of-memory, false otherwise. 471 */ 472 MY_ATTRIBUTE((warn_unused_result)) reserve(size_type n)473 bool reserve(size_type n) 474 { 475 assert(n <= m_container.max_size()); 476 try 477 { 478 m_container.reserve(n); 479 } 480 catch(std::bad_alloc const &) 481 { 482 return true; 483 } 484 return false; 485 } 486 487 private: 488 container_type m_container; 489 }; 490 491 492 #if defined(EXTRA_CODE_FOR_UNIT_TESTING) 493 template <class T, class Container, class Less> 494 inline std::ostream& 495 operator<<(std::ostream& os, 496 Priority_queue<T, Container, Less> const& pq) 497 { 498 typedef typename Priority_queue<T, Container, Less>::size_type size_type; 499 500 for (size_type i = 0; i < pq.size(); i++) 501 { 502 os << pq[i] << " " << std::flush; 503 } 504 505 return os; 506 } 507 508 509 template <class T, class Container, class Less> 510 inline std::stringstream& 511 operator<<(std::stringstream& ss, 512 Priority_queue<T, Container, Less> const& pq) 513 { 514 typedef typename Priority_queue<T, Container, Less>::size_type size_type; 515 516 for (size_type i = 0; i < pq.size(); i++) 517 { 518 ss << pq[i] << " ";; 519 } 520 521 return ss; 522 } 523 #endif // EXTRA_CODE_FOR_UNIT_TESTING 524 525 526 #endif // PRIORITY_QUEUE_INCLUDED 527