Blender  V3.3
BLI_inplace_priority_queue.hh
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #pragma once
4 
5 #include "BLI_array.hh"
6 #include "BLI_dot_export.hh"
7 
8 namespace blender {
9 
19 template<
20  /* Type of the elements in the underlying array. */
21  typename T,
22  /* Binary function that takes two `const T &` inputs and returns true,
23  * when the first input has greater priority than the second. */
24  typename FirstHasHigherPriority = std::greater<T>>
26  private:
27  /* Underlying array the priority queue is built upon. This is a span instead of a mutable span,
28  * because this data structure never changes the values itself. */
29  Span<T> data_;
30  /* Maps indices from the heap (binary tree in array format) to indices of the underlying/original
31  * array. */
32  Array<int64_t> heap_to_orig_;
33  /* This is the inversion of the above mapping. */
34  Array<int64_t> orig_to_heap_;
35  /* Number of elements that are currently in the priority queue. */
36  int64_t heap_size_ = 0;
37  /* Function that can be changed to customize how the priority of two elements is compared. */
38  FirstHasHigherPriority first_has_higher_priority_fn_;
39 
40  public:
45  : data_(data), heap_to_orig_(data_.size()), orig_to_heap_(data_.size())
46  {
47  for (const int64_t i : IndexRange(data_.size())) {
48  heap_to_orig_[i] = i;
49  orig_to_heap_[i] = i;
50  }
51 
52  this->rebuild();
53  }
54 
58  void rebuild()
59  {
60  const int final_heap_size = data_.size();
61  if (final_heap_size > 1) {
62  for (int64_t i = this->get_parent(final_heap_size - 1); i >= 0; i--) {
63  this->heapify(i, final_heap_size);
64  }
65  }
66  heap_size_ = final_heap_size;
67  }
68 
73  int64_t size() const
74  {
75  return heap_size_;
76  }
77 
82  bool is_empty() const
83  {
84  return heap_size_ == 0;
85  }
86 
92  const T &peek() const
93  {
94  return data_[this->peek_index()];
95  }
96 
102  const T &pop()
103  {
104  return data_[this->pop_index()];
105  }
106 
111  {
112  BLI_assert(!this->is_empty());
113  return heap_to_orig_[0];
114  }
115 
120  {
121  BLI_assert(!this->is_empty());
122  const int64_t top_index_orig = heap_to_orig_[0];
123  heap_size_--;
124  if (heap_size_ > 1) {
125  this->swap_indices(0, heap_size_);
126  this->heapify(0, heap_size_);
127  }
128  return top_index_orig;
129  }
130 
135  void priority_decreased(const int64_t index)
136  {
137  const int64_t heap_index = orig_to_heap_[index];
138  if (heap_index >= heap_size_) {
139  /* This element is not in the queue currently. */
140  return;
141  }
142  this->heapify(heap_index, heap_size_);
143  }
144 
149  void priority_increased(const int64_t index)
150  {
151  int64_t current = orig_to_heap_[index];
152  if (current >= heap_size_) {
153  /* This element is not in the queue currently. */
154  return;
155  }
156  while (true) {
157  if (current == 0) {
158  break;
159  }
160  const int64_t parent = this->get_parent(current);
161  if (this->first_has_higher_priority(parent, current)) {
162  break;
163  }
164  this->swap_indices(current, parent);
165  current = parent;
166  }
167  }
168 
173  void priority_changed(const int64_t index)
174  {
175  this->priority_increased(index);
176  this->priority_decreased(index);
177  }
178 
184  {
185  return heap_to_orig_.as_span().take_front(heap_size_);
186  }
187 
194  {
195  return heap_to_orig_.as_span().drop_front(heap_size_);
196  }
197 
202  {
203  return heap_to_orig_;
204  }
205 
210  std::string to_dot() const
211  {
212  return this->partial_to_dot(heap_size_);
213  }
214 
215  private:
216  bool first_has_higher_priority(const int64_t a, const int64_t b)
217  {
218  const T &value_a = data_[heap_to_orig_[a]];
219  const T &value_b = data_[heap_to_orig_[b]];
220  return first_has_higher_priority_fn_(value_a, value_b);
221  }
222 
223  void swap_indices(const int64_t a, const int64_t b)
224  {
225  std::swap(heap_to_orig_[a], heap_to_orig_[b]);
226  orig_to_heap_[heap_to_orig_[a]] = a;
227  orig_to_heap_[heap_to_orig_[b]] = b;
228  }
229 
230  void heapify(const int64_t parent, const int64_t heap_size)
231  {
232  int64_t max_index = parent;
233  const int left = this->get_left(parent);
234  const int right = this->get_right(parent);
235  if (left < heap_size && this->first_has_higher_priority(left, max_index)) {
236  max_index = left;
237  }
238  if (right < heap_size && this->first_has_higher_priority(right, max_index)) {
239  max_index = right;
240  }
241  if (max_index != parent) {
242  this->swap_indices(parent, max_index);
243  this->heapify(max_index, heap_size);
244  }
245  if (left < heap_size) {
246  BLI_assert(!this->first_has_higher_priority(left, parent));
247  }
248  if (right < heap_size) {
249  BLI_assert(!this->first_has_higher_priority(right, parent));
250  }
251  }
252 
253  int64_t get_parent(const int64_t child) const
254  {
255  BLI_assert(child > 0);
256  return (child - 1) / 2;
257  }
258 
259  int64_t get_left(const int64_t parent) const
260  {
261  return parent * 2 + 1;
262  }
263 
264  int64_t get_right(const int64_t parent) const
265  {
266  return parent * 2 + 2;
267  }
268 
269  std::string partial_to_dot(const int size) const
270  {
271  dot::DirectedGraph digraph;
272  Array<dot::Node *> dot_nodes(size);
273  for (const int i : IndexRange(size)) {
274  std::stringstream ss;
275  ss << data_[heap_to_orig_[i]];
276  const std::string name = ss.str();
277  dot::Node &node = digraph.new_node(name);
278  node.set_shape(dot::Attr_shape::Rectangle);
279  node.attributes.set("ordering", "out");
280  dot_nodes[i] = &node;
281  if (i > 0) {
282  const int64_t parent = this->get_parent(i);
283  digraph.new_edge(*dot_nodes[parent], node);
284  }
285  }
286  return digraph.to_dot_string();
287  }
288 };
289 
290 } // namespace blender
#define BLI_assert(a)
Definition: BLI_assert.h:46
void swap(T &a, T &b)
Definition: Common.h:19
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble right
Span< T > as_span() const
Definition: BLI_array.hh:231
void priority_decreased(const int64_t index)
void priority_increased(const int64_t index)
void priority_changed(const int64_t index)
constexpr Span drop_front(int64_t n) const
Definition: BLI_span.hh:159
constexpr Span take_front(int64_t n) const
Definition: BLI_span.hh:181
DirectedEdge & new_edge(NodePort from, NodePort to)
Definition: dot_export.cc:37
std::string to_dot_string() const
Definition: dot_export.cc:121
Node & new_node(StringRef label)
Definition: dot_export.cc:12
OperationNode * node
T * data_
Definition: eval_output.h:163
static int left
#define T
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
__int64 int64_t
Definition: stdint.h:89