diff options
42 files changed, 3857 insertions, 0 deletions
diff --git a/.github/CODEOWNERS b/.github/CODEOWNERS new file mode 100644 index 0000000..9f28f1e --- /dev/null +++ b/.github/CODEOWNERS @@ -0,0 +1,2 @@ +* @caesar0301 +* @liamlundy diff --git a/.github/workflows/pypi-publish.yml b/.github/workflows/pypi-publish.yml new file mode 100644 index 0000000..bdaab28 --- /dev/null +++ b/.github/workflows/pypi-publish.yml @@ -0,0 +1,39 @@ +# This workflow will upload a Python Package using Twine when a release is created +# For more information see: https://docs.github.com/en/actions/automating-builds-and-tests/building-and-testing-python#publishing-to-package-registries + +# This workflow uses actions that are not certified by GitHub. +# They are provided by a third-party and are governed by +# separate terms of service, privacy policy, and support +# documentation. + +name: Upload Python Package + +on: + release: + types: [published] + +permissions: + contents: read + +jobs: + deploy: + + runs-on: ubuntu-latest + + steps: + - uses: actions/checkout@v3 + - name: Set up Python + uses: actions/setup-python@v3 + with: + python-version: '3.x' + - name: Install dependencies + run: | + python -m pip install --upgrade pip + pip install build + - name: Build package + run: python -m build + - name: Publish package + uses: pypa/gh-action-pypi-publish@27b31702a0e7fc50959f5ad993c78deac1bdfc29 + with: + user: __token__ + password: ${{ secrets.PYPI_API_TOKEN }} diff --git a/.github/workflows/python-package.yml b/.github/workflows/python-package.yml new file mode 100644 index 0000000..5ffa075 --- /dev/null +++ b/.github/workflows/python-package.yml @@ -0,0 +1,59 @@ +# This workflow will install Python dependencies, run tests and lint with a variety of Python versions +# For more information see: https://docs.github.com/en/actions/automating-builds-and-tests/building-and-testing-python +name: Package testing + +on: + push: + branches: [ "master", "dev" ] + pull_request: + branches: [ "master" ] + +jobs: + build-pre37: + + runs-on: ubuntu-latest + strategy: + fail-fast: false + matrix: + python-version: ["2.7"] + + steps: + - uses: actions/checkout@v3 + - name: Set up Python ${{ matrix.python-version }} + uses: actions/setup-python@v3 + with: + python-version: ${{ matrix.python-version }} + - name: Install dependencies + run: | + python -m pip install --upgrade pip + if [ -f requirements.txt ]; then pip install -r requirements.txt; fi + if [ -f requirements-t-pre37.txt ]; then pip install -r requirements-t-pre37.txt; fi + - name: Test with nosetests + run: | + ./scripts/testing.sh + + build: + + runs-on: ubuntu-latest + strategy: + fail-fast: false + matrix: + python-version: ["3.7", "3.8", "3.9", "3.10", "3.11"] + + steps: + - uses: actions/checkout@v3 + - name: Set up Python ${{ matrix.python-version }} + uses: actions/setup-python@v3 + with: + python-version: ${{ matrix.python-version }} + - name: Install dependencies + run: | + python -m pip install --upgrade pip + if [ -f requirements.txt ]; then pip install -r requirements.txt; fi + if [ -f requirements-t.txt ]; then pip install -r requirements-t.txt; fi + - name: Lint with flake8 + run: | + ./scripts/flake8.sh + - name: Test with pytest + run: | + pytest diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..0144f2f --- /dev/null +++ b/.gitignore @@ -0,0 +1,41 @@ +*.py[cod] +.idea +env/* +.python-version + +# C extensions +*.so + +# Packages +*.egg +*.egg-info +dist +build +eggs +parts +bin +var +sdist +develop-eggs +.installed.cfg +lib +lib64 +__pycache__ +\.vscode/* + +# Installer logs +pip-log.txt + +# Unit test / coverage reports +.coverage +.tox +nosetests.xml + +# Translations +*.mo + +# Mr Developer +.mr.developer.cfg +.project +.pydevproject +*.swp diff --git a/.travis.yml b/.travis.yml new file mode 100644 index 0000000..944c475 --- /dev/null +++ b/.travis.yml @@ -0,0 +1,15 @@ +language: python +python: + - "2.7" + - "3.4" + - "3.5" + - "3.6" + - "3.7" + - "3.8" + +install: + - "python setup.py install" + +script: + - pip install -r requirements-testing.txt + - sh testing.sh @@ -0,0 +1,10 @@ +# Contributors + +* Brett Alistair Kromkamp (brettkromkamp@gmail.com): Post basic idea online. +* Xiaming Chen (chenxm35@gmail.com): Finished primary parts and made the library freely public. +* Holger Bast (holgerbast@gmx.de): Replaced list with `dict` for fast node index and optimized the performance. +* Ilya Kuprik (ilya-spy@ynadex.ru): Added ZIGZAG tree-walk algorithm to tree traversal. + +and other committers etc. + +Thank you all. @@ -0,0 +1,53 @@ +# History + +Mar 27, 2023 V1.6.3 +Apply to black code style. Migrate future to six + + +Oct 13, 2019 V1.5.6 +Add ability to independently mutate multiple shallow copies of same initial tree. + + +Aug 10, 2017 V1.4.0 +Abandon supporting Python 3.2 since v1.4.0. + + +Mar 27, 2014 V1.2.6 +Node identifier supports multiple data types beyond int and str. +Finish depth() and leaves() routines. +Add siblings() routine. +Add unit test to the whole module. + + +Dec 21, 2013 V1.2.5 +Add root() routine to Tree class. +Add all_nodes() routine to Tree class. + + +May 1, 2013 +Pulish the module on PyPI with version 1.2 under GNU General Pulic License +version 3. + + +Mar 21, 2013 +Replace the list implementation with dict to improve performance to a +large extend. Thanks to @aronadaal + + +Dec 30, 2012 +Make a pretty print routine to the tree and give some examples in README + + +Dec 19, 2012 +Little modification and add get_node routine by @pgebhard. + + +Jul 13, 2012 +Add rsearch routines to implement reversed searching from leaf to tree root. + + +Jul 07, 2012 +Initiate the project on GitHub. +For my research paper, I need the python implementation of tree structure. +Based on the imcompleted code of Brett A. Kromkamp, I finished all methods +and added subtree and paste routines. @@ -0,0 +1,16 @@ +Thanks for downloading treelib. + +To install it, make sure you have Python 2.6 or greater installed. Then run +this command from the command prompt: + + python setup.py install + +If you're upgrading from a previous version, you need to remove it first. + +AS AN ALTERNATIVE, you can just copy the entire "treelib" directory to Python's +site-packages directory, which is located wherever your Python installation +lives. Some places you might check are: + + /usr/lib/python2.7/site-packages (Unix, Python 2.7) + /usr/lib/python2.6/site-packages (Unix, Python 2.6) + C:\\PYTHON\site-packages (Windows) @@ -0,0 +1,21 @@ +treelib - Simple to use for you. +Python 2/3 Tree Implementation + +Copyright (C) 2011 + Brett Alistair Kromkamp - brettkromkamp@gmail.com +Copyright (C) 2012-2017 + Xiaming Chen - chenxm35@gmail.com + and other contributors. +All rights reserved. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License.
\ No newline at end of file diff --git a/MANIFEST.in b/MANIFEST.in new file mode 100644 index 0000000..dbf81f1 --- /dev/null +++ b/MANIFEST.in @@ -0,0 +1,8 @@ +include README* +include HISTORY* +include LICENSE* +include MANIFEST* +include *.py +recursive-include treelib *.py +recursive-include tests *.py +recursive-include examples *.py diff --git a/README.md b/README.md new file mode 100644 index 0000000..c1ee089 --- /dev/null +++ b/README.md @@ -0,0 +1,38 @@ +# treelib + +Tree implementation in python: simple for you to use. + +[](https://github.com/caesar0301/treelib/actions) +[](https://github.com/psf/black) +[](http://treelib.readthedocs.io/en/latest/?badge=latest) +[](https://pypi.python.org/pypi/treelib) +[](https://pypi.python.org/pypi/treelib) +[](https://pypi.python.org/pypi/treelib) +[](https://pypi.python.org/pypi/treelib/) +[](https://GitHub.com/caesar0301/treelib/graphs/contributors/) + +[](http://makeapullrequest.com) +[](https://GitHub.com/caesar0301/treelib/pulls) +[](https://GitHub.com/caesar0301/treelib/pulls?q=is%3Apr+is%3Aclosed) + +## Quick Start + + pip install -U treelib + +## Documentation + +For installation, APIs and examples, see http://treelib.readthedocs.io/en/latest/ + +## Code Style + +`treelib` complies with [black](https://github.com/psf/black) formatter and +specific [flake8 validations](https://github.com/caesar0301/treelib/blob/master/scripts/flake8.sh). +Before creating a pull request, please make sure you pass the local validation +with `scripts/flake8.sh`. + +## Contributors + +Thank you all, +[committers](https://github.com/caesar0301/treelib/graphs/contributors). + +[](https://GitHub.com/Naereen/) diff --git a/docs/Makefile b/docs/Makefile new file mode 100644 index 0000000..69fe55e --- /dev/null +++ b/docs/Makefile @@ -0,0 +1,19 @@ +# Minimal makefile for Sphinx documentation +# + +# You can set these variables from the command line. +SPHINXOPTS = +SPHINXBUILD = sphinx-build +SOURCEDIR = source +BUILDDIR = build + +# Put it first so that "make" without argument is like "make help". +help: + @$(SPHINXBUILD) -M help "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O) + +.PHONY: help Makefile + +# Catch-all target: route all unknown targets to Sphinx using the new +# "make mode" option. $(O) is meant as a shortcut for $(SPHINXOPTS). +%: Makefile + @$(SPHINXBUILD) -M $@ "$(SOURCEDIR)" "$(BUILDDIR)" $(SPHINXOPTS) $(O)
\ No newline at end of file diff --git a/docs/make.bat b/docs/make.bat new file mode 100644 index 0000000..543c6b1 --- /dev/null +++ b/docs/make.bat @@ -0,0 +1,35 @@ +@ECHO OFF
+
+pushd %~dp0
+
+REM Command file for Sphinx documentation
+
+if "%SPHINXBUILD%" == "" (
+ set SPHINXBUILD=sphinx-build
+)
+set SOURCEDIR=source
+set BUILDDIR=build
+
+if "%1" == "" goto help
+
+%SPHINXBUILD% >NUL 2>NUL
+if errorlevel 9009 (
+ echo.
+ echo.The 'sphinx-build' command was not found. Make sure you have Sphinx
+ echo.installed, then set the SPHINXBUILD environment variable to point
+ echo.to the full path of the 'sphinx-build' executable. Alternatively you
+ echo.may add the Sphinx directory to PATH.
+ echo.
+ echo.If you don't have Sphinx installed, grab it from
+ echo.http://sphinx-doc.org/
+ exit /b 1
+)
+
+%SPHINXBUILD% -M %1 %SOURCEDIR% %BUILDDIR% %SPHINXOPTS%
+goto end
+
+:help
+%SPHINXBUILD% -M help %SOURCEDIR% %BUILDDIR% %SPHINXOPTS%
+
+:end
+popd
diff --git a/docs/publish.sh b/docs/publish.sh new file mode 100755 index 0000000..4839ba7 --- /dev/null +++ b/docs/publish.sh @@ -0,0 +1,12 @@ +#!/bin/bash + +SOURCE=source +PYLIB=../treelib +TARGET=html +BUILT=build + +rm -rf $BUILD +sphinx-apidoc -o $SOURCE $PYLIB +make $TARGET +touch $BUILT/$TARGET/.nojekyll +ghp-import -p $BUILT/$TARGET diff --git a/docs/requirements.txt b/docs/requirements.txt new file mode 100644 index 0000000..e4472be --- /dev/null +++ b/docs/requirements.txt @@ -0,0 +1,2 @@ +ghp-import==0.5.5 +sphinx==1.8.1 diff --git a/docs/source/conf.py b/docs/source/conf.py new file mode 100644 index 0000000..11cb707 --- /dev/null +++ b/docs/source/conf.py @@ -0,0 +1,187 @@ +# -*- coding: utf-8 -*- +# +# Configuration file for the Sphinx documentation builder. +# +# This file does only contain a selection of the most common options. For a +# full list see the documentation: +# http://www.sphinx-doc.org/en/master/config + +# -- Path setup -------------------------------------------------------------- + +# If extensions (or modules to document with autodoc) are in another directory, +# add these directories to sys.path here. If the directory is relative to the +# documentation root, use os.path.abspath to make it absolute, like shown here. +# +import os +import sys +sys.path.insert(0, os.path.abspath('../..')) + +from setup import __version__ + +# -- Project information ----------------------------------------------------- + +project = u'treelib' +copyright = u'2018, Xiaming Chen' +author = u'Xiaming Chen' + +# The short X.Y version +version = __version__ +# The full version, including alpha/beta/rc tags +release = __version__ + + +# -- General configuration --------------------------------------------------- + +# If your documentation needs a minimal Sphinx version, state it here. +# +# needs_sphinx = '1.0' + +# Add any Sphinx extension module names here, as strings. They can be +# extensions coming with Sphinx (named 'sphinx.ext.*') or your custom +# ones. +extensions = [ + 'sphinx.ext.autodoc', + 'sphinx.ext.coverage', + 'sphinx.ext.mathjax', + 'sphinx.ext.viewcode', + 'sphinx.ext.githubpages', +] + +# Add any paths that contain templates here, relative to this directory. +templates_path = ['_templates'] + +# The suffix(es) of source filenames. +# You can specify multiple suffix as a list of string: +# +# source_suffix = ['.rst', '.md'] +source_suffix = '.rst' + +# The master toctree document. +master_doc = 'index' + +# The language for content autogenerated by Sphinx. Refer to documentation +# for a list of supported languages. +# +# This is also used if you do content translation via gettext catalogs. +# Usually you set "language" from the command line for these cases. +language = None + +# List of patterns, relative to source directory, that match files and +# directories to ignore when looking for source files. +# This pattern also affects html_static_path and html_extra_path. +exclude_patterns = [] + +# The name of the Pygments (syntax highlighting) style to use. +pygments_style = None + + +# -- Options for HTML output ------------------------------------------------- + +# The theme to use for HTML and HTML Help pages. See the documentation for +# a list of builtin themes. +# +html_theme = 'alabaster' + +# Theme options are theme-specific and customize the look and feel of a theme +# further. For a list of options available for each theme, see the +# documentation. +# +# html_theme_options = {} + +# Add any paths that contain custom static files (such as style sheets) here, +# relative to this directory. They are copied after the builtin static files, +# so a file named "default.css" will overwrite the builtin "default.css". +html_static_path = ['_static'] + +# Custom sidebar templates, must be a dictionary that maps document names +# to template names. +# +# The default sidebars (for documents that don't match any pattern) are +# defined by theme itself. Builtin themes are using these templates by +# default: ``['localtoc.html', 'relations.html', 'sourcelink.html', +# 'searchbox.html']``. +# +# html_sidebars = {} + + +# -- Options for HTMLHelp output --------------------------------------------- + +# Output file base name for HTML help builder. +htmlhelp_basename = 'treelibdoc' + + +# -- Options for LaTeX output ------------------------------------------------ + +latex_elements = { + # The paper size ('letterpaper' or 'a4paper'). + # + # 'papersize': 'letterpaper', + + # The font size ('10pt', '11pt' or '12pt'). + # + # 'pointsize': '10pt', + + # Additional stuff for the LaTeX preamble. + # + # 'preamble': '', + + # Latex figure (float) alignment + # + # 'figure_align': 'htbp', +} + +# Grouping the document tree into LaTeX files. List of tuples +# (source start file, target name, title, +# author, documentclass [howto, manual, or own class]). +latex_documents = [ + (master_doc, 'treelib.tex', u'treelib Documentation', + u'Xiaming Chen', 'manual'), +] + + +# -- Options for manual page output ------------------------------------------ + +# One entry per manual page. List of tuples +# (source start file, name, description, authors, manual section). +man_pages = [ + (master_doc, 'treelib', u'treelib Documentation', + [author], 1) +] + + +# -- Options for Texinfo output ---------------------------------------------- + +# Grouping the document tree into Texinfo files. List of tuples +# (source start file, target name, title, author, +# dir menu entry, description, category) +texinfo_documents = [ + (master_doc, 'treelib', u'treelib Documentation', + author, 'treelib', 'One line description of project.', + 'Miscellaneous'), +] + + +# -- Options for Epub output ------------------------------------------------- + +# Bibliographic Dublin Core info. +epub_title = project + +# The unique identifier of the text. This can be a ISBN number +# or the project homepage. +# +# epub_identifier = '' + +# A unique identification for the text. +# +# epub_uid = '' + +# A list of files that should not be packed into the epub file. +epub_exclude_files = ['search.html'] + + +# -- Extension configuration ------------------------------------------------- + +# -- Options for intersphinx extension --------------------------------------- + +# Example configuration for intersphinx: refer to the Python standard library. +intersphinx_mapping = {'https://docs.python.org/': None}
\ No newline at end of file diff --git a/docs/source/index.rst b/docs/source/index.rst new file mode 100644 index 0000000..2834bec --- /dev/null +++ b/docs/source/index.rst @@ -0,0 +1,241 @@ +.. treelib documentation master file, created by + sphinx-quickstart on Thu Dec 20 16:30:18 2018. + You can adapt this file completely to your liking, but it should at least + contain the root `toctree` directive. + +Welcome to treelib's documentation! +*********************************** + +.. toctree:: + :maxdepth: 2 + :caption: Contents: + +Introduction +============ + +`Tree <http://en.wikipedia.org/wiki/Tree_%28data_structure%29>`_ is an +important data structure in computer science. Examples are shown in ML algorithm designs such as random forest tree and software engineering such as file system index. `treelib <https://github.com/caesar0301/pyTree>`_ is created to provide an efficient implementation of tree data structure in Python. + +The main features of `treelib` includes: + * Efficient operation of node searching, O(1). + * Support common tree operations like **traversing**, **insertion**, **deletion**, **node moving**, **shallow/deep copying**, **subtree cutting** etc. + * Support user-defined data payload to accelerate your model construction. + * Pretty tree showing and text/json dump for pretty show and offline analysis. + * Compatible with Python 2 and 3. + +Installation +============ + +The rapidest way to install treelib is using the package management tools like +``easy_install`` or ``pip`` with command + + .. code-block:: sh + + $ sudo easy_install -U treelib + +or the setup script + + .. code-block:: sh + + $ sudo python setup.py install + +**Note**: With the package management tools, the hosted version may be falling +behind current development branch on `Github +<https://github.com/caesar0301/pyTree>`_. If you encounter some problems, try +the freshest version on Github or open `issues +<https://github.com/caesar0301/pyTree/issues>`_ to let me know your problem. + +Examples +======== + +Basic Usage +------------- + +.. code-block:: sh + + >>> from treelib import Node, Tree + >>> tree = Tree() + >>> tree.create_node("Harry", "harry") # root node + >>> tree.create_node("Jane", "jane", parent="harry") + >>> tree.create_node("Bill", "bill", parent="harry") + >>> tree.create_node("Diane", "diane", parent="jane") + >>> tree.create_node("Mary", "mary", parent="diane") + >>> tree.create_node("Mark", "mark", parent="jane") + >>> tree.show() + Harry + ├── Bill + └── Jane + ├── Diane + │ └── Mary + └── Mark + + +API Examples +-------------- + +**Example 1**: Expand a tree with specific mode (Tree.DEPTH [default], +Tree.WIDTH, Tree.ZIGZAG). + +.. code-block:: sh + + >>> print(','.join([tree[node].tag for node in \ + tree.expand_tree(mode=Tree.DEPTH)])) + Harry,Bill,Jane,Diane,Mary,Mark + +**Example 2**: Expand tree with custom filter. + +.. code-block:: sh + + >>> print(','.join([tree[node].tag for node in \ + tree.expand_tree(filter = lambda x: \ + x.identifier != 'diane')])) + Harry,Bill,Jane,Mark + +**Example 3**: Get a subtree with the root of 'diane'. + +.. code-block:: sh + + >>> sub_t = tree.subtree('diane') + >>> sub_t.show() + Diane + └── Mary + +**Example 4**: Paste a new tree to the original one. + +.. code-block:: sh + + >>> new_tree = Tree() + >>> new_tree.create_node("n1", 1) # root node + >>> new_tree.create_node("n2", 2, parent=1) + >>> new_tree.create_node("n3", 3, parent=1) + >>> tree.paste('bill', new_tree) + >>> tree.show() + Harry + ├── Bill + │ └── n1 + │ ├── n2 + │ └── n3 + └── Jane + ├── Diane + │ └── Mary + └── Mark + +**Example 5**: Remove the existing node from the tree + +.. code-block:: sh + + >>> tree.remove_node(1) + >>> tree.show() + Harry + ├── Bill + └── Jane + ├── Diane + │ └── Mary + └── Mark + +**Example 6**: Move a node to another parent. + +.. code-block:: sh + + >>> tree.move_node('mary', 'harry') + >>> tree.show() + Harry + ├── Bill + ├── Jane + │ ├── Diane + │ └── Mark + └── Mary + +**Example 7**: Get the height of the tree. + +.. code-block:: sh + + >>> tree.depth() + 2 + +**Example 8**: Get the level of a node. + +.. code-block:: sh + + >>> node = tree.get_node("bill") + >>> tree.depth(node) + 1 + +**Example 9**: Print or dump tree structure. For example, the same tree in + basic example can be printed with 'ascii-em': + +.. code-block:: sh + + >>> tree.show(line_type="ascii-em") + Harry + ╠══ Bill + ╠══ Jane + ║ ╠══ Diane + ║ ╚══ Mark + ╚══ Mary + +In the JSON form, to_json() takes optional parameter with_data to trigger if +the data field is appended into JSON string. For example, + +.. code-block:: sh + + >>> print(tree.to_json(with_data=True)) + {"Harry": {"data": null, "children": [{"Bill": {"data": null}}, {"Jane": {"data": null, "children": [{"Diane": {"data": null}}, {"Mark": {"data": null}}]}}, {"Mary": {"data": null}}]}} + +**Example 10**: Save tree into file + The function save2file require a filename. + The file is opened to write using mode 'ab'. + +.. code-block:: sh + + >>> tree.save2file('tree.txt') + + +Advanced Usage +---------------- + +Sometimes, you need trees to store your own data. The newest version of +:mod:`treelib` supports ``.data`` variable to store whatever you want. For +example, to define a flower tree with your own data: + +.. code-block:: sh + + >>> class Flower(object): \ + def __init__(self, color): \ + self.color = color + +You can create a flower tree now: + +.. code-block:: sh + + >>> ftree = Tree() + >>> ftree.create_node("Root", "root", data=Flower("black")) + >>> ftree.create_node("F1", "f1", parent='root', data=Flower("white")) + >>> ftree.create_node("F2", "f2", parent='root', data=Flower("red")) + +Printing the colors of the tree: + +.. code-block:: sh + + >>> ftree.show(data_property="color") + black + ├── white + └── red + +**Notes:** Before version 1.2.5, you may need to inherit and modify the behaviors of tree. Both are supported since then. For flower example, + +.. code-block:: sh + + >>> class FlowerNode(treelib.Node): \ + def __init__(self, color): \ + self.color = color + >>> # create a new node + >>> fnode = FlowerNode("white") + + +Indices and tables +================== + +* :ref:`genindex` +* :ref:`modindex` +* :ref:`search` diff --git a/docs/source/modules.rst b/docs/source/modules.rst new file mode 100644 index 0000000..9e7d4d7 --- /dev/null +++ b/docs/source/modules.rst @@ -0,0 +1,7 @@ +treelib +======= + +.. toctree:: + :maxdepth: 4 + + treelib diff --git a/docs/source/treelib.rst b/docs/source/treelib.rst new file mode 100644 index 0000000..c6034e9 --- /dev/null +++ b/docs/source/treelib.rst @@ -0,0 +1,45 @@ +treelib package +=============== + +Module contents +--------------- + +.. automodule:: treelib + :members: + :undoc-members: + :show-inheritance: + +Submodules +---------- + +treelib.node module +------------------- + +.. automodule:: treelib.node + :members: + :undoc-members: + :show-inheritance: + +treelib.tree module +------------------- + +.. automodule:: treelib.tree + :members: + :undoc-members: + :show-inheritance: + +treelib.plugins module +---------------------- + +.. automodule:: treelib.plugins + :members: + :undoc-members: + :show-inheritance: + +treelib.exceptions module +------------------------- + +.. automodule:: treelib.exceptions + :members: + :undoc-members: + :show-inheritance: diff --git a/examples/family_tree.py b/examples/family_tree.py new file mode 100644 index 0000000..fa2293d --- /dev/null +++ b/examples/family_tree.py @@ -0,0 +1,65 @@ +#!/usr/bin/env python +# Example usage of treelib +# +# Author: chenxm +# +__author__ = "chenxm" + +from treelib import Tree + + +def create_family_tree(): + # Create the family tree + tree = Tree() + tree.create_node("Harry", "harry") # root node + tree.create_node("Jane", "jane", parent="harry") + tree.create_node("Bill", "bill", parent="harry") + tree.create_node("Diane", "diane", parent="jane") + tree.create_node("Mary", "mary", parent="diane") + tree.create_node("Mark", "mark", parent="jane") + return tree + + +def example(desp): + sep = "-" * 20 + "\n" + print(sep + desp) + + +if __name__ == "__main__": + tree = create_family_tree() + + example("Tree of the whole family:") + tree.show(key=lambda x: x.tag, reverse=True, line_type="ascii-em") + + example("All family members in DEPTH mode:") + print(",".join([tree[node].tag for node in tree.expand_tree()])) + + example("All family members (with identifiers) but Diane's sub-family:") + tree.show(idhidden=False, filter=lambda x: x.identifier != "diane") + + example("Let me introduce Diane family only:") + sub_t = tree.subtree("diane") + sub_t.show() + + example("Children of Diane:") + for child in tree.is_branch("diane"): + print(tree[child].tag) + + example("New members join Jill's family:") + new_tree = Tree() + new_tree.create_node("n1", 1) # root node + new_tree.create_node("n2", 2, parent=1) + new_tree.create_node("n3", 3, parent=1) + tree.paste("bill", new_tree) + tree.show() + + example("They leave after a while:") + tree.remove_node(1) + tree.show() + + example("Now Mary moves to live with grandfather Harry:") + tree.move_node("mary", "harry") + tree.show() + + example("A big family for Mark to send message to the oldest Harry:") + print(",".join([tree[node].tag for node in tree.rsearch("mark")])) diff --git a/examples/folder_tree.py b/examples/folder_tree.py new file mode 100644 index 0000000..695d6ef --- /dev/null +++ b/examples/folder_tree.py @@ -0,0 +1,207 @@ +#!/usr/bin/env python +# A file folder scanner contributed by @holger +# +# You can spicify the scanned folder and file pattern by changing rootPath +# and pattern variables +# + +__author__ = "holger" + +from treelib import tree + +import fnmatch +import os +import zlib +import argparse + +DEBUG = 0 +FILECOUNT = 0 +DIRCOUNT = 0 +DIR_ERRORLIST = [] +FILE_ERRORLIST = [] + + +# Time Profiling +PROFILING = 0 +# 0 - nothing +# 1 - time +# 2 - cProfile + +if PROFILING == 1: + import timeit +if PROFILING == 2: + import cProfile + + +parser = argparse.ArgumentParser( + description="Scan the given folder and print its structure in a tree." +) +parser.add_argument("abspath", type=str, help="An absolute path to be scanned.") +parser.add_argument( + "pattern", type=str, help="File name pattern to filtered, e.g. *.pdf" +) + +args = parser.parse_args() +rootPath = args.abspath +pattern = args.pattern + +folder_blacklist = [] + +dir_tree = tree.Tree() +dir_tree.create_node("Root", rootPath) # root node + + +def crc32(data): + data = bytes(data, "UTF-8") + + if DEBUG: + print("++++++ CRC32 ++++++") + print("input: " + str(data)) + print("crc32: " + hex(zlib.crc32(data) & 0xFFFFFFFF)) + print("+++++++++++++++++++") + return hex( + zlib.crc32(data) & 0xFFFFFFFF + ) # crc32 returns a signed value, &-ing it will match py3k + + +parent = rootPath +i = 1 + +# calculating start depth +start_depth = rootPath.count("/") + + +def get_noteid(depth, root, dir): + """get_noteid returns + - depth contains the current depth of the folder hierarchy + - dir contains the current directory + + Function returns a string containing the current depth, the folder name and unique ID build by hashing the + absolute path of the directory. All spaces are replaced by '_' + + <depth>_<dirname>+++<crc32> + e.g. 2_Folder_XYZ_1+++<crc32> + """ + return ( + str(str(depth) + "_" + dir).replace(" ", "_") + + "+++" + + crc32(os.path.join(root, dir)) + ) + + +# TODO: Verzeichnistiefe pruefen: Was ist mit sowas /mp3/ + + +def get_parentid(current_depth, root, dir): + # special case for the 'root' of the tree + # because we don't want a cryptic root-name + if current_depth == 0: + return root + + # looking for parent directory + # e.g. /home/user1/mp3/folder1/parent_folder/current_folder + # get 'parent_folder' + + search_string = os.path.join(root, dir) + pos2 = search_string.rfind("/") + pos1 = search_string.rfind("/", 0, pos2) + parent_dir = search_string[pos1 + 1 : pos2] # noqa: E203 + parentid = ( + str(current_depth - 1) + + "_" + + parent_dir.replace(" ", "_") + + "+++" + + crc32(root) + ) + return parentid + # TODO: catch error + + +def print_node(dir, node_id, parent_id): + print("#############################") + print("node created") + print(" dir: " + dir) + print(" note_id: " + node_id) + print(" parent: " + parent_id) + + +def crawler(): + global DIRCOUNT + global FILECOUNT + + for root, dirs, files in os.walk(rootPath): + # +++ DIRECTORIES +++ + for dir in dirs: + # calculating current depth + current_depth = os.path.join(root, dir).count("/") - start_depth + + if DEBUG: + print("current: " + os.path.join(root, dir)) + + node_id = get_noteid(current_depth, root, dir) + parent_id = str(get_parentid(current_depth, root, dir)) + + if parent_id == str(None): + DIR_ERRORLIST.append(os.path.join(root, dir)) + + if DEBUG: + print_node(dir, node_id, parent_id) + + # create node + dir_tree.create_node(dir, node_id, parent_id) + DIRCOUNT += 1 + + # +++ FILES +++ + for filename in fnmatch.filter(files, pattern): + if dir in folder_blacklist: + continue + + # calculating current depth + current_depth = os.path.join(root, filename).count("/") - start_depth + + if DEBUG: + print("current: " + os.path.join(root, filename)) + + node_id = get_noteid(current_depth, root, filename) + parent_id = str(get_parentid(current_depth, root, filename)) + + if parent_id == str(None): + FILE_ERRORLIST.append(os.path.join(root, dir)) + + if DEBUG: + print_node(filename, node_id, parent_id) + + # create node + dir_tree.create_node(filename, node_id, parent_id) + FILECOUNT += 1 + + +if PROFILING == 0: + crawler() +if PROFILING == 1: + t1 = timeit.Timer("crawler()", "from __main__ import crawler") + print("time: " + str(t1.timeit(number=1))) +if PROFILING == 2: + cProfile.run("crawler()") + + +print("filecount: " + str(FILECOUNT)) +print("dircount: " + str(DIRCOUNT)) + +if DIR_ERRORLIST: + for item in DIR_ERRORLIST: + print(item) +else: + print("no directory errors") + +print("\n\n\n") + +if FILE_ERRORLIST: + for item in FILE_ERRORLIST: + print(item) +else: + print("no file errors") + +print("nodes: " + str(len(dir_tree.nodes))) + +dir_tree.show() diff --git a/examples/recursive_dirtree_generator.py b/examples/recursive_dirtree_generator.py new file mode 100644 index 0000000..986cd1a --- /dev/null +++ b/examples/recursive_dirtree_generator.py @@ -0,0 +1,89 @@ +#!/usr/bin/env python + +""" +Example of treelib usage to generate recursive tree of directories. +It could be useful to implement Directory Tree data structure + +2016 samuelsh +""" + +import treelib +import random +import hashlib +from string import digits, letters +import sys + + +MAX_FILES_PER_DIR = 10 + + +def range2(stop): + if sys.version_info[0] < 3: + return xrange(stop) # noqa: F821 + else: + return range(stop) + + +def get_random_string(length): + return "".join(random.choice(digits + letters) for _ in range2(length)) + + +def build_recursive_tree(tree, base, depth, width): + """ + Args: + tree: Tree + base: Node + depth: int + width: int + + Returns: + + """ + if depth >= 0: + depth -= 1 + for i in range2(width): + directory = Directory() + tree.create_node( + "{0}".format(directory.name), + "{0}".format(hashlib.md5(directory.name)), + parent=base.identifier, + data=directory, + ) # node identifier is md5 hash of it's name + dirs_nodes = tree.children(base.identifier) + for dir in dirs_nodes: + newbase = tree.get_node(dir.identifier) + build_recursive_tree(tree, newbase, depth, width) + else: + return + + +class Directory(object): + def __init__(self): + self._name = get_random_string(64) + self._files = [ + File() for _ in range2(MAX_FILES_PER_DIR) + ] # Each directory contains 1000 files + + @property + def name(self): + return self._name + + @property + def files(self): + return self._files + + +class File(object): + def __init__(self): + self._name = get_random_string(64) + + @property + def name(self): + return self._name + + +tree = treelib.Tree() +base = tree.create_node("Root", "root") +build_recursive_tree(tree, base, 2, 10) + +tree.show() diff --git a/examples/save_tree_2_file.py b/examples/save_tree_2_file.py new file mode 100644 index 0000000..3b564f5 --- /dev/null +++ b/examples/save_tree_2_file.py @@ -0,0 +1,12 @@ +# -*- coding: utf-8 -*- + +from treelib import Tree + +tree = Tree() +tree.create_node("Harry", "harry") # root node +tree.create_node("Jane", "jane", parent="harry") +tree.create_node("Bill", "bill", parent="harry") +tree.create_node("Diane", "diane", parent="jane") +tree.create_node("Mary", "mary", parent="diane") +tree.create_node("Mark", "mark", parent="jane") +tree.save2file("tree.txt") diff --git a/recipe/conda_build.sh b/recipe/conda_build.sh new file mode 100644 index 0000000..9cf439b --- /dev/null +++ b/recipe/conda_build.sh @@ -0,0 +1,33 @@ +export VERSION="1.5.3" +export BUILD_NAME="0" +export CONDA_BLD_PATH=~/conda-bld +USER="e3sm" +PLATFORM="noarch" +PKG="treelib" + +if [ -d $CONDA_BLD_PATH ]; then + rm -rf $CONDA_BLD_PATH +fi +echo "Creating build dir at" $CONDA_BLD_PATH +mkdir $CONDA_BLD_PATH + +conda config --set anaconda_upload no +if [ ! -z "$1" ]; then + export TAG="$1" +else + export TAG="master" +fi +echo "Building" $VERSION"-"$BUILD_NAME "for label:" $TAG + +conda build . + +if [ $? -eq 1 ]; then + echo "conda build failed" + exit +fi + +if [ ! -z "$1" ]; then + anaconda upload -u $USER -l "$1" $CONDA_BLD_PATH/$PLATFORM/$PKG-$VERSION-$BUILD_NAME.tar.bz2 +else + anaconda upload -u $USER $CONDA_BLD_PATH/$PLATFORM/$PKG-$VERSION-$BUILD_NAME.tar.bz2 +fi diff --git a/recipe/meta.yaml b/recipe/meta.yaml new file mode 100644 index 0000000..7dad9ac --- /dev/null +++ b/recipe/meta.yaml @@ -0,0 +1,25 @@ +package: + name: treelib + version: {{ environ['VERSION'] }} + +source: + git_url: git://github.com/caesar0301/treelib.git + git_tag: {{ environ['TAG'] }} + +build: + script: python setup.py install + string: {{ environ['BUILD_NAME'] }} + noarch: python + +about: + home: https://treelib.readthedocs.io/en/latest/ + summary: An efficient implementation of tree data structure in python 2/3. + +requirements: + build: + - python + - setuptools + - pip + + run: + - python diff --git a/requirements-t-pre37.txt b/requirements-t-pre37.txt new file mode 100644 index 0000000..b50e6c3 --- /dev/null +++ b/requirements-t-pre37.txt @@ -0,0 +1,3 @@ +nose>=1.3.7 +nose-exclude>=0.5.0 +coverage>=4.4.1
\ No newline at end of file diff --git a/requirements-t.txt b/requirements-t.txt new file mode 100644 index 0000000..eaed303 --- /dev/null +++ b/requirements-t.txt @@ -0,0 +1,5 @@ +pytest>=7.0.0 +coverage>=4.4.1 +flake8==5.0.0 +flake8-black==0.3.6 +black==23.1.0
\ No newline at end of file diff --git a/requirements.txt b/requirements.txt new file mode 100644 index 0000000..63a9655 --- /dev/null +++ b/requirements.txt @@ -0,0 +1 @@ +six>=1.13.0
\ No newline at end of file diff --git a/scripts/flake8.sh b/scripts/flake8.sh new file mode 100755 index 0000000..b93226d --- /dev/null +++ b/scripts/flake8.sh @@ -0,0 +1,3 @@ +#!/bin/bash +flake8 . --count --select=E9,F63,F7,F82 --show-source --statistics +flake8 . --count --max-line-length=127 --exclude docs/source/conf.py --statistics diff --git a/scripts/testing.sh b/scripts/testing.sh new file mode 100755 index 0000000..28f70e2 --- /dev/null +++ b/scripts/testing.sh @@ -0,0 +1,6 @@ +#!/usr/bin/env bash + +nosetests --with-coverage --cover-package=treelib \ + --cover-erase --cover-tests \ + -d --all-modules \ + tests diff --git a/setup.cfg b/setup.cfg new file mode 100644 index 0000000..224a779 --- /dev/null +++ b/setup.cfg @@ -0,0 +1,2 @@ +[metadata] +description-file = README.md
\ No newline at end of file diff --git a/setup.py b/setup.py new file mode 100644 index 0000000..910e467 --- /dev/null +++ b/setup.py @@ -0,0 +1,39 @@ +from setuptools import setup + +__version__ = "1.6.4" + + +setup( + name="treelib", + version=__version__, + url="https://github.com/caesar0301/treelib", + author="Xiaming Chen", + author_email="chenxm35@gmail.com", + description="A Python 2/3 implementation of tree structure.", + long_description="""This is a simple tree data structure implementation in python.""", + license="Apache License, Version 2.0", + packages=["treelib"], + keywords=["data structure", "tree", "tools"], + install_requires=["six"], + classifiers=[ + "Development Status :: 4 - Beta", + "Environment :: Console", + "Intended Audience :: Developers", + "License :: OSI Approved :: Apache Software License", + "Operating System :: OS Independent", + "Programming Language :: Python", + "Programming Language :: Python :: 2", + "Programming Language :: Python :: 2.7", + "Programming Language :: Python :: 3", + "Programming Language :: Python :: 3.4", + "Programming Language :: Python :: 3.5", + "Programming Language :: Python :: 3.6", + "Programming Language :: Python :: 3.7", + "Programming Language :: Python :: 3.8", + "Programming Language :: Python :: 3.9", + "Programming Language :: Python :: 3.10", + "Programming Language :: Python :: 3.11", + "Programming Language :: Python :: 3.12", + "Topic :: Software Development :: Libraries :: Python Modules", + ], +) diff --git a/tests/__init__.py b/tests/__init__.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/tests/__init__.py diff --git a/tests/test_node.py b/tests/test_node.py new file mode 100644 index 0000000..b67dfe5 --- /dev/null +++ b/tests/test_node.py @@ -0,0 +1,88 @@ +import unittest + +from collections import defaultdict +from treelib import Node + + +class NodeCase(unittest.TestCase): + def setUp(self): + self.node1 = Node("Test One", "identifier 1") + self.node2 = Node("Test Two", "identifier 2") + + def test_initialization(self): + self.assertEqual(self.node1.tag, "Test One") + self.assertEqual(self.node1.identifier, "identifier 1") + # retro-compatibility + self.assertEqual(self.node1.bpointer, None) + self.assertEqual(self.node1.fpointer, []) + + self.assertEqual(self.node1.expanded, True) + self.assertEqual(self.node1._predecessor, {}) + self.assertEqual(self.node1._successors, defaultdict(list)) + self.assertEqual(self.node1.data, None) + + def test_set_tag(self): + self.node1.tag = "Test 1" + self.assertEqual(self.node1.tag, "Test 1") + self.node1.tag = "Test One" + + def test_object_as_node_tag(self): + node = Node(tag=(0, 1)) + self.assertEqual(node.tag, (0, 1)) + self.assertTrue(node.__repr__().startswith("Node")) + + def test_set_identifier(self): + self.node1.identifier = "ID1" + self.assertEqual(self.node1.identifier, "ID1") + self.node1.identifier = "identifier 1" + + def test_set_fpointer(self): + # retro-compatibility + self.node1.update_fpointer("identifier 2") + self.assertEqual(self.node1.fpointer, ["identifier 2"]) + self.node1.fpointer = [] + self.assertEqual(self.node1.fpointer, []) + + def test_update_successors(self): + self.node1.update_successors("identifier 2", tree_id="tree 1") + self.assertEqual(self.node1.successors("tree 1"), ["identifier 2"]) + self.assertEqual(self.node1._successors["tree 1"], ["identifier 2"]) + self.node1.set_successors([], tree_id="tree 1") + self.assertEqual(self.node1._successors["tree 1"], []) + + def test_set_bpointer(self): + # retro-compatibility + self.node2.update_bpointer("identifier 1") + self.assertEqual(self.node2.bpointer, "identifier 1") + self.node2.bpointer = None + self.assertEqual(self.node2.bpointer, None) + + def test_set_predecessor(self): + self.node2.set_predecessor("identifier 1", "tree 1") + self.assertEqual(self.node2.predecessor("tree 1"), "identifier 1") + self.assertEqual(self.node2._predecessor["tree 1"], "identifier 1") + self.node2.set_predecessor(None, "tree 1") + self.assertEqual(self.node2.predecessor("tree 1"), None) + + def test_set_is_leaf(self): + self.node1.update_fpointer("identifier 2") + self.node2.update_bpointer("identifier 1") + self.assertEqual(self.node1.is_leaf(), False) + self.assertEqual(self.node2.is_leaf(), True) + + def test_tree_wise_is_leaf(self): + self.node1.update_successors("identifier 2", tree_id="tree 1") + self.node2.set_predecessor("identifier 1", "tree 1") + self.assertEqual(self.node1.is_leaf("tree 1"), False) + self.assertEqual(self.node2.is_leaf("tree 1"), True) + + def test_data(self): + class Flower(object): + def __init__(self, color): + self.color = color + + def __str__(self): + return "%s" % self.color + + self.node1.data = Flower("red") + self.assertEqual(self.node1.data.color, "red") diff --git a/tests/test_plugins.py b/tests/test_plugins.py new file mode 100644 index 0000000..0f04fbf --- /dev/null +++ b/tests/test_plugins.py @@ -0,0 +1,113 @@ +#!/usr/bin/env python +# -*- coding: utf-8 -*- +from __future__ import unicode_literals + +import codecs +import os +import unittest + +from treelib import Tree +from treelib.plugins import export_to_dot + + +class DotExportCase(unittest.TestCase): + """Test class for the export to dot format function""" + + def setUp(self): + tree = Tree() + tree.create_node("Hárry", "hárry") + tree.create_node("Jane", "jane", parent="hárry") + tree.create_node("Bill", "bill", parent="hárry") + tree.create_node("Diane", "diane", parent="jane") + tree.create_node("George", "george", parent="bill") + self.tree = tree + + def read_generated_output(self, filename): + output = codecs.open(filename, "r", "utf-8") + generated = output.read() + output.close() + + return generated + + def test_export_to_dot(self): + export_to_dot(self.tree, "tree.dot") + expected = """\ +digraph tree { +\t"hárry" [label="Hárry", shape=circle] +\t"bill" [label="Bill", shape=circle] +\t"jane" [label="Jane", shape=circle] +\t"george" [label="George", shape=circle] +\t"diane" [label="Diane", shape=circle] + +\t"hárry" -> "jane" +\t"hárry" -> "bill" +\t"bill" -> "george" +\t"jane" -> "diane" +}""" + + self.assertTrue( + os.path.isfile("tree.dot"), "The file tree.dot could not be found." + ) + generated = self.read_generated_output("tree.dot") + + self.assertEqual( + generated, expected, "Generated dot tree is not the expected one" + ) + os.remove("tree.dot") + + def test_export_to_dot_empty_tree(self): + empty_tree = Tree() + export_to_dot(empty_tree, "tree.dot") + + expected = """\ +digraph tree { +}""" + self.assertTrue( + os.path.isfile("tree.dot"), "The file tree.dot could not be found." + ) + generated = self.read_generated_output("tree.dot") + + self.assertEqual( + expected, generated, "The generated output for an empty tree is not empty" + ) + os.remove("tree.dot") + + def test_unicode_filename(self): + tree = Tree() + tree.create_node("Node 1", "node_1") + export_to_dot(tree, "ŕʩϢ.dot") + + expected = """\ +digraph tree { +\t"node_1" [label="Node 1", shape=circle] +}""" + self.assertTrue( + os.path.isfile("ŕʩϢ.dot"), "The file ŕʩϢ.dot could not be found." + ) + generated = self.read_generated_output("ŕʩϢ.dot") + self.assertEqual( + expected, generated, "The generated file content is not the expected one" + ) + os.remove("ŕʩϢ.dot") + + def test_export_with_minus_in_filename(self): + tree = Tree() + tree.create_node("Example Node", "example-node") + expected = """\ +digraph tree { +\t"example-node" [label="Example Node", shape=circle] +}""" + + export_to_dot(tree, "id_with_minus.dot") + self.assertTrue( + os.path.isfile("id_with_minus.dot"), + "The file id_with_minus.dot could not be found.", + ) + generated = self.read_generated_output("id_with_minus.dot") + self.assertEqual( + expected, generated, "The generated file content is not the expected one" + ) + os.remove("id_with_minus.dot") + + def tearDown(self): + self.tree = None diff --git a/tests/test_tree.py b/tests/test_tree.py new file mode 100644 index 0000000..287b734 --- /dev/null +++ b/tests/test_tree.py @@ -0,0 +1,736 @@ +#!/usr/bin/env python +# -*- coding: utf-8 -*- +from __future__ import unicode_literals + +import sys + +import os + +import unittest +from treelib import Tree, Node +from treelib.tree import NodeIDAbsentError, LoopError + + +def encode(value): + if sys.version_info[0] == 2: + # Python2.x : + return value.encode("utf-8") + else: + # Python3.x : + return value + + +class TreeCase(unittest.TestCase): + def setUp(self): + tree = Tree(identifier="tree 1") + tree.create_node("Hárry", "hárry") + tree.create_node("Jane", "jane", parent="hárry") + tree.create_node("Bill", "bill", parent="hárry") + tree.create_node("Diane", "diane", parent="jane") + tree.create_node("George", "george", parent="bill") + # Hárry + # |-- Jane + # |-- Diane + # |-- Bill + # |-- George + self.tree = tree + self.copytree = Tree(self.tree, deep=True) + + @staticmethod + def get_t1(): + """ + root + ├── A + │ └── A1 + └── B + """ + t = Tree(identifier="t1") + t.create_node(tag="root", identifier="r") + t.create_node(tag="A", identifier="a", parent="r") + t.create_node(tag="B", identifier="b", parent="r") + t.create_node(tag="A1", identifier="a1", parent="a") + return t + + @staticmethod + def get_t2(): + """ + root2 + ├── C + └── D + └── D1 + """ + t = Tree(identifier="t2") + t.create_node(tag="root2", identifier="r2") + t.create_node(tag="C", identifier="c", parent="r2") + t.create_node(tag="D", identifier="d", parent="r2") + t.create_node(tag="D1", identifier="d1", parent="d") + return t + + def test_tree(self): + self.assertEqual(isinstance(self.tree, Tree), True) + self.assertEqual(isinstance(self.copytree, Tree), True) + + def test_is_root(self): + # retro-compatibility + self.assertTrue(self.tree._nodes["hárry"].is_root()) + self.assertFalse(self.tree._nodes["jane"].is_root()) + + def test_tree_wise_is_root(self): + subtree = self.tree.subtree("jane", identifier="subtree 2") + # harry is root of tree 1 but not present in subtree 2 + self.assertTrue(self.tree._nodes["hárry"].is_root("tree 1")) + self.assertNotIn("hárry", subtree._nodes) + # jane is not root of tree 1 but is root of subtree 2 + self.assertFalse(self.tree._nodes["jane"].is_root("tree 1")) + self.assertTrue(subtree._nodes["jane"].is_root("subtree 2")) + + def test_paths_to_leaves(self): + paths = self.tree.paths_to_leaves() + self.assertEqual(len(paths), 2) + self.assertTrue(["hárry", "jane", "diane"] in paths) + self.assertTrue(["hárry", "bill", "george"] in paths) + + def test_nodes(self): + self.assertEqual(len(self.tree.nodes), 5) + self.assertEqual(len(self.tree.all_nodes()), 5) + self.assertEqual(self.tree.size(), 5) + self.assertEqual(self.tree.get_node("jane").tag, "Jane") + self.assertEqual(self.tree.contains("jane"), True) + self.assertEqual("jane" in self.tree, True) + self.assertEqual(self.tree.contains("alien"), False) + self.tree.create_node("Alien", "alien", parent="jane") + self.assertEqual(self.tree.contains("alien"), True) + self.tree.remove_node("alien") + + def test_getitem(self): + """Nodes can be accessed via getitem.""" + for node_id in self.tree.nodes: + try: + self.tree[node_id] + except NodeIDAbsentError: + self.fail("Node access should be possible via getitem.") + try: + self.tree["root"] + except NodeIDAbsentError: + pass + else: + self.fail("There should be no default fallback value for getitem.") + + def test_parent(self): + for nid in self.tree.nodes: + if nid == self.tree.root: + self.assertEqual(self.tree.parent(nid), None) + else: + self.assertEqual(self.tree.parent(nid) in self.tree.all_nodes(), True) + + def test_ancestor(self): + for nid in self.tree.nodes: + if nid == self.tree.root: + self.assertEqual(self.tree.ancestor(nid), None) + else: + for level in range(self.tree.level(nid) - 1, 0, -1): + self.assertEqual( + self.tree.ancestor(nid, level=level) in self.tree.all_nodes(), + True, + ) + + def test_children(self): + for nid in self.tree.nodes: + children = self.tree.is_branch(nid) + for child in children: + self.assertEqual(self.tree[child] in self.tree.all_nodes(), True) + children = self.tree.children(nid) + for child in children: + self.assertEqual(child in self.tree.all_nodes(), True) + try: + self.tree.is_branch("alien") + except NodeIDAbsentError: + pass + else: + self.fail("The absent node should be declaimed.") + + def test_remove_node(self): + self.tree.create_node("Jill", "jill", parent="george") + self.tree.create_node("Mark", "mark", parent="jill") + self.assertEqual(self.tree.remove_node("jill"), 2) + self.assertEqual(self.tree.get_node("jill") is None, True) + self.assertEqual(self.tree.get_node("mark") is None, True) + + def test_tree_wise_depth(self): + # Try getting the level of this tree + self.assertEqual(self.tree.depth(), 2) + self.tree.create_node("Jill", "jill", parent="george") + self.assertEqual(self.tree.depth(), 3) + self.tree.create_node("Mark", "mark", parent="jill") + self.assertEqual(self.tree.depth(), 4) + + # Try getting the level of the node + """ + self.tree.show() + Hárry + |___ Bill + | |___ George + | |___ Jill + | |___ Mark + |___ Jane + | |___ Diane + """ + self.assertEqual(self.tree.depth(self.tree.get_node("mark")), 4) + self.assertEqual(self.tree.depth(self.tree.get_node("jill")), 3) + self.assertEqual(self.tree.depth(self.tree.get_node("george")), 2) + self.assertEqual(self.tree.depth("jane"), 1) + self.assertEqual(self.tree.depth("bill"), 1) + self.assertEqual(self.tree.depth("hárry"), 0) + + # Try getting Exception + node = Node("Test One", "identifier 1") + self.assertRaises(NodeIDAbsentError, self.tree.depth, node) + + # Reset the test case + self.tree.remove_node("jill") + + def test_leaves(self): + # retro-compatibility + leaves = self.tree.leaves() + for nid in self.tree.expand_tree(): + self.assertEqual( + (self.tree[nid].is_leaf()) == (self.tree[nid] in leaves), True + ) + leaves = self.tree.leaves(nid="jane") + for nid in self.tree.expand_tree(nid="jane"): + self.assertEqual( + self.tree[nid].is_leaf() == (self.tree[nid] in leaves), True + ) + + def test_tree_wise_leaves(self): + leaves = self.tree.leaves() + for nid in self.tree.expand_tree(): + self.assertEqual( + (self.tree[nid].is_leaf("tree 1")) == (self.tree[nid] in leaves), True + ) + leaves = self.tree.leaves(nid="jane") + for nid in self.tree.expand_tree(nid="jane"): + self.assertEqual( + self.tree[nid].is_leaf("tree 1") == (self.tree[nid] in leaves), True + ) + + def test_link_past_node(self): + self.tree.create_node("Jill", "jill", parent="hárry") + self.tree.create_node("Mark", "mark", parent="jill") + self.assertEqual("mark" not in self.tree.is_branch("hárry"), True) + self.tree.link_past_node("jill") + self.assertEqual("mark" in self.tree.is_branch("hárry"), True) + + def test_expand_tree(self): + # default config + # Hárry + # |-- Jane + # |-- Diane + # |-- Bill + # |-- George + # Traverse in depth first mode preserving insertion order + nodes = [nid for nid in self.tree.expand_tree(sorting=False)] + self.assertEqual(nodes, ["h\xe1rry", "jane", "diane", "bill", "george"]) + self.assertEqual(len(nodes), 5) + + # By default traverse depth first and sort child nodes by node tag + nodes = [nid for nid in self.tree.expand_tree()] + self.assertEqual(nodes, ["h\xe1rry", "bill", "george", "jane", "diane"]) + self.assertEqual(len(nodes), 5) + + # expanding from specific node + nodes = [nid for nid in self.tree.expand_tree(nid="bill")] + self.assertEqual(nodes, ["bill", "george"]) + self.assertEqual(len(nodes), 2) + + # changing into width mode preserving insertion order + nodes = [nid for nid in self.tree.expand_tree(mode=Tree.WIDTH, sorting=False)] + self.assertEqual(nodes, ["h\xe1rry", "jane", "bill", "diane", "george"]) + self.assertEqual(len(nodes), 5) + + # Breadth first mode, child nodes sorting by tag + nodes = [nid for nid in self.tree.expand_tree(mode=Tree.WIDTH)] + self.assertEqual(nodes, ["h\xe1rry", "bill", "jane", "george", "diane"]) + self.assertEqual(len(nodes), 5) + + # expanding by filters + # Stops at root + nodes = [nid for nid in self.tree.expand_tree(filter=lambda x: x.tag == "Bill")] + self.assertEqual(len(nodes), 0) + nodes = [nid for nid in self.tree.expand_tree(filter=lambda x: x.tag != "Bill")] + self.assertEqual(nodes, ["h\xe1rry", "jane", "diane"]) + self.assertEqual(len(nodes), 3) + + def test_move_node(self): + diane_parent = self.tree.parent("diane") + self.tree.move_node("diane", "bill") + self.assertEqual("diane" in self.tree.is_branch("bill"), True) + self.tree.move_node("diane", diane_parent.identifier) + + def test_paste_tree(self): + new_tree = Tree() + new_tree.create_node("Jill", "jill") + new_tree.create_node("Mark", "mark", parent="jill") + self.tree.paste("jane", new_tree) + self.assertEqual("jill" in self.tree.is_branch("jane"), True) + self.tree.show() + self.assertEqual( + self.tree._reader, + """Hárry +├── Bill +│ └── George +└── Jane + ├── Diane + └── Jill + └── Mark +""", + ) + self.tree.remove_node("jill") + self.assertNotIn("jill", self.tree.nodes.keys()) + self.assertNotIn("mark", self.tree.nodes.keys()) + self.tree.show() + self.assertEqual( + self.tree._reader, + """Hárry +├── Bill +│ └── George +└── Jane + └── Diane +""", + ) + + def test_merge(self): + # merge on empty initial tree + t1 = Tree(identifier="t1") + t2 = self.get_t2() + t1.merge(nid=None, new_tree=t2) + + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r2") + self.assertEqual(set(t1._nodes.keys()), {"r2", "c", "d", "d1"}) + self.assertEqual( + t1.show(stdout=False), + """root2 +├── C +└── D + └── D1 +""", + ) + + # merge empty new_tree (on root) + t1 = self.get_t1() + t2 = Tree(identifier="t2") + t1.merge(nid="r", new_tree=t2) + + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r") + self.assertEqual(set(t1._nodes.keys()), {"r", "a", "a1", "b"}) + self.assertEqual( + t1.show(stdout=False), + """root +├── A +│ └── A1 +└── B +""", + ) + + # merge at root + t1 = self.get_t1() + t2 = self.get_t2() + t1.merge(nid="r", new_tree=t2) + + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r") + self.assertNotIn("r2", t1._nodes.keys()) + self.assertEqual(set(t1._nodes.keys()), {"r", "a", "a1", "b", "c", "d", "d1"}) + self.assertEqual( + t1.show(stdout=False), + """root +├── A +│ └── A1 +├── B +├── C +└── D + └── D1 +""", + ) + + # merge on node + t1 = self.get_t1() + t2 = self.get_t2() + t1.merge(nid="b", new_tree=t2) + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r") + self.assertNotIn("r2", t1._nodes.keys()) + self.assertEqual(set(t1._nodes.keys()), {"r", "a", "a1", "b", "c", "d", "d1"}) + self.assertEqual( + t1.show(stdout=False), + """root +├── A +│ └── A1 +└── B + ├── C + └── D + └── D1 +""", + ) + + def test_paste(self): + # paste under root + t1 = self.get_t1() + t2 = self.get_t2() + t1.paste(nid="r", new_tree=t2) + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r") + self.assertEqual(t1.parent("r2").identifier, "r") + self.assertEqual( + set(t1._nodes.keys()), {"r", "r2", "a", "a1", "b", "c", "d", "d1"} + ) + self.assertEqual( + t1.show(stdout=False), + """root +├── A +│ └── A1 +├── B +└── root2 + ├── C + └── D + └── D1 +""", + ) + + # paste under non-existing node + t1 = self.get_t1() + t2 = self.get_t2() + with self.assertRaises(NodeIDAbsentError) as e: + t1.paste(nid="not_existing", new_tree=t2) + self.assertEqual(e.exception.args[0], "Node 'not_existing' is not in the tree") + + # paste under None nid + t1 = self.get_t1() + t2 = self.get_t2() + with self.assertRaises(ValueError) as e: + t1.paste(nid=None, new_tree=t2) + self.assertEqual( + e.exception.args[0], 'Must define "nid" under which new tree is pasted.' + ) + + # paste under node + t1 = self.get_t1() + t2 = self.get_t2() + t1.paste(nid="b", new_tree=t2) + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r") + self.assertEqual(t1.parent("b").identifier, "r") + self.assertEqual( + set(t1._nodes.keys()), {"r", "a", "a1", "b", "c", "d", "d1", "r2"} + ) + self.assertEqual( + t1.show(stdout=False), + """root +├── A +│ └── A1 +└── B + └── root2 + ├── C + └── D + └── D1 +""", + ) + # paste empty new_tree (under root) + t1 = self.get_t1() + t2 = Tree(identifier="t2") + t1.paste(nid="r", new_tree=t2) + + self.assertEqual(t1.identifier, "t1") + self.assertEqual(t1.root, "r") + self.assertEqual(set(t1._nodes.keys()), {"r", "a", "a1", "b"}) + self.assertEqual( + t1.show(stdout=False), + """root +├── A +│ └── A1 +└── B +""", + ) + + def test_rsearch(self): + for nid in ["hárry", "jane", "diane"]: + self.assertEqual(nid in self.tree.rsearch("diane"), True) + + def test_subtree(self): + subtree_copy = Tree(self.tree.subtree("jane"), deep=True) + self.assertEqual(subtree_copy.parent("jane") is None, True) + subtree_copy["jane"].tag = "Sweeti" + self.assertEqual(self.tree["jane"].tag == "Jane", True) + self.assertEqual(subtree_copy.level("diane"), 1) + self.assertEqual(subtree_copy.level("jane"), 0) + self.assertEqual(self.tree.level("jane"), 1) + + def test_remove_subtree(self): + subtree_shallow = self.tree.remove_subtree("jane") + self.assertEqual("jane" not in self.tree.is_branch("hárry"), True) + self.tree.paste("hárry", subtree_shallow) + + def test_remove_subtree_whole_tree(self): + self.tree.remove_subtree("hárry") + self.assertIsNone(self.tree.root) + self.assertEqual(len(self.tree.nodes.keys()), 0) + + def test_to_json(self): + self.assertEqual.__self__.maxDiff = None + self.tree.to_json() + self.tree.to_json(True) + + def test_siblings(self): + self.assertEqual(len(self.tree.siblings("hárry")) == 0, True) + self.assertEqual(self.tree.siblings("jane")[0].identifier == "bill", True) + + def test_tree_data(self): + class Flower(object): + def __init__(self, color): + self.color = color + + self.tree.create_node("Jill", "jill", parent="jane", data=Flower("white")) + self.assertEqual(self.tree["jill"].data.color, "white") + self.tree.remove_node("jill") + + def test_show_data_property(self): + new_tree = Tree() + + sys.stdout = open(os.devnull, "w") # stops from printing to console + + try: + new_tree.show() + + class Flower(object): + def __init__(self, color): + self.color = color + + new_tree.create_node("Jill", "jill", data=Flower("white")) + new_tree.show(data_property="color") + finally: + sys.stdout.close() + sys.stdout = sys.__stdout__ # stops from printing to console + + def test_level(self): + self.assertEqual(self.tree.level("hárry"), 0) + depth = self.tree.depth() + self.assertEqual(self.tree.level("diane"), depth) + self.assertEqual( + self.tree.level("diane", lambda x: x.identifier != "jane"), depth - 1 + ) + + def test_size(self): + self.assertEqual(self.tree.size(level=2), 2) + self.assertEqual(self.tree.size(level=1), 2) + self.assertEqual(self.tree.size(level=0), 1) + + def test_print_backend(self): + expected_result = """\ +Hárry +├── Bill +│ └── George +└── Jane + └── Diane +""" + + assert str(self.tree) == encode(expected_result) + + def test_show(self): + if sys.version_info[0] < 3: + reload(sys) # noqa: F821 + sys.setdefaultencoding("utf-8") + sys.stdout = open(os.devnull, "w") # stops from printing to console + + try: + self.tree.show() + finally: + sys.stdout.close() + sys.stdout = sys.__stdout__ # stops from printing to console + + def tearDown(self): + self.tree = None + self.copytree = None + + def test_show_without_sorting(self): + t = Tree() + t.create_node("Students", "Students", parent=None) + Node(tag="Students", identifier="Students", data=None) + t.create_node("Ben", "Ben", parent="Students") + Node(tag="Ben", identifier="Ben", data=None) + t.create_node("Annie", "Annie", parent="Students") + Node(tag="Annie", identifier="Annie", data=None) + t.show() + self.assertEqual( + t.show(sorting=False, stdout=False), + """Students +├── Ben +└── Annie +""", + ) + + def test_all_nodes_itr(self): + """ + tests: Tree.all_nodes_iter + Added by: William Rusnack + """ + new_tree = Tree() + self.assertEqual(len(new_tree.all_nodes_itr()), 0) + nodes = list() + nodes.append(new_tree.create_node("root_node")) + nodes.append(new_tree.create_node("second", parent=new_tree.root)) + for nd in new_tree.all_nodes_itr(): + self.assertTrue(nd in nodes) + + def test_filter_nodes(self): + """ + tests: Tree.filter_nodes + Added by: William Rusnack + """ + new_tree = Tree(identifier="tree 1") + + self.assertEqual(tuple(new_tree.filter_nodes(lambda n: True)), ()) + + nodes = list() + nodes.append(new_tree.create_node("root_node")) + nodes.append(new_tree.create_node("second", parent=new_tree.root)) + + self.assertEqual(tuple(new_tree.filter_nodes(lambda n: False)), ()) + self.assertEqual( + tuple(new_tree.filter_nodes(lambda n: n.is_root("tree 1"))), (nodes[0],) + ) + self.assertEqual( + tuple(new_tree.filter_nodes(lambda n: not n.is_root("tree 1"))), (nodes[1],) + ) + self.assertTrue(set(new_tree.filter_nodes(lambda n: True)), set(nodes)) + + def test_loop(self): + tree = Tree() + tree.create_node("a", "a") + tree.create_node("b", "b", parent="a") + tree.create_node("c", "c", parent="b") + tree.create_node("d", "d", parent="c") + try: + tree.move_node("b", "d") + except LoopError: + pass + + def test_modify_node_identifier_directly_failed(self): + tree = Tree() + tree.create_node("Harry", "harry") + tree.create_node("Jane", "jane", parent="harry") + n = tree.get_node("jane") + self.assertTrue(n.identifier == "jane") + + # Failed to modify + n.identifier = "xyz" + self.assertTrue(tree.get_node("xyz") is None) + self.assertTrue(tree.get_node("jane").identifier == "xyz") + + def test_modify_node_identifier_recursively(self): + tree = Tree() + tree.create_node("Harry", "harry") + tree.create_node("Jane", "jane", parent="harry") + n = tree.get_node("jane") + self.assertTrue(n.identifier == "jane") + + # Success to modify + tree.update_node(n.identifier, identifier="xyz") + self.assertTrue(tree.get_node("jane") is None) + self.assertTrue(tree.get_node("xyz").identifier == "xyz") + + def test_modify_node_identifier_root(self): + tree = Tree(identifier="tree 3") + tree.create_node("Harry", "harry") + tree.create_node("Jane", "jane", parent="harry") + tree.update_node(tree["harry"].identifier, identifier="xyz", tag="XYZ") + self.assertTrue(tree.root == "xyz") + self.assertTrue(tree["xyz"].tag == "XYZ") + self.assertEqual(tree.parent("jane").identifier, "xyz") + + def test_subclassing(self): + class SubNode(Node): + pass + + class SubTree(Tree): + node_class = SubNode + + tree = SubTree() + node = tree.create_node() + self.assertTrue(isinstance(node, SubNode)) + + tree = Tree(node_class=SubNode) + node = tree.create_node() + self.assertTrue(isinstance(node, SubNode)) + + def test_shallow_copy_hermetic_pointers(self): + # tree 1 + # Hárry + # └── Jane + # └── Diane + # └── Bill + # └── George + tree2 = self.tree.subtree(nid="jane", identifier="tree 2") + # tree 2 + # Jane + # └── Diane + + # check that in shallow copy, instances are the same + self.assertIs(self.tree["jane"], tree2["jane"]) + self.assertEqual( + self.tree["jane"]._predecessor, {"tree 1": "hárry", "tree 2": None} + ) + self.assertEqual( + dict(self.tree["jane"]._successors), + {"tree 1": ["diane"], "tree 2": ["diane"]}, + ) + + # when creating new node on subtree, check that it has no impact on initial tree + tree2.create_node("Jill", "jill", parent="diane") + self.assertIn("jill", tree2) + self.assertIn("jill", tree2.is_branch("diane")) + self.assertNotIn("jill", self.tree) + self.assertNotIn("jill", self.tree.is_branch("diane")) + + def test_paste_duplicate_nodes(self): + t1 = Tree() + t1.create_node(identifier="A") + t2 = Tree() + t2.create_node(identifier="A") + t2.create_node(identifier="B", parent="A") + + with self.assertRaises(ValueError) as e: + t1.paste("A", t2) + self.assertEqual(e.exception.args, ("Duplicated nodes ['A'] exists.",)) + + def test_shallow_paste(self): + t1 = Tree() + n1 = t1.create_node(identifier="A") + + t2 = Tree() + n2 = t2.create_node(identifier="B") + + t3 = Tree() + n3 = t3.create_node(identifier="C") + + t1.paste(n1.identifier, t2) + self.assertEqual(t1.to_dict(), {"A": {"children": ["B"]}}) + t1.paste(n1.identifier, t3) + self.assertEqual(t1.to_dict(), {"A": {"children": ["B", "C"]}}) + + self.assertEqual(t1.level(n1.identifier), 0) + self.assertEqual(t1.level(n2.identifier), 1) + self.assertEqual(t1.level(n3.identifier), 1) + + def test_root_removal(self): + t = Tree() + t.create_node(identifier="root-A") + self.assertEqual(len(t.nodes.keys()), 1) + self.assertEqual(t.root, "root-A") + t.remove_node(identifier="root-A") + self.assertEqual(len(t.nodes.keys()), 0) + self.assertEqual(t.root, None) + t.create_node(identifier="root-B") + self.assertEqual(len(t.nodes.keys()), 1) + self.assertEqual(t.root, "root-B") diff --git a/treelib/__init__.py b/treelib/__init__.py new file mode 100644 index 0000000..4902412 --- /dev/null +++ b/treelib/__init__.py @@ -0,0 +1,39 @@ +# Copyright (C) 2011 +# Brett Alistair Kromkamp - brettkromkamp@gmail.com +# Copyright (C) 2012-2017 +# Xiaming Chen - chenxm35@gmail.com +# and other contributors. +# All rights reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +""" +treelib - Python 2/3 Tree Implementation + +`treelib` is a Python module with two primary classes: Node and Tree. +Tree is a self-contained structure with some nodes and connected by branches. +A tree owns merely a root, while a node (except root) has some children and one parent. + +Note: To solve string compatibility between Python 2.x and 3.x, treelib follows +the way of porting Python 3.x to 2/3. That means, all strings are manipulated as +unicode and you do not need u'' prefix anymore. The impacted functions include `str()`, +`show()` and `save2file()` routines. +But if your data contains non-ascii characters and Python 2.x is used, +you have to trigger the compatibility by declaring `unicode_literals` in the code: + +.. code-block:: python + + >>> from __future__ import unicode_literals +""" + +from .tree import Tree # noqa: F401 +from .node import Node # noqa: F401 diff --git a/treelib/exceptions.py b/treelib/exceptions.py new file mode 100644 index 0000000..fc955c5 --- /dev/null +++ b/treelib/exceptions.py @@ -0,0 +1,50 @@ +class NodePropertyError(Exception): + """Basic Node attribute error""" + + pass + + +class NodeIDAbsentError(NodePropertyError): + """Exception throwed if a node's identifier is unknown""" + + pass + + +class NodePropertyAbsentError(NodePropertyError): + """Exception throwed if a node's data property is not specified""" + + pass + + +class MultipleRootError(Exception): + """Exception throwed if more than one root exists in a tree.""" + + pass + + +class DuplicatedNodeIdError(Exception): + """Exception throwed if an identifier already exists in a tree.""" + + pass + + +class LinkPastRootNodeError(Exception): + """ + Exception throwed in Tree.link_past_node() if one attempts + to "link past" the root node of a tree. + """ + + pass + + +class InvalidLevelNumber(Exception): + pass + + +class LoopError(Exception): + """ + Exception thrown if trying to move node B to node A's position + while A is B's ancestor. + """ + + pass diff --git a/treelib/misc.py b/treelib/misc.py new file mode 100644 index 0000000..37ab7f5 --- /dev/null +++ b/treelib/misc.py @@ -0,0 +1,47 @@ +#!/usr/bin/env python +# Copyright (C) 2011 +# Brett Alistair Kromkamp - brettkromkamp@gmail.com +# Copyright (C) 2012-2017 +# Xiaming Chen - chenxm35@gmail.com +# and other contributors. +# All rights reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +import functools +from warnings import warn, simplefilter + + +def deprecated(alias): + def real_deco(func): + """This is a decorator which can be used to mark functions + as deprecated. It will result in a warning being emmitted + when the function is used. + Derived from answer by Leando: https://stackoverflow.com/a/30253848 + """ + + @functools.wraps(func) + def wrapper(*args, **kwargs): + simplefilter("always", DeprecationWarning) # turn off filter + warn( + 'Call to deprecated function "{}"; use "{}" instead.'.format( + func.__name__, alias + ), + category=DeprecationWarning, + stacklevel=2, + ) + simplefilter("default", DeprecationWarning) # reset filter + return func(*args, **kwargs) + + return wrapper + + return real_deco diff --git a/treelib/node.py b/treelib/node.py new file mode 100644 index 0000000..958c734 --- /dev/null +++ b/treelib/node.py @@ -0,0 +1,279 @@ +#!/usr/bin/env python +# Copyright (C) 2011 +# Brett Alistair Kromkamp - brettkromkamp@gmail.com +# Copyright (C) 2012-2017 +# Xiaming Chen - chenxm35@gmail.com +# and other contributors. +# All rights reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +""" +Node structure in treelib. + +A :class:`Node` object contains basic properties such as node identifier, +node tag, parent node, children nodes etc., and some operations for a node. +""" +from __future__ import unicode_literals + +import copy +import uuid +from collections import defaultdict +from warnings import warn + +from .exceptions import NodePropertyError +from .misc import deprecated + + +class Node(object): + """ + Nodes are elementary objects that are stored in the `_nodes` dictionary of a Tree. + Use `data` attribute to store node-specific data. + """ + + #: Mode constants for routine `update_fpointer()`. + (ADD, DELETE, INSERT, REPLACE) = list(range(4)) + + def __init__(self, tag=None, identifier=None, expanded=True, data=None): + """Create a new Node object to be placed inside a Tree object""" + + #: if given as a parameter, must be unique + self._identifier = None + self._set_identifier(identifier) + + #: None or something else + #: if None, self._identifier will be set to the identifier's value. + if tag is None: + self._tag = self._identifier + else: + self._tag = tag + + #: boolean + self.expanded = expanded + + #: identifier of the parent's node : + self._predecessor = {} + #: identifier(s) of the soons' node(s) : + self._successors = defaultdict(list) + + #: User payload associated with this node. + self.data = data + + # for retro-compatibility on bpointer/fpointer + self._initial_tree_id = None + + def __lt__(self, other): + return self.tag < other.tag + + def set_initial_tree_id(self, tree_id): + if self._initial_tree_id is None: + self._initial_tree_id = tree_id + + def _set_identifier(self, nid): + """Initialize self._set_identifier""" + if nid is None: + self._identifier = str(uuid.uuid1()) + else: + self._identifier = nid + + @property + @deprecated(alias="node.predecessor") + def bpointer(self): + """Use predecessor method, this property is deprecated and only kept for retro-compatilibity. Parents of + a node are dependant on a given tree. This implementation keeps the previous behavior by keeping returning + bpointer of first declared tree. + """ + if self._initial_tree_id not in self._predecessor.keys(): + return None + return self._predecessor[self._initial_tree_id] + + @bpointer.setter + @deprecated(alias="node.set_predecessor") + def bpointer(self, value): + self.set_predecessor(value, self._initial_tree_id) + + @deprecated(alias="node.set_predecessor") + def update_bpointer(self, nid): + self.set_predecessor(nid, self._initial_tree_id) + + @property + @deprecated(alias="node.successors") + def fpointer(self): + """Use successors method, this property is deprecated and only kept for retro-compatilibity. Children of + a node are dependant on a given tree. This implementation keeps the previous behavior by keeping returning + fpointer of first declared tree. + """ + if self._initial_tree_id not in self._successors: + return [] + return self._successors[self._initial_tree_id] + + @fpointer.setter + @deprecated(alias="node.update_successors") + def fpointer(self, value): + self.set_successors(value, tree_id=self._initial_tree_id) + + @deprecated(alias="node.update_successors") + def update_fpointer(self, nid, mode=ADD, replace=None): + """Deprecated""" + self.update_successors(nid, mode, replace, self._initial_tree_id) + + def predecessor(self, tree_id): + """ + The parent ID of a node in a given tree. + """ + return self._predecessor[tree_id] + + def set_predecessor(self, nid, tree_id): + """Set the value of `_predecessor`.""" + self._predecessor[tree_id] = nid + + def successors(self, tree_id): + """ + With a getting operator, a list of IDs of node's children is obtained. With + a setting operator, the value can be list, set, or dict. For list or set, + it is converted to a list type by the package; for dict, the keys are + treated as the node IDs. + """ + return self._successors[tree_id] + + def set_successors(self, value, tree_id=None): + """Set the value of `_successors`.""" + setter_lookup = { + "NoneType": lambda x: list(), + "list": lambda x: x, + "dict": lambda x: list(x.keys()), + "set": lambda x: list(x), + } + + t = value.__class__.__name__ + if t in setter_lookup: + f_setter = setter_lookup[t] + self._successors[tree_id] = f_setter(value) + else: + raise NotImplementedError("Unsupported value type %s" % t) + + def update_successors(self, nid, mode=ADD, replace=None, tree_id=None): + """ + Update the children list with different modes: addition (Node.ADD or + Node.INSERT) and deletion (Node.DELETE). + """ + if nid is None: + return + + def _manipulator_append(): + self.successors(tree_id).append(nid) + + def _manipulator_delete(): + if nid in self.successors(tree_id): + self.successors(tree_id).remove(nid) + else: + warn("Nid %s wasn't present in fpointer" % nid) + + def _manipulator_insert(): + warn("WARNING: INSERT is deprecated to ADD mode") + self.update_successors(nid, tree_id=tree_id) + + def _manipulator_replace(): + if replace is None: + raise NodePropertyError( + 'Argument "repalce" should be provided when mode is {}'.format(mode) + ) + ind = self.successors(tree_id).index(nid) + self.successors(tree_id)[ind] = replace + + manipulator_lookup = { + self.ADD: "_manipulator_append", + self.DELETE: "_manipulator_delete", + self.INSERT: "_manipulator_insert", + self.REPLACE: "_manipulator_replace", + } + + if mode not in manipulator_lookup: + raise NotImplementedError("Unsupported node updating mode %s" % str(mode)) + + f_name = manipulator_lookup.get(mode) + f = locals()[f_name] + return f() + + @property + def identifier(self): + """ + The unique ID of a node within the scope of a tree. This attribute can be + accessed and modified with ``.`` and ``=`` operator respectively. + """ + return self._identifier + + def clone_pointers(self, former_tree_id, new_tree_id): + former_bpointer = self.predecessor(former_tree_id) + self.set_predecessor(former_bpointer, new_tree_id) + former_fpointer = self.successors(former_tree_id) + # fpointer is a list and would be copied by reference without deepcopy + self.set_successors(copy.deepcopy(former_fpointer), tree_id=new_tree_id) + + def reset_pointers(self, tree_id): + self.set_predecessor(None, tree_id) + self.set_successors([], tree_id=tree_id) + + @identifier.setter + def identifier(self, value): + """Set the value of `_identifier`.""" + if value is None: + print("WARNING: node ID can not be None") + else: + self._set_identifier(value) + + def is_leaf(self, tree_id=None): + """Return true if current node has no children.""" + if tree_id is None: + # for retro-compatilibity + if self._initial_tree_id not in self._successors.keys(): + return True + else: + tree_id = self._initial_tree_id + + if len(self.successors(tree_id)) == 0: + return True + else: + return False + + def is_root(self, tree_id=None): + """Return true if self has no parent, i.e. as root.""" + if tree_id is None: + # for retro-compatilibity + if self._initial_tree_id not in self._predecessor.keys(): + return True + else: + tree_id = self._initial_tree_id + + return self.predecessor(tree_id) is None + + @property + def tag(self): + """ + The readable node name for human. This attribute can be accessed and + modified with ``.`` and ``=`` operator respectively. + """ + return self._tag + + @tag.setter + def tag(self, value): + """Set the value of `_tag`.""" + self._tag = value if value is not None else None + + def __repr__(self): + name = self.__class__.__name__ + kwargs = [ + "tag={0}".format(self.tag), + "identifier={0}".format(self.identifier), + "data={0}".format(self.data), + ] + return "%s(%s)" % (name, ", ".join(kwargs)) diff --git a/treelib/plugins.py b/treelib/plugins.py new file mode 100644 index 0000000..0736c73 --- /dev/null +++ b/treelib/plugins.py @@ -0,0 +1,35 @@ +#!/usr/bin/env python +# -*- coding: utf-8 -*- +# Copyright (C) 2011 +# Brett Alistair Kromkamp - brettkromkamp@gmail.com +# Copyright (C) 2012-2017 +# Xiaming Chen - chenxm35@gmail.com +# and other contributors. +# All rights reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +""" +This is a public location to maintain contributed +utilities to extend the basic Tree class. + +Deprecated! We prefer a unified processing of Tree object. +""" +from __future__ import unicode_literals + +from .misc import deprecated + + +@deprecated(alias="tree.to_graphviz()") +def export_to_dot(tree, filename=None, shape="circle", graph="digraph"): + """Exports the tree in the dot format of the graphviz software""" + tree.to_graphviz(filename=filename, shape=shape, graph=graph) diff --git a/treelib/tree.py b/treelib/tree.py new file mode 100644 index 0000000..7d92297 --- /dev/null +++ b/treelib/tree.py @@ -0,0 +1,1130 @@ +#!/usr/bin/env python +# -*- coding: utf-8 -*- +# Copyright (C) 2011 +# Brett Alistair Kromkamp - brettkromkamp@gmail.com +# Copyright (C) 2012-2017 +# Xiaming Chen - chenxm35@gmail.com +# and other contributors. +# All rights reserved. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +""" +Tree structure in `treelib`. + +The :class:`Tree` object defines the tree-like structure based on :class:`Node` objects. +A new tree can be created from scratch without any parameter or a shallow/deep copy of another tree. +When deep=True, a deepcopy operation is performed on feeding tree parameter and more memory +is required to create the tree. +""" +from __future__ import print_function +from __future__ import unicode_literals + +try: + from builtins import str as text +except ImportError: + from __builtin__ import str as text + +import codecs +import json +import uuid +from copy import deepcopy +from six import python_2_unicode_compatible, iteritems + +try: + from StringIO import StringIO +except ImportError: + from io import StringIO + +from .exceptions import ( + NodeIDAbsentError, + DuplicatedNodeIdError, + MultipleRootError, + InvalidLevelNumber, + LinkPastRootNodeError, + LoopError, +) +from .node import Node + +__author__ = "chenxm" + + +@python_2_unicode_compatible +class Tree(object): + """Tree objects are made of Node(s) stored in _nodes dictionary.""" + + #: ROOT, DEPTH, WIDTH, ZIGZAG constants : + (ROOT, DEPTH, WIDTH, ZIGZAG) = list(range(4)) + node_class = Node + + def __contains__(self, identifier): + return identifier in self.nodes.keys() + + def __init__(self, tree=None, deep=False, node_class=None, identifier=None): + """Initiate a new tree or copy another tree with a shallow or + deep copy. + """ + self._identifier = None + self._set_identifier(identifier) + + if node_class: + assert issubclass(node_class, Node) + self.node_class = node_class + + #: dictionary, identifier: Node object + self._nodes = {} + + #: Get or set the identifier of the root. This attribute can be accessed and modified + #: with ``.`` and ``=`` operator respectively. + self.root = None + + if tree is not None: + self.root = tree.root + for nid, node in iteritems(tree.nodes): + new_node = deepcopy(node) if deep else node + self._nodes[nid] = new_node + if tree.identifier != self._identifier: + new_node.clone_pointers(tree.identifier, self._identifier) + + def _clone(self, identifier=None, with_tree=False, deep=False): + """Clone current instance, with or without tree. + + Method intended to be overloaded, to avoid rewriting whole "subtree" and "remove_subtree" methods when + inheriting from Tree. + >>> class TreeWithComposition(Tree): + >>> def __init__(self, tree_description, tree=None, deep=False, identifier=None): + >>> self.tree_description = tree_description + >>> super(TreeWithComposition, self).__init__(tree=tree, deep=deep, identifier=identifier) + >>> + >>> def _clone(self, identifier=None, with_tree=False, deep=False): + >>> return TreeWithComposition( + >>> identifier=identifier, + >>> deep=deep, + >>> tree=self if with_tree else None, + >>> tree_description=self.tree_description + >>> ) + >>> my_custom_tree = TreeWithComposition(tree_description="smart tree") + >>> subtree = my_custom_tree.subtree() + >>> subtree.tree_description + "smart tree" + """ + return self.__class__( + identifier=identifier, tree=self if with_tree else None, deep=deep + ) + + @property + def identifier(self): + return self._identifier + + def _set_identifier(self, nid): + """Initialize self._set_identifier""" + if nid is None: + self._identifier = str(uuid.uuid1()) + else: + self._identifier = nid + + def __getitem__(self, key): + """Return _nodes[key]""" + try: + return self._nodes[key] + except KeyError: + raise NodeIDAbsentError("Node '%s' is not in the tree" % key) + + def __len__(self): + """Return len(_nodes)""" + return len(self._nodes) + + def __str__(self): + self._reader = "" + + def write(line): + self._reader += line.decode("utf-8") + "\n" + + self.__print_backend(func=write) + return self._reader + + def __print_backend( + self, + nid=None, + level=ROOT, + idhidden=True, + filter=None, + key=None, + reverse=False, + line_type="ascii-ex", + data_property=None, + sorting=True, + func=print, + ): + """ + Another implementation of printing tree using Stack + Print tree structure in hierarchy style. + + For example: + + .. code-block:: bash + + Root + |___ C01 + | |___ C11 + | |___ C111 + | |___ C112 + |___ C02 + |___ C03 + | |___ C31 + + A more elegant way to achieve this function using Stack + structure, for constructing the Nodes Stack push and pop nodes + with additional level info. + + UPDATE: the @key @reverse is present to sort node at each + level. + """ + # Factory for proper get_label() function + if data_property: + if idhidden: + + def get_label(node): + return getattr(node.data, data_property) + + else: + + def get_label(node): + return "%s[%s]" % ( + getattr(node.data, data_property), + node.identifier, + ) + + else: + if idhidden: + + def get_label(node): + return node.tag + + else: + + def get_label(node): + return "%s[%s]" % (node.tag, node.identifier) + + # legacy ordering + if sorting and key is None: + + def key(node): + return node + + # iter with func + for pre, node in self.__get( + nid, level, filter, key, reverse, line_type, sorting + ): + label = get_label(node) + func("{0}{1}".format(pre, label).encode("utf-8")) + + def __get(self, nid, level, filter_, key, reverse, line_type, sorting): + # default filter + if filter_ is None: + + def filter_(node): + return True + + # render characters + dt = { + "ascii": ("|", "|-- ", "+-- "), + "ascii-ex": ("\u2502", "\u251c\u2500\u2500 ", "\u2514\u2500\u2500 "), + "ascii-exr": ("\u2502", "\u251c\u2500\u2500 ", "\u2570\u2500\u2500 "), + "ascii-em": ("\u2551", "\u2560\u2550\u2550 ", "\u255a\u2550\u2550 "), + "ascii-emv": ("\u2551", "\u255f\u2500\u2500 ", "\u2559\u2500\u2500 "), + "ascii-emh": ("\u2502", "\u255e\u2550\u2550 ", "\u2558\u2550\u2550 "), + }[line_type] + + return self.__get_iter(nid, level, filter_, key, reverse, dt, [], sorting) + + def __get_iter(self, nid, level, filter_, key, reverse, dt, is_last, sorting): + dt_vertical_line, dt_line_box, dt_line_corner = dt + + nid = self.root if nid is None else nid + node = self[nid] + + if level == self.ROOT: + yield "", node + else: + leading = "".join( + map( + lambda x: dt_vertical_line + " " * 3 if not x else " " * 4, + is_last[0:-1], + ) + ) + lasting = dt_line_corner if is_last[-1] else dt_line_box + yield leading + lasting, node + + if filter_(node) and node.expanded: + children = [ + self[i] for i in node.successors(self._identifier) if filter_(self[i]) + ] + idxlast = len(children) - 1 + if sorting: + if key: + children.sort(key=key, reverse=reverse) + elif reverse: + children = reversed(children) + level += 1 + for idx, child in enumerate(children): + is_last.append(idx == idxlast) + for item in self.__get_iter( + child.identifier, level, filter_, key, reverse, dt, is_last, sorting + ): + yield item + is_last.pop() + + def __update_bpointer(self, nid, parent_id): + """set self[nid].bpointer""" + self[nid].set_predecessor(parent_id, self._identifier) + + def __update_fpointer(self, nid, child_id, mode): + if nid is None: + return + else: + self[nid].update_successors(child_id, mode, tree_id=self._identifier) + + def add_node(self, node, parent=None): + """ + Add a new node object to the tree and make the parent as the root by default. + + The 'node' parameter refers to an instance of Class::Node. + """ + if not isinstance(node, self.node_class): + raise OSError( + "First parameter must be object of {}".format(self.node_class) + ) + + if node.identifier in self._nodes: + raise DuplicatedNodeIdError( + "Can't create node " "with ID '%s'" % node.identifier + ) + + pid = parent.identifier if isinstance(parent, self.node_class) else parent + + if pid is None: + if self.root is not None: + raise MultipleRootError("A tree takes one root merely.") + else: + self.root = node.identifier + elif not self.contains(pid): + raise NodeIDAbsentError("Parent node '%s' " "is not in the tree" % pid) + + self._nodes.update({node.identifier: node}) + self.__update_fpointer(pid, node.identifier, self.node_class.ADD) + self.__update_bpointer(node.identifier, pid) + node.set_initial_tree_id(self._identifier) + + def all_nodes(self): + """Return all nodes in a list""" + return list(self._nodes.values()) + + def all_nodes_itr(self): + """ + Returns all nodes in an iterator. + Added by William Rusnack + """ + return self._nodes.values() + + def ancestor(self, nid, level=None): + """ + For a given id, get ancestor node object at a given level. + If no level is provided, the parent node is returned. + """ + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + descendant = self[nid] + ascendant = self[nid]._predecessor[self._identifier] + ascendant_level = self.level(ascendant) + + if level is None: + return ascendant + elif nid == self.root: + return self[nid] + elif level >= self.level(descendant.identifier): + raise InvalidLevelNumber( + "Descendant level (level %s) must be greater \ + than its ancestor's level (level %s)" + % (str(self.level(descendant.identifier)), level) + ) + + while ascendant is not None: + if ascendant_level == level: + return self[ascendant] + else: + descendant = ascendant + ascendant = self[descendant]._predecessor[self._identifier] + ascendant_level = self.level(ascendant) + return None + + def children(self, nid): + """ + Return the children (Node) list of nid. + Empty list is returned if nid does not exist + """ + return [self[i] for i in self.is_branch(nid)] + + def contains(self, nid): + """Check if the tree contains node of given id""" + return True if nid in self._nodes else False + + def create_node(self, tag=None, identifier=None, parent=None, data=None): + """ + Create a child node for given @parent node. If ``identifier`` is absent, + a UUID will be generated automatically. + """ + node = self.node_class(tag=tag, identifier=identifier, data=data) + self.add_node(node, parent) + return node + + def depth(self, node=None): + """ + Get the maximum level of this tree or the level of the given node. + + @param node Node instance or identifier + @return int + @throw NodeIDAbsentError + """ + ret = 0 + if node is None: + # Get maximum level of this tree + leaves = self.leaves() + for leave in leaves: + level = self.level(leave.identifier) + ret = level if level >= ret else ret + else: + # Get level of the given node + if not isinstance(node, self.node_class): + nid = node + else: + nid = node.identifier + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + ret = self.level(nid) + return ret + + def expand_tree( + self, nid=None, mode=DEPTH, filter=None, key=None, reverse=False, sorting=True + ): + """ + Python generator to traverse the tree (or a subtree) with optional + node filtering and sorting. + + Loosely based on an algorithm from 'Essential LISP' by John R. Anderson, + Albert T. Corbett, and Brian J. Reiser, page 239-241. + + :param nid: Node identifier from which tree traversal will start. + If None tree root will be used + :param mode: Traversal mode, may be either DEPTH, WIDTH or ZIGZAG + :param filter: the @filter function is performed on Node object during + traversing. In this manner, the traversing will NOT visit the node + whose condition does not pass the filter and its children. + :param key: the @key and @reverse are present to sort nodes at each + level. If @key is None sorting is performed on node tag. + :param reverse: if True reverse sorting + :param sorting: if True perform node sorting, if False return + nodes in original insertion order. In latter case @key and + @reverse parameters are ignored. + :return: Node IDs that satisfy the conditions + :rtype: generator object + """ + nid = self.root if nid is None else nid + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + filter = (lambda x: True) if (filter is None) else filter + if filter(self[nid]): + yield nid + queue = [ + self[i] + for i in self[nid].successors(self._identifier) + if filter(self[i]) + ] + if mode in [self.DEPTH, self.WIDTH]: + if sorting: + queue.sort(key=key, reverse=reverse) + while queue: + yield queue[0].identifier + expansion = [ + self[i] + for i in queue[0].successors(self._identifier) + if filter(self[i]) + ] + if sorting: + expansion.sort(key=key, reverse=reverse) + if mode is self.DEPTH: + queue = expansion + queue[1:] # depth-first + elif mode is self.WIDTH: + queue = queue[1:] + expansion # width-first + + elif mode is self.ZIGZAG: + # Suggested by Ilya Kuprik (ilya-spy@ynadex.ru). + stack_fw = [] + queue.reverse() + stack = stack_bw = queue + direction = False + while stack: + expansion = [ + self[i] + for i in stack[0].successors(self._identifier) + if filter(self[i]) + ] + yield stack.pop(0).identifier + if direction: + expansion.reverse() + stack_bw = expansion + stack_bw + else: + stack_fw = expansion + stack_fw + if not stack: + direction = not direction + stack = stack_fw if direction else stack_bw + + else: + raise ValueError("Traversal mode '{}' is not supported".format(mode)) + + def filter_nodes(self, func): + """ + Filters all nodes by function. + + :param func: is passed one node as an argument and that node is included if function returns true, + :return: a filter iterator of the node in python 3 or a list of the nodes in python 2. + + Added by William Rusnack. + """ + return filter(func, self.all_nodes_itr()) + + def get_node(self, nid): + """ + Get the object of the node with ID of ``nid``. + + An alternative way is using '[]' operation on the tree. But small difference exists between them: + ``get_node()`` will return None if ``nid`` is absent, whereas '[]' will raise ``KeyError``. + """ + if nid is None or not self.contains(nid): + return None + return self._nodes[nid] + + def is_branch(self, nid): + """ + Return the children (ID) list of nid. + Empty list is returned if nid does not exist + """ + if nid is None: + raise OSError("First parameter can't be None") + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + try: + fpointer = self[nid].successors(self._identifier) + except KeyError: + fpointer = [] + return fpointer + + def leaves(self, nid=None): + """Get leaves of the whole tree or a subtree.""" + leaves = [] + if nid is None: + for node in self._nodes.values(): + if node.is_leaf(self._identifier): + leaves.append(node) + else: + for node in self.expand_tree(nid): + if self[node].is_leaf(self._identifier): + leaves.append(self[node]) + return leaves + + def level(self, nid, filter=None): + """ + Get the node level in this tree. + The level is an integer starting with '0' at the root. + In other words, the root lives at level '0'; + + Update: @filter params is added to calculate level passing + exclusive nodes. + """ + return len([n for n in self.rsearch(nid, filter)]) - 1 + + def link_past_node(self, nid): + """ + Delete a node by linking past it. + + For example, if we have `a -> b -> c` and delete node b, we are left + with `a -> c`. + """ + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + if self.root == nid: + raise LinkPastRootNodeError( + "Cannot link past the root node, " "delete it with remove_node()" + ) + # Get the parent of the node we are linking past + parent = self[self[nid].predecessor(self._identifier)] + # Set the children of the node to the parent + for child in self[nid].successors(self._identifier): + self[child].set_predecessor(parent.identifier, self._identifier) + # Link the children to the parent + for id_ in self[nid].successors(self._identifier) or []: + parent.update_successors(id_, tree_id=self._identifier) + # Delete the node + parent.update_successors(nid, mode=parent.DELETE, tree_id=self._identifier) + del self._nodes[nid] + + def move_node(self, source, destination): + """ + Move node @source from its parent to another parent @destination. + """ + if not self.contains(source) or not self.contains(destination): + raise NodeIDAbsentError + elif self.is_ancestor(source, destination): + raise LoopError + + parent = self[source].predecessor(self._identifier) + self.__update_fpointer(parent, source, self.node_class.DELETE) + self.__update_fpointer(destination, source, self.node_class.ADD) + self.__update_bpointer(source, destination) + + def is_ancestor(self, ancestor, grandchild): + """ + Check if the @ancestor the preceding nodes of @grandchild. + + :param ancestor: the node identifier + :param grandchild: the node identifier + :return: True or False + """ + parent = self[grandchild].predecessor(self._identifier) + child = grandchild + while parent is not None: + if parent == ancestor: + return True + else: + child = self[child].predecessor(self._identifier) + parent = self[child].predecessor(self._identifier) + return False + + @property + def nodes(self): + """Return a dict form of nodes in a tree: {id: node_instance}.""" + return self._nodes + + def parent(self, nid): + """Get parent :class:`Node` object of given id.""" + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + pid = self[nid].predecessor(self._identifier) + if pid is None or not self.contains(pid): + return None + + return self[pid] + + def merge(self, nid, new_tree, deep=False): + """Patch @new_tree on current tree by pasting new_tree root children on current tree @nid node. + + Consider the following tree: + >>> current.show() + root + ├── A + └── B + >>> new_tree.show() + root2 + ├── C + └── D + └── D1 + Merging new_tree on B node: + >>>current.merge('B', new_tree) + >>>current.show() + root + ├── A + └── B + ├── C + └── D + └── D1 + + Note: if current tree is empty and nid is None, the new_tree root will be used as root on current tree. In all + other cases new_tree root is not pasted. + """ + if new_tree.root is None: + return + + if nid is None: + if self.root is None: + new_tree_root = new_tree[new_tree.root] + self.add_node(new_tree_root) + nid = new_tree.root + else: + raise ValueError('Must define "nid" under which new tree is merged.') + for child in new_tree.children(new_tree.root): + self.paste(nid=nid, new_tree=new_tree.subtree(child.identifier), deep=deep) + + def paste(self, nid, new_tree, deep=False): + """ + Paste a @new_tree to the original one by linking the root + of new tree to given node (nid). + + Update: add @deep copy of pasted tree. + """ + assert isinstance(new_tree, Tree) + + if new_tree.root is None: + return + + if nid is None: + raise ValueError('Must define "nid" under which new tree is pasted.') + + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + set_joint = set(new_tree._nodes) & set(self._nodes) # joint keys + if set_joint: + raise ValueError("Duplicated nodes %s exists." % list(map(text, set_joint))) + + for cid, node in iteritems(new_tree.nodes): + if deep: + node = deepcopy(new_tree[node]) + self._nodes.update({cid: node}) + node.clone_pointers(new_tree.identifier, self._identifier) + + self.__update_bpointer(new_tree.root, nid) + self.__update_fpointer(nid, new_tree.root, self.node_class.ADD) + + def paths_to_leaves(self): + """ + Use this function to get the identifiers allowing to go from the root + nodes to each leaf. + + :return: a list of list of identifiers, root being not omitted. + + For example: + + .. code-block:: python + + Harry + |___ Bill + |___ Jane + | |___ Diane + | |___ George + | |___ Jill + | |___ Mary + | |___ Mark + + Expected result: + + .. code-block:: python + + [['harry', 'jane', 'diane', 'mary'], + ['harry', 'jane', 'mark'], + ['harry', 'jane', 'diane', 'george', 'jill'], + ['harry', 'bill']] + + """ + res = [] + + for leaf in self.leaves(): + res.append([nid for nid in self.rsearch(leaf.identifier)][::-1]) + + return res + + def remove_node(self, identifier): + """Remove a node indicated by 'identifier' with all its successors. + Return the number of removed nodes. + """ + if not self.contains(identifier): + raise NodeIDAbsentError("Node '%s' " "is not in the tree" % identifier) + + parent = self[identifier].predecessor(self._identifier) + + # Remove node and its children + removed = list(self.expand_tree(identifier)) + + for id_ in removed: + if id_ == self.root: + self.root = None + self.__update_bpointer(id_, None) + for cid in self[id_].successors(self._identifier) or []: + self.__update_fpointer(id_, cid, self.node_class.DELETE) + + # Update parent info + self.__update_fpointer(parent, identifier, self.node_class.DELETE) + self.__update_bpointer(identifier, None) + + for id_ in removed: + self.nodes.pop(id_) + return len(removed) + + def remove_subtree(self, nid, identifier=None): + """ + Get a subtree with ``nid`` being the root. If nid is None, an + empty tree is returned. + + For the original tree, this method is similar to + `remove_node(self,nid)`, because given node and its children + are removed from the original tree in both methods. + For the returned value and performance, these two methods are + different: + + * `remove_node` returns the number of deleted nodes; + * `remove_subtree` returns a subtree of deleted nodes; + + You are always suggested to use `remove_node` if your only to + delete nodes from a tree, as the other one need memory + allocation to store the new tree. + + :return: a :class:`Tree` object. + """ + st = self._clone(identifier) + if nid is None: + return st + + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + st.root = nid + + # in original tree, the removed nid will be unreferenced from its parents children + parent = self[nid].predecessor(self._identifier) + + removed = list(self.expand_tree(nid)) + for id_ in removed: + if id_ == self.root: + self.root = None + st._nodes.update({id_: self._nodes.pop(id_)}) + st[id_].clone_pointers(self._identifier, st.identifier) + st[id_].reset_pointers(self._identifier) + if id_ == nid: + st[id_].set_predecessor(None, st.identifier) + self.__update_fpointer(parent, nid, self.node_class.DELETE) + return st + + def rsearch(self, nid, filter=None): + """ + Traverse the tree branch along the branch from nid to its + ancestors (until root). + + :param filter: the function of one variable to act on the :class:`Node` object. + """ + if nid is None: + return + + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + filter = (lambda x: True) if (filter is None) else filter + + current = nid + while current is not None: + if filter(self[current]): + yield current + # subtree() hasn't update the bpointer + current = ( + self[current].predecessor(self._identifier) + if self.root != current + else None + ) + + def save2file( + self, + filename, + nid=None, + level=ROOT, + idhidden=True, + filter=None, + key=None, + reverse=False, + line_type="ascii-ex", + data_property=None, + sorting=True, + ): + """ + Save the tree into file for offline analysis. + """ + + def _write_line(line, f): + f.write(line + b"\n") + + def handler(x): + return _write_line(x, open(filename, "ab")) + + self.__print_backend( + nid, + level, + idhidden, + filter, + key, + reverse, + line_type, + data_property, + sorting, + func=handler, + ) + + def show( + self, + nid=None, + level=ROOT, + idhidden=True, + filter=None, + key=None, + reverse=False, + line_type="ascii-ex", + data_property=None, + stdout=True, + sorting=True, + ): + """ + Print the tree structure in hierarchy style. + + You have three ways to output your tree data, i.e., stdout with ``show()``, + plain text file with ``save2file()``, and json string with ``to_json()``. The + former two use the same backend to generate a string of tree structure in a + text graph. + + * Version >= 1.2.7a*: you can also specify the ``line_type`` parameter, + such as 'ascii' (default), 'ascii-ex', 'ascii-exr', 'ascii-em', 'ascii-emv', + 'ascii-emh') to the change graphical form. + + :param nid: the reference node to start expanding. + :param level: the node level in the tree (root as level 0). + :param idhidden: whether hiding the node ID when printing. + :param filter: the function of one variable to act on the :class:`Node` object. + When this parameter is specified, the traversing will not continue to following + children of node whose condition does not pass the filter. + :param key: the ``key`` param for sorting :class:`Node` objects in the same level. + :param reverse: the ``reverse`` param for sorting :class:`Node` objects in the same level. + :param line_type: + :param data_property: the property on the node data object to be printed. + :param sorting: if True perform node sorting, if False return + nodes in original insertion order. In latter case @key and + @reverse parameters are ignored. + :return: None + """ + self._reader = "" + + def write(line): + self._reader += line.decode("utf-8") + "\n" + + try: + self.__print_backend( + nid, + level, + idhidden, + filter, + key, + reverse, + line_type, + data_property, + sorting, + func=write, + ) + except NodeIDAbsentError: + print("Tree is empty") + + if stdout: + print(self._reader) + else: + return self._reader + + def siblings(self, nid): + """ + Return the siblings of given @nid. + + If @nid is root or there are no siblings, an empty list is returned. + """ + siblings = [] + + if nid != self.root: + pid = self[nid].predecessor(self._identifier) + siblings = [ + self[i] for i in self[pid].successors(self._identifier) if i != nid + ] + + return siblings + + def size(self, level=None): + """ + Get the number of nodes of the whole tree if @level is not + given. Otherwise, the total number of nodes at specific level + is returned. + + @param level The level number in the tree. It must be between + [0, tree.depth]. + + Otherwise, InvalidLevelNumber exception will be raised. + """ + if level is None: + return len(self._nodes) + else: + try: + level = int(level) + return len( + [ + node + for node in self.all_nodes_itr() + if self.level(node.identifier) == level + ] + ) + except Exception: + raise TypeError( + "level should be an integer instead of '%s'" % type(level) + ) + + def subtree(self, nid, identifier=None): + """ + Return a shallow COPY of subtree with nid being the new root. + If nid is None, return an empty tree. + If you are looking for a deepcopy, please create a new tree + with this shallow copy, e.g., + + .. code-block:: python + + new_tree = Tree(t.subtree(t.root), deep=True) + + This line creates a deep copy of the entire tree. + """ + st = self._clone(identifier) + if nid is None: + return st + + if not self.contains(nid): + raise NodeIDAbsentError("Node '%s' is not in the tree" % nid) + + st.root = nid + for node_n in self.expand_tree(nid): + st._nodes.update({self[node_n].identifier: self[node_n]}) + # define nodes parent/children in this tree + # all pointers are the same as copied tree, except the root + st[node_n].clone_pointers(self._identifier, st.identifier) + if node_n == nid: + # reset root parent for the new tree + st[node_n].set_predecessor(None, st.identifier) + return st + + def update_node(self, nid, **attrs): + """ + Update node's attributes. + + :param nid: the identifier of modified node + :param attrs: attribute pairs recognized by Node object + :return: None + """ + cn = self[nid] + for attr, val in iteritems(attrs): + if attr == "identifier": + # Updating node id meets following contraints: + # * Update node identifier property + # * Update parent's followers + # * Update children's parents + # * Update tree registration of var _nodes + # * Update tree root if necessary + cn = self._nodes.pop(nid) + setattr(cn, "identifier", val) + self._nodes[val] = cn + + if cn.predecessor(self._identifier) is not None: + self[cn.predecessor(self._identifier)].update_successors( + nid, + mode=self.node_class.REPLACE, + replace=val, + tree_id=self._identifier, + ) + + for fp in cn.successors(self._identifier): + self[fp].set_predecessor(val, self._identifier) + + if self.root == nid: + self.root = val + else: + setattr(cn, attr, val) + + def to_dict(self, nid=None, key=None, sort=True, reverse=False, with_data=False): + """Transform the whole tree into a dict.""" + + nid = self.root if (nid is None) else nid + ntag = self[nid].tag + tree_dict = {ntag: {"children": []}} + if with_data: + tree_dict[ntag]["data"] = self[nid].data + + if self[nid].expanded: + queue = [self[i] for i in self[nid].successors(self._identifier)] + key = (lambda x: x) if (key is None) else key + if sort: + queue.sort(key=key, reverse=reverse) + + for elem in queue: + tree_dict[ntag]["children"].append( + self.to_dict( + elem.identifier, with_data=with_data, sort=sort, reverse=reverse + ) + ) + if len(tree_dict[ntag]["children"]) == 0: + tree_dict = ( + self[nid].tag if not with_data else {ntag: {"data": self[nid].data}} + ) + return tree_dict + + def to_json(self, with_data=False, sort=True, reverse=False): + """To format the tree in JSON format.""" + return json.dumps(self.to_dict(with_data=with_data, sort=sort, reverse=reverse)) + + def to_graphviz( + self, + filename=None, + shape="circle", + graph="digraph", + filter=None, + key=None, + reverse=False, + sorting=True, + ): + """Exports the tree in the dot format of the graphviz software""" + nodes, connections = [], [] + if self.nodes: + for n in self.expand_tree( + mode=self.WIDTH, + filter=filter, + key=key, + reverse=reverse, + sorting=sorting, + ): + nid = self[n].identifier + state = '"{0}" [label="{1}", shape={2}]'.format(nid, self[n].tag, shape) + nodes.append(state) + + for c in self.children(nid): + cid = c.identifier + edge = "->" if graph == "digraph" else "--" + connections.append(('"{0}" ' + edge + ' "{1}"').format(nid, cid)) + + # write nodes and connections to dot format + is_plain_file = filename is not None + if is_plain_file: + f = codecs.open(filename, "w", "utf-8") + else: + f = StringIO() + + f.write(graph + " tree {\n") + for n in nodes: + f.write("\t" + n + "\n") + + if len(connections) > 0: + f.write("\n") + + for c in connections: + f.write("\t" + c + "\n") + + f.write("}") + + if not is_plain_file: + print(f.getvalue()) + + f.close() |