"""program to implement the basic operations of disjoint set."""
import time
import sys
t0=time.clock()
class DisjointSetNode:
    def __init__(self, value):
        self.value = value
        self.parent = self
        self.rank = 0

def find_set(x):
    if x != x.parent:
        x.parent = find_set(x.parent)
    return x.parent

def union(x, y):
    link(find_set(x), find_set(y))

def link(x, y):
    if x.rank > y.rank:
        y.parent = x
    else:
        x.parent = y
        if x.rank == y.rank:
            y.rank = y.rank + 1
            
def test(small,big):
    small_list = test_build_list(small)
    big_list = test_build_list(big)

    test_union(small_list)
    test_union(big_list)

    print "Small Letters"
    test_print_parents(small_list)

    print
    print "Big Letters"
    test_print_parents(big_list)

    union(small_list[0], big_list[0])
    print
    print "Unioned Letters"
    test_print_parents(small_list)
    test_print_parents(big_list)

def test_build_list(values):
    result = []
    for v in values:
        result.append(DisjointSetNode(v))
    return result

def test_union(nodes):
    N = len(nodes)
    n = N / 2
    for i in range(n-1):
        union(nodes[i+1], nodes[i])
    for i in range(n, N-1):
        union(nodes[i], nodes[i+1])
    union(nodes[0], nodes[N-1])
    

def test_print_parents(list_of_nodes):
    for x in list_of_nodes:
        original_parent = x.parent.value
        set_parent = find_set(x)
        after_parent = x.parent.value
        print "Value:", x.value,
        w.write('\n'+"value"+repr(x.value))
        print "OriginalParent:", original_parent
        w.write('\n'+'originalparent:'+repr(original_parent))
        print "ParentAfterPathComparession:", after_parent
        w.write('\n'+'afterparent'+repr(after_parent))
        

a=[]
b=[]
fi=open("in_sec21_8.txt",'r')
w=open("out_18_sec21_8.txt",'w')
count=0
for row in fi:
    if count==0:
            a.append(row)
print a
test(a[0],a[1])
t1=time.clock()
t2=t1-t0
mem=sys.getsizeof(t1)+sys.getsizeof(t0)+sys.getsizeof(t2)+sys.getsizeof(count)+60
print t2
w.write('\n'+'time used by program='+repr(t2))
w.write('\n'+'memeory used='+repr(mem))
print mem