diff options
| author | Jacques Lucke <jacques@blender.org> | 2020-07-08 15:57:31 +0300 |
|---|---|---|
| committer | Jacques Lucke <jacques@blender.org> | 2020-07-08 16:10:30 +0300 |
| commit | ff133bbd33f10b87b5aaf65515453809a3730fe4 (patch) | |
| tree | 61d2f82339104e99501e160c342be279760e6dcd /tests | |
| parent | a8ff8b64dc4d4bea9ec620920639440496dfcba0 (diff) | |
BLI: add disjoint set data structure
This can be used to find separate islands in meshes efficiently (as is
done in cycles already). Furthermore, this helps to implement some
algorithms on node trees more efficiently.
Diffstat (limited to 'tests')
| -rw-r--r-- | tests/gtests/blenlib/BLI_disjoint_set_test.cc | 34 | ||||
| -rw-r--r-- | tests/gtests/blenlib/CMakeLists.txt | 1 |
2 files changed, 35 insertions, 0 deletions
diff --git a/tests/gtests/blenlib/BLI_disjoint_set_test.cc b/tests/gtests/blenlib/BLI_disjoint_set_test.cc new file mode 100644 index 00000000000..a46f8612e93 --- /dev/null +++ b/tests/gtests/blenlib/BLI_disjoint_set_test.cc @@ -0,0 +1,34 @@ +#include "BLI_disjoint_set.hh" +#include "BLI_strict_flags.h" + +#include "testing/testing.h" + +namespace blender { + +TEST(disjoint_set, Test) +{ + DisjointSet disjoint_set(6); + EXPECT_FALSE(disjoint_set.in_same_set(1, 2)); + EXPECT_FALSE(disjoint_set.in_same_set(5, 3)); + EXPECT_TRUE(disjoint_set.in_same_set(2, 2)); + EXPECT_EQ(disjoint_set.find_root(3), 3u); + + disjoint_set.join(1, 2); + + EXPECT_TRUE(disjoint_set.in_same_set(1, 2)); + EXPECT_FALSE(disjoint_set.in_same_set(0, 1)); + + disjoint_set.join(3, 4); + + EXPECT_FALSE(disjoint_set.in_same_set(2, 3)); + EXPECT_TRUE(disjoint_set.in_same_set(3, 4)); + + disjoint_set.join(1, 4); + + EXPECT_TRUE(disjoint_set.in_same_set(1, 4)); + EXPECT_TRUE(disjoint_set.in_same_set(1, 3)); + EXPECT_TRUE(disjoint_set.in_same_set(2, 4)); + EXPECT_FALSE(disjoint_set.in_same_set(0, 4)); +} + +} // namespace blender diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index 0831024556b..496fe44234e 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -43,6 +43,7 @@ BLENDER_TEST(BLI_array "bf_blenlib") BLENDER_TEST(BLI_array_store "bf_blenlib") BLENDER_TEST(BLI_array_utils "bf_blenlib") BLENDER_TEST(BLI_delaunay_2d "bf_blenlib") +BLENDER_TEST(BLI_disjoint_set "bf_blenlib") BLENDER_TEST(BLI_edgehash "bf_blenlib") BLENDER_TEST(BLI_expr_pylike_eval "bf_blenlib") BLENDER_TEST(BLI_ghash "bf_blenlib") |