BLI: add new InplacePriorityQueue data structure

This data structure adds priority queue functionality to an existing array.
The underlying array is not changed. Instead, the priority queue maintains
indices into the original array.

Changing priorities of elements dynamically is supported, but the priority
queue has to  be informed of such changes.

This data structure is needed for D9787.

source/blender/blenlib/BLI_inplace_priority_queue.hh

@@ -0,0 +1,304 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#pragma once
+
+#include "BLI_array.hh"
+#include "BLI_dot_export.hh"
+
+namespace blender {
+
+/**
+ * An InplacePriorityQueue adds priority queue functionality to an existing array. The underlying
+ * array is not changed. Instead, the priority queue maintains indices into the original array.
+ *
+ * The priority queue provides efficient access to the element in order of their priorities.
+ *
+ * When a priority changes, the priority queue has to be informed using one of the following
+ * methods: #priority_decreased, #priority_increased or #priority_changed.
+ */
+template<
+    /* Type of the elements in the underlying array. */
+    typename T,
+    /* Binary function that takes two `const T &` inputs and returns true, when the first input has
+       greater priority than the second. */
+    typename FirstHasHigherPriority = std::greater<T>>
+class InplacePriorityQueue {
+ private:
+  /* Underlying array the priority queue is built upon. This is a span instead of a mutable span,
+   * because this data structure never changes the values itself. */
+  Span<T> data_;
+  /* Maps indices from the heap (binary tree in array format) to indices of the underlying/original
+   * array. */
+  Array<int64_t> heap_to_orig_;
+  /* This is the inversion of the above mapping. */
+  Array<int64_t> orig_to_heap_;
+  /* Number of elements that are currently in the priority queue. */
+  int64_t heap_size_ = 0;
+  /* Function that can be changed to customize how the priority of two elements is compared. */
+  FirstHasHigherPriority first_has_higher_priority_fn_;
+
+ public:
+  /**
+   * Construct the priority queue on top of the data in the given span.
+   */
+  InplacePriorityQueue(Span<T> data)
+      : data_(data), heap_to_orig_(data_.size()), orig_to_heap_(data_.size())
+  {
+    for (const int64_t i : IndexRange(data_.size())) {
+      heap_to_orig_[i] = i;
+      orig_to_heap_[i] = i;
+    }
+
+    this->rebuild();
+  }
+
+  /**
+   * Rebuilds the priority queue from the array that has been passed to the constructor.
+   */
+  void rebuild()
+  {
+    const int final_heap_size = data_.size();
+    if (final_heap_size > 1) {
+      for (int64_t i = this->get_parent(final_heap_size - 1); i >= 0; i--) {
+        this->heapify(i, final_heap_size);
+      }
+    }
+    heap_size_ = final_heap_size;
+  }
+
+  /**
+   * Returns the number of elements in the priority queue.
+   * This is less or equal than the size of the underlying array.
+   */
+  int64_t size() const
+  {
+    return heap_size_;
+  }
+
+  /**
+   * Returns true, when the priority queue contains no elements. If this returns true, #peek and
+   * #pop must not be used.
+   */
+  bool is_empty() const
+  {
+    return heap_size_ == 0;
+  }
+
+  /**
+   * Get the element with the highest priority in the priority queue.
+   * The returned reference is const, because the priority queue has read-only access to the
+   * underlying data. If you need a mutable reference, use #peek_index instead.
+   */
+  const T &peek() const
+  {
+    return data_[this->peek_index()];
+  }
+
+  /**
+   * Get the element with the highest priority in the priority queue and remove it.
+   * The returned reference is const, because the priority queue has read-only access to the
+   * underlying data. If you need a mutable reference, use #pop_index instead.
+   */
+  const T &pop()
+  {
+    return data_[this->pop_index()];
+  }
+
+  /**
+   * Get the index of the element with the highest priority in the priority queue.
+   */
+  int64_t peek_index() const
+  {
+    BLI_assert(!this->is_empty());
+    return heap_to_orig_[0];
+  }
+
+  /**
+   * Get the index of the element with the highest priority in the priority queue and remove it.
+   */
+  int64_t pop_index()
+  {
+    BLI_assert(!this->is_empty());
+    const int64_t top_index_orig = heap_to_orig_[0];
+    heap_size_--;
+    if (heap_size_ > 1) {
+      this->swap_indices(0, heap_size_);
+      this->heapify(0, heap_size_);
+    }
+    return top_index_orig;
+  }
+
+  /**
+   * Inform the priority queue that the priority of the element at the given index has been
+   * decreased.
+   */
+  void priority_decreased(const int64_t index)
+  {
+    const int64_t heap_index = orig_to_heap_[index];
+    if (heap_index >= heap_size_) {
+      /* This element is not in the queue currently. */
+      return;
+    }
+    this->heapify(heap_index, heap_size_);
+  }
+
+  /**
+   * Inform the priority queue that the priority of the element at the given index has been
+   * increased.
+   */
+  void priority_increased(const int64_t index)
+  {
+    int64_t current = orig_to_heap_[index];
+    if (current >= heap_size_) {
+      /* This element is not in the queue currently. */
+      return;
+    }
+    while (true) {
+      if (current == 0) {
+        break;
+      }
+      const int64_t parent = this->get_parent(current);
+      if (this->first_has_higher_priority(parent, current)) {
+        break;
+      }
+      this->swap_indices(current, parent);
+      current = parent;
+    }
+  }
+
+  /**
+   * Inform the priority queue that the priority of the element at the given index has been
+   * changed.
+   */
+  void priority_changed(const int64_t index)
+  {
+    this->priority_increased(index);
+    this->priority_decreased(index);
+  }
+
+  /**
+   * Returns the indices of all elements that are in the priority queue.
+   * There are no guarantees about the order of indices.
+   */
+  Span<int64_t> active_indices() const
+  {
+    return heap_to_orig_.as_span().take_front(heap_size_);
+  }
+
+  /**
+   * Returns the indices of all elements that are not in the priority queue.
+   * The indices are in reverse order of their removal from the queue.
+   * I.e. the index that has been removed last, comes first.
+   */
+  Span<int64_t> inactive_indices() const
+  {
+    return heap_to_orig_.as_span().drop_front(heap_size_);
+  }
+
+  /**
+   * Returns the concatenation of the active and inactive indices.
+   */
+  Span<int64_t> all_indices() const
+  {
+    return heap_to_orig_;
+  }
+
+  /**
+   * Return the heap used by the priority queue as dot graph string.
+   * This exists for debugging purposes.
+   */
+  std::string to_dot() const
+  {
+    return this->partial_to_dot(heap_size_);
+  }
+
+ private:
+  bool first_has_higher_priority(const int64_t a, const int64_t b)
+  {
+    const T &value_a = data_[heap_to_orig_[a]];
+    const T &value_b = data_[heap_to_orig_[b]];
+    return first_has_higher_priority_fn_(value_a, value_b);
+  }
+
+  void swap_indices(const int64_t a, const int64_t b)
+  {
+    std::swap(heap_to_orig_[a], heap_to_orig_[b]);
+    orig_to_heap_[heap_to_orig_[a]] = a;
+    orig_to_heap_[heap_to_orig_[b]] = b;
+  }
+
+  void heapify(const int64_t parent, const int64_t heap_size)
+  {
+    int64_t max_index = parent;
+    const int left = this->get_left(parent);
+    const int right = this->get_right(parent);
+    if (left < heap_size && this->first_has_higher_priority(left, max_index)) {
+      max_index = left;
+    }
+    if (right < heap_size && this->first_has_higher_priority(right, max_index)) {
+      max_index = right;
+    }
+    if (max_index != parent) {
+      this->swap_indices(parent, max_index);
+      this->heapify(max_index, heap_size);
+    }
+    if (left < heap_size) {
+      BLI_assert(!this->first_has_higher_priority(left, parent));
+    }
+    if (right < heap_size) {
+      BLI_assert(!this->first_has_higher_priority(right, parent));
+    }
+  }
+
+  int64_t get_parent(const int64_t child) const
+  {
+    BLI_assert(child > 0);
+    return (child - 1) / 2;
+  }
+
+  int64_t get_left(const int64_t parent) const
+  {
+    return parent * 2 + 1;
+  }
+
+  int64_t get_right(const int64_t parent) const
+  {
+    return parent * 2 + 2;
+  }
+
+  std::string partial_to_dot(const int size) const
+  {
+    dot::DirectedGraph digraph;
+    Array<dot::Node *> dot_nodes(size);
+    for (const int i : IndexRange(size)) {
+      std::stringstream ss;
+      ss << data_[heap_to_orig_[i]];
+      const std::string name = ss.str();
+      dot::Node &node = digraph.new_node(name);
+      node.set_shape(dot::Attr_shape::Rectangle);
+      node.attributes.set("ordering", "out");
+      dot_nodes[i] = &node;
+      if (i > 0) {
+        const int64_t parent = this->get_parent(i);
+        digraph.new_edge(*dot_nodes[parent], node);
+      }
+    }
+    return digraph.to_dot_string();
+  }
+};
+
+}  // namespace blender

