Build transitive closure of equality classes

12 files changed, 180 insertions, 0 deletions

diff --git a/library/cpp/CMakeLists.darwin-x86_64.txt b/library/cpp/CMakeLists.darwin-x86_64.txt
index 2e5648a15c..86cbdf3d7e 100644
--- a/library/cpp/CMakeLists.darwin-x86_64.txt
+++ b/library/cpp/CMakeLists.darwin-x86_64.txt
@@ -32,6 +32,7 @@ add_subdirectory(dbg_output)
 add_subdirectory(deprecated)
 add_subdirectory(diff)
 add_subdirectory(digest)
+add_subdirectory(disjoint_sets)
 add_subdirectory(dns)
 add_subdirectory(enumbitset)
 add_subdirectory(execprofile)
diff --git a/library/cpp/CMakeLists.linux-aarch64.txt b/library/cpp/CMakeLists.linux-aarch64.txt
index 09cf4909bb..4f422c15bc 100644
--- a/library/cpp/CMakeLists.linux-aarch64.txt
+++ b/library/cpp/CMakeLists.linux-aarch64.txt
@@ -31,6 +31,7 @@ add_subdirectory(dbg_output)
 add_subdirectory(deprecated)
 add_subdirectory(diff)
 add_subdirectory(digest)
+add_subdirectory(disjoint_sets)
 add_subdirectory(dns)
 add_subdirectory(enumbitset)
 add_subdirectory(execprofile)
diff --git a/library/cpp/CMakeLists.linux-x86_64.txt b/library/cpp/CMakeLists.linux-x86_64.txt
index 2e5648a15c..86cbdf3d7e 100644
--- a/library/cpp/CMakeLists.linux-x86_64.txt
+++ b/library/cpp/CMakeLists.linux-x86_64.txt
@@ -32,6 +32,7 @@ add_subdirectory(dbg_output)
 add_subdirectory(deprecated)
 add_subdirectory(diff)
 add_subdirectory(digest)
+add_subdirectory(disjoint_sets)
 add_subdirectory(dns)
 add_subdirectory(enumbitset)
 add_subdirectory(execprofile)
diff --git a/library/cpp/CMakeLists.windows-x86_64.txt b/library/cpp/CMakeLists.windows-x86_64.txt
index 2e5648a15c..86cbdf3d7e 100644
--- a/library/cpp/CMakeLists.windows-x86_64.txt
+++ b/library/cpp/CMakeLists.windows-x86_64.txt
@@ -32,6 +32,7 @@ add_subdirectory(dbg_output)
 add_subdirectory(deprecated)
 add_subdirectory(diff)
 add_subdirectory(digest)
+add_subdirectory(disjoint_sets)
 add_subdirectory(dns)
 add_subdirectory(enumbitset)
 add_subdirectory(execprofile)
