[Bf-blender-cvs] [31c86e643c2] temp-inplace-priority-queue: add indices accessor

[Jacques Lucke]

Commit: 31c86e643c2f6a98f8ae0d375f808f0c3bde8e39
Author: Jacques Lucke
Date:   Wed Dec 16 11:27:43 2020 +0100
Branches: temp-inplace-priority-queue
https://developer.blender.org/rB31c86e643c2f6a98f8ae0d375f808f0c3bde8e39

add indices accessor

===================================================================

M	source/blender/blenlib/BLI_inplace_priority_queue.hh
M	source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc

===================================================================

diff --git a/source/blender/blenlib/BLI_inplace_priority_queue.hh b/source/blender/blenlib/BLI_inplace_priority_queue.hh
index 5aa2bba4bfa..6147f7d0889 100644
--- a/source/blender/blenlib/BLI_inplace_priority_queue.hh
+++ b/source/blender/blenlib/BLI_inplace_priority_queue.hh
@@ -181,6 +181,25 @@ class InplacePriorityQueue {
     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_);
+  }
+
   /**
    * Return the heap used by the priority queue as dot graph string.
    * This exists for debugging purposes.
diff --git a/source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc b/source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc
index 36be6756cf4..2abef992d09 100644
--- a/source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc
+++ b/source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc
@@ -64,4 +64,21 @@ TEST(inplace_priority_queue, PopAll)
   }
 }
 
+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.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.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);
+}
+
 }  // namespace blender::tests