Download the PHP package dakujem/oliva without Composer

Oliva 🌳

Flexible tree structure,
tree builders (materialized path trees, recursive trees, data wrappers),
tree traversal iterators, filter iterator.

💿 composer require dakujem/oliva

This package is a modern reimplementation of oliva/tree.

Tree

A tree is a form of a graph, specifically a directed acyclic graph (DAG).
Each node in a tree can have at most one parent and any number of children.
The node without a parent is called the root.
A node without children is called a leaf.

Read more on Wikipedia: Tree (data structure).

Oliva trees consist of node instances implementing TreeNodeContract.

Builders

Oliva provides tree builders, classes that construct structured trees from unstructured data. The data is usually in form of iterable collections, typically a result of SQL queries, API calls, YAML config, and such.

The builders are flexible and allow to create any node instances via the node factory parameter.
The simplest factory may look like this

... but it's really up to the integrator to provide a node factory according to his needs:

Anything callable may be a node factory, as long as it returns a class instance implementing \Dakujem\Oliva\MovableNodeContract.

💡

The full signature of the node factory callable is fn(mixed $data, mixed $dataIndex): MovableNodeContract.
That means the keys (indexes) of the input collection may also be used for node construction.

Each of the builders also requires extractors, described below, callables that provide the builder with information about the tree structure.

Materialized path trees

MPT refers to the technique of storing the position of nodes relative to the root node (a.k.a. "path") in the data.

There are multiple ways to actually do that and Oliva is agnostic of them.
A typical path of a node may look like the following:

• "1.33.2", "/1/33/2", also known as the delimited variant
• "001033002", known as the fixed (or fixed-width) variant with constant width of 3 characters per level (here 001, 033 and 002)
• [1,33,2], as an array of integers, here also referred to as a vector

Also, the individual references may either mean the position relative to other siblings on a given level, or be direct node references (ancestor IDs). That is, a path 1.2.3 may mean "the third child of the second child of the first child of the root", or it may mean that a node's ancestor IDs are [1,2,3], 3 being the parent's ID.

To enable all the different techniques, Oliva MPT TreeBuilder requires the user to pass a vector extractor function, e.g. fn($item) => explode('.', $item->path). Oliva comes with two common-case extractor factories: Path::fixed() and Path::delimited().

The following tree will be used in the examples below:

Simple example of a fixed-length MPT:

Same example with an equivalent delimited MPT:

💡

Since child nodes are added to parents sequentially (i.e. without specific keys) in the order they appear in the source data, sorting the source collection by path prior to building the tree may be a good idea.

If sorting of siblings is needed after a tree has been built, LevelOrderTraversal can be used to traverse and modify the tree.

The same is true for cases where the children need to be keyed by specific keys. Use LevelOrderTraversal, remove the children, then sort them and/or calculate their keys and add them back under the new keys and/or in the new order.

Recursive trees

Each node's data has a (recursive) reference to its parent node's data.
Probably the most common and trivial way of persisting trees.

Above, self and parent parameters expect extractors with signature fn(mixed $data, mixed $dataIndex, TreeNodeContract $node): string|int,
while root expects a value of the root node's parent. The node with this parent value will be returned.

The most natural case for root is null because nodes without a parent are considered to be root nodes. The value can be changed to 0, "" or whatever else is suitable for the particular dataset.
This is useful when building a subtree.

Wrapping arrays, JSON, YAML...

In case the data is already structured as tree data, a simple wrapper may be used to build the tree structure.

Above, children expects an extractor with signature fn(mixed $data, TreeNodeContract $node): ?iterable.

💡

Remember, it is up to the integrator to construct the tree nodes. Any transformation can be done with the data, as long as a node implementing the MovableNodeContract is returned.

Manual tree building

Using a manual node builder:

Using the low-level node interface (MovableNodeContract) for building a tree:

... yeah, that is not the most optimal way to build a tree.

Using high-level manipulator (Tree) for doing the same:

... or a more concise way:

Moving nodes around

TL;DR Use the Tree::link static method.

In some cases it is sufficient to use the low-level interface of nodes (setParent, addChild, removeChild methods), but in most cases the Tree::link works better:

