class Node:	
	def __init__(self):
		self.labelIndex = -1
		self.name = 'Top'
		self.children = []
		self.parent = -1		
		self.subsize = 0
		self.depth = 0
		self.level = 0
	
	def get_all_node_ids(self, name_2_id, cache):
		cache.append(self.name)
		if self.labelIndex != -1:			
			name_2_id['\\'.join(cache[1:])] = self.labelIndex			
		for c in self.children:			
			c.get_all_node_ids(name_2_id, cache)
		cache.pop()
			
	def get_all_node_ids_label_id(self, name_2_id, cache):
		cache.append(str(self.labelIndex))
		if self.labelIndex != -1:			
			name_2_id['\\'.join(cache[1:])] = self.labelIndex			
		for c in self.children:			
			c.get_all_node_ids_label_id(name_2_id, cache)
		cache.pop()
		
	def get_all_node_ids_2(self, id_paths, cache):
		cache.append(str(self.labelIndex))
		if self.labelIndex != -1:			
			id_paths.append('/'.join(cache[1:]))
		for c in self.children:			
			c.get_all_node_ids_2(id_paths, cache)
		cache.pop()
		
	def sort_label_ids(self, old_2_new_mapper, new_2_old_mapper):
		q = []
		for ch in self.children:
			q.append(ch)
		id = 0
		while q != []:
			nd = q.pop(0)
			#record mapping
			old_2_new_mapper[nd.labelIndex] = id
			new_2_old_mapper[id] = nd.labelIndex
			#change label 
			nd.labelIndex = id
			id += 1
			for ch in nd.children:
				q.append(ch)			
		
	def add(self, child):
		self.children.append(child)
		child.parent = self
		child.depth = self.depth + 1
	
	def find_child(self, nm):
		for c in self.children:
			if c.name == nm:
				return c
		return -1
						
	def get_tree_size(self):
		sum = 1
		for i in self.children:
			sum += i.get_tree_size()
		self.subsize = sum
		return sum
	
	def get_each_subtree_size(self, sub_sizes):
		sum = 1
		for i in self.children:
			v = i.get_each_subtree_size(sub_sizes)
			sub_sizes[i.labelIndex] = v
			sum += v
		self.subsize = sum
		return sum
		
	def get_subtree_size(self):
		for c in self.children:
			c.subsize = c.get_tree_size()
		
	def get_subtree_weight(self,weight):
		for c in self.children:
			ratio = float(c.subsize) / c.parent.subsize
			weight[c.labelIndex] = ratio
			c.get_subtree_weight(weight)
	
	def read_dmoz_tree(self, file):
		root = Node()
		fd = open(file)
		for line in fd:
			line = line.replace('\n', '')
			line = line.split('\t')
			path = line[0]
			id = line[1]
			path = path.split('/')
			nd = root
			for p in path:
				ret = nd.find_child(p)
				if ret == -1:
					t_nd = Node()
					t_nd.labelIndex = int(id)
					t_nd.name = p
					nd.add(t_nd)
					nd = t_nd
				else:
					nd = ret
		fd.close()
		return root
	
	def read_dmoz_ontology_tree(self, file):
		#create nodes
		nodes = []
		for i in range(100000):
			nd = Node()
			nd.labelIndex = i-1
			nodes.append(nd)				
		fd = open(file)		
		for line in fd:
			labels = line.strip().split('\t')	
			parent = int(labels[0])
			child = int(labels[1])			
			nodes[parent].add(nodes[child])
		fd.close()
		return nodes[0]
		
	def read_ohsumed_tree(self, file):
		fd= open(file)
		id = 0
		top = Node()		
		for line in fd:
			line = line.replace('\n', '')
			line = line.split('\\')
			nd = top
			for l in line:
				c = nd.find_child(l)
				if c == -1:
					new_nd = Node()
					new_nd.labelIndex = id
					new_nd.name = l
					nd.add(new_nd)
					nd = new_nd
				else:
					nd = c					
			id += 1
 		fd.close()
		return top
		
	def read_wipo_tree(self, file, max_depth):
		root = Node()
		fd = open(file)
		id = 0
		for line in fd:
			line = line.strip()								
			path = line.split('\\')
			nd = root
			for p in path[:max_depth]:				
				ret = nd.find_child(p)
				if ret == -1:
					t_nd = Node()
					t_nd.labelIndex = int(id)
					id += 1
					t_nd.name = p
					nd.add(t_nd)
					nd = t_nd
				else:
					nd = ret
		fd.close()
		return root
		
	def read_tree(self,file):
		#read all string
		fd=open(file)
		ct=fd.read()
		fd.close()
		#create nodes
		nodes = []
		for i in range(50000):
			nd = Node()
			nd.labelIndex = i-1
			nodes.append(nd)
		#begin parse		
		ct = ct.replace('#','')
		ct_nodes = ct.split('|')
		for n in ct_nodes:
			if n is not '' and n != '\n':
				ct_ns = n.split(',')	
				labelIndex = int(ct_ns[0])
				for id in ct_ns[1:(len(ct_ns)-1)]:
					nodes[labelIndex].add(nodes[int(id)])
		return nodes[0]	
	
	def read_parent_child_pair_tree(self, file):		
		#create nodes
		nodes = {}
		fd = open(file)
		for line in fd:
			line = line.replace('\n','')
			line = line.split(',')
			parent = int(line[0])
			child = int(line[1])
			if parent not in nodes:
				nd = Node()
				nd.labelIndex = parent
				nodes[parent] = nd
			if child not in nodes:
				nd = Node()
				nd.labelIndex = child
				nodes[child] = nd
			nodes[parent].add(nodes[child])
		fd.close()
		root = Node()
		roots = []
		for label in nodes.keys():
			if nodes[label].parent == -1:				
				roots.append(label)
		if len(roots) == 1:
			root = nodes[roots[0]]
		else:
			for label in roots:
				root.add(nodes[label])
		return root, nodes
	
	#added by xiao 06012012
	#get number of potencial subtrees expanded from root
	def get_total_subtrees(self):	
		if len(self.children) == 0:
			return 1
		else:
			p = 1
			for c in self.children:
				v = 1 + c.get_total_subtrees()
				p *= v
			return p
			
	def write_tree(self, file):
		q = [self]
		out_str = ''
		while q != []:
			top = q.pop(0)
			if top.children != []:
				out_str += str(top.labelIndex+1) + ','
				for nd in top.children:
					out_str += str(nd.labelIndex +1) + ','
					q.append(nd)
				out_str += '|'
		out_str += '#'
		fd = open(file,'w')
		fd.write(out_str)
		fd.close()

	def get_ancestor_nodes(self, ancestors):
		for c in self.children:
			n = c.parent
			while n.labelIndex is not -1:
				ancestors[c.labelIndex].append(n.labelIndex)
				n = n.parent
			c.get_ancestor_nodes(ancestors)
			
	def get_parents(self, parents):
		for c in self.children:
			parents[c.labelIndex] = c.parent.labelIndex
			c.get_parents(parents)
			
	def get_nodes_per_level(self, nodes):
		for c in self.children:
			nodes[c.depth].append(c.labelIndex)
			c.get_nodes_per_level(nodes)
	
	def get_nodes_per_level(self, depth, nodes):
		for c in self.children:
			nodes[depth].append(c.labelIndex)
			c.get_nodes_per_level(depth + 1, nodes)
			
	def get_max_level(self):
		level = 0
		for c in self.children:		
			if c.get_max_level() + 1 > level:
				level = c.get_max_level() + 1
		return level	
	
	def get_subtree_level(self):
		for c in self.children:
			c.level = c.get_max_level()			
			
	def get_leaves(self, leaves):
		for c in self.children:
			if c.children == []:
				leaves.append(c)
			else:
				c.get_leaves(leaves)
	
	def get_node_depth(self, depth_seq):
		for c in self.children:
			depth_seq[c.labelIndex] = c.depth
			c.get_node_depth(depth_seq)
		
	def find_leaves_in_list(self, st, leaves):	
		if self.labelIndex != -1:
			if self.labelIndex in st:				
				is_leaf = 1
				for c in self.children:
					if c.labelIndex in st:
						is_leaf = 0
						break
				if is_leaf == 1:
					leaves.add(self.labelIndex)				
				for c in self.children:
					c.find_leaves_in_list(st, leaves)
		else:
			for c in self.children:
				c.find_leaves_in_list(st, leaves)
	
def readUnlabeledDocIDs(file):
	fd=open('al_dmoz_unlabeled_doc_ids','r')
	undocids=set()
	for line in fd:
		line.replace('\n','')
		undocids.add(int(line))
	fd.close()
	return undocids
	
def writeUnlabeledDocIDs(in_doc_ids, selected_doc_ids, out_file):
	remain = in_doc_ids - selected_doc_ids
	fd = open(out_file, 'w')
	for x in remain:
		fd.write(x + '\n')