PyPI version License Python versions supported Format

Continuous integration test status Continuous integration test coverage Documentation status

Description

This module can be used to build, handle, process and search tries

Interpreter

The package has been developed and tested with Python 2.7, 3.5, 3.6 and 3.7 under Linux (Debian, Ubuntu), Apple macOS and Microsoft Windows

Installing

$ pip install ptrie

Documentation

Available at Read the Docs

Contributing

  1. Abide by the adopted code of conduct

  2. Fork the repository from GitHub and then clone personal copy [1]:

    $ github_user=myname
$ git clone --recurse-submodules \
      https://github.com/"${github_user}"/ptrie.git
Cloning into 'ptrie'...
...
$ cd ptrie || exit 1
$ export PTRIE_DIR=${PWD}
$

  3. The package uses two sub-modules: a set of custom Pylint plugins to help with some areas of code quality and consistency (under the pylint_plugins directory), and a lightweight package management framework (under the pypkg directory). Additionally, the pre-commit framework is used to perform various pre-commit code quality and consistency checks. To enable the pre-commit hooks:

    $ cd "${PTRIE_DIR}" || exit 1
$ pre-commit install
pre-commit installed at .../ptrie/.git/hooks/pre-commit
$

  4. Ensure that the Python interpreter can find the package modules (update the $PYTHONPATH environment variable, or use sys.paths(), etc.)

    $ export PYTHONPATH=${PYTHONPATH}:${PTRIE_DIR}
$

  5. Install the dependencies (if needed, done automatically by pip):

  6. Implement a new feature or fix a bug

  7. Write a unit test which shows that the contributed code works as expected. Run the package tests to ensure that the bug fix or new feature does not have adverse side effects. If possible achieve 100% code and branch coverage of the contribution. Thorough package validation can be done via Tox and Pytest:

    $ PKG_NAME=ptrie tox
GLOB sdist-make: .../ptrie/setup.py
py27-pkg create: .../ptrie/.tox/py27
py27-pkg installdeps: -r.../ptrie/requirements/tests_py27.pip, -r.../ptrie/requirements/docs_py27.pip
...
  py27-pkg: commands succeeded
  py35-pkg: commands succeeded
  py36-pkg: commands succeeded
  py37-pkg: commands succeeded
  congratulations :)
$

    Setuptools can also be used (Tox is configured as its virtual environment manager):

    $ PKG_NAME=ptrie python setup.py tests
running tests
running egg_info
writing ptrie.egg-info/PKG-INFO
writing dependency_links to ptrie.egg-info/dependency_links.txt
writing requirements to ptrie.egg-info/requires.txt
...
  py27-pkg: commands succeeded
  py35-pkg: commands succeeded
  py36-pkg: commands succeeded
  py37-pkg: commands succeeded
  congratulations :)
$

    Tox (or Setuptools via Tox) runs with the following default environments: py27-pkg, py35-pkg, py36-pkg and py37-pkg [3]. These use the 2.7, 3.5, 3.6 and 3.7 interpreters, respectively, to test all code in the documentation (both in Sphinx *.rst source files and in docstrings), run all unit tests, measure test coverage and re-build the exceptions documentation. To pass arguments to Pytest (the test runner) use a double dash (--) after all the Tox arguments, for example:

    $ PKG_NAME=ptrie tox -e py27-pkg -- -n 4
GLOB sdist-make: .../ptrie/setup.py
py27-pkg inst-nodeps: .../ptrie/.tox/.tmp/package/1/ptrie-1.1.6.zip
...
  py27-pkg: commands succeeded
  congratulations :)
$

    Or use the -a Setuptools optional argument followed by a quoted string with the arguments for Pytest. For example:

    $ PKG_NAME=ptrie python setup.py tests -a "-e py27-pkg -- -n 4"
running tests
...
  py27-pkg: commands succeeded
  congratulations :)
