# Tree
[![Build Status](https://travis-ci.org/nicmart/Tree.svg?branch=master)](https://travis-ci.org/nicmart/Tree)
[![Latest Stable Version](https://poser.pugx.org/nicmart/tree/v/stable)](https://packagist.org/packages/nicmart/tree)
[![Total Downloads](https://poser.pugx.org/nicmart/tree/downloads)](https://packagist.org/packages/nicmart/tree)
[![License](https://poser.pugx.org/nicmart/tree/license)](https://packagist.org/packages/nicmart/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.
## Changelog
- 0.2.7 Pre-order and post-order visitors ([PR 24](https://github.com/nicmart/Tree/pull/24)), thanks to [localheinz](https://github.com/localheinz)
- 0.2.6 New getSize method ([PR 17](https://github.com/nicmart/Tree/pull/17)), thanks to [djuki](https://github.com/Djuki)
- 0.2.5 New getDepth and getHeight methods ([Issue 9](https://github.com/nicmart/Tree/issues/9))
- 0.2.4 New accessor methods ([PR 6](https://github.com/nicmart/Tree/pull/6), thanks to [mdwheele](https://github.com/mdwheele))
- 0.2.3 Node::getAncestors now does not return the current node ([Issue 4](https://github.com/nicmart/Tree/issues/4))
- 0.2.2 Fixed a bug in the builder ([Issue 3](https://github.com/nicmart/Tree/issues/3))
- 0.2.1 root() and isRoot() methods
- 0.2.0 Dropped php 5.3 support. Node implemented as a trait.
- 0.1.2 Added YieldVisitor, to get the yield of the tree
- 0.1.1 Parent and neighbors methods (thanks to https://github.com/jdeniau)
## 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
```php
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.
```php
$node->setValue('my value');
echo $node->getValue(); //Prints 'my value'
```
### Adding one or more children
```php
$child1 = new Node('child1');
$child2 = new Node('child2');
$node
->addChild($child1)
->addChild($child2);
```
### Removing a child
```php
$node->removeChild($child1);
```
### Getting the array of all children
```php
$children = $node->getChildren();
```
### Overwriting the children set
```php
$node->setChildren([new Node('foo'), new Node('bar')]);
```
### Removing all children
```php
$node->removeAllChildren();
```
### Getting if the node is a leaf or not
A leaf is a node with no children.
```php
$node->isLeaf();
```
### Getting if the node is a child or not
A child is a node that has a parent.
```php
$node->isChild();
```
### Getting the parent of a node
Reference to the parent node is automatically managed by child-modifiers methods
```php
$root->addChild($node = new Node('child'));
$node->getParent(); // Returns $root
```
### Getting the ancestors of a node
```php
$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
```php
$root = $node->root();
```
### Getting the neighbors of a node
```php
$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
```php
$node->getSize();
```
### Getting the depth of a node
```php
$node->getDepth();
```
### Getting the height of a node
```php
$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 ```BuilderInterface```class.
### 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:
```php
$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 ```tree```method,
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
```php
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:
```php
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:
```php
use Tree\Visitor\PostOrderVisitor;
$visitor = new PostOrderVisitor;
$yield = $node->accept($visitor);
// $yield will contain nodes B, G, H, D, E, F, C, A
```
## Install
The best way to install Tree is [through composer](http://getcomposer.org).
Just create a composer.json file for your project:
```JSON
{
"require": {
"nicmart/tree": "~0.2"
}
}
```
Then you can run these two commands to install it:
$ curl -s http://getcomposer.org/installer | php
$ php composer.phar install
or simply run `composer install` if you have have already [installed the composer globally](http://getcomposer.org/doc/00-intro.md#globally).
Then you can include the autoloader, and you will have access to the library classes:
```php