# Path: unionfind/quickfind.py
# class QuickFind(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def parent(self, index):
#         return self.arr[index]
# 
#     def connect(self, item1, item2):
#         pid1 = self.arr[item1]
#         pid2 = self.arr[item2]
# 
#         for i in xrange(self.n):
#             if self.arr[i] == pid2:
#                 self.arr[i] = pid1
# 
# Path: unionfind/quickunion.py
# class QuickUnion(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         self.arr[pid2] = pid1
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         return current_item
# 
# Path: unionfind/weightedquickunion.py
# class WeightedQuickUnion(QuickUnion):
# 
#     def __init__(self, n):
#         QuickUnion.__init__(self, n)
#         self.item_counts = [1] * n
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         if self.item_counts[pid1] > self.item_counts[pid2]:
#             self.arr[pid2] = pid1
#             self.item_counts[pid1] += self.item_counts[pid2]
#         else:
#             self.arr[pid1] = pid2
#             self.item_counts[pid2] += self.item_counts[pid1]
# 
# Path: unionfind/wquwithpathcompression.py
# class WQUWithPathCompression(WeightedQuickUnion):
# 
#     def __init__(self, n):
#         WeightedQuickUnion.__init__(self, n)
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         update_index = index
#         while self.arr[update_index] != current_item:
#             parent_index = self.arr[update_index]
#             self.arr[update_index] = current_item
#             update_index = parent_index
# 
#         return current_item


from unittest import TestCase
from unionfind.quickfind import QuickFind
from unionfind.quickunion import QuickUnion
from unionfind.weightedquickunion import WeightedQuickUnion
from unionfind.wquwithpathcompression import WQUWithPathCompression
__author__ = 'orhan'



class UnionFindTests():

    def test_initial(self):
        self.assertEqual(self.algorithm.parent(1), 1)

    def test_simple_connect(self):
        self.algorithm.connect(1, 2)
        self.assertTrue(self.algorithm.isConnected(1, 2))

    def test_multiple_connect(self):
        self.algorithm.connect(1, 2)
        self.algorithm.connect(3, 4)
        self.assertTrue(not self.algorithm.isConnected(2, 3))
        self.algorithm.connect(1, 4)
        self.assertTrue(self.algorithm.isConnected(2, 3))
        self.assertTrue(self.algorithm.isConnected(2, 4))
        self.assertTrue(not self.algorithm.isConnected(2, 9))


class QuickFindTests(UnionFindTests, TestCase):

    def setUp(self):

# Path: unionfind/quickfind.py
# class QuickFind(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def parent(self, index):
#         return self.arr[index]
# 
#     def connect(self, item1, item2):
#         pid1 = self.arr[item1]
#         pid2 = self.arr[item2]
# 
#         for i in xrange(self.n):
#             if self.arr[i] == pid2:
#                 self.arr[i] = pid1
# 
# Path: unionfind/quickunion.py
# class QuickUnion(UnionFind):
# 
#     def __init__(self, n):
#         UnionFind.__init__(self, n)
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         self.arr[pid2] = pid1
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         return current_item
# 
# Path: unionfind/weightedquickunion.py
# class WeightedQuickUnion(QuickUnion):
# 
#     def __init__(self, n):
#         QuickUnion.__init__(self, n)
#         self.item_counts = [1] * n
# 
#     def connect(self, item1, item2):
#         pid1 = self.parent(item1)
#         pid2 = self.parent(item2)
#         if self.item_counts[pid1] > self.item_counts[pid2]:
#             self.arr[pid2] = pid1
#             self.item_counts[pid1] += self.item_counts[pid2]
#         else:
#             self.arr[pid1] = pid2
#             self.item_counts[pid2] += self.item_counts[pid1]
# 
# Path: unionfind/wquwithpathcompression.py
# class WQUWithPathCompression(WeightedQuickUnion):
# 
#     def __init__(self, n):
#         WeightedQuickUnion.__init__(self, n)
# 
#     def parent(self, index):
#         current_item = index
#         while self.arr[current_item] != current_item:
#             current_item = self.arr[current_item]
# 
#         update_index = index
#         while self.arr[update_index] != current_item:
#             parent_index = self.arr[update_index]
#             self.arr[update_index] = current_item
#             update_index = parent_index
# 
#         return current_item


# Path: tests/unionfind/unionfind_test.py
from unittest import TestCase
from unionfind.quickfind import QuickFind
from unionfind.quickunion import QuickUnion
from unionfind.weightedquickunion import WeightedQuickUnion
from unionfind.wquwithpathcompression import WQUWithPathCompression

__author__ = 'orhan'



class UnionFindTests():

    def test_initial(self):
        self.assertEqual(self.algorithm.parent(1), 1)

    def test_simple_connect(self):
        self.algorithm.connect(1, 2)
        self.assertTrue(self.algorithm.isConnected(1, 2))

    def test_multiple_connect(self):
        self.algorithm.connect(1, 2)
        self.algorithm.connect(3, 4)
        self.assertTrue(not self.algorithm.isConnected(2, 3))
        self.algorithm.connect(1, 4)
        self.assertTrue(self.algorithm.isConnected(2, 3))
        self.assertTrue(self.algorithm.isConnected(2, 4))
        self.assertTrue(not self.algorithm.isConnected(2, 9))


class QuickFindTests(UnionFindTests, TestCase):

    def setUp(self):

        self.algorithm = QuickFind(100)