From ff133bbd33f10b87b5aaf65515453809a3730fe4 Mon Sep 17 00:00:00 2001
From: Jacques Lucke <jacques@blender.org>
Date: Wed, 8 Jul 2020 14:57:31 +0200
Subject: 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.
---
 tests/gtests/blenlib/BLI_disjoint_set_test.cc | 34 +++++++++++++++++++++++++++
 tests/gtests/blenlib/CMakeLists.txt           |  1 +
 2 files changed, 35 insertions(+)
 create mode 100644 tests/gtests/blenlib/BLI_disjoint_set_test.cc

(limited to 'tests/gtests')

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")
-- 
cgit v1.2.3