diff options
author | Jacques Lucke <jacques@blender.org> | 2020-12-16 14:19:17 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-12-16 14:19:17 +0300 |
commit | 985d673374a48eef6af5e73b0b24d4462a911f4b (patch) | |
tree | 1a89c23b88f3f339c14bd6c7e2dfb8227fa4678d /source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc | |
parent | 4f128269b2dcf453647e7293f68f35173d45486a (diff) |
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.
Diffstat (limited to 'source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc')
-rw-r--r-- | source/blender/blenlib/tests/BLI_inplace_priority_queue_test.cc | 113 |
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 |