source/blender/blenlib/CMakeLists.txt

@@ -203,6 +203,7 @@ set(SRC
   BLI_heap_simple.h
   BLI_index_mask.hh
   BLI_index_range.hh
+  BLI_inplace_priority_queue.hh
   BLI_iterator.h
   BLI_jitter_2d.h
   BLI_kdopbvh.h
@@ -390,6 +391,7 @@ if(WITH_GTESTS)
     tests/BLI_heap_test.cc
     tests/BLI_index_mask_test.cc
     tests/BLI_index_range_test.cc
+    tests/BLI_inplace_priority_queue_test.cc
     tests/BLI_kdopbvh_test.cc
     tests/BLI_linear_allocator_test.cc
     tests/BLI_linklist_lockfree_test.cc

source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc

@@ -0,0 +1,113 @@
+/* Apache License, Version 2.0 */
+
+#include "testing/testing.h"
+
+#include "BLI_inplace_priority_queue.hh"
+#include "BLI_rand.hh"
+
+namespace blender::tests {
+
+TEST(inplace_priority_queue, BuildSmall)
+{
+  Array<int> values = {1, 5, 2, 8, 5, 6, 5, 4, 3, 6, 7, 3};
+  InplacePriorityQueue<int> priority_queue{values};
+
+  EXPECT_EQ(priority_queue.peek(), 8);
+  EXPECT_EQ(priority_queue.pop(), 8);
+  EXPECT_EQ(priority_queue.peek(), 7);
+  EXPECT_EQ(priority_queue.pop(), 7);
+  EXPECT_EQ(priority_queue.pop(), 6);
+  EXPECT_EQ(priority_queue.pop(), 6);
+  EXPECT_EQ(priority_queue.pop(), 5);
+}
+
+TEST(inplace_priority_queue, DecreasePriority)
+{
+  Array<int> values = {5, 2, 7, 4};
+  InplacePriorityQueue<int> priority_queue(values);
+
+  EXPECT_EQ(priority_queue.peek(), 7);
+  values[2] = 0;
+  EXPECT_EQ(priority_queue.peek(), 0);
+  priority_queue.priority_decreased(2);
+  EXPECT_EQ(priority_queue.peek(), 5);
+}
+
+TEST(inplace_priority_queue, IncreasePriority)
+{
+  Array<int> values = {5, 2, 7, 4};
+  InplacePriorityQueue<int> priority_queue(values);
+
+  EXPECT_EQ(priority_queue.peek(), 7);
+  values[1] = 10;
+  EXPECT_EQ(priority_queue.peek(), 7);
+  priority_queue.priority_increased(1);
+  EXPECT_EQ(priority_queue.peek(), 10);
+}
+
+TEST(inplace_priority_queue, PopAll)
+{
+  RandomNumberGenerator rng;
+  Vector<int> values;
+  const int amount = 1000;
+  for (int i = 0; i < amount; i++) {
+    values.append(rng.get_int32() % amount);
+  }
+
+  InplacePriorityQueue<int> priority_queue(values);
+
+  int last_value = amount;
+  while (!priority_queue.is_empty()) {
+    const int value = priority_queue.pop();
+    EXPECT_LE(value, last_value);
+    last_value = value;
+  }
+}
+
+TEST(inplace_priority_queue, ManyPriorityChanges)
+{
+  RandomNumberGenerator rng;
+  Vector<int> values;
+  const int amount = 1000;
+  for (int i = 0; i < amount; i++) {
+    values.append(rng.get_int32() % amount);
+  }
+
+  InplacePriorityQueue<int> priority_queue(values);
+
+  for (int i = 0; i < amount; i++) {
+    const int index = rng.get_int32() % amount;
+    const int new_priority = rng.get_int32() % amount;
+    values[index] = new_priority;
+    priority_queue.priority_changed(index);
+  }
+
+  int last_value = amount;
+  while (!priority_queue.is_empty()) {
+    const int value = priority_queue.pop();
+    EXPECT_LE(value, last_value);
+    last_value = value;
+  }
+}
+
+TEST(inplace_priority_queue, IndicesAccess)
+{
+  Array<int> values = {4, 6, 2, 4, 8, 1, 10, 2, 5};
+  InplacePriorityQueue<int> priority_queue(values);
+
+  EXPECT_EQ(priority_queue.active_indices().size(), 9);
+  EXPECT_EQ(priority_queue.inactive_indices().size(), 0);
+  EXPECT_EQ(priority_queue.all_indices().size(), 9);
+  EXPECT_EQ(priority_queue.pop(), 10);
+  EXPECT_EQ(priority_queue.active_indices().size(), 8);
+  EXPECT_EQ(priority_queue.inactive_indices().size(), 1);
+  EXPECT_EQ(values[priority_queue.inactive_indices()[0]], 10);
+  EXPECT_EQ(priority_queue.all_indices().size(), 9);
+  EXPECT_EQ(priority_queue.pop(), 8);
+  EXPECT_EQ(priority_queue.inactive_indices().size(), 2);
+  EXPECT_EQ(values[priority_queue.inactive_indices()[0]], 8);
+  EXPECT_EQ(values[priority_queue.inactive_indices()[1]], 10);
+  EXPECT_EQ(priority_queue.all_indices().size(), 9);
+}
+
+}  // namespace blender::tests