$

    There are other convenience environments defined for Tox [3]:

    • py27-repl, py35-repl, py36-repl and py37-repl run the Python 2.7, 3.5, 3.6 and 3.7 REPL, respectively, in the appropriate virtual environment. The ptrie package is pip-installed by Tox when the environments are created. Arguments to the interpreter can be passed in the command line after a double dash (--).

    • py27-test, py35-test, py36-test and py37-test run Pytest using the Python 2.7, 3.5, 3.6 and 3.7 interpreter, respectively, in the appropriate virtual environment. Arguments to pytest can be passed in the command line after a double dash (--) , for example:

      $ PKG_NAME=ptrie tox -e py27-test -- -x test_ptrie.py
GLOB sdist-make: .../ptrie/setup.py
py27-pkg inst-nodeps: .../ptrie/.tox/.tmp/package/1/ptrie-1.1.6.zip
...
  py27-pkg: commands succeeded
  congratulations :)
$

    • py27-test, py35-test, py36-test and py37-test test code and branch coverage using the 2.7, 3.5, 3.6 and 3.7 interpreter, respectively, in the appropriate virtual environment. Arguments to pytest can be passed in the command line after a double dash (--). The report can be found in ${PTRIE_DIR}/.tox/py[PV]/usr/share/ptr ie/tests/htmlcov/index.html where [PV] stands for 2.7, 3.5, 3.6 or 3.7 depending on the interpreter used.

  8. Verify that continuous integration tests pass. The package has continuous integration configured for Linux, Apple macOS and Microsoft Windows (all via Azure DevOps).

  9. Document the new feature or bug fix (if needed). The script ${PTRIE_DIR}/pypkg/build_docs.py re-builds the whole package documentation (re-generates images, cogs source files, etc.):

    $ "${PTRIE_DIR}"/pypkg/build_docs.py -h
usage: build_docs.py [-h] [-d DIRECTORY] [-r]
                     [-n NUM_CPUS] [-t]

Build ptrie package documentation

optional arguments:
  -h, --help            show this help message and exit
  -d DIRECTORY, --directory DIRECTORY
                        specify source file directory
                        (default ../ptrie)
  -r, --rebuild         rebuild exceptions documentation.
                        If no module name is given all
                        modules with auto-generated
                        exceptions documentation are
                        rebuilt
  -n NUM_CPUS, --num-cpus NUM_CPUS
                        number of CPUs to use (default: 1)
  -t, --test            diff original and rebuilt file(s)
                        (exit code 0 indicates file(s) are
                        identical, exit code 1 indicates
                        file(s) are different)

Footnotes

[1]All examples are for the bash shell
[2]It is assumed that all the Python interpreters are in the executables path. Source code for the interpreters can be downloaded from Python’s main site
[3](1, 2) Tox configuration largely inspired by Ionel’s codelog

Changelog

  • 1.1.6 [2019-03-21]: Dependency bug fix
  • 1.1.5 [2019-03-21]: Dependency update
  • 1.1.4 [2019-03-21]: Documentation update
  • 1.1.3 [2019-03-04]: Documentation update
  • 1.1.2 [2019-03-02]: Critical dependencies update
  • 1.1.1 [2019-03-01]: Updated package management framework
  • 1.1.0 [2018-01-18]: Dropped support for Python interpreter versions 2.6, 3.3 and 3.4. Updated dependencies versions to their current versions
  • 1.0.6 [2017-02-09]: Package build enhancements and fixes
  • 1.0.5 [2017-02-07]: Python 3.6 support
  • 1.0.4 [2016-06-11]: Minor documentation build bug fix
  • 1.0.3 [2016-05-13]: Documentation update
  • 1.0.2 [2016-05-11]: Documentation update
  • 1.0.1 [2016-05-02]: Minor documentation and testing enhancements
  • 1.0.0 [2016-04-25]: Final release of 1.0.0 branch
  • 1.0.0rc1 [2016-04-25]: Initial commit, forked off putil PyPI package

License

The MIT License (MIT)

Copyright (c) 2013-2019 Pablo Acosta-Serafini

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Contents

PyPI version License Python versions supported Format

Continuous integration test status Continuous integration test coverage Documentation status

Description

This module can be used to build, handle, process and search tries

Interpreter

The package has been developed and tested with Python 2.7, 3.5, 3.6 and 3.7 under Linux (Debian, Ubuntu), Apple macOS and Microsoft Windows

Installing

$ pip install ptrie

Documentation

Available at Read the Docs

Contributing

  1. Abide by the adopted code of conduct

  2. Fork the repository from GitHub and then clone personal copy [1]:

    $ github_user=myname
$ git clone --recurse-submodules \
      https://github.com/"${github_user}"/ptrie.git
Cloning into 'ptrie'...
...
$ cd ptrie || exit 1
$ export PTRIE_DIR=${PWD}
$

  3. The package uses two sub-modules: a set of custom Pylint plugins to help with some areas of code quality and consistency (under the pylint_plugins directory), and a lightweight package management framework (under the pypkg directory). Additionally, the pre-commit framework is used to perform various pre-commit code quality and consistency checks. To enable the pre-commit hooks:

    $ cd "${PTRIE_DIR}" || exit 1
$ pre-commit install
pre-commit installed at .../ptrie/.git/hooks/pre-commit
$

  4. Ensure that the Python interpreter can find the package modules (update the $PYTHONPATH environment variable, or use sys.paths(), etc.)

    $ export PYTHONPATH=${PYTHONPATH}:${PTRIE_DIR}
$

  5. Install the dependencies (if needed, done automatically by pip):

  6. Implement a new feature or fix a bug

  7. Write a unit test which shows that the contributed code works as expected. Run the package tests to ensure that the bug fix or new feature does not have adverse side effects. If possible achieve 100% code and branch coverage of the contribution. Thorough package validation can be done via Tox and Pytest:

    $ PKG_NAME=ptrie tox
GLOB sdist-make: .../ptrie/setup.py
py27-pkg create: .../ptrie/.tox/py27
py27-pkg installdeps: -r.../ptrie/requirements/tests_py27.pip, -r.../ptrie/requirements/docs_py27.pip
...
  py27-pkg: commands succeeded
  py35-pkg: commands succeeded
  py36-pkg: commands succeeded
  py37-pkg: commands succeeded
  congratulations :)
$

    Setuptools can also be used (Tox is configured as its virtual environment manager):

    $ PKG_NAME=ptrie python setup.py tests
running tests
running egg_info
writing ptrie.egg-info/PKG-INFO
writing dependency_links to ptrie.egg-info/dependency_links.txt
writing requirements to ptrie.egg-info/requires.txt
...
  py27-pkg: commands succeeded
  py35-pkg: commands succeeded
  py36-pkg: commands succeeded
  py37-pkg: commands succeeded
  congratulations :)
$

    Tox (or Setuptools via Tox) runs with the following default environments: py27-pkg, py35-pkg, py36-pkg and py37-pkg [3]. These use the 2.7, 3.5, 3.6 and 3.7 interpreters, respectively, to test all code in the documentation (both in Sphinx *.rst source files and in docstrings), run all unit tests, measure test coverage and re-build the exceptions documentation. To pass arguments to Pytest (the test runner) use a double dash (--) after all the Tox arguments, for example:

    $ PKG_NAME=ptrie tox -e py27-pkg -- -n 4
GLOB sdist-make: .../ptrie/setup.py
py27-pkg inst-nodeps: .../ptrie/.tox/.tmp/package/1/ptrie-1.1.6.zip
...
  py27-pkg: commands succeeded
  congratulations :)
$

    Or use the -a Setuptools optional argument followed by a quoted string with the arguments for Pytest. For example:

    $ PKG_NAME=ptrie python setup.py tests -a "-e py27-pkg -- -n 4"
running tests
...
  py27-pkg: commands succeeded
  congratulations :)
$

    There are other convenience environments defined for Tox [3]:

    • py27-repl, py35-repl, py36-repl and py37-repl run the Python 2.7, 3.5, 3.6 and 3.7 REPL, respectively, in the appropriate virtual environment. The ptrie package is pip-installed by Tox when the environments are created. Arguments to the interpreter can be passed in the command line after a double dash (--).

    • py27-test, py35-test, py36-test and py37-test run Pytest using the Python 2.7, 3.5, 3.6 and 3.7 interpreter, respectively, in the appropriate virtual environment. Arguments to pytest can be passed in the command line after a double dash (--) , for example:

      $ PKG_NAME=ptrie tox -e py27-test -- -x test_ptrie.py
GLOB sdist-make: .../ptrie/setup.py
py27-pkg inst-nodeps: .../ptrie/.tox/.tmp/package/1/ptrie-1.1.6.zip
...
  py27-pkg: commands succeeded
  congratulations :)
$

    • py27-test, py35-test, py36-test and py37-test test code and branch coverage using the 2.7, 3.5, 3.6 and 3.7 interpreter, respectively, in the appropriate virtual environment. Arguments to pytest can be passed in the command line after a double dash (--). The report can be found in ${PTRIE_DIR}/.tox/py[PV]/usr/share/ptr ie/tests/htmlcov/index.html where [PV] stands for 2.7, 3.5, 3.6 or 3.7 depending on the interpreter used.

  8. Verify that continuous integration tests pass. The package has continuous integration configured for Linux, Apple macOS and Microsoft Windows (all via Azure DevOps).

  9. Document the new feature or bug fix (if needed). The script ${PTRIE_DIR}/pypkg/build_docs.py re-builds the whole package documentation (re-generates images, cogs source files, etc.):

    $ "${PTRIE_DIR}"/pypkg/build_docs.py -h
usage: build_docs.py [-h] [-d DIRECTORY] [-r]
                     [-n NUM_CPUS] [-t]

Build ptrie package documentation

optional arguments:
  -h, --help            show this help message and exit
  -d DIRECTORY, --directory DIRECTORY
                        specify source file directory
                        (default ../ptrie)
  -r, --rebuild         rebuild exceptions documentation.
                        If no module name is given all
                        modules with auto-generated
                        exceptions documentation are
                        rebuilt
  -n NUM_CPUS, --num-cpus NUM_CPUS
                        number of CPUs to use (default: 1)
  -t, --test            diff original and rebuilt file(s)
                        (exit code 0 indicates file(s) are
                        identical, exit code 1 indicates
                        file(s) are different)

Footnotes

[1]All examples are for the bash shell
[2]It is assumed that all the Python interpreters are in the executables path. Source code for the interpreters can be downloaded from Python’s main site
[3](1, 2) Tox configuration largely inspired by Ionel’s codelog

Changelog

  • 1.1.6 [2019-03-21]: Dependency bug fix
  • 1.1.5 [2019-03-21]: Dependency update
  • 1.1.4 [2019-03-21]: Documentation update
  • 1.1.3 [2019-03-04]: Documentation update
  • 1.1.2 [2019-03-02]: Critical dependencies update
  • 1.1.1 [2019-03-01]: Updated package management framework
  • 1.1.0 [2018-01-18]: Dropped support for Python interpreter versions 2.6, 3.3 and 3.4. Updated dependencies versions to their current versions
  • 1.0.6 [2017-02-09]: Package build enhancements and fixes
  • 1.0.5 [2017-02-07]: Python 3.6 support
  • 1.0.4 [2016-06-11]: Minor documentation build bug fix
  • 1.0.3 [2016-05-13]: Documentation update
  • 1.0.2 [2016-05-11]: Documentation update
  • 1.0.1 [2016-05-02]: Minor documentation and testing enhancements
  • 1.0.0 [2016-04-25]: Final release of 1.0.0 branch
  • 1.0.0rc1 [2016-04-25]: Initial commit, forked off putil PyPI package

License

The MIT License (MIT)

Copyright (c) 2013-2019 Pablo Acosta-Serafini

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

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 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__()

Return 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__()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Search 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

Indices and tables