nicmart / tree

A basic but flexible tree data structure for php and a fluent tree builder implementation.

Tree

In Tree you can find a basic but flexible tree data structure for php together with and an handful Builder class, that enables you to build tree in a fluent way.

The tree data structure

The Tree\Node\NodeInterface interface abstracts the concept of a tree node. In Tree a Node has essentially two things: a set of children (that implements the same NodeInterface interface) and a value.

On the other hand, the Tree\Node\Node gives a straight implementation for that interface.

Creating a node

use Tree\Node\Node;

$node = new Node('foo');

Getting and setting the value of a node

Each node has a value property, that can be any php value.

$node->setValue('my value');
echo $node->getValue(); //Prints 'my value'

Adding one or more children

$child1 = new Node('child1');
$child2 = new Node('child2');

$node
    ->addChild($child1)
    ->addChild($child2);

Removing a child

$node->removeChild($child1);

Getting the array of all children

$children = $node->getChildren();

Overwriting the children set

$node->setChildren([new Node('foo'), new Node('bar')]);

Removing all children

$node->removeAllChildren();

Getting if the node is a leaf or not

A leaf is a node with no children.

$node->isLeaf();

Getting if the node is a child or not

A child is a node that has a parent.

$node->isChild();

Getting the parent of a node

Reference to the parent node is automatically managed by child-modifiers methods

$root->addChild($node = new Node('child'));
$node->getParent(); // Returns $root

Getting the ancestors of a node

$root = (new Node('root'))
    ->addChild($child = new Node('child'))
    ->addChild($grandChild = new Node('grandchild'))
;

$grandchild->getAncestors(); // Returns [$root, $child]

Related Methods

• getAncestorsAndSelf retrieves ancestors of a node with the current node included.

Getting the root of a node

$root = $node->root();

Getting the neighbors of a node

$root = (new Node('root'))
    ->addChild($child1 = new Node('child1'))
    ->addChild($child2 = new Node('child2'))
    ->addChild($child3 = new Node('child3'))
;

$child2->getNeighbors(); // Returns [$child1, $child3]

Related Methods

• getNeighborsAndSelf retrieves neighbors of current node and the node itself.

Getting the number of nodes in the tree

$node->getSize();

Getting the depth of a node

$node->getDepth();

Getting the height of a node

$node->getHeight();

The Builder

The builder provides a convenient way to build trees. It is provided by the Builder class, but you can implement your own builder making an implementation of the BuilderInterfaceclass.

Example

Let's see how to build the following tree, where the nodes label are represents nodes values:

       A
      / \
     B   C
        /|\
       D E F
      /|
     G H

And here is the code:

$builder = new Tree\Builder\NodeBuilder;

$builder
    ->value('A')
    ->leaf('B')
    ->tree('C')
        ->tree('D')
            ->leaf('G')
            ->leaf('H')
            ->end()
        ->leaf('E')
        ->leaf('F')
        ->end()
;

$nodeA = $builder->getNode();

The example should be self-explanatory, but here you are a brief description of the methods used above.

Builder::value($value)

Set the value of the current node to $value

Builder::leaf($value)

Add to the current node a new child whose value is $value.

Builder::tree($value)

Add to the current node a new child whose value is $value, and set the new node as the builder current node.

Builder::end()

Returns to the context the builder was before the call to treemethod, i.e. make the builder go one level up.

Builder::getNode()

Returns the current node.

Traversing a tree

Yield

You can obtain the yield of a tree (i.e. the list of leaves in a pre-order traversal) using the YieldVisitor.

For example, if $node is the tree built above, then

use Tree\Visitor\YieldVisitor;

$visitor = new YieldVisitor;

$yield = $node->accept($visitor);
// $yield will contain nodes B, G, H, E, F

Pre-order Traversal

You can walk a tree in pre-order:

use Tree\Visitor\PreOrderVisitor;

$visitor = new PreOrderVisitor;

$yield = $node->accept($visitor);
// $yield will contain nodes A, B, C, D, G, H, E, F

Post-order Traversal

You can walk a tree in post-order:

use Tree\Visitor\PostOrderVisitor;

$visitor = new PostOrderVisitor;

$yield = $node->accept($visitor);
// $yield will contain nodes B, G, H, D, E, F, C, A

Install

Run

$ composer require nicmart/tree

Tests

phpunit

Changelog

Please have a look at CHANGELOG.md.

Contributing

