Quick-union (lazy approach)

#include "pch.h"
#include <iostream>
#include <crtdbg.h>
#include <span>
#include<tuple>


import unionfind;
import nodes;
import utilitytest;
import unionfindtest;



class QuickUnionTest : public ::testing::Test {
protected:
	std::unique_ptr<UnionFind> m_unionFind;
	OneBasedArray oneBasedArray;
	ZeroBasedArray zeroBasedArray;
	
public:


	virtual void SetUp() override
	{
		int size = 8;
		m_unionFind = std::make_unique <QuickUnion>(size, oneBasedArray);
		m_unionFind->initialize();

	}



	virtual void TearDown() override
	{

	}

};




TEST_F(QuickUnionTest, testUnion3and7)
{
	MemoryLeakDetector leakDetector;
	m_unionFind->union_nodes(3, 7);
	int expected[] = { 1, 2, 7, 4, 5, 6, 7, 8 };
	const std::vector<int>& values = m_unionFind->getAllValues();
	assert_that(values, expected);

}


TEST_F(QuickUnionTest, testMultipleUnion)
{
	MemoryLeakDetector leakDetector;
	unionlistOfNodes(m_unionFind.get(), {{3,7},{2,5},{2,3},{3,6},{1,4},{8,1},{4,7}});
	int expected[] = { 4, 5, 7, 6, 7, 6, 6, 4 };
	const std::vector<int>& values = m_unionFind->getAllValues();
	assert_that(values, expected);

}



TEST_F(QuickUnionTest, testMultipleUnion_pathCompressionWith2Nodes)
{
	MemoryLeakDetector leakDetector;
	std::unique_ptr<QuickUnion> quickUnion;
	constexpr int size = 2;
	ZeroBasedArray zeroBasedArray;
	quickUnion = std::make_unique <QuickUnion>(size, zeroBasedArray);

	quickUnion->setRootpathCompressionWithSinglePass;

	std::vector<int> values = { 0, 1 };

	quickUnion->setAllValuesmove(values);

	quickUnion->union_nodes(0, 1);

	int expected[size] = { 1, 1 };
	const std::vector<int>& newValues = quickUnion->getAllValues();
	printAll(newValues);
	assert_that(newValues, expected);

}

#include "pch.h"
#include <functional>

export  module unionfind:quickunion;

import :uf;
import nodes;


using rootFunction = std::function<int(Nodes &, int)>;


export class QuickUnion : public UnionFind {
	
	rootFunction root_fn;

public:
	
	class RootFunctions {
	public:
		static int root(Nodes& nodes, int a)
		{
			for (; nodes[a] != a; a = nodes[a]);
			return a;
		}

		static int pathCompressionWithSinglePass(Nodes& nodes, int a)
		{
			for (; nodes[a] != a; nodes[a] = nodes[nodes[a]], a = nodes[a]);
			return a;
		}

		static int pathCompressionWithDoublePass(Nodes& nodes, int a)
		{
			int r = root(nodes, a);
			while ( r != a)
			{
				int parent = nodes[a];
				nodes[a] = r;
				a = parent;
			}
			return a;
		}


	};
	
	
	virtual ~QuickUnion() = default;

	QuickUnion(const int size, ArrayType& arrayType) :UnionFind(size, arrayType)
	{
		root_fn = RootFunctions::root;
	}

	virtual int getValue(const int index)
	{
		return m_nodes[index];
	}

	void setRoot(rootFunction rf)
	{
		root_fn = rf;
	}

	virtual int root(  int a)
	{
		return root_fn(m_nodes, a);
	}


	virtual void union_nodes(
		const int a, 
		const int b
		)
	{
		const int i = root( a );
		const int j = root( b );
		m_nodes.set(m_nodes.get(i), j);
	}

	virtual int depth(int a)
	{
		int depthOfNode = 1;
		for ( ; m_nodes[a] != a; a = m_nodes[a], depthOfNode++ );
		return depthOfNode;
	}

	virtual int maxDepth()
	{
		int depthestNode;
		for (int i = m_nodes.firstIndex(); i <= m_nodes.lastIndex(); i++)
			depthestNode = std::max( depthestNode, depth(i) );

		return depthestNode;
	}

};