#!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: spalakod@purdue.edu

#Each Set is represented by a linked list. 

valueNodeDict = {}

class Node():
	'''Represents a node of the linked list'''
	
	def __init__(self, value, parent, next=None):
		self.value = value
		self.next = next
		self.parent = parent
		valueNodeDict[value] = self
	
	def __str__(self):
		return str(self.value)


class List():
	'''Represents the linked list itself'''

	def __init__(self, name, value=None):
		'''Creates a set and sets head and tail to the appropriate nodes'''
		self.name = name
		self.count = 0
		if value is None:
			self.head = None
			self.tail = None
			
		else:
			self.head = Node(value, self)
			self.tail = self.head 
			self.count += 1


	def __str__(self):
		'''Lists out all the elements'''
		s = self.name + ": "
		node = self.head
		while node != None:
			s += str(node) + ", "
			node = node.next
		return s + "\n"
	
	def addElement(self, node):
		'''Add another node'''
		self.tail.next = node
		self.tail = self.tail.next
		self.count += 1

	def changeParent(self, newParent):
		'''Changes the parent of every node in the set'''
		node = self.head
		while node is not None:
			node.parent = newParent
			node = node.next
	
	
	
class Universe():
	'''Operations you can perform in the universe'''
	def __init__(self, name="U"):
		'''Creates the universe where all your subsequent sets belong'''
		self.name = name
		self.setCount = 0
		self.sets = []
	
	def __str__(self):
		s = self.name + ":\n"
		for set in self.__sets:
			s += "\t" + str(set) + "\n"
		return s

	def addSet(self, name=None, value=None):
		'''Adds a set to the universe'''
		if name is None:
			self.__sets.append(List("S"+str(self.setCount), value))
			self.setCount += 1
		else:
			self.__sets.add(List(name, value))

U = Universe()

def MakeSet(x, name=None):
	'''Makes a new Linked List'''
	U.addSet(name, x)

def FindSet(x):
	'''Find The Set This Node Belongs To'''
	return valueNodeDict[x].parent

def Union(x, y):
	'''Destructively Perform The Union'''
	if valueNodeDict[x].parent is not valueNodeDict[y].parent:
		x_set = valueNodeDict[x].parent
		y_set = valueNodeDict[y].parent

		if x_set.count < y_set.count:
			#x gets appended to y
			y_set.count += x_set.count
			x_set.changeParent(y_set)
			y_set.tail.next = x_set.head
			y_set.tail = x_set.tail
			U.sets.remove(x_set)
		else:
			#y gets appended to x
			x_set.count += y_set.count
			y_set.changeParent(x_set)
			x_set.tail.next = y_set.head
			x_set.tail = y_set.tail
			U.sets.remove(y_set)

if __name__ == "__main__":
	a = [1, 2, 3, 4, 5, 6, 7, 8]
	for i in a:
		MakeSet(i)
	print U

	Union(1 , 2)

	print U

	Union(2, 3)

	print U

	Union(4, 5)

	print U

	Union(3, 4)

	print U