Please have a look at CONTRIBUTING.md.

License

This package is licensed using the MIT License.

Please have a look at LICENSE.md.

tree's Issues

Convert to array

Hi,

Is it possible to convert tree to multidimensional array?

Deleting children in a Visitor cause Fatal error

Calling $node->removeChild($child) in a Visitor causes

HP Fatal error: Nesting level too deep - recursive dependency? in vendor/nicmart/tree/src/Node/NodeTrait.php on line 82

class CategoryNameDeleter implements Visitor
{
    /**
     * @var string
     */
    protected $valueToFind;

    /**
     * @param string $valueToFind Node value to find
     */
    public function __construct(string $valueToFind)
    {
        $this->valueToFind = $valueToFind;
    }

    /**
     * @param NodeInterface $node
     *
     * @return bool
     */
    public function visit(NodeInterface $node): bool
    {
        if (empty(self::$response)) {
            self::$response = $node;
        }

        /** @var Node $child */
        foreach ($node->getChildren() as $child) {
            if ($child->getValue()->name()->get() == $this->valueToFind) {
                $node->removeChild($child);
                return true;
            }
            if ($child->accept($this)) {
                return true;
            }
        }

        return false;
    }
}

PHP Unit test line:
$this->assertTrue($this->tree->accept(new CategoryNameDeleter('B')));

Tree builder for test

$builder = new NodeBuilder();
        $builder->value($this->createCategory('root'))
            ->tree($this->createCategory('A'))
                ->leaf($this->createCategory('A1'))
                ->leaf($this->createCategory('A2'))
                ->end()
            ->tree($this->createCategory('B'))
                ->leaf($this->createCategory('B1'))
                ->leaf($this->createCategory('B2'))
                ->end();

        $this->tree = $builder->getNode();

Attach a branch to a node

Hi!

I like your code very much - the quick question is:

Can you please enhance your brilliant code implementing (pseudocode) as follows:

1. $branch = $node->getBranch($childNode)

This should return an array defining $childNode (what is a child node of $node) with all its children.

2. $branch = $node->detatchBranch($childNode)

This should behave as (1) but also remove $childNode and all it's children from $node

3. $node->attachBranch($branch)

This should attach $childNode with all its children to $node

Having this functionality this library would be really great as it would enable complex manipulation on the tree structure.

Problem with builder : tree are not children

Hi,

I get your Builder example and tried this :

$builder = new \Tree\Builder\NodeBuilder();
$builder->value('A')
    ->leaf('B')
    ->tree('C')
        ->leaf('D')
    ->end()
;

$nodeA = $builder->getNode();
var_dump($nodeA->getChildren());

Result :

array(1) {
  [0] => object(Tree\Node\Node)#291 (3) {
    ["value":"Tree\Node\Node":private] => string(1) "B"
    ["parent":"Tree\Node\Node":private] => object(Tree\Node\Node)#290 (3) {
      ["value":"Tree\Node\Node":private] => string(1) "A"
      ["parent":"Tree\Node\Node":private] => NULL
      ["children":"Tree\Node\Node":private] => *RECURSION*
    }
    ["children":"Tree\Node\Node":private] => array(0) {
    }
  }
}

I build it manyally

$node = new \Tree\Node\Node('A');
$node->setChildren([$b = new \Tree\Node\Node('B'), $c = new \Tree\Node\Node('C')]);
$c->addChild($d = new \Tree\Node\Node('D'));

var_dump($node->getChildren());

And got :

array(2) {
  [0] => object(Tree\Node\Node)#296 (3) {
    ["value":"Tree\Node\Node":private] => string(1) "B"
    ["parent":"Tree\Node\Node":private] => object(Tree\Node\Node)#295 (3) {
      ["value":"Tree\Node\Node":private] => string(1) "A"
      ["parent":"Tree\Node\Node":private] => NULL
      ["children":"Tree\Node\Node":private] => *RECURSION*
    }
    ["children":"Tree\Node\Node":private] => array(0) {
    }
  }
  [1] => object(Tree\Node\Node)#297 (3) {
    ["value":"Tree\Node\Node":private] => string(1) "C"
    ["parent":"Tree\Node\Node":private] => object(Tree\Node\Node)#295 (3) {
      ["value":"Tree\Node\Node":private] => string(1) "A"
      ["parent":"Tree\Node\Node":private] => NULL
      ["children":"Tree\Node\Node":private] => *RECURSION*
    }
    ["children":"Tree\Node\Node":private] => array(1) {
      [0] => object(Tree\Node\Node)#298 (3) {
        ["value":"Tree\Node\Node":private] => string(1) "D"
        ["parent":"Tree\Node\Node":private] => *RECURSION*
        ["children":"Tree\Node\Node":private] => array(0) {
        }
      }
    }
  }
}

