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.

1 files changed, 113 insertions, 0 deletions

diff --git a/source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc b/source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc
new file mode 100644
index 00000000000..3adf12f36a7
--- /dev/null
+++ b/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