Download the PHP package dakujem/oliva without Composer
On this page you can find all versions of the php package dakujem/oliva. It is possible to download/install these versions without Composer. Possible dependencies are resolved automatically.
Download dakujem/oliva
More information about dakujem/oliva
Files in dakujem/oliva
Package oliva
Short Description Flexible tree structure, tree builders (materialized paths, recursive, wrappers), traversal iterators, filter.
License Unlicense
Informations about the package oliva
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 (here001
,033
and002
)[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
isnull
because nodes without a parent are considered to be root nodes. The value can be changed to0
,""
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
generatorPreOrderTraversal
iterator
Depth-first search, post-order traversal
Traversal::postOrder
generatorPostOrderTraversal
iterator
Breadth-first search, level-order traversal
Traversal::levelOrder
generatorLevelOrderTraversal
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.
💡
Traversals may be used to decorate nodes or even alter the trees.
Be sure to understand how each of the traversals work before altering the tree structure within a traversal, otherwise you may experience the unexpected.
Filtering nodes
Finally, the filter iterator Iterator\Filter
may be used for filtering either the input data or tree nodes.
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) - current node's index within its parent's children is the last element of the vector
$seq
is the current sibling numerator (first child is0
, second child is1
, 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::merged
to prepend an item with fabricated root data, but then Seed::omitRoot
must be used to omit the root instead:
Recursive tree without root data
Similar situation may happen 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 🙏.