In other way, got same result :

$node = new \Tree\Node\Node('A');
$node->addChild($b = new \Tree\Node\Node('B'))
    ->addChild($c = new \Tree\Node\Node('C'));

$c->addChild($d = new \Tree\Node\Node('D'));

var_dump($node->getChildren());


array(2) {
  [0] => object(Tree\Node\Node)#300 (3) {
    ["value":"Tree\Node\Node":private] => string(1) "B"
    ["parent":"Tree\Node\Node":private] => object(Tree\Node\Node)#299 (3) {
      ["value":"Tree\Node\Node":private] => string(1) "A"
      ["parent":"Tree\Node\Node":private] => NULL
      ["children":"Tree\Node\Node":private] => *RECURSION*
    }
    ["children":"Tree\Node\Node":private] => array(0) {
    }
  }
  [1] => object(Tree\Node\Node)#301 (3) {
    ["value":"Tree\Node\Node":private] => string(1) "C"
    ["parent":"Tree\Node\Node":private] => object(Tree\Node\Node)#299 (3) {
      ["value":"Tree\Node\Node":private] => string(1) "A"
      ["parent":"Tree\Node\Node":private] => NULL
      ["children":"Tree\Node\Node":private] => *RECURSION*
    }
    ["children":"Tree\Node\Node":private] => array(1) {
      [0] => object(Tree\Node\Node)#302 (3) {
        ["value":"Tree\Node\Node":private] => string(1) "D"
        ["parent":"Tree\Node\Node":private] => *RECURSION*
        ["children":"Tree\Node\Node":private] => array(0) {
        }
      }
    }
  }
}

I expected that "Builder::tree()" create a leaf, and point to it ;
So, i expected B & C will be children of A with the Builder

What i'm doing wrong ?

Thanks

Can one child object be associated with multiple parent objects in this ?

Hi, I want to build a dependency tree, e.g. I have jobs which depends on multiple jobs and other multiple jobs depends on it. Can we build such tree ?

Add variable-length argument lists in `NodeBuilder::leafs()`

Suggestion

I think that we can take advantage of the ... syntax

Justification

Considering the documentation, they encourage us to avoid this technique:

Note: It is also possible to achieve variable-length arguments by using func_num_args(), func_get_arg(), and func_get_args() functions. This technique is not recommended as it was used prior to the introduction of the ... token.

Afected files:

Tree/src/Builder/NodeBuilder.php

Line 55 in 8387cc4

public function leafs(mixed $value1 /* , $value2, ... */): static

Tree/src/Builder/NodeBuilderInterface.php

Line 46 in 8387cc4

public function leafs(mixed $value /* , $value2, ... */): static;

Is it a breaking change?

No, the users of this package could use NodeBuilder::leafs() as they are used to.

🌺

Use String key to represent a Node

I see at the moment children member variable is private and it uses the default integer as array index, I wanted to change that behaviour to support string keys in addChild so I overrode that method in my child class, but since children is private to NodeTrait I can't override the children behaviour. My question is, is there any particular reason for keeping the children private in NodeTrait?

How to Traverse the entire Tree ?

Hey thankyou for this nice tree implementation, do you know how can Iterate through the root and its all children nodes?

PHP Warning: Undefined array key -1

Steps required to reproduce the problem

use Tree\Builder\NodeBuilder;

(new NodeBuilder)->value('some value')->end()->getNode();

Expected Result

An exception should to be thrown if pre-conditions are not met.

Actual Result

PHP Warning:  Undefined array key -1 in vendor/nicmart/tree/src/Builder/NodeBuilder.php on line 43

---

Code in question:

Tree/src/Builder/NodeBuilder.php

Lines 41 to 44 in 409ba5d

	public function getNode(): NodeInterface
	{
	return $this->nodeStack[\count($this->nodeStack) - 1];
	}

Create a node

following the example, I have to use Tree\Node\Node to create a node instead of Tree\Node;

fill tree with node contains parent

can I fill the tree with data with parent like:

