tree module¶
This module can be used to build, handle, process and search tries
Classes¶
-
class
putil.tree.
Tree
(node_separator='.')¶ Bases: object
Provides basic trie (radix tree) functionality
Parameters: node_separator (string) – Single character used to separate nodes in the tree Return type: putil.tree.Tree object Raises: RuntimeError (Argument `node_separator` is not valid) -
__nonzero__
()¶ Returns
False
if tree object has no nodes,True
otherwise. For example:>>> from __future__ import print_function >>> import putil.tree >>> tobj = putil.tree.Tree() >>> if tobj: ... print('Boolean test returned: True') ... else: ... print('Boolean test returned: False') Boolean test returned: False >>> tobj.add_nodes([{'name':'root.branch1', 'data':5}]) >>> if tobj: ... print('Boolean test returned: True') ... else: ... print('Boolean test returned: False') Boolean test returned: True
-
__str__
()¶ Returns a string with the tree ‘pretty printed’ as a character-based structure. Only node names are shown, nodes with data are marked with an asterisk (
*
). For example:>>> from __future__ import print_function >>> import putil.tree >>> tobj = putil.tree.Tree() >>> tobj.add_nodes([ ... {'name':'root.branch1', 'data':5}, ... {'name':'root.branch2', 'data':[]}, ... {'name':'root.branch1.leaf1', 'data':[]}, ... {'name':'root.branch1.leaf2', 'data':'Hello world!'} ... ]) >>> print(tobj) root ├branch1 (*) │├leaf1 │└leaf2 (*) └branch2
Return type: Unicode string
-
add_nodes
(nodes)¶ Adds nodes to tree
Parameters: nodes (NodesWithData) – Node(s) to add with associated data. If there are several list items in the argument with the same node name the resulting node data is a list with items corresponding to the data of each entry in the argument 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 Raises: - RuntimeError (Argument `nodes` is not valid)
- ValueError (Illegal node name: [node_name])
For example:
# tree_example.py import putil.tree def create_tree(): tobj = putil.tree.Tree() tobj.add_nodes([ {'name':'root.branch1', 'data':5}, {'name':'root.branch1', 'data':7}, {'name':'root.branch2', 'data':[]}, {'name':'root.branch1.leaf1', 'data':[]}, {'name':'root.branch1.leaf1.subleaf1', 'data':333}, {'name':'root.branch1.leaf2', 'data':'Hello world!'}, {'name':'root.branch1.leaf2.subleaf2', 'data':[]}, ]) return tobj
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> tobj.get_data('root.branch1') [5, 7]
-
collapse_subtree
(name, recursive=True)¶ Collapses a sub-tree; nodes that have a single child and no data are combined with their child as a single tree node
Parameters: - name (NodeName) – Root of the sub-tree to collapse
- recursive (boolean) – Flag that indicates whether the collapse operation is performed on the whole sub-tree (True) or whether it stops upon reaching the first node where the collapsing condition is not satisfied (False)
Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Argument `recursive` is not valid)
- RuntimeError (Node [name] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> tobj.collapse_subtree('root.branch1') >>> print(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
) and this child does have data associated with it,'Hello world!'
-
copy_subtree
(source_node, dest_node)¶ Copies a sub-tree from one sub-node to another. Data is added if some nodes of the source sub-tree exist in the destination sub-tree
Parameters: Raises: - RuntimeError (Argument `dest_node` is not valid)
- RuntimeError (Argument `source_node` is not valid)
- RuntimeError (Illegal root in destination node)
- RuntimeError (Node [source_node] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> tobj.copy_subtree('root.branch1', 'root.branch3') >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 ├branch2 └branch3 (*) ├leaf1 │└subleaf1 (*) └leaf2 (*) └subleaf2
-
delete_prefix
(name)¶ Deletes hierarchy levels from all nodes in the tree
Parameters: nodes (NodeName) – Prefix to delete Raises: - RuntimeError (Argument `name` is not a valid prefix)
- RuntimeError (Argument `name` is not valid)
For example:
>>> from __future__ import print_function >>> import putil.tree >>> tobj = putil.tree.Tree('/') >>> tobj.add_nodes([ ... {'name':'hello/world/root', 'data':[]}, ... {'name':'hello/world/root/anode', 'data':7}, ... {'name':'hello/world/root/bnode', 'data':8}, ... {'name':'hello/world/root/cnode', 'data':False}, ... {'name':'hello/world/root/bnode/anode', 'data':['a', 'b']}, ... {'name':'hello/world/root/cnode/anode/leaf', 'data':True} ... ]) >>> tobj.collapse_subtree('hello', recursive=False) >>> print(tobj) hello/world/root ├anode (*) ├bnode (*) │└anode (*) └cnode (*) └anode └leaf (*) >>> tobj.delete_prefix('hello/world') >>> print(tobj) root ├anode (*) ├bnode (*) │└anode (*) └cnode (*) └anode └leaf (*)
-
delete_subtree
(nodes)¶ Deletes nodes (and their sub-trees) from the tree
Parameters: nodes (NodeName or list of NodeName) – Node(s) to delete Raises: - RuntimeError (Argument `nodes` is not valid)
- RuntimeError (Node [node_name] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> tobj.delete_subtree(['root.branch1.leaf1', 'root.branch2']) >>> print(tobj) root └branch1 (*) └leaf2 (*) └subleaf2
-
flatten_subtree
(name)¶ Flattens sub-tree; nodes that have children and no data are merged with each child
Parameters: name (NodeName) – Ending hierarchy node whose sub-trees are to be flattened Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> tobj.add_nodes([ ... {'name':'root.branch1.leaf1.subleaf2', 'data':[]}, ... {'name':'root.branch2.leaf1', 'data':'loren ipsum'}, ... {'name':'root.branch2.leaf1.another_subleaf1', 'data':[]}, ... {'name':'root.branch2.leaf1.another_subleaf2', 'data':[]} ... ]) >>> print(str(tobj)) root ├branch1 (*) │├leaf1 ││├subleaf1 (*) ││└subleaf2 │└leaf2 (*) │ └subleaf2 └branch2 └leaf1 (*) ├another_subleaf1 └another_subleaf2 >>> tobj.flatten_subtree('root.branch1.leaf1') >>> print(str(tobj)) root ├branch1 (*) │├leaf1.subleaf1 (*) │├leaf1.subleaf2 │└leaf2 (*) │ └subleaf2 └branch2 └leaf1 (*) ├another_subleaf1 └another_subleaf2 >>> tobj.flatten_subtree('root.branch2.leaf1') >>> print(str(tobj)) root ├branch1 (*) │├leaf1.subleaf1 (*) │├leaf1.subleaf2 │└leaf2 (*) │ └subleaf2 └branch2 └leaf1 (*) ├another_subleaf1 └another_subleaf2
-
get_children
(name)¶ Gets the children node names of a node
Parameters: name (NodeName) – Parent node name Return type: list of NodeName Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
get_data
(name)¶ Gets the data associated with a node
Parameters: name (NodeName) – Node name Return type: any type or list of objects of any type Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
get_leafs
(name)¶ Gets the sub-tree leaf node(s)
Parameters: name (NodeName) – Sub-tree root node name Return type: list of NodeName Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
get_node
(name)¶ Gets a tree node structure. The structure is a dictionary with the following keys:
- parent (NodeName) Parent node name,
''
if the node is the root node - children (list of NodeName) Children node names, an empty list if node is a leaf
- data (list) Node data, an empty list if node contains no data
Parameters: name (string) – Node name Return type: dictionary Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
- parent (NodeName) Parent node name,
-
get_node_children
(name)¶ Gets the list of children structures of a node. See putil.tree.Tree.get_node() for details about the structure
Parameters: name (NodeName) – Parent node name Return type: list Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
get_node_parent
(name)¶ Gets the parent structure of a node. See putil.tree.Tree.get_node() for details about the structure
Parameters: name (NodeName) – Child node name Return type: dictionary Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
get_subtree
(name)¶ Gets all node names in a sub-tree
Parameters: name (NodeName) – Sub-tree root node name Return type: list of NodeName Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example, pprint >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> pprint.pprint(tobj.get_subtree('root.branch1')) ['root.branch1', 'root.branch1.leaf1', 'root.branch1.leaf1.subleaf1', 'root.branch1.leaf2', 'root.branch1.leaf2.subleaf2']
-
is_root
(name)¶ Tests if a node is the root node (node with no ancestors)
Parameters: name (NodeName) – Node name Return type: boolean Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
in_tree
(name)¶ Tests if a node is in the tree
Parameters: name (NodeName) – Node name to search for Return type: boolean Raises: RuntimeError (Argument `name` is not valid)
-
is_leaf
(name)¶ Tests if a node is a leaf node (node with no children)
Parameters: name (NodeName) – Node name Return type: boolean Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
-
make_root
(name)¶ Makes a sub-node the root node of the tree. All nodes not belonging to the sub-tree are deleted
Parameters: name (NodeName) – New root node name Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> tobj.make_root('root.branch1') >>> print(tobj) root.branch1 (*) ├leaf1 │└subleaf1 (*) └leaf2 (*) └subleaf2
-
print_node
(name)¶ Prints node information (parent, children and data)
Parameters: name (NodeName) – Node name Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Node [name] not in tree)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> print(tobj.print_node('root.branch1')) Name: root.branch1 Parent: root Children: leaf1, leaf2 Data: [5, 7]
-
rename_node
(name, new_name)¶ Renames a tree node. It is typical to have a root node name with more than one hierarchy level after using putil.tree.Tree.make_root(). In this instance the root node can be renamed as long as the new root name has the same or less hierarchy levels as the existing root name
Parameters: name (NodeName) – Node name to rename Raises: - RuntimeError (Argument `name` is not valid)
- RuntimeError (Argument `new_name` has an illegal root node)
- RuntimeError (Argument `new_name` is an illegal root node name)
- RuntimeError (Argument `new_name` is not valid)
- RuntimeError (Node [name] not in tree)
- RuntimeError (Node [new_name] already exists)
Using the same example tree created in putil.tree.Tree.add_nodes():
>>> from __future__ import print_function >>> import docs.support.tree_example >>> tobj = docs.support.tree_example.create_tree() >>> print(tobj) root ├branch1 (*) │├leaf1 ││└subleaf1 (*) │└leaf2 (*) │ └subleaf2 └branch2 >>> tobj.rename_node( ... 'root.branch1.leaf1', ... 'root.branch1.mapleleaf1' ... ) >>> print(tobj) root ├branch1 (*) │├leaf2 (*) ││└subleaf2 │└mapleleaf1 │ └subleaf1 (*) └branch2
-
search_tree
(name)¶ Searches tree for all nodes with a specific name
Parameters: name (NodeName) – Node name to search for Raises: RuntimeError (Argument `name` is not valid) For example:
>>> from __future__ import print_function >>> import pprint, putil.tree >>> tobj = putil.tree.Tree('/') >>> tobj.add_nodes([ ... {'name':'root', 'data':[]}, ... {'name':'root/anode', 'data':7}, ... {'name':'root/bnode', 'data':[]}, ... {'name':'root/cnode', 'data':[]}, ... {'name':'root/bnode/anode', 'data':['a', 'b', 'c']}, ... {'name':'root/cnode/anode/leaf', 'data':True} ... ]) >>> print(tobj) root ├anode (*) ├bnode │└anode (*) └cnode └anode └leaf (*) >>> pprint.pprint(tobj.search_tree('anode'), width=40) ['root/anode', 'root/bnode/anode', 'root/cnode/anode', 'root/cnode/anode/leaf']
-
nodes
¶ Gets the name of all tree nodes,
None
if the tree is emptyReturn type: list of NodeName or None
-
node_separator
¶ Gets the node separator character
Return type: string
-
root_name
¶ Gets the tree root node name,
None
if the putil.tree.Tree object has no nodesReturn type: NodeName or None
-
root_node
¶ Gets the tree root node structure or
None
if putil.tree.Tree object has no nodes. See putil.tree.Tree.get_node() for details about returned dictionaryReturn type: dictionary or None
-