try:
    import xml.etree.cElementTree as ET
except ImportError:
    import xml.etree.ElementTree as ET

def get_parent_map(root):
	return dict((c, p) for p in root.getiterator() for c in p)

def parent(root, element):
	parent_map = get_parent_map(root)
	return parent_map[element]

def compare_element(lhs, rhs):
	return lhs.tag < rhs.tag

def diff(old, new):
	add = []
	modify = []
	remove = []
	for key in old:
		if key in new:
			if old[key] != new[key]:
				modify.append(key)
		else:
			remove.append(key)
	for key in new:
		if key not in old:
			add.append(key)

	return (add, remove, modify);

def find_tag(tag, elements):
	for element in elements:
		if tag == element.tag:
			return True

	return False

def diffchildren(old, new):
	old_local = old[0:]
	new_local = new[0:]

	add = []
	remove = []
	move = []

	for child in old_local:
		if not find_tag(child.tag, new_local):
			remove.append(child)

	for child in remove:
		old_local.remove(child)

	for child in new_local:
		if not find_tag(child.tag, old_local):
			add.append(child)

	for child in add:
		new_local.remove(child)

	for index in range(len(old_local)):
		if old_local[index].tag != new_local[index].tag:
			move.append(old_local[index])

	old_local.sort(compare_element)
	new_local.sort(compare_element)

	return (add, remove, move, (old_local, new_local))

class MyElementTree(ET.ElementTree):
	def __init__(self, root):
		ET.ElementTree.__init__(self, root)
		self.parent_map = get_parent_map(self.getroot())
		self.parent_map[self.getroot()] = None

	def parent(self, element):
		return self.parent_map[element]

	def path(self, element):
		path = []
		current = element
		while ET.iselement(current) :
			path.append(current)
			current = self.parent_map[current]
		path.reverse()
		return path

	def compare(self, other, visitor):
		self.compare_element(self.getroot(), other.getroot(), visitor)

	def compare_element(self, self_element, other_element, visitor):
		if self_element.tag != other_element.tag:
			return

		(attribAdd, attribRemove, attribModify) = diff(self_element.attrib, other_element.attrib)

		path = self.path(self_element)

		if len(attribAdd) != 0:
			visitor.attribAdd(path, other_element, attribAdd)

		if len(attribRemove) != 0:
			visitor.attribRemove(path, self_element, attribRemove)

		if len(attribModify) != 0:
			visitor.attribModify(path, self_element, other_element, attribModify)

		(childElementAdd, childElementRemove, childElementMove, (sameOldChildren, sameNewChildren)) \
		= diffchildren(self_element.getchildren(), other_element.getchildren())

		if len(childElementAdd) != 0:
			visitor.childElementAdd(path, other_element, childElementAdd)

		if len(childElementRemove) != 0:
			visitor.childElementRemove(path, self_element, childElementRemove)

		if len(childElementMove) != 0:
			visitor.childElementMove(path, self_element, other_element, childElementMove)

		for index in range(len(sameOldChildren)):
			self.compare_element(sameOldChildren[index], sameNewChildren[index], visitor)	

def xml_compare_with_visitor(lhs, rhs, visitor):
	lhs.compare(rhs, visitor)