The Tree::link call will take care of all the relations: unlinking the original parent and linking the subtree to the new one.

Tree traversal and iterators

Oliva provides tree traversal iterators, generators and a filter iterator.

The traversal iterators and generators will iterate over all the tree's nodes in a specific order.

Depth-first search, pre-order traversal

• Traversal::preOrder generator
• PreOrderTraversal iterator

Depth-first search, post-order traversal

• Traversal::postOrder generator
• PostOrderTraversal iterator

Breadth-first search, level-order traversal

• Traversal::levelOrder generator
• LevelOrderTraversal iterator

If unsure what the different traversals mean, read more about Tree traversal.

💡

The key difference between the iterator classes and generator methods is in the keys. If the keys in the iteration do not matter, use the Traversal's generator methods for slightly better performance.

If the order of traversal is not important, a Node instance can simply be iterated over:

The above will iterate over the whole subtree, including the node itself and all its descendants.

💡

For manipulating tree iterators, or any other iterable collections, dakujem/toru may be used.
Toru is based on generators and thus provides efficient operations when recursive filter iterators are used.

Filtering nodes

Finally, the filter iterator Iterator\Filter may be used for filtering either the input data or tree nodes.

For manipulating iterators, dakujem/toru may be used, which provides more robust implementation and many more manipulation methods than the Seed class offers.

Searching for specific nodes

Oliva does not provide a direct way to search for specific nodes, but it is trivial to create one yourself:

A class may be appropriate too...

Node keys

Normally, the keys will increment during a traversal (using any traversal iterator or generator).

When using any of the traversal iterators, it is possible to alter the key sequence using a key callable.
This example generates a delimited materialized path:

This example indexes the nodes by an ID found in the data:

The full signature of the key callable is

where

• $node is the current node
• $vector is the node's vector in a tree
  • it is a path from the root to the node with child indexes being the vector's elements
  • vector of a root is empty [] (or equal to $startingVector if passed to the iterator constructor)
  • the current node's index within its parent's children is the last element of the vector
• $seq is the current sibling numerator (first child is 0, second child is 1, and so on)
• $counter is the default iteration numerator that increments by 1 with each node (0, 1, 2, ...)
  • without a key callable, this is the key sequence

All Oliva traversal iterators accept a key callable and a starting vector (a prefix to the $vector).

💡

Be careful with iterator_to_array when using key callable, because colliding keys will be overwritten without a warning.
The key callable SHOULD generate unique keys.

Cookbook

Materialized path tree without root data

There may be situations where the source data does not contain a root.
It may be a result of storing article comments, menus or forum posts and considering the parent object (the article, the thread or the site) to be the root.

One of the solutions is to prepend an empty data element and then ignore it during iterations if it is not desired to iterate over the root.

Observe the use of the Seed helper class:

We could also use Seed::chain to prepend an item with fabricated root data, but then Seed::omitRoot must be used to omit the root instead of Seed::omitNull:

Recursive tree without root data

A similar situation may occur when using the recursive builder on a subtree, when the root node of the subtree has a non-null parent.

This is very simply solved by passing the $root argument to the tree builder.

If a node's parent matches the value, it is considered the root node.

Migrating from the old oliva/tree library

Builders and iterators

If migrating from the previous library (oliva/tree), the most common problems are caused by

• the new builders not automatically adding an empty root node
• the new iterators iterating over root node

For both, see "Materialized path tree without root data" and "Recursive tree without root data" sections in the "Cookbook" section above.

Node classes

Neither magic props proxying nor array access of the Oliva\Utils\Tree\Node\Node are supported.
Migrating to the new Dakujem\Oliva\Node class is recommended instead of attempting to recreate the old behaviour.

The Dakujem\Oliva\Node is very similar to Oliva\Utils\Tree\Node\SimpleNode, migrating from that one should be trivial (migrate the getter/setter usage).

Testing

Run unit tests using the following command:

Contributing

Ideas, issues or code contribution is welcome. Please send a PR or submit an issue.

And if you happen to like the library, give it a star and spread the word 🙏.