diff --git a/library/cpp/disjoint_sets/CMakeLists.darwin-x86_64.txt b/library/cpp/disjoint_sets/CMakeLists.darwin-x86_64.txt
new file mode 100644
index 0000000000..83a72be4c8
--- /dev/null
+++ b/library/cpp/disjoint_sets/CMakeLists.darwin-x86_64.txt
@@ -0,0 +1,17 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(library-cpp-disjoint_sets)
+target_link_libraries(library-cpp-disjoint_sets PUBLIC
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(library-cpp-disjoint_sets PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/disjoint_sets/disjoint_sets.cpp
+)
diff --git a/library/cpp/disjoint_sets/CMakeLists.linux-aarch64.txt b/library/cpp/disjoint_sets/CMakeLists.linux-aarch64.txt
new file mode 100644
index 0000000000..66c7676cda
--- /dev/null
+++ b/library/cpp/disjoint_sets/CMakeLists.linux-aarch64.txt
@@ -0,0 +1,18 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(library-cpp-disjoint_sets)
+target_link_libraries(library-cpp-disjoint_sets PUBLIC
+  contrib-libs-linux-headers
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(library-cpp-disjoint_sets PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/disjoint_sets/disjoint_sets.cpp
+)
diff --git a/library/cpp/disjoint_sets/CMakeLists.linux-x86_64.txt b/library/cpp/disjoint_sets/CMakeLists.linux-x86_64.txt
new file mode 100644
index 0000000000..66c7676cda
--- /dev/null
+++ b/library/cpp/disjoint_sets/CMakeLists.linux-x86_64.txt
@@ -0,0 +1,18 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(library-cpp-disjoint_sets)
+target_link_libraries(library-cpp-disjoint_sets PUBLIC
+  contrib-libs-linux-headers
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(library-cpp-disjoint_sets PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/disjoint_sets/disjoint_sets.cpp
+)
diff --git a/library/cpp/disjoint_sets/CMakeLists.txt b/library/cpp/disjoint_sets/CMakeLists.txt
new file mode 100644
index 0000000000..f8b31df0c1
--- /dev/null
+++ b/library/cpp/disjoint_sets/CMakeLists.txt
@@ -0,0 +1,17 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+if (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "aarch64" AND NOT HAVE_CUDA)
+  include(CMakeLists.linux-aarch64.txt)
+elseif (CMAKE_SYSTEM_NAME STREQUAL "Darwin" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64")
+  include(CMakeLists.darwin-x86_64.txt)
+elseif (WIN32 AND CMAKE_SYSTEM_PROCESSOR STREQUAL "AMD64" AND NOT HAVE_CUDA)
+  include(CMakeLists.windows-x86_64.txt)
+elseif (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64" AND NOT HAVE_CUDA)
+  include(CMakeLists.linux-x86_64.txt)
+endif()
diff --git a/library/cpp/disjoint_sets/CMakeLists.windows-x86_64.txt b/library/cpp/disjoint_sets/CMakeLists.windows-x86_64.txt
new file mode 100644
index 0000000000..83a72be4c8
--- /dev/null
+++ b/library/cpp/disjoint_sets/CMakeLists.windows-x86_64.txt
@@ -0,0 +1,17 @@
+
+# This file was generated by the build system used internally in the Yandex monorepo.
+# Only simple modifications are allowed (adding source-files to targets, adding simple properties
+# like target_include_directories). These modifications will be ported to original
+# ya.make files by maintainers. Any complex modifications which can't be ported back to the
+# original buildsystem will not be accepted.
+
+
+
+add_library(library-cpp-disjoint_sets)
+target_link_libraries(library-cpp-disjoint_sets PUBLIC
+  contrib-libs-cxxsupp
+  yutil
+)
+target_sources(library-cpp-disjoint_sets PRIVATE
+  ${CMAKE_SOURCE_DIR}/library/cpp/disjoint_sets/disjoint_sets.cpp
+)
diff --git a/library/cpp/disjoint_sets/disjoint_sets.cpp b/library/cpp/disjoint_sets/disjoint_sets.cpp
new file mode 100644
index 0000000000..5720e6c41a
--- /dev/null
+++ b/library/cpp/disjoint_sets/disjoint_sets.cpp
@@ -0,0 +1 @@
+#include "disjoint_sets.h"
diff --git a/library/cpp/disjoint_sets/disjoint_sets.h b/library/cpp/disjoint_sets/disjoint_sets.h
new file mode 100644
index 0000000000..5768886704
--- /dev/null
+++ b/library/cpp/disjoint_sets/disjoint_sets.h
@@ -0,0 +1,81 @@
+#pragma once
+
+#include <util/system/yassert.h>
+#include <util/generic/vector.h>
+
+// Implementation of disjoint-set data structure with union by rank and path compression.
+// See http://en.wikipedia.org/wiki/Disjoint-set_data_structure
+class TDisjointSets {
+public:
+    using TElement = size_t;
+
+private:
+    mutable TVector<TElement> Parents;
+    TVector<size_t> Ranks;
+    TVector<size_t> Sizes;
+    size_t NumberOfSets;
+
+public:
+    TDisjointSets(size_t setCount)
+        : Parents(setCount)
+        , Ranks(setCount, 0)
+        , Sizes(setCount, 1)
+        , NumberOfSets(setCount)
+    {
+        for (size_t i = 0; i < setCount; ++i)
+            Parents[i] = i;
+    }
+
+    TElement CanonicSetElement(TElement item) const {
+        if (Parents[item] != item)
+            Parents[item] = CanonicSetElement(Parents[item]);
+        return Parents[item];
+    }
+
+    size_t SizeOfSet(TElement item) const {
+        return Sizes[CanonicSetElement(item)];
+    }
+
+    size_t InitialSetCount() const {
+        return Parents.size();
+    }
+
+    size_t SetCount() const {
+        return NumberOfSets;
+    }
+
+    void UnionSets(TElement item1, TElement item2) {
+        TElement canonic1 = CanonicSetElement(item1);
+        TElement canonic2 = CanonicSetElement(item2);
+        if (canonic1 == canonic2)
+            return;
+
+        --NumberOfSets;
+        if (Ranks[canonic1] < Ranks[canonic2]) {
+            Parents[canonic1] = canonic2;
+            Sizes[canonic2] += Sizes[canonic1];
+        } else {
+            Parents[canonic2] = canonic1;
+            Sizes[canonic1] += Sizes[canonic2];
+            Ranks[canonic2] += Ranks[canonic1] == Ranks[canonic2] ? 1 : 0;
+        }
+    }
+
+    void Expand(size_t setCount) {
+        if (setCount < Parents.size()) {
+            return;
+        }
+
+        size_t prevSize = Parents.size();
+        Parents.resize(setCount);
+        Ranks.resize(setCount);
+        Sizes.resize(setCount);
+        NumberOfSets += setCount - prevSize;
+
+        for (size_t i = prevSize; i < setCount; ++i) {
+            Parents[i] = i;
+            Ranks[i] = 0;
+            Sizes[i] = 1;
+        }
+    }
+};
diff --git a/library/cpp/disjoint_sets/ya.make b/library/cpp/disjoint_sets/ya.make
new file mode 100644
index 0000000000..2104298baa
--- /dev/null
+++ b/library/cpp/disjoint_sets/ya.make
@@ -0,0 +1,7 @@
+LIBRARY()
+
+SRCS(
+    disjoint_sets.cpp
+)
+
+END()