# Path: pyalgs/algorithms/commons/union_find.py
# class UnionFind(object):
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def union(self, v, w):
#         pass
# 
#     @abstractmethod
#     def connected(self, v, w):
#         pass
# 
#     @staticmethod
#     def create(size):
#         return QuickUnion(size)
# 
# class QuickFind(UnionFind):
#     id = None
# 
#     def __init__(self, capacity):
#         self.id = [i for i in range(capacity)]
# 
#     def connected(self, v, w):
#         return self.id[v] == self.id[w]
# 
#     def union(self, v, w):
#         p = self.id[v]
#         q = self.id[w]
# 
#         if p != q:
#             for i in range(len(self.id)):
#                 if self.id[i] == p:
#                     self.id[i] = q
# 
# class QuickUnion(UnionFind):
#     id = None
#     sizes = None
# 
#     def __init__(self, capacity):
#         self.id = [i for i in range(capacity)]
#         self.sizes = [1] * capacity
# 
#     def root(self, v):
#         while v != self.id[v]:
#             self.id[v] = self.id[self.id[v]]  # path compression
#             v = self.id[v]
#         return v
# 
#     def connected(self, v, w):
#         return self.root(v) == self.root(w)
# 
#     def union(self, v, w):
#         vroot = self.root(v)
#         wroot = self.root(w)
# 
#         if self.sizes[vroot] > self.sizes[wroot]:
#             self.id[wroot] = vroot
#             self.sizes[vroot] += self.sizes[wroot]
#         else:
#             self.id[vroot] = wroot
#             self.sizes[wroot] += self.sizes[vroot]


import unittest
from pyalgs.algorithms.commons.union_find import UnionFind, QuickFind, QuickUnion



class UnionFindUnitTest(unittest.TestCase):
    def test_find(self):
        uf = UnionFind.create(10)

        uf.union(1, 3)
        uf.union(2, 4)
        uf.union(1, 5)

        self.assertTrue(uf.connected(1, 3))
        self.assertTrue(uf.connected(3, 5))
        self.assertFalse(uf.connected(1, 2))
        self.assertFalse(uf.connected(1, 4))


class QuickFindUnitTest(unittest.TestCase):
    def test_find(self):
        uf = QuickFind(10)

        uf.union(1, 3)

# Path: pyalgs/algorithms/commons/union_find.py
# class UnionFind(object):
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def union(self, v, w):
#         pass
# 
#     @abstractmethod
#     def connected(self, v, w):
#         pass
# 
#     @staticmethod
#     def create(size):
#         return QuickUnion(size)
# 
# class QuickFind(UnionFind):
#     id = None
# 
#     def __init__(self, capacity):
#         self.id = [i for i in range(capacity)]
# 
#     def connected(self, v, w):
#         return self.id[v] == self.id[w]
# 
#     def union(self, v, w):
#         p = self.id[v]
#         q = self.id[w]
# 
#         if p != q:
#             for i in range(len(self.id)):
#                 if self.id[i] == p:
#                     self.id[i] = q
# 
# class QuickUnion(UnionFind):
#     id = None
#     sizes = None
# 
#     def __init__(self, capacity):
#         self.id = [i for i in range(capacity)]
#         self.sizes = [1] * capacity
# 
#     def root(self, v):
#         while v != self.id[v]:
#             self.id[v] = self.id[self.id[v]]  # path compression
#             v = self.id[v]
#         return v
# 
#     def connected(self, v, w):
#         return self.root(v) == self.root(w)
# 
#     def union(self, v, w):
#         vroot = self.root(v)
#         wroot = self.root(w)
# 
#         if self.sizes[vroot] > self.sizes[wroot]:
#             self.id[wroot] = vroot
#             self.sizes[vroot] += self.sizes[wroot]
#         else:
#             self.id[vroot] = wroot
#             self.sizes[wroot] += self.sizes[vroot]


# Path: tests/algorithms/commons/union_find_unit_test.py
import unittest
from pyalgs.algorithms.commons.union_find import UnionFind, QuickFind, QuickUnion




class UnionFindUnitTest(unittest.TestCase):
    def test_find(self):
        uf = UnionFind.create(10)

        uf.union(1, 3)
        uf.union(2, 4)
        uf.union(1, 5)

        self.assertTrue(uf.connected(1, 3))
        self.assertTrue(uf.connected(3, 5))
        self.assertFalse(uf.connected(1, 2))
        self.assertFalse(uf.connected(1, 4))


class QuickFindUnitTest(unittest.TestCase):
    def test_find(self):
        uf = QuickFind(10)

        uf.union(1, 3)

        uf.union(2, 4)