From 60b8ecaf2afb874b733c1c61be26da68df51d989 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 11 May 2023 10:46:20 +0200 Subject: Adding upstream version 1.6.4. Signed-off-by: Daniel Baumann --- .github/CODEOWNERS | 2 + .github/workflows/pypi-publish.yml | 39 ++ .github/workflows/python-package.yml | 59 ++ .gitignore | 41 ++ .travis.yml | 15 + AUTHORS | 10 + HISTORY | 53 ++ INSTALL | 16 + LICENSE | 21 + MANIFEST.in | 8 + README.md | 38 ++ docs/Makefile | 19 + docs/make.bat | 35 + docs/publish.sh | 12 + docs/requirements.txt | 2 + docs/source/conf.py | 187 +++++ docs/source/index.rst | 241 +++++++ docs/source/modules.rst | 7 + docs/source/treelib.rst | 45 ++ examples/family_tree.py | 65 ++ examples/folder_tree.py | 207 ++++++ examples/recursive_dirtree_generator.py | 89 +++ examples/save_tree_2_file.py | 12 + recipe/conda_build.sh | 33 + recipe/meta.yaml | 25 + requirements-t-pre37.txt | 3 + requirements-t.txt | 5 + requirements.txt | 1 + scripts/flake8.sh | 3 + scripts/testing.sh | 6 + setup.cfg | 2 + setup.py | 39 ++ tests/__init__.py | 0 tests/test_node.py | 88 +++ tests/test_plugins.py | 113 ++++ tests/test_tree.py | 736 ++++++++++++++++++++ treelib/__init__.py | 39 ++ treelib/exceptions.py | 50 ++ treelib/misc.py | 47 ++ treelib/node.py | 279 ++++++++ treelib/plugins.py | 35 + treelib/tree.py | 1130 +++++++++++++++++++++++++++++++ 42 files changed, 3857 insertions(+) create mode 100644 .github/CODEOWNERS create mode 100644 .github/workflows/pypi-publish.yml create mode 100644 .github/workflows/python-package.yml create mode 100644 .gitignore create mode 100644 .travis.yml create mode 100644 AUTHORS create mode 100644 HISTORY create mode 100644 INSTALL create mode 100644 LICENSE create mode 100644 MANIFEST.in create mode 100644 README.md create mode 100644 docs/Makefile create mode 100644 docs/make.bat create mode 100755 docs/publish.sh create mode 100644 docs/requirements.txt create mode 100644 docs/source/conf.py create mode 100644 docs/source/index.rst create mode 100644 docs/source/modules.rst create mode 100644 docs/source/treelib.rst create mode 100644 examples/family_tree.py create mode 100644 examples/folder_tree.py create mode 100644 examples/recursive_dirtree_generator.py create mode 100644 examples/save_tree_2_file.py create mode 100644 recipe/conda_build.sh create mode 100644 recipe/meta.yaml create mode 100644 requirements-t-pre37.txt create mode 100644 requirements-t.txt create mode 100644 requirements.txt create mode 100755 scripts/flake8.sh create mode 100755 scripts/testing.sh create mode 100644 setup.cfg create mode 100644 setup.py create mode 100644 tests/__init__.py create mode 100644 tests/test_node.py create mode 100644 tests/test_plugins.py create mode 100644 tests/test_tree.py create mode 100644 treelib/__init__.py create mode 100644 treelib/exceptions.py create mode 100644 treelib/misc.py create mode 100644 treelib/node.py create mode 100644 treelib/plugins.py create mode 100644 treelib/tree.py 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 diff --git a/AUTHORS b/AUTHORS new file mode 100644 index 0000000..ad58a53 --- /dev/null +++ b/AUTHORS @@ -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. diff --git a/HISTORY b/HISTORY new file mode 100644 index 0000000..2e1491d --- /dev/null +++ b/HISTORY @@ -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. diff --git a/INSTALL b/INSTALL new file mode 100644 index 0000000..9e4c23c --- /dev/null +++ b/INSTALL @@ -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) diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..2eb58b2 --- /dev/null +++ b/LICENSE @@ -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. + +[![Build Status](https://github.com/caesar0301/treelib/actions/workflows/python-package.yml/badge.svg)](https://github.com/caesar0301/treelib/actions) +[![Code style: black](https://img.shields.io/badge/code%20style-black-000000.svg)](https://github.com/psf/black) +[![Documentation Status](https://readthedocs.org/projects/treelib/badge/?version=latest)](http://treelib.readthedocs.io/en/latest/?badge=latest) +[![Status](https://img.shields.io/pypi/status/treelib.svg)](https://pypi.python.org/pypi/treelib) +[![Latest](https://img.shields.io/pypi/v/treelib.svg)](https://pypi.python.org/pypi/treelib) +[![PyV](https://img.shields.io/pypi/pyversions/treelib.svg)](https://pypi.python.org/pypi/treelib) +[![PyPI download month](https://img.shields.io/pypi/dm/treelib.svg)](https://pypi.python.org/pypi/treelib/) +[![GitHub contributors](https://img.shields.io/github/contributors/caesar0301/treelib.svg)](https://GitHub.com/caesar0301/treelib/graphs/contributors/) + +[![PRs Welcome](https://img.shields.io/badge/PRs-welcome-brightgreen.svg?style=flat-square)](http://makeapullrequest.com) +[![GitHub pull-requests](https://img.shields.io/github/issues-pr/caesar0301/treelib.svg)](https://GitHub.com/caesar0301/treelib/pulls) +[![GitHub pull-requests closed](https://img.shields.io/github/issues-pr-closed/caesar0301/treelib.svg)](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). + +[![ForTheBadge built-with-love](http://ForTheBadge.com/images/badges/built-with-love.svg)](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 `_ 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 `_ 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 +`_. If you encounter some problems, try +the freshest version on Github or open `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 '_' + + _+++ + e.g. 2_Folder_XYZ_1+++ + """ + 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 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() -- cgit v1.2.3