Metadata-Version: 2.4
Name: simpletree3
Version: 3.0.0
Summary: A simple tree structure and associated search/iteration tools for python 3.10+.
Author: arcombe012
License-Expression: Apache-2.0
Project-URL: source, https://github.com/arcombe012/simpletree3.git
Keywords: tree,tree structure,python3 tree class
Classifier: Programming Language :: Python
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Typing :: Typed
Classifier: Operating System :: OS Independent
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Developers
Classifier: Topic :: Software Development :: Libraries
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.10
Description-Content-Type: text/x-rst
License-File: LICENSE
Dynamic: license-file

Simpletree3 module
==================

Offers classes implementing basic tree-like
functionality, as well as iterators for walking
the trees and node search functionality. Requires Python 3.10 or later.

The design goal is to provide a basic class implementing the
essential tree structure and functionality. Practical applications will
want to inherit from one of the provided classes
in order to provide custom functionality. Tree walking
algorithms are implemented as generators, in order to
minimize the use of temporary objects and focus on
speed and efficiency.

Classes
-------

Two classes are provided: *SimpleNode* and
*FlexibleNode*.

SimpleNode
^^^^^^^^^^

This is the base class that provides the
tree node functionality by connecting
parents to children. Additional functionality
can be added by deriving from *SimpleNode*.

Each node is identified by a *key* parameter
of an arbitrary hashable type. Node keys must be unique
among the direct children of a node, since node
children are held in a dict using the key attribute as
dictionary keys (hence the hashable requirement).

Connections with nodes up and down the tree are
accessed through the parent and children properties
(children offers an iterator for the child nodes,
sorted by node key; set the class attribute
``sort_children = False`` in a subclass to iterate
in insertion order instead, which is faster and
allows keys of mixed, non-comparable types).
The root node of a tree is the node with parent
equal to None. Setting the parent of a node
checks that no loops or duplicate keys are inserted and adds
the current node to the parent's children (if needed).
All checks run before anything is changed, so a failed
assignment leaves the tree untouched.
Deleting a parent sets it to None and removes
the node from the parent's children.

Some additional convenience properties are defined -
siblings, ancestors, path, key_path, root, depth, height, size -
as well as methods for adding and removing child nodes
(add_child, remove_child, remove_children, detach),
walking down by keys (``get_descendant(*keys)``) and
checking relationships (is_ancestor_of, is_descendant_of).

FlexibleNode
^^^^^^^^^^^^
This is a convenience class that adds hooks to
setting and deleting a parent. The delete hooks fire
whenever a node is detached from its parent
(``del node.parent``, ``detach()``, ``remove_child()``,
``remove_children()``). The motivation for
providing it is that currently Python does not
offer a simple syntax for calling a base class
property from a derived class when that property is
overriden, so by inheriting from *FlexibleNode*
instead of *SimpleNode* one only has to override
the hooks to perform any desired operations.
Adding and deleting children can be
directly overriden, since they are not implemented
as properties. The design decision of having the
hook functionality implemented in a separate class
allows one to choose the trade-off between
speed and flexibility of tree building
(important for very large trees).


Iterators
---------

The module implements preorder, postorder, level
and leaf iterators. Each comes in two flavors - a simple
one, iterating through all nodes, and a filtered
one, where specific nodes can be selected
and/or specific subtrees can be ignored.
All walks are iterative, so arbitrarily deep trees
do not hit Python's recursion limit.

Utility functions ``count_nodes(node)`` and
``lowest_common_ancestor(a, b)`` are also provided.

Search functionality
--------------------

The simplest search is done using a preorder iteration
procedure that yields nodes with the specified key.
A separate find function returns the first node matching
that key. Search results are never cached, so they always
reflect the current state of the tree.

A common use case when building trees is that
subsequent nodes are added in a subtree containing the last
inserted node. To optimize for this case, a separate
search procedure is implemented, which walks up the
tree from the start node and searches for the
specified key in the subtree rooted in each ancestor.