$data = array(
    // 0 is root
    array('id' => 1, 'parent' => 0, 'name' => 'Europe'),
    array('id' => 4, 'parent' => 0, 'name' => 'Asia'),
    // --
    array('id' => 7, 'parent' => 1, 'name' => 'Germany'),
    array('id' => 8, 'parent' => 1, 'name' => 'Germany2'),
    array('id' => 10, 'parent' => 4, 'name' => 'Portugal'),
);

     root
      / \
    1    4
   /  \   \
 7     8   10

Improve traverse tree

As I can see, visitors return array of nodes, and how I should use it after I get it?
Proposed I should reiterate this array?

1. It looks like visit method should yield value and lazy step by tree when I iterate by yield, otherwise the whole point of traversing the tree is lost (because it turns out a double tree walk).
2. Another solution should be call visit method with callback param (anonymous function).
   E.g. in other libs:
   https://github.com/slince/tree-samples/blob/master/tests/Traversal/BFSTest.php#L17
   https://github.com/jorpo-co/tree/blob/master/tests/Traversal/BreadthFirstTraversalTest.php#L36

Iterable Node and Proxy Node

Great library. I just wrote a few traits for a project we are using it if you are interested in including them I can make a PR.

IterableNode just implements IteratorAggregate to allow for foreaching over a node/tree

trait IterableNodeTrait 
{
    public function getIterator() {
        return new ArrayIterator($this->getChildren());
    }
}

ProxyNodeTrait proxies method calls on the Node to the underlying value object so you can do $node->getName() instead of $node->getValue()->getName(). In our use case the combination of these makes our template code less aware that its dealing with a tree structure since it acts like an array of business objects (for example a tree of clients with their files).

trait ProxyNodeTrait 
{

    /**
     * Proxy method calls to the value of the node
     * This makes it so you can do $node->getName() instead of $node->getValue()->getName()
     * 
     * @param string $name Method name to call
     * @param array $arguments Arguments for the method
     */
    public function __call($name, array $arguments) {
        $value = $this->getValue();
        $method = $this->determineMethodName($name);

        if ($method) {
            return call_user_func_array([$value, $method], $arguments);
        }

        throw new BadMethodCallException('Invalid method call on '.get_class($this->getValue()).': '.$name);
    }

    /**
     * Determine which method to call on the node's value object based on the $name passed to __call
     * Looks for $name() and get$name()
     * 
     * @param string $name Method name
     * @return string|false
     */
    private function determineMethodName($name) {
        $object = $this->getValue();
        $methods = [$name, 'get'.ucfirst($name)];
        foreach ($methods as $method) {
            if (is_callable([$object, $method])) {
                return $method;
            }
        }
        return false;
    }
}

Level order traversal

Can we get a level order traversal built in? I could help with the implementation

Semantics...

First of all, awesome work guys, very useful and helpful.

Just a comment about semantics if I may.

Your generic "Visitor" is more like an "Iterator".
The "Visitor" pattern usually doesn't decide how to traverse the tree, that's what an Iterator does.

Yes, your visitors also define an output, but you might wanna separate the two concerns: turn the PreOrder and PostOrder visitors into iterators.
The iterator returns the nodes one by one, and then you can pass them to a visitor that does something on them.

That way you'd decouple the traverse algorithm from whatever operation/processing the visitor wants to do.

Makes sense?

Enable Sourcegraph

I want to use Sourcegraph for Tree code search, browsing, and usage examples. Can an admin enable Sourcegraph for this repository? Just go to https://sourcegraph.com/github.com/nicmart/Tree. (It should only take 30 seconds.)

Thank you!

Bug or Feature: getAncestors returns leaf

According to your documentation (getAncestors) the leaf that initiated the ancestors query shouldn't be returned. But it is :)

root -> grandpa -> pa -> child
child->getAncestors() returns root -> grandpa -> pa -> child
Version 0.2.2

From my point of view (and according to your documentation) this is not correct but might be wanted under certain circumstances. Either change the code or the docs :)

[Enhancement] Big children size issue

Please fix me if I am wrong, but I believe for the cases when we have really big children nodes in the $children array property, the code might be crashed to the memory limit when we take $this->getChildren() in visitors.

In fact, would be great to make each visitor (TraversalPreOrder, TraversalPostOrder) via generators.
There is a yield visitor, but in fact, it does not have anything in common with the generator

Depth of a Node

Hi!

I would just like to ask if how can you get the depth of a certain node?