API¶
Pseudo-types¶
NodeName¶
String where hierarchy levels are denoted by node separator characters
('.'
by default). Node names cannot contain spaces, empty hierarchy
levels, start or end with a node separator character.
For this example tree:
The node names are 'root'
, 'root.branch1'
, 'root.branch1.leaf1'
,
'root.branch1.leaf2'
and 'root.branch2'
Class¶
-
class
ptrie.
Trie
(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: ptrie.Trie 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 ptrie >>> tobj = ptrie.Trie() >>> 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 ptrie >>> tobj = ptrie.Trie() >>> 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:
# ptrie_example.py import ptrie def create_tree(): tobj = ptrie.Trie() 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.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie >>> tobj = ptrie.Trie('/') >>> 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: Raises: - RuntimeError (Argument `nodes` is not valid)
- RuntimeError (Node [node_name] not in tree)
Using the same example tree created in ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie.Trie.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 ptrie.Trie.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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example, pprint >>> tobj = docs.support.ptrie_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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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 ptrie.Trie.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 ptrie.Trie.add_nodes():
>>> from __future__ import print_function >>> import docs.support.ptrie_example >>> tobj = docs.support.ptrie_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, ptrie >>> tobj = ptrie.Trie('/') >>> 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 ptrie.Trie object has no nodesReturn type: NodeName or None
-
root_node
¶ Gets the tree root node structure or
None
if ptrie.Trie object has no nodes. See ptrie.Trie.get_node() for details about returned dictionaryReturn type: dictionary or None
-