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:

root
├branch1
│├leaf1
│└leaf2
└branch2

The node names are 'root', 'root.branch1', 'root.branch1.leaf1', 'root.branch1.leaf2' and 'root.branch2'

NodesWithData

Dictionary or list of dictionaries; each dictionary must contain exactly two keys:

  • name (NodeName) Node name. See NodeName pseudo-type specification
  • data (any) node data

The node data should be an empty list to create a node without data, for example: {'name':'a.b.c', 'data':[]}

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:
  • source_name (NodeName) – Root node of the sub-tree to copy from
  • dest_name (NodeName) – Root node of the sub-tree to copy to
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:

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 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)
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 empty

Return 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 nodes

Return 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 dictionary

Return type:dictionary or None