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