<commit_before># -*- coding: utf-8 -*-
# pylint: disable=W0212,C0111
# tree.py
# Copyright (c) 2014 <NAME>
# See LICENSE for details


import putil.check

###
# Node name custom pseudo-type
###
class NodeName(object):	#pylint: disable=R0903
	""" Hierarchical node name data type class """
	def includes(self, test_obj):	#pylint: disable=R0201,W0613
		"""	Test that an object belongs to the pseudo-type """
		return False if (not isinstance(test_obj, str)) or (isinstance(test_obj, str) and (' ' in test_obj)) else all([element.strip() != '' for element in test_obj.strip().split('.')])

	def istype(self, test_obj):	#pylint: disable=R0201
		"""	Checks to see if object is of the same class type """
		return isinstance(test_obj, str)

	def exception(self, param_name):	#pylint: disable=R0201,W0613
		"""	Returns a suitable exception message """
		exp_dict = dict()
		exp_dict['type'] = ValueError
		exp_dict['msg'] = 'Argument `{0}` is not a valid node name'.format(param_name)
		return exp_dict
putil.check.register_new_type(NodeName, 'Hierarchical node name')


class Tree(object):	#pylint: disable=R0903
	"""
	Provides basic trie (radix tree) functionality

	:rtype: :py:class:`putil.tree.Tree()` object
	"""
	def __init__(self):	#pylint: disable=R0913
		self._db = dict()
		self._root = None
		self._vertical = unichr(0x2502)
		self._vertical_and_right = unichr(0x251C)
		self._up_and_right = unichr(0x2514)
		#{'name':{'parent':None, 'children':None, 'data':data}}

	def __str__(self):
		u"""
		String with the tree structure 'pretty printed' as a character-based tree structure. Only node names are shown, nodes with data are marked with an asterisk (*). For example:

			>>> import putil.tree
			>>> tobj = putil.tree.Tree()
			>>> tobj.add([
			...		{'name':'root.branch1', 'data':5},
			...		{'name':'root.branch2', 'data':list()},
			...		{'name':'root.branch1.leaf1', 'data':list()},
			...		{'name':'root.branch1.leaf2', 'data':'Hello world!'}
			... ])
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			│└leaf2 (*)
			└branch2

		:rtype: Unicode string
		"""
		return self._prt(name=self.root_name, lparent=-1, sep='', pre1='', pre2='').encode('utf-8')

	def _collapse_node(self, name):
		""" Collapse a single node """
		while True:
			node = self._db[name]
			if (len(node['children']) == 1) and (not node['data']):
				child_name = node['children'][0]
				self._db[child_name]['parent'] = node['parent']
				self._db[self._db[name]['parent']]['children'].remove(name)
				self._db[self._db[name]['parent']]['children'] = sorted(self._db[self._db[name]['parent']]['children']+[child_name])
				del self._db[name]
				name = child_name
			else:
				break
		node = self._db[name]
		for name in node['children'][:]:
			self._collapse_node(name)

	def _get_nodes(self):	#pylint: disable=C0111
		return None if not self._db else sorted(self._db.keys())

	def _get_root_node(self):	#pylint: disable=C0111
		return None if not self.root_name else self.get_node(self.root_name)

	def _get_root_name(self):	#pylint: disable=C0111
		return self._root

	def _get_subtree(self, name):
		if self.is_leaf(name):
			return [name]
		children = self.get_children(name)
		ret = [name]
		for child in children:
			ret += self._get_subtree(child)
		return ret

	def _node_in_tree(self, name):	#pylint: disable=C0111
		if name not in self._db:
			raise RuntimeError('Node {0} not in tree'.format(name))

	def _prt(self, name, lparent, sep, pre1, pre2):	#pylint: disable=C0111,R0913,R0914
		# Characters from http://www.unicode.org/charts/PDF/U2500.pdf
		node_name = name[lparent+1:]
		#node_name = name.split('.')[-1]
		children = self._db[name]['children']
		ncmu = len(children)-1
		plist1 = ncmu*[self._vertical_and_right]+[self._up_and_right]
		plist2 = ncmu*[self._vertical]+[' ']
		slist = (ncmu+1)*[sep+pre2]
		dmark = ' (*)' if self._db[name]['data'] else ''
		return '\n'.join([u'{0}{1}{2}{3}'.format(sep, pre1, node_name, dmark)]+[self._prt(child, len(name), sep=schar, pre1=p1, pre2=p2) for child, p1, p2, schar in zip(children, plist1, plist2, slist)])

	def _rnode(self, root, name, hierarchy):	#pylint: disable=C0111,R0913,R0914
		suffix = name[len(root):]
		new_suffix = suffix.replace('.'+hierarchy, '').replace('..', '.')
		new_name = root+new_suffix
		if new_name != name:
			if not self.in_tree(new_name):
				self._db[new_name] = self._db[name].copy()
				self._db[self._db[name]['parent']]['children'] = sorted(list(set([child for child in self._db[self._db[name]['parent']]['children'] if child != name]+[new_name])))
			else:
				if self._db[name]['data']:
					raise RuntimeError('Hierarchy {0} cannot be deleted'.format(hierarchy))
				if self._db[name]['parent'] == new_name:
					self._db[self._db[name]['parent']]['children'] = sorted(list(set([child for child in self._db[self._db[name]['parent']]['children'] if child != name])))
				new_children = sorted(self._db[new_name]['children']+self._db[name]['children'])
				if len(new_children) != len(set(new_children)):
					raise RuntimeError('Inconsitency when deleting hierarchy')
				self._db[new_name]['children'] = new_children
			for child in self.get_children(name):
				self._db[child]['parent'] = new_name
			del self._db[name]
		for child in self.get_children(new_name):
			self._rnode(root, child, hierarchy)

	def _set_root_name(self, name):	#pylint: disable=C0111
		self._root = name

	def _split_node_name(self, name):	#pylint: disable=C0111,R0201
		return [element.strip() for element in name.strip().split('.')]

	@putil.check.check_argument(putil.check.PolymorphicType([{'name':NodeName(), 'data':putil.check.Any()}, putil.check.ArbitraryLengthList({'name':NodeName(), 'data':putil.check.Any()})]))
	def add(self, nodes):
		"""
		Add nodes to tree

		:param	nodes: Node(s) to add. Each dictionary must contain exactly two keys:

		 * **name** (*string*) node name

		 * **data** (*any*) node data.

		 If there are several list items in **nodes** with the same node name the resulting node data is a list with items corresponding to the data of each entry in **nodes** with the same node name, in their order \
		 of appearance, in addition to any existing node data if the node is already present in the tree.

		 The node data should be an empty list to create a node without data, for example: `{'node':'a.b.c', 'data':list()}`

		:type	nodes: dictionary or list of dictionaries

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('add')) ]]]
		.. [[[end]]]


		For example:

			>>> import putil.tree
			>>> tobj = putil.tree.Tree()
			>>> tobj.add([
			...		{'name':'root.branch1', 'data':5},
			...		{'name':'root.branch1', 'data':7},
			...		{'name':'root.branch2', 'data':list()},
			...		{'name':'root.branch1.leaf1', 'data':list()},
			...		{'name':'root.branch1.leaf1.subleaf1', 'data':333},
			...		{'name':'root.branch1.leaf2', 'data':'Hello world!'},
			...		{'name':'root.branch1.leaf2.subleaf2', 'data':list()},
			... ])
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.get_data('root.branch1')
			[5, 7]

		"""
		nodes = nodes if isinstance(nodes, list) else [nodes]
		if not self.root_name:
			self._set_root_name(nodes[0]['name'].split('.')[0].strip())
			self._db[self.root_name] = {'parent':'', 'children':list(), 'data':list()}
		for node_dict in nodes:
			name = node_dict['name']
			data = node_dict['data']
			if not self.in_tree(name):
				hierarchy = self._split_node_name(name)
				if hierarchy[0] != self.root_name:
					raise ValueError('Illegal node name: {0}'.format(name))
				for num in range(len(hierarchy)):
					child = '.'.join(hierarchy[:num+1])
					if not self.in_tree(child):
						parent = '.'.join(self._split_node_name(child)[:-1])
						self._db[child] = {'parent':parent, 'children':list(), 'data':list()}
						self._db[parent]['children'] = list(sorted(set(self._db[parent]['children']+[child])))
			data = data if isinstance(data, list) and (len(data) > 0) else (list() if isinstance(data, list) else [data])
			self._db[name]['data'] = self._db[name]['data']+data

	@putil.check.check_argument(NodeName())
	def collapse(self, name):
		"""
		Collapses hierarchy. Nodes that have a single child and no data are combined with their children.

		:param	name: Root of the sub-tree to collapse
		:type	name: string

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('collapse')) ]]]
		.. [[[end]]]


		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.collapse('branch1')
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1.subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2

		``root.branch1.leaf1`` is collapsed because it only has one child (``root.branch1.leaf1.subleaf1``) and no data; ``root.branch1.leaf2`` is not collapsed because although it has one child (``root.branch1.leaf2.subleaf2``) \
		it does have data associated with it, *'Hello world!'*
		"""
		self._node_in_tree(name)
		for child in self._db[name]['children'][:]:
			self._collapse_node(child)

	@putil.check.check_argument(putil.check.PolymorphicType([NodeName(), putil.check.ArbitraryLengthList(NodeName())]))
	def delete(self, nodes):
		"""
		Delete nodes (and their sub-trees) from tree

		:param	nodes: Node(s) to delete
		:type	nodes: string or list of strings

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('delete')) ]]]
		.. [[[end]]]

		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.delete(['root.branch1.leaf1', 'root.branch2'])
			>>> print str(tobj)
			root
			└branch1 (*)
			 └leaf2 (*)
			  └subleaf2

		"""
		nodes = nodes if isinstance(nodes, list) else [nodes]
		for node in nodes:
			self._node_in_tree(node)
			parent = self.get_node(node)['parent']
			# Delete link to parent (if not root node)
			del_list = self._get_subtree(node)
			if parent:
				self._db[parent]['children'] = [child for child in self._db[parent]['children'] if child != node]
			# Delete children (sub-tree)
			for child in del_list:
				del self._db[child]
			if not len(self._db):
				self._root = None

	@putil.check.check_argument(NodeName())
	def flatten_subtree(self, name):
		"""
		Flattens sub-trees below node names whose hierarchy ends at a particular hierarchy node and that contain no data

		:param	name: Ending hierarchy node whose sub-trees are to be flattened
		:type	name: string

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('delete')) ]]]
		.. [[[end]]]

		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> tobj.add([{'name':'root.branch1.leaf1.subleaf2', 'data':list()},
			...           {'name':'root.branch2.leaf1.another_subleaf1', 'data':list()},
			...           {'name':'root.branch2.leaf1.another_subleaf2', 'data':list()}
			...         ])
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││├subleaf1 (*)
			││└subleaf2
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			 └leaf1
			  ├another_subleaf1
			  └another_subleaf2
			>>> tobj.flatten_subtree('leaf1')
			root
			├branch1 (*)
			│├leaf1.subleaf1 (*)
			│├leaf1.subleaf2
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			 ├leaf1.another_subleaf1
			 └leaf1.another_subleaf2

		"""
		if len(name.split('.')) > 1:
			raise ValueError('Illegal ending hierarchy node name')
		for node in self._db.keys():
			hierarchy = self._split_node_name(node)
			if (hierarchy[-1] == name) and (not self.is_root(node)) and (not self.get_data(node)):
				parent = self._db[node]['parent']
				children = self._db[node]['children']
				for child in children:
					self._db[child]['parent'] = parent
				self._db[parent]['children'] = sorted([child for child in self._db[parent]['children'] if child != node]+children)
				del self._db[node]

	@putil.check.check_argument(NodeName())
	def get_node(self, name):	#pylint: disable=C0111
		"""
		Get tree node structure. The structure is a dictionary with the following keys:

		 * **parent** (*string*) Parent node name, *''* if node is the root node

		 * **children** (*list*) Children node names, empty list if node is a leaf

		 * **data** (*list*) Node data, empty list if node contains no data

		:param	name: Node name
		:type	name: string
		:rtype: dictionary

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_node')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return self._db[name]

	@putil.check.check_argument(NodeName())
	def get_node_parent(self, name):	#pylint: disable=C0111
		"""
		Retrieves parent structure of a node. See :py:meth:`putil.tree.Tree.get_node()` for details about structure.

		:param	name: Child node name
		:type	name: string
		:rtype: dictionary

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_node_parent')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return self._db[self._db[name]['parent']] if not self.is_root(name) else {}

	@putil.check.check_argument(NodeName())
	def get_children(self, name):	#pylint: disable=C0111
		"""
		Retrieves children node names of a node

		:param	name: Node name
		:type	name: string
		:rtype	data: list of strings

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_children')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return sorted(self._db[name]['children'])

	@putil.check.check_argument(NodeName())
	def get_data(self, name):	#pylint: disable=C0111
		"""
		Get node data

		:param	name: Node name
		:type	name: string
		:type	data: any type or list of objects of any type

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_data')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return self._db[name]['data']

	@putil.check.check_argument(NodeName())
	def in_tree(self, name):
		"""
		Search tree for a paticular node. Returns *True* if node name is in the tree, *False* otherwise

		:param	name: Node name to search for
		:type	name: string
		:rtype	data: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('in_tree')) ]]]
		.. [[[end]]]
		"""
		return name in self._db

	@putil.check.check_argument(NodeName())
	def is_root(self, name):	#pylint: disable=C0111
		"""
		Root node flag, *True* if node is the root node (node with no ancestors), *False* otherwise

		:param	name: Node name
		:type	name: string
		:rtype: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('is_root')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return not self._db[name]['parent']

	@putil.check.check_argument(NodeName())
	def is_leaf(self, name):	#pylint: disable=C0111
		"""
		Leaf node flag, *True* if node is a leaf node (node with no children), *False* otherwise

		:param	name: Node name
		:type	name: string
		:rtype: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('is_leaf')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return not self._db[name]['children']

	@putil.check.check_argument(NodeName())
	def make_root(self, name):	#pylint: disable=C0111
		"""
		Makes a sub-node the root node of tree

		:param	name: Node name
		:type	name: string
		:rtype: boolean
		:raises:
		 * TypeError (Argument `name` is of the wrong type)

		 * ValueError (Argument `name` is not a valid node name)

		 * RuntimeError (Node *[name]* not in tree)
		"""
		self._node_in_tree(name)
		dlist = [key for key in self.nodes if key.find(name) != 0]
		for key in dlist:
			del self._db[key]
		self._db[name]['parent'] = ''
		self._root = name

		return not self._db[name]['children']

	@putil.check.check_argument(NodeName())
	def print_node(self, name):	#pylint: disable=C0111
		"""
		Prints node information

		:param	name: Node name
		:type	name: string
		:raises:
		 * TypeError (Argument `name` is of the wrong type)

		 * ValueError (Argument `nodes` is not a valid node name)

		 * RuntimeError (Node *[name]* not in tree)
		"""
		node = self.get_node(name)
		children = [self._split_node_name(child)[-1] for child in node['children']] if node['children'] else node['children']
		data = node['data'][0] if node['data'] and (len(node['data']) == 1) else node['data']
		return 'Name: {0}\nParent: {1}\nChildren: {2}\nData: {3}'.format(name, node['parent'] if node['parent'] else None, ', '.join(children) if children else None, data if data else None)


	@putil.check.check_arguments({'name':NodeName(), 'hierarchy':NodeName()})
	def remove_hierarchy(self, name, hierarchy):	#pylint: disable=C0111
		"""
		Get node data

		:param	name:		Root node of sub-tree to remove hierarchy from
		:type	name:		string
		:param	hierarchy:	Hierarchy to remove from node names in sub-tree
		:type	hierarhcy:	string
		:raises:
		 * TypeError (Argument `name` is of the wrong type)

		 * ValueError (Argument `name` is not a valid node name)

		 * TypeError (Argument `hierarchy` is of the wrong type)

		 * ValueError (Argument `hierarchy` is not a valid node name)

		 * RuntimeError (Node *[name]* not in tree)
		"""
		self._node_in_tree(name)
		# REMOVE print 'Entry function children {0}'.format(self.get_children(name))
		for child in self.get_children(name):
			# REMOVE print 'Entry function child {0}'.format(child)
			self._rnode(name, child, hierarchy)

	@putil.check.check_argument(NodeName())
	def remove_prefix(self, prefix):
		index = self.root_name.find(prefix)
		if index != 0:
			raise ValueError('Illegal prefix')
		cstart = len(prefix)+1
		ndb = dict()
		for key in self._db.keys():
			new_key = key[cstart:]
			self._db[key]['parent'] = self._db[key]['parent'] if not self._db[key]['parent'] else self._db[key]['parent'][cstart:]
			self._db[key]['children'] = sorted([child[cstart:] for child in self._db[key]['children']])
			ndb[new_key] = self._db[key].copy()
			del self._db[key]
		self._db = ndb
		self._set_root_name(self.root_name[cstart:])

	# Managed attributes
	nodes = property(_get_nodes, None, None, doc='Tree nodes')
	"""
	Name of all tree nodes, *None* if an empty tree

	:rtype: list or None
	"""	#pylint: disable=W0105

	root_node = property(_get_root_node, None, None, doc='Tree root node')
	"""
	Tree root node or *None* if :py:class:`putil.tree.Tree()` object has no nodes. See :py:meth:`putil.tree.Tree.get_node()` for details about returned dictionary.

	:rtype: dictionary or None
	"""	#pylint: disable=W0105

	root_name = property(_get_root_name, None, None, doc='Tree root node name')
	"""
	Tree root node name, *None* if :py:class:`putil.tree.Tree()` object has no nodes.

	:rtype: string or None
	"""	#pylint: disable=W0105

@putil.check.check_arguments({'tree':Tree, 'name':NodeName()})
def search_for_node(tree, name):
	"""
	Searches tree node and its children for a particular node name, which can be specified hierarchically. Returns *None* if node name not found.

	:param	tree:	Tree to search
	:type	tree:	:py:class:`putil.tree.Tree()` object
	:param	name:	Node name to search for (case sensitive). Levels of hierarchy are denoted by '.', for example 'root.branch1.leaf2'.
	:type	name:	string
	:rtype:	same as :py:meth:`putil.tree.Tree.get_node()` or *None*
	:raises:
	 * TypeError (Argument `tree` is of the wrong type)

	 * TypeError (Argument `name` is of the wrong type)
	"""
	return None if not tree.in_tree(name) else tree.get_node(name)

@putil.check.check_argument(putil.check.PolymorphicType([{'node':NodeName(), 'data':putil.check.Any()}, putil.check.ArbitraryLengthList({'node':NodeName(), 'data':putil.check.Any()})]))
def build_trees(nodes):
	"""
	Build tree objects

	:param	nodes:	Tree information. Each dictionary must contain only two keys, *name*, with a (hierarchical) node name, and *data*, with the node data. Multiple entries for a given node name may exist, \
	and the resulting node data will be a list whose elements are the values of the *data* key of all dictionaries in **tree_info** that share the same node name
	:type	nodes:	dictionary or list of dictionaries.
	:rtype:	:py:class:`putil.tree.TreeNode()` object or list of :py:class:`putil.tree.TreeNode()` objects if there are multiple root nodes
	:raises:
	 * TypeError (Argument `tree_info` is of the wrong type)

	 * Same as :py:attr:`putil.tree.TreeNode.name`
	"""
	roots = list()
	nodes = nodes if isinstance(nodes, list) else [nodes]
	for node in nodes:
		root_name = [element.strip() for element in node['name'].strip().split('.')][0]
		# Find or create tree to add nodes and data to
		for tobj in roots:
			if tobj.root_name == root_name:
				break
		else:
			tobj = Tree()
			roots.append(tobj)
		tobj.add(node)
	return roots
<commit_msg>tree module:  * Documentation updates  * Change flatten_subtree() method to only flatten sub-tree under the    node name given exh module:  * Updated _flatten_ex_tree() method to reflect changed functionality of    tree.Tree.flatten_subtree() method<commit_after># -*- coding: utf-8 -*-
# pylint: disable=W0212,C0111
# tree.py
# Copyright (c) 2014 <NAME>
# See LICENSE for details


import putil.check

###
# Node name custom pseudo-type
###
class NodeName(object):	#pylint: disable=R0903
	""" Hierarchical node name data type class """
	def includes(self, test_obj):	#pylint: disable=R0201,W0613
		"""	Test that an object belongs to the pseudo-type """
		return False if (not isinstance(test_obj, str)) or (isinstance(test_obj, str) and (' ' in test_obj)) else all([element.strip() != '' for element in test_obj.strip().split('.')])

	def istype(self, test_obj):	#pylint: disable=R0201
		"""	Checks to see if object is of the same class type """
		return isinstance(test_obj, str)

	def exception(self, param_name):	#pylint: disable=R0201,W0613
		"""	Returns a suitable exception message """
		exp_dict = dict()
		exp_dict['type'] = ValueError
		exp_dict['msg'] = 'Argument `{0}` is not a valid node name'.format(param_name)
		return exp_dict
putil.check.register_new_type(NodeName, 'Hierarchical node name')


class Tree(object):	#pylint: disable=R0903
	"""
	Provides basic trie (radix tree) functionality

	:rtype: :py:class:`putil.tree.Tree()` object
	"""
	def __init__(self):	#pylint: disable=R0913
		self._db = dict()
		self._root = None
		self._vertical = unichr(0x2502)
		self._vertical_and_right = unichr(0x251C)
		self._up_and_right = unichr(0x2514)
		#{'name':{'parent':None, 'children':None, 'data':data}}

	def __str__(self):
		u"""
		String with the tree structure 'pretty printed' as a character-based tree structure. Only node names are shown, nodes with data are marked with an asterisk (*). For example:

			>>> import putil.tree
			>>> tobj = putil.tree.Tree()
			>>> tobj.add([
			...		{'name':'root.branch1', 'data':5},
			...		{'name':'root.branch2', 'data':list()},
			...		{'name':'root.branch1.leaf1', 'data':list()},
			...		{'name':'root.branch1.leaf2', 'data':'Hello world!'}
			... ])
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			│└leaf2 (*)
			└branch2

		:rtype: Unicode string
		"""
		return self._prt(name=self.root_name, lparent=-1, sep='', pre1='', pre2='').encode('utf-8')

	def _collapse_node(self, name):
		""" Collapse a single node """
		while True:
			node = self._db[name]
			if (len(node['children']) == 1) and (not node['data']):
				child_name = node['children'][0]
				self._db[child_name]['parent'] = node['parent']
				self._db[self._db[name]['parent']]['children'].remove(name)
				self._db[self._db[name]['parent']]['children'] = sorted(self._db[self._db[name]['parent']]['children']+[child_name])
				del self._db[name]
				name = child_name
			else:
				break
		node = self._db[name]
		for name in node['children'][:]:
			self._collapse_node(name)

	def _get_nodes(self):	#pylint: disable=C0111
		return None if not self._db else sorted(self._db.keys())

	def _get_root_node(self):	#pylint: disable=C0111
		return None if not self.root_name else self.get_node(self.root_name)

	def _get_root_name(self):	#pylint: disable=C0111
		return self._root

	def _get_subtree(self, name):
		if self.is_leaf(name):
			return [name]
		children = self.get_children(name)
		ret = [name]
		for child in children:
			ret += self._get_subtree(child)
		return ret

	def _node_in_tree(self, name):	#pylint: disable=C0111
		if name not in self._db:
			raise RuntimeError('Node {0} not in tree'.format(name))

	def _prt(self, name, lparent, sep, pre1, pre2):	#pylint: disable=C0111,R0913,R0914
		# Characters from http://www.unicode.org/charts/PDF/U2500.pdf
		node_name = name[lparent+1:]
		#node_name = name.split('.')[-1]
		children = self._db[name]['children']
		ncmu = len(children)-1
		plist1 = ncmu*[self._vertical_and_right]+[self._up_and_right]
		plist2 = ncmu*[self._vertical]+[' ']
		slist = (ncmu+1)*[sep+pre2]
		dmark = ' (*)' if self._db[name]['data'] else ''
		return '\n'.join([u'{0}{1}{2}{3}'.format(sep, pre1, node_name, dmark)]+[self._prt(child, len(name), sep=schar, pre1=p1, pre2=p2) for child, p1, p2, schar in zip(children, plist1, plist2, slist)])

	def _rnode(self, root, name, hierarchy):	#pylint: disable=C0111,R0913,R0914
		suffix = name[len(root):]
		new_suffix = suffix.replace('.'+hierarchy, '').replace('..', '.')
		new_name = root+new_suffix
		if new_name != name:
			if not self.in_tree(new_name):
				self._db[new_name] = self._db[name].copy()
				self._db[self._db[name]['parent']]['children'] = sorted(list(set([child for child in self._db[self._db[name]['parent']]['children'] if child != name]+[new_name])))
			else:
				if self._db[name]['data']:
					raise RuntimeError('Hierarchy {0} cannot be deleted'.format(hierarchy))
				if self._db[name]['parent'] == new_name:
					self._db[self._db[name]['parent']]['children'] = sorted(list(set([child for child in self._db[self._db[name]['parent']]['children'] if child != name])))
				new_children = sorted(self._db[new_name]['children']+self._db[name]['children'])
				if len(new_children) != len(set(new_children)):
					raise RuntimeError('Inconsitency when deleting hierarchy')
				self._db[new_name]['children'] = new_children
			for child in self.get_children(name):
				self._db[child]['parent'] = new_name
			del self._db[name]
		for child in self.get_children(new_name):
			self._rnode(root, child, hierarchy)

	def _set_root_name(self, name):	#pylint: disable=C0111
		self._root = name

	def _split_node_name(self, name):	#pylint: disable=C0111,R0201
		return [element.strip() for element in name.strip().split('.')]

	@putil.check.check_argument(putil.check.PolymorphicType([{'name':NodeName(), 'data':putil.check.Any()}, putil.check.ArbitraryLengthList({'name':NodeName(), 'data':putil.check.Any()})]))
	def add(self, nodes):
		"""
		Add nodes to tree

		:param	nodes: Node(s) to add. Each dictionary must contain exactly two keys:

		 * **name** (*string*) node name

		 * **data** (*any*) node data.

		 If there are several list items in **nodes** with the same node name the resulting node data is a list with items corresponding to the data of each entry in **nodes** with the same node name, in their order \
		 of appearance, in addition to any existing node data if the node is already present in the tree.

		 The node data should be an empty list to create a node without data, for example: `{'node':'a.b.c', 'data':list()}`

		:type	nodes: dictionary or list of dictionaries

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('add')) ]]]
		.. [[[end]]]


		For example:

			>>> import putil.tree
			>>> tobj = putil.tree.Tree()
			>>> tobj.add([
			...		{'name':'root.branch1', 'data':5},
			...		{'name':'root.branch1', 'data':7},
			...		{'name':'root.branch2', 'data':list()},
			...		{'name':'root.branch1.leaf1', 'data':list()},
			...		{'name':'root.branch1.leaf1.subleaf1', 'data':333},
			...		{'name':'root.branch1.leaf2', 'data':'Hello world!'},
			...		{'name':'root.branch1.leaf2.subleaf2', 'data':list()},
			... ])
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.get_data('root.branch1')
			[5, 7]

		"""
		nodes = nodes if isinstance(nodes, list) else [nodes]
		if not self.root_name:
			self._set_root_name(nodes[0]['name'].split('.')[0].strip())
			self._db[self.root_name] = {'parent':'', 'children':list(), 'data':list()}
		for node_dict in nodes:
			name = node_dict['name']
			data = node_dict['data']
			if not self.in_tree(name):
				hierarchy = self._split_node_name(name)
				if hierarchy[0] != self.root_name:
					raise ValueError('Illegal node name: {0}'.format(name))
				for num in range(len(hierarchy)):
					child = '.'.join(hierarchy[:num+1])
					if not self.in_tree(child):
						parent = '.'.join(self._split_node_name(child)[:-1])
						self._db[child] = {'parent':parent, 'children':list(), 'data':list()}
						self._db[parent]['children'] = list(sorted(set(self._db[parent]['children']+[child])))
			data = data if isinstance(data, list) and (len(data) > 0) else (list() if isinstance(data, list) else [data])
			self._db[name]['data'] = self._db[name]['data']+data

	@putil.check.check_argument(NodeName())
	def collapse(self, name):
		"""
		Collapses hierarchy. Nodes that have a single child and no data are combined with their children.

		:param	name: Root of the sub-tree to collapse
		:type	name: string

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('collapse')) ]]]
		.. [[[end]]]


		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.collapse('branch1')
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1.subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2

		``root.branch1.leaf1`` is collapsed because it only has one child (``root.branch1.leaf1.subleaf1``) and no data; ``root.branch1.leaf2`` is not collapsed because although it has one child (``root.branch1.leaf2.subleaf2``) \
		it does have data associated with it, *'Hello world!'*
		"""
		self._node_in_tree(name)
		for child in self._db[name]['children'][:]:
			self._collapse_node(child)

	@putil.check.check_argument(putil.check.PolymorphicType([NodeName(), putil.check.ArbitraryLengthList(NodeName())]))
	def delete(self, nodes):
		"""
		Delete nodes (and their sub-trees) from tree

		:param	nodes: Node(s) to delete
		:type	nodes: string or list of strings

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('delete')) ]]]
		.. [[[end]]]

		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.delete(['root.branch1.leaf1', 'root.branch2'])
			>>> print str(tobj)
			root
			└branch1 (*)
			 └leaf2 (*)
			  └subleaf2

		"""
		nodes = nodes if isinstance(nodes, list) else [nodes]
		for node in nodes:
			self._node_in_tree(node)
			parent = self.get_node(node)['parent']
			# Delete link to parent (if not root node)
			del_list = self._get_subtree(node)
			if parent:
				self._db[parent]['children'] = [child for child in self._db[parent]['children'] if child != node]
			# Delete children (sub-tree)
			for child in del_list:
				del self._db[child]
			if not len(self._db):
				self._root = None

	@putil.check.check_argument(NodeName())
	def flatten_subtree(self, name):
		"""
		Flatten sub-tree below a particular node if the node contains no data

		:param	name: Ending hierarchy node whose sub-trees are to be flattened
		:type	name: string

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('delete')) ]]]
		.. [[[end]]]

		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> tobj.add([{'name':'root.branch1.leaf1.subleaf2', 'data':list()},
			...           {'name':'root.branch2.leaf1', 'data':'loren ipsum'},
			...           {'name':'root.branch2.leaf1.another_subleaf1', 'data':list()},
			...           {'name':'root.branch2.leaf1.another_subleaf2', 'data':list()}
			...         ])
			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││├subleaf1 (*)
			││└subleaf2
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			 └leaf1
			  ├another_subleaf1
			  └another_subleaf2
			>>> tobj.flatten_subtree('root1.branch1.leaf1')
			root
			├branch1 (*)
			│├leaf1.subleaf1 (*)
			│├leaf1.subleaf2
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			 └leaf1 (*)
			  ├another_subleaf1
			  └another_subleaf2
			>>> tobj.flatten_subtree('root1.branch2.leaf1')
			root
			├branch1 (*)
			│├leaf1.subleaf1 (*)
			│├leaf1.subleaf2
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			 └leaf1 (*)
			  ├another_subleaf1
			  └another_subleaf2

		"""
		self._node_in_tree(name)
		if (not self.is_root(name)) and (not self.get_data(name)):
			parent = self._db[name]['parent']
			children = self._db[name]['children']
			for child in children:
				self._db[child]['parent'] = parent
			self._db[parent]['children'] = sorted([child for child in self._db[parent]['children'] if child != name]+children)
			del self._db[name]

	@putil.check.check_argument(NodeName())
	def get_node(self, name):	#pylint: disable=C0111
		"""
		Get tree node structure. The structure is a dictionary with the following keys:

		 * **parent** (*string*) Parent node name, *''* if node is the root node

		 * **children** (*list*) Children node names, empty list if node is a leaf

		 * **data** (*list*) Node data, empty list if node contains no data

		:param	name: Node name
		:type	name: string
		:rtype: dictionary

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_node')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return self._db[name]

	@putil.check.check_argument(NodeName())
	def get_node_children(self, name):	#pylint: disable=C0111
		"""
		Return list of children structures of a node. See :py:meth:`putil.tree.Tree.get_node()` for details about structure.

		:param	name: Child node name
		:type	name: string
		:rtype: list

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_node_parent')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return [self.get_node(child) for child in self.get_children(name)]

	@putil.check.check_argument(NodeName())
	def get_node_parent(self, name):	#pylint: disable=C0111
		"""
		Return parent structure of a node. See :py:meth:`putil.tree.Tree.get_node()` for details about structure

		:param	name: Child node name
		:type	name: string
		:rtype: dictionary

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_node_parent')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return self._db[self._db[name]['parent']] if not self.is_root(name) else dict()

	@putil.check.check_argument(NodeName())
	def get_children(self, name):	#pylint: disable=C0111
		"""
		Return children node names of a node

		:param	name: Node name
		:type	name: string
		:rtype	data: list of strings

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_children')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return sorted(self._db[name]['children'])

	@putil.check.check_argument(NodeName())
	def get_data(self, name):	#pylint: disable=C0111
		"""
		Return node data

		:param	name: Node name
		:type	name: string
		:type	data: any type or list of objects of any type

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('get_data')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return self._db[name]['data']

	@putil.check.check_argument(NodeName())
	def in_tree(self, name):
		"""
		Return *True* if node name is in the tree, *False* otherwise

		:param	name: Node name to search for
		:type	name: string
		:rtype	data: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('in_tree')) ]]]
		.. [[[end]]]
		"""
		return name in self._db

	@putil.check.check_argument(NodeName())
	def is_root(self, name):	#pylint: disable=C0111
		"""
		Root node flag, *True* if node is the root node (node with no ancestors), *False* otherwise

		:param	name: Node name
		:type	name: string
		:rtype: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('is_root')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return not self._db[name]['parent']

	@putil.check.check_argument(NodeName())
	def is_leaf(self, name):	#pylint: disable=C0111
		"""
		Leaf node flag, *True* if node is a leaf node (node with no children), *False* otherwise

		:param	name: Node name
		:type	name: string
		:rtype: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('is_leaf')) ]]]
		.. [[[end]]]
		"""
		self._node_in_tree(name)
		return not self._db[name]['children']

	@putil.check.check_argument(NodeName())
	def make_root(self, name):	#pylint: disable=C0111
		"""
		Makes a sub-node the root node of the tree. All nodes not belonging to the sub-tree are deleted

		:param	name: New root node name
		:type	name: string
		:rtype: boolean

		.. [[[cog cog.out(exobj_tree.get_sphinx_doc_for_member('make_root')) ]]]
		.. [[[end]]]

		For example, using the same example tree created in :py:meth:`putil.tree.Tree.add`:

			>>> print str(tobj)
			root
			├branch1 (*)
			│├leaf1
			││└subleaf1 (*)
			│└leaf2 (*)
			│ └subleaf2
			└branch2
			>>> tobj.make_root('root.branch1')
			>>> print str(tobj)
			root.branch1 (*)
			├leaf1
			│└subleaf1 (*)
			└leaf2 (*)
			 └subleaf2

		"""
		if name != self.root_name:
			self._node_in_tree(name)
			dlist = [key for key in self.nodes if key.find(name) != 0]
			for key in dlist:
				del self._db[key]
			self._db[name]['parent'] = ''
			self._root = name

	@putil.check.check_argument(NodeName())
	def print_node(self, name):	#pylint: disable=C0111
		"""
		Prints node information

		:param	name: Node name
		:type	name: string
		:raises:
		 * TypeError (Argument `name` is of the wrong type)

		 * ValueError (Argument `nodes` is not a valid node name)

		 * RuntimeError (Node *[name]* not in tree)
		"""
		node = self.get_node(name)
		children = [self._split_node_name(child)[-1] for child in node['children']] if node['children'] else node['children']
		data = node['data'][0] if node['data'] and (len(node['data']) == 1) else node['data']
		return 'Name: {0}\nParent: {1}\nChildren: {2}\nData: {3}'.format(name, node['parent'] if node['parent'] else None, ', '.join(children) if children else None, data if data else None)

	@putil.check.check_argument(NodeName())
	def remove_prefix(self, prefix):
		index = self.root_name.find(prefix)
		if (index != 0) or (self.in_tree(prefix)):
			raise ValueError('Illegal prefix')
		cstart = len(prefix)+1
		ndb = dict()
		for key in self._db.keys():
			new_key = key[cstart:]
			self._db[key]['parent'] = self._db[key]['parent'] if not self._db[key]['parent'] else self._db[key]['parent'][cstart:]
			self._db[key]['children'] = sorted([child[cstart:] for child in self._db[key]['children']])
			ndb[new_key] = self._db[key].copy()
			del self._db[key]
		self._db = ndb
		self._set_root_name(self.root_name[cstart:])

	# Managed attributes
	nodes = property(_get_nodes, None, None, doc='Tree nodes')
	"""
	Name of all tree nodes, *None* if an empty tree

	:rtype: list or None
	"""	#pylint: disable=W0105

	root_node = property(_get_root_node, None, None, doc='Tree root node')
	"""
	Tree root node or *None* if :py:class:`putil.tree.Tree()` object has no nodes. See :py:meth:`putil.tree.Tree.get_node()` for details about returned dictionary.

	:rtype: dictionary or None
	"""	#pylint: disable=W0105

	root_name = property(_get_root_name, None, None, doc='Tree root node name')
	"""
	Tree root node name, *None* if :py:class:`putil.tree.Tree()` object has no nodes.

	:rtype: string or None
	"""	#pylint: disable=W0105

@putil.check.check_arguments({'tree':Tree, 'name':NodeName()})
def search_for_node(tree, name):
	"""
	Searches tree node and its children for a particular node name, which can be specified hierarchically. Returns *None* if node name not found.

	:param	tree:	Tree to search
	:type	tree:	:py:class:`putil.tree.Tree()` object
	:param	name:	Node name to search for (case sensitive). Levels of hierarchy are denoted by '.', for example 'root.branch1.leaf2'.
	:type	name:	string
	:rtype:	same as :py:meth:`putil.tree.Tree.get_node()` or *None*
	:raises:
	 * TypeError (Argument `tree` is of the wrong type)

	 * TypeError (Argument `name` is of the wrong type)
	"""
	return None if not tree.in_tree(name) else tree.get_node(name)

@putil.check.check_argument(putil.check.PolymorphicType([{'node':NodeName(), 'data':putil.check.Any()}, putil.check.ArbitraryLengthList({'node':NodeName(), 'data':putil.check.Any()})]))
def build_trees(nodes):
	"""
	Build tree objects

	:param	nodes:	Tree information. Each dictionary must contain only two keys, *name*, with a (hierarchical) node name, and *data*, with the node data. Multiple entries for a given node name may exist, \
	and the resulting node data will be a list whose elements are the values of the *data* key of all dictionaries in **tree_info** that share the same node name
	:type	nodes:	dictionary or list of dictionaries.
	:rtype:	:py:class:`putil.tree.TreeNode()` object or list of :py:class:`putil.tree.TreeNode()` objects if there are multiple root nodes
	:raises:
	 * TypeError (Argument `tree_info` is of the wrong type)

	 * Same as :py:attr:`putil.tree.TreeNode.name`
	"""
	roots = list()
	nodes = nodes if isinstance(nodes, list) else [nodes]
	for node in nodes:
		root_name = [element.strip() for element in node['name'].strip().split('.')][0]
		# Find or create tree to add nodes and data to
		for tobj in roots:
			if tobj.root_name == root_name:
				break
		else:
			tobj = Tree()
			roots.append(tobj)
		tobj.add(node)
	return roots

{'fraction_non_alphanumeric': 0.16546676265898727, 'fraction_numerical': 0.016102711783057354, 'mean_word_length': 4.1726663356504465, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 128, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1631214', 'n_tokens_mistral': 16659, 'n_tokens_neox': 15011, 'n_words': 3762}