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