ocarina/libsaria/trees.py

# Bryan Schumaker (11/06/2010)

from libsaria.path import files
from libsaria.path import sep

class Tree(dict):
	def __init__(self):
		dict.__init__(self)

	def __len__(self):
		count = 0;
		for path in self.walk():
			count += 1
		return count

	def __disp__(self, child, level):
		return "%s", child

	def disp(self, level = 0):
		for child in self:
			space     = "  " * level
			fmt, vals = self.__disp__(child, level)
			print space, fmt % vals
			self[child].disp(level + 1)

	def walk(self):
		keys = self.keys()
		keys.sort()

		for key in keys:
			child = self[key]
			if len(child.keys()) == 0:
				yield [key]
				continue
			for res in child.walk():
				yield [key] + res

	def __insert__(self, path):
		path_part = path[0]
		child     = self.get(path_part, None)
		if child == None:
			child = self.__class__()
			self[path_part] = child
		return child

	def insert(self, path):
		child = self.__insert__(path)
		if len(path) > 1:
			child.insert(path[1:])

	def lookup(self, path):
		child = self.get(path[0], None)
		if child == None:
			return child
		if len(path) > 1:
			return child.lookup(path[1:])
		return child.keys()

	def lookup_child(self, path):
		child = self.get(path[0], None)
		if child == None:
			return child
		if len(path) > 1:
			return child.lookup_child(path[1:])
		return child


class DLTree(Tree):
	def __init__(self):
		Tree.__init__(self)
		self.parent = None

	def walk_backwards(self, child = None):
		key = None
		if child != None:
			idc = id(child)
			key = [i[0] for i in self.items() if id(i[1]) == idc]
			if self.parent == None:
				return key
		ret = self.parent.walk_backwards(self)
		if key:
			return ret + key
		else:
			return ret

	def insert(self, path):
		child = self.__insert__(path)
		child.parent = self
		if len(path) > 1:
			return child.insert(path[1:])
		return child


class FSTree(Tree):
	def __init__(self):
		Tree.__init__(self)

	def walk_paths(self):
		for path in self.walk():
			yield sep.join(path)

	def insert_path(self, base, file = None):
		path = base.split(sep)
		self.insert_path_split(path, file)

	def insert_path_split(self, base, file = None):
		if file == None:
			self.insert(base)
		else:
			self.insert(base + [file])


class DLFSTree(DLTree, FSTree):
	def __init__(self):
		DLTree.__init__(self)
		FSTree.__init__(self)

	def walk_path_backwards(self):
		return sep.join( self.walk_backwards() )

	def insert_path(self, base, file = None):
		path = base.split(sep)
		return self.insert_path_split(path, file)

	def insert_path_split(self, base, file = None):
		if file == None:
			child = self.insert(base)
		else:
			child = self.insert(base + [file])
		return child


class ValTree(Tree):
	def __init__(self):
		Tree.__init__(self)
		self.value = None

	def __disp__(self, child, level):
		return "%s (%s)", (child, self[child].value)

	def __walk_vals__(self, path):
		node = self
		res  = []
		for key in path:
			node = node[key]
			res.append(node.value)
		return res

	def walk_vals(self):
		for path in self.walk():
			yield self.__walk_vals__(path)

	def insert(self, path, values):
		child = self.__insert__(path)
		if len(values) > 0:
			child.value = values[0]
			vals = values[1:]
		else:
			vals = values
		if len(path) > 1:
			child.insert(path[1:], values[1:])


class DLValTree(DLTree, ValTree):
	def __init__(self):
		DLTree.__init__(self)
		ValTree.__init__(self)

	def walk_vals_backwards(self, child = None):
		key = None
		if child != None:
			idc = id(child)
			key = [i[0] for i in self.items() if id(i[1]) == idc]
			if self.parent == None:
				return [self[key[0]].value]
		ret = self.parent.walk_vals_backwards(self)
		if key:
			return ret + [self[key[0]].value]
		else:
			return ret

	def insert(self, path, values):
		child = self.__insert__(path)
		child.parent = self
		if len(values) > 0:
			child.value = values[0]
			vals = values[1:]
		else:
			vals = values
		if len(path) > 1:
			return child.insert(path[1:], vals)
		return child