Differential D16472 Diff 57552 source/blender/blenlib/BLI_disjoint_set.hh

Changeset View

Standalone View

source/blender/blenlib/BLI_disjoint_set.hh

	/* SPDX-License-Identifier: GPL-2.0-or-later */			/* SPDX-License-Identifier: GPL-2.0-or-later */

	#pragma once			#pragma once

	/** \file			/** \file
	* \ingroup bli			* \ingroup bli
	*			*
	* This implements the disjoint set data structure with path compression and union by rank.			* This implements the disjoint set data structure with path compression and union by rank.
	*/			*/

	#include "BLI_array.hh"			#include "BLI_array.hh"
				#include "BLI_index_range.hh"

	namespace blender {			namespace blender {

	class DisjointSet {			template<typename T = int64_t> class DisjointSet {
	private:			private:
	Array<int64_t> parents_;			Array<T> parents_;
	Array<int64_t> ranks_;			Array<T> ranks_;

	public:			public:
	/**			/**
	* Create a new disjoint set with the given size. Initially, every element is in a separate set.			* Create a new disjoint set with the given size. Initially, every element is in a separate set.
	*/			*/
	DisjointSet(int64_t size) : parents_(size), ranks_(size, 0)			DisjointSet(const int64_t size) : parents_(size), ranks_(size, 0)
	{			{
	BLI_assert(size >= 0);			BLI_assert(size >= 0);
	for (int64_t i = 0; i < size; i++) {			for (const int64_t i : IndexRange(size)) {
	parents_[i] = i;			parents_[i] = T(i);
	}			}
	}			}

	/**			/**
	* Join the sets containing elements x and y. Nothing happens when they have been in the same set			* Join the sets containing elements x and y. Nothing happens when they have been in the same set
	* before.			* before.
	*/			*/
	void join(int64_t x, int64_t y)			void join(const T x, const T y)
	{			{
	int64_t root1 = this->find_root(x);			T root1 = this->find_root(x);
	int64_t root2 = this->find_root(y);			T root2 = this->find_root(y);

	/* x and y are in the same set already. */			/* x and y are in the same set already. */
	if (root1 == root2) {			if (root1 == root2) {
	return;			return;
	}			}

	/* Implement union by rank heuristic. */			/* Implement union by rank heuristic. */
	if (ranks_[root1] < ranks_[root2]) {			if (ranks_[root1] < ranks_[root2]) {
	std::swap(root1, root2);			std::swap(root1, root2);
	}			}
	parents_[root2] = root1;			parents_[root2] = root1;

	if (ranks_[root1] == ranks_[root2]) {			if (ranks_[root1] == ranks_[root2]) {
	ranks_[root1]++;			ranks_[root1]++;
	}			}
	}			}

	/**			/**
	* Return true when x and y are in the same set.			* Return true when x and y are in the same set.
	*/			*/
	bool in_same_set(int64_t x, int64_t y)			bool in_same_set(const T x, const T y)
	{			{
	int64_t root1 = this->find_root(x);			T root1 = this->find_root(x);
	int64_t root2 = this->find_root(y);			T root2 = this->find_root(y);
	return root1 == root2;			return root1 == root2;
	}			}

	/**			/**
	* Find the element that represents the set containing x currently.			* Find the element that represents the set containing x currently.
	*/			*/
	int64_t find_root(int64_t x)			T find_root(const T x)
	{			{
	/* Find root by following parents. */			/* Find root by following parents. */
	int64_t root = x;			T root = x;
	while (parents_[root] != root) {			while (parents_[root] != root) {
	root = parents_[root];			root = parents_[root];
	}			}

	/* Compress path. */			/* Compress path. */
	while (parents_[x] != root) {			T to_root = x;
	int64_t parent = parents_[x];			while (parents_[to_root] != root) {
	parents_[x] = root;			const T parent = parents_[to_root];
	x = parent;			parents_[to_root] = root;
				to_root = parent;
	}			}

	return root;			return root;
	}			}
	};			};

	} // namespace blender			} // namespace blender