diff options
author | Yaco <franco@reevo.org> | 2020-06-04 11:01:00 -0300 |
---|---|---|
committer | Yaco <franco@reevo.org> | 2020-06-04 11:01:00 -0300 |
commit | fc7369835258467bf97eb64f184b93691f9a9fd5 (patch) | |
tree | daabd60089d2dd76d9f5fb416b005fbe159c799d /www/wiki/vendor/nicmart |
first commit
Diffstat (limited to 'www/wiki/vendor/nicmart')
21 files changed, 1975 insertions, 0 deletions
diff --git a/www/wiki/vendor/nicmart/tree/.gitignore b/www/wiki/vendor/nicmart/tree/.gitignore new file mode 100644 index 00000000..8b557579 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/.gitignore @@ -0,0 +1,2 @@ +vendor/ +phpunit.xml
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/.travis.yml b/www/wiki/vendor/nicmart/tree/.travis.yml new file mode 100644 index 00000000..c8281770 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/.travis.yml @@ -0,0 +1,16 @@ +language: php + +sudo: false + +php: + - 5.4 + - 5.5 + - 5.6 + - 7.0 + - hhvm + +before_script: + - composer install + +script: + - phpunit diff --git a/www/wiki/vendor/nicmart/tree/LICENSE b/www/wiki/vendor/nicmart/tree/LICENSE new file mode 100644 index 00000000..c993b94f --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/LICENSE @@ -0,0 +1,19 @@ +Copyright (c) 2013 Nicolò Martini + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is furnished +to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE.
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/README.md b/www/wiki/vendor/nicmart/tree/README.md new file mode 100644 index 00000000..ba39c25f --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/README.md @@ -0,0 +1,299 @@ +# 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 +<?php +require 'vendor/autoload.php'; +``` + +# Tests + +``` +phpunit +``` diff --git a/www/wiki/vendor/nicmart/tree/composer.json b/www/wiki/vendor/nicmart/tree/composer.json new file mode 100644 index 00000000..803abf41 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/composer.json @@ -0,0 +1,27 @@ +{ + "name": "nicmart/tree", + "type": "library", + "description": "A basic but flexible php tree data structure and a fluent tree builder implementation.", + "keywords": [], + "license": "MIT", + "authors": [ + { + "name": "Nicolò Martini", + "email": "nicmartnic@gmail.com" + } + ], + "require": { + "php": ">=5.4" + }, + "autoload": { + "psr-4": { + "Tree\\": "src/" + } + }, + "autoload-dev": { + "psr-4": { + "Tree\\Test\\": "tests/" + } + } +} + diff --git a/www/wiki/vendor/nicmart/tree/composer.lock b/www/wiki/vendor/nicmart/tree/composer.lock new file mode 100644 index 00000000..c9357e5f --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/composer.lock @@ -0,0 +1,19 @@ +{ + "_readme": [ + "This file locks the dependencies of your project to a known state", + "Read more about it at https://getcomposer.org/doc/01-basic-usage.md#composer-lock-the-lock-file", + "This file is @generated automatically" + ], + "hash": "c390d79a97a7207157bdab1c1fbb9417", + "packages": [], + "packages-dev": [], + "aliases": [], + "minimum-stability": "stable", + "stability-flags": [], + "prefer-stable": false, + "prefer-lowest": false, + "platform": { + "php": ">=5.4" + }, + "platform-dev": [] +} diff --git a/www/wiki/vendor/nicmart/tree/phpunit.xml.dist b/www/wiki/vendor/nicmart/tree/phpunit.xml.dist new file mode 100644 index 00000000..8b8f2ebf --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/phpunit.xml.dist @@ -0,0 +1,24 @@ +<?xml version="1.0" encoding="UTF-8"?> + +<phpunit backupGlobals="false" + backupStaticAttributes="false" + colors="true" + convertErrorsToExceptions="true" + convertNoticesToExceptions="true" + convertWarningsToExceptions="true" + processIsolation="false" + stopOnFailure="false" + bootstrap="vendor/autoload.php" +> + <testsuites> + <testsuite name="Tree test suite"> + <directory>./tests/</directory> + </testsuite> + </testsuites> + + <filter> + <whitelist> + <directory>./</directory> + </whitelist> + </filter> +</phpunit>
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/src/Builder/NodeBuilder.php b/www/wiki/vendor/nicmart/tree/src/Builder/NodeBuilder.php new file mode 100644 index 00000000..dfa683dc --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Builder/NodeBuilder.php @@ -0,0 +1,137 @@ +<?php +/* + * This file is part of Tree. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ + +namespace Tree\Builder; + +use Tree\Node\NodeInterface; +use Tree\Node\Node; + +/** + * Main implementation of the NodeBuilderInterface + */ +class NodeBuilder implements NodeBuilderInterface +{ + /** + * @var NodeInterface[] + */ + private $nodeStack = []; + + /** + * @param NodeInterface $node + */ + public function __construct(NodeInterface $node = null) + { + $this->setNode($node ?: $this->nodeInstanceByValue()); + } + + /** + * {@inheritdoc} + */ + public function setNode(NodeInterface $node) + { + $this + ->emptyStack() + ->pushNode($node) + ; + + return $this; + } + + /** + * {@inheritdoc} + */ + public function getNode() + { + return $this->nodeStack[count($this->nodeStack) - 1]; + } + + /** + * {@inheritdoc} + */ + public function leaf($value = null) + { + $this->getNode()->addChild( + $this->nodeInstanceByValue($value) + ); + + return $this; + } + + /** + * {@inheritdoc} + */ + public function leafs($value1 /*, $value2, ... */) + { + foreach (func_get_args() as $value) { + $this->leaf($value); + } + + return $this; + } + + /** + * {@inheritdoc} + */ + public function tree($value = null) + { + $node = $this->nodeInstanceByValue($value); + $this->getNode()->addChild($node); + $this->pushNode($node); + + return $this; + } + + /** + * {@inheritdoc} + */ + public function end() + { + $this->popNode(); + + return $this; + } + + /** + * {@inheritdoc} + */ + public function nodeInstanceByValue($value = null) + { + return new Node($value); + } + + /** + * {@inheritdoc} + */ + public function value($value) + { + $this->getNode()->setValue($value); + + return $this; + } + + private function emptyStack() + { + $this->nodeStack = []; + + return $this; + } + + private function pushNode(NodeInterface $node) + { + array_push($this->nodeStack, $node); + + return $this; + } + + private function popNode() + { + return array_pop($this->nodeStack); + } +} diff --git a/www/wiki/vendor/nicmart/tree/src/Builder/NodeBuilderInterface.php b/www/wiki/vendor/nicmart/tree/src/Builder/NodeBuilderInterface.php new file mode 100644 index 00000000..e8082dbd --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Builder/NodeBuilderInterface.php @@ -0,0 +1,91 @@ +<?php +/* + * This file is part of library-template. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace Tree\Builder; + +use Tree\Node\NodeInterface; + +/** + * Interface that allows a fluent tree building. + * + * @package Tree + * @author Nicolò Martini <nicmartnic@gmail.com> + */ +interface NodeBuilderInterface +{ + /** + * Set the node the builder will manage + * + * @param NodeInterface $node + * + * @return NodeBuilderInterface The current instance + */ + public function setNode(NodeInterface $node); + + /** + * Get the node the builder manages + * + * @return NodeInterface + */ + public function getNode(); + + /** + * Set the value of the underlaying node + * + * @param mixed $value + * + * @return NodebuilderInterface The current instance + */ + public function value($value); + + /** + * Add a leaf to the node + * + * @param mixed $value The value of the leaf node + * + * @return NodeBuilderInterface The current instance + */ + public function leaf($value = null); + + /** + * Add several leafs to the node + * + * @param $value, ... An arbitrary long list of values + * + * @return NodeBuilderInterface The current instance + */ + public function leafs($value); + + /** + * Add a child to the node enter in its scope + * + * @param null $value + * + * @return NodeBuilderInterface A NodeBuilderInterface instance linked to the child node + */ + public function tree($value = null); + + /** + * Goes up to the parent node context + * + * @return null|NodeBuilderInterface A NodeBuilderInterface instanced linked to the parent node + */ + public function end(); + + /** + * Return a node instance set with the given value. Implementation can follow their own logic + * in choosing the NodeInterface implmentation taking into account the value + * + * @param mixed $value + * + * @return NodeInterface + */ + public function nodeInstanceByValue($value = null); +} + diff --git a/www/wiki/vendor/nicmart/tree/src/Node/Node.php b/www/wiki/vendor/nicmart/tree/src/Node/Node.php new file mode 100644 index 00000000..e489cd55 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Node/Node.php @@ -0,0 +1,19 @@ +<?php +/* + * This file is part of Tree. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ + +namespace Tree\Node; + +/** + * Class Node + */ +class Node implements NodeInterface +{ + use NodeTrait; +} diff --git a/www/wiki/vendor/nicmart/tree/src/Node/NodeInterface.php b/www/wiki/vendor/nicmart/tree/src/Node/NodeInterface.php new file mode 100644 index 00000000..ef2d717e --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Node/NodeInterface.php @@ -0,0 +1,164 @@ +<?php +/* + * This file is part of Tree library. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace Tree\Node; + +use Tree\Visitor\Visitor; + +/** + * Interface for tree nodes + * + * @package Tree + * @author Nicolò Martini <nicmartnic@gmail.com> + */ +interface NodeInterface +{ + /** + * Set the value of the current node + * + * @param mixed $value + * + * @return NodeInterface the current instance + */ + public function setValue($value); + + /** + * Get the current node value + * + * @return mixed + */ + public function getValue(); + + /** + * Add a child + * + * @param NodeInterface $child + * + * @return mixed + */ + public function addChild(NodeInterface $child); + + /** + * Remove a node from children + * + * @param NodeInterface $child + * + * @return NodeInterface the current instance + */ + public function removeChild(NodeInterface $child); + + /** + * Remove all children + * + * @return NodeInterface The current instance + */ + public function removeAllChildren(); + + /** + * Return the array of children + * + * @return NodeInterface[] + */ + public function getChildren(); + + /** + * Replace the children set with the given one + * + * @param NodeInterface[] $children + * + * @return mixed + */ + public function setChildren(array $children); + + /** + * setParent + * + * @param NodeInterface $parent + * @return void + */ + public function setParent(NodeInterface $parent = null); + + /** + * getParent + * + * @return NodeInterface + */ + public function getParent(); + + /** + * Retrieves all ancestors of node excluding current node. + * + * @return array + */ + public function getAncestors(); + + /** + * Retrieves all ancestors of node as well as the node itself. + * + * @return Node[] + */ + public function getAncestorsAndSelf(); + + /** + * Retrieves all neighboring nodes, excluding the current node. + * + * @return array + */ + public function getNeighbors(); + + /** + * Returns all neighboring nodes, including the current node. + * + * @return Node[] + */ + public function getNeighborsAndSelf(); + + /** + * Return true if the node is the root, false otherwise + * + * @return bool + */ + public function isRoot(); + + /** + * Return true if the node is a child, false otherwise. + * + * @return bool + */ + public function isChild(); + + /** + * Return true if the node has no children, false otherwise + * + * @return bool + */ + public function isLeaf(); + + /** + * Return the distance from the current node to the root + * + * @return int + */ + public function getDepth(); + + /** + * Return the height of the tree whose root is this node + * + * @return int + */ + public function getHeight(); + + /** + * Accept method for the visitor pattern (see http://en.wikipedia.org/wiki/Visitor_pattern) + * + * @param Visitor $visitor + * @return void + */ + public function accept(Visitor $visitor); +} diff --git a/www/wiki/vendor/nicmart/tree/src/Node/NodeTrait.php b/www/wiki/vendor/nicmart/tree/src/Node/NodeTrait.php new file mode 100644 index 00000000..8d8c5429 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Node/NodeTrait.php @@ -0,0 +1,295 @@ +<?php +/** + * This file is part of Tree + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + * + * @author Nicolò Martini <nicmartnic@gmail.com> + */ + +namespace Tree\Node; + +use Tree\Visitor\Visitor; + +trait NodeTrait +{ + /** + * @var mixed + */ + private $value; + + /** + * parent + * + * @var NodeInterface + * @access private + */ + private $parent; + + /** + * @var NodeInterface[] + */ + private $children = []; + + /** + * @param mixed $value + * @param NodeInterface[] $children + */ + public function __construct($value = null, array $children = []) + { + $this->setValue($value); + if (!empty($children)) { + $this->setChildren($children); + } + } + + /** + * {@inheritdoc} + */ + public function setValue($value) + { + $this->value = $value; + + return $this; + } + + /** + * {@inheritdoc} + */ + public function getValue() + { + return $this->value; + } + + /** + * {@inheritdoc} + */ + public function addChild(NodeInterface $child) + { + $child->setParent($this); + $this->children[] = $child; + + return $this; + } + + /** + * {@inheritdoc} + */ + public function removeChild(NodeInterface $child) + { + foreach ($this->children as $key => $myChild) { + if ($child == $myChild) { + unset($this->children[$key]); + } + } + + $this->children = array_values($this->children); + + $child->setParent(null); + + return $this; + } + + /** + * {@inheritdoc} + */ + public function removeAllChildren() + { + $this->setChildren([]); + + return $this; + } + + /** + * {@inheritdoc} + */ + public function getChildren() + { + return $this->children; + } + + /** + * {@inheritdoc} + */ + public function setChildren(array $children) + { + $this->removeParentFromChildren(); + $this->children = []; + + foreach ($children as $child) { + $this->addChild($child); + } + + return $this; + } + + /** + * {@inheritdoc} + */ + public function setParent(NodeInterface $parent = null) + { + $this->parent = $parent; + } + + /** + * {@inheritdoc} + */ + public function getParent() + { + return $this->parent; + } + + /** + * {@inheritdoc} + */ + public function getAncestors() + { + $parents = []; + $node = $this; + while ($parent = $node->getParent()) { + array_unshift($parents, $parent); + $node = $parent; + } + + return $parents; + } + + /** + * {@inheritDoc} + */ + public function getAncestorsAndSelf() + { + return array_merge($this->getAncestors(), [$this]); + } + + /** + * {@inheritdoc} + */ + public function getNeighbors() + { + $neighbors = $this->getParent()->getChildren(); + $current = $this; + + // Uses array_values to reset indexes after filter. + return array_values( + array_filter( + $neighbors, + function ($item) use ($current) { + return $item != $current; + } + ) + ); + } + + /** + * {@inheritDoc} + */ + public function getNeighborsAndSelf() + { + return $this->getParent()->getChildren(); + } + + /** + * {@inheritDoc} + */ + public function isLeaf() + { + return count($this->children) === 0; + } + + /** + * @return bool + */ + public function isRoot() + { + return $this->getParent() === null; + } + + /** + * {@inheritDoc} + */ + public function isChild() + { + return $this->getParent() !== null; + } + + /** + * Find the root of the node + * + * @return NodeInterface + */ + public function root() + { + $node = $this; + + while ($parent = $node->getParent()) + $node = $parent; + + return $node; + } + + /** + * Return the distance from the current node to the root. + * + * Warning, can be expensive, since each descendant is visited + * + * @return int + */ + public function getDepth() + { + if ($this->isRoot()) { + return 0; + } + + return $this->getParent()->getDepth() + 1; + } + + /** + * Return the height of the tree whose root is this node + * + * @return int + */ + public function getHeight() + { + if ($this->isLeaf()) { + return 0; + } + + $heights = []; + + foreach ($this->getChildren() as $child) { + $heights[] = $child->getHeight(); + } + + return max($heights) + 1; + } + + /** + * Return the number of nodes in a tree + * @return int + */ + public function getSize() + { + $size = 1; + foreach ($this->getChildren() as $child) { + $size += $child->getSize(); + } + + return $size; + } + + /** + * {@inheritdoc} + */ + public function accept(Visitor $visitor) + { + return $visitor->visit($this); + } + + private function removeParentFromChildren() + { + foreach ($this->getChildren() as $child) + $child->setParent(null); + } +} diff --git a/www/wiki/vendor/nicmart/tree/src/Visitor/PostOrderVisitor.php b/www/wiki/vendor/nicmart/tree/src/Visitor/PostOrderVisitor.php new file mode 100644 index 00000000..64414452 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Visitor/PostOrderVisitor.php @@ -0,0 +1,24 @@ +<?php + +namespace Tree\Visitor; + +use Tree\Node\NodeInterface; + +class PostOrderVisitor implements Visitor +{ + public function visit(NodeInterface $node) + { + $nodes = []; + + foreach ($node->getChildren() as $child) { + $nodes = array_merge( + $nodes, + $child->accept($this) + ); + } + + $nodes[] = $node; + + return $nodes; + } +} diff --git a/www/wiki/vendor/nicmart/tree/src/Visitor/PreOrderVisitor.php b/www/wiki/vendor/nicmart/tree/src/Visitor/PreOrderVisitor.php new file mode 100644 index 00000000..c0142065 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Visitor/PreOrderVisitor.php @@ -0,0 +1,24 @@ +<?php + +namespace Tree\Visitor; + +use Tree\Node\NodeInterface; + +class PreOrderVisitor implements Visitor +{ + public function visit(NodeInterface $node) + { + $nodes = [ + $node, + ]; + + foreach ($node->getChildren() as $child) { + $nodes = array_merge( + $nodes, + $child->accept($this) + ); + } + + return $nodes; + } +} diff --git a/www/wiki/vendor/nicmart/tree/src/Visitor/Visitor.php b/www/wiki/vendor/nicmart/tree/src/Visitor/Visitor.php new file mode 100644 index 00000000..f54f0496 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Visitor/Visitor.php @@ -0,0 +1,27 @@ +<?php +/* + * This file is part of Tree library. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace Tree\Visitor; + +use Tree\Node\NodeInterface; + +/** + * Visitor interface for Nodes + * + * @package Tree + * @author Nicolò Martini <nicmartnic@gmail.com> + */ +interface Visitor +{ + /** + * @param NodeInterface $node + * @return mixed + */ + public function visit(NodeInterface $node); +}
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/src/Visitor/YieldVisitor.php b/www/wiki/vendor/nicmart/tree/src/Visitor/YieldVisitor.php new file mode 100644 index 00000000..6a8c65a1 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/src/Visitor/YieldVisitor.php @@ -0,0 +1,40 @@ +<?php +/** + * This file is part of Tree + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + * + * @author Nicolò Martini <nicmartnic@gmail.com> + */ + +namespace Tree\Visitor; + + +use Tree\Node\NodeInterface; + +/** + * Class YieldVisitor + * + * @package Tree\Visitor + */ +class YieldVisitor implements Visitor +{ + /** + * {@inheritdoc} + */ + public function visit(NodeInterface $node) + { + if ($node->isLeaf()) { + return [$node]; + } + + $yield = []; + + foreach ($node->getChildren() as $child) { + $yield = array_merge($yield, $child->accept($this)); + } + + return $yield; + } +}
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/tests/Builder/NodeBuilderTest.php b/www/wiki/vendor/nicmart/tree/tests/Builder/NodeBuilderTest.php new file mode 100644 index 00000000..fd1804d7 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/tests/Builder/NodeBuilderTest.php @@ -0,0 +1,138 @@ +<?php +/* + * This file is part of Tree. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace Tree\Test\Builder; + +use Tree\Node\Node; +use Tree\Builder\NodeBuilder; + +/** + * Unit tests for class FirstClass + */ +class NodeTest extends \PHPUnit_Framework_TestCase +{ + /** @var NodeBuilder */ + protected $builder; + + public function setUp() + { + $this->builder = new NodeBuilder; + } + + public function testConstructorCreatesEmptyNodeIfNoSpecified() + { + $builder = new NodeBuilder; + + $this->assertNull($builder->getNode()->getValue()); + } + + public function testConstructor() + { + $builder = new NodeBuilder($node = new Node('node')); + + $this->assertEquals($node, $builder->getNode()); + } + + public function testSetNodeAndGetNode() + { + $this->builder->setNode($node1 = new Node('node1')); + $this->assertEquals($node1, $this->builder->getNode()); + + $this->builder->setNode($node2 = new Node('node2')); + $this->assertEquals($node2, $this->builder->getNode()); + } + + public function testLeaf() + { + $this->builder->leaf('a')->leaf('b'); + + $children = $this->builder->getNode()->getChildren(); + + $this->assertEquals('a', $children[0]->getValue()); + $this->assertEquals('b', $children[1]->getValue()); + } + + public function testLeafs() + { + $this->builder->leafs('a', 'b'); + + $children = $this->builder->getNode()->getChildren(); + + $this->assertEquals('a', $children[0]->getValue()); + $this->assertEquals('b', $children[1]->getValue()); + } + + public function testTreeAddNewNodeAsChildOfTheParentNode() + { + $this->builder + ->value('root') + ->tree('a') + ->tree('b')->end() + ->leaf('c') + ->end() + ; + + $node = $this->builder->getNode(); + $this->assertEquals(array('a'), $this->childrenValues($node->getChildren())); + + $subtree = $node->getChildren()[0]; + $this->assertEquals(array('b', 'c'), $this->childrenValues($subtree->getChildren())); + } + + public function testTree() + { + $this->builder->tree('a')->tree('b'); + + $this->assertEquals('b', $this->builder->getNode()->getValue()); + } + + public function testEnd() + { + $this->builder + ->value('root') + ->tree('a') + ->tree('b') + ->tree('c') + ->end(); + + $this->assertEquals('b', $this->builder->getNode()->getValue()); + + $this->builder->end(); + $this->assertEquals('a', $this->builder->getNode()->getValue()); + + $this->builder->end(); + $this->assertEquals('root', $this->builder->getNode()->getValue()); + } + + public function testValue() + { + $this->builder->value('foo')->value('bar'); + + $this->assertEquals('bar', $this->builder->getNode()->getValue()); + } + + public function testNodeInstanceByValue() + { + $node = $this->builder->nodeInstanceByValue('baz'); + + $this->assertEquals('baz', $node->getValue()); + $this->assertInstanceOf('Tree\Node\Node', $node); + } + + /** + * @param array[Node] $children + * @return array + */ + private function childrenValues(array $children) + { + return array_map(function(Node $node) { + return $node->getValue(); + }, $children); + } +}
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/tests/Node/NodeTest.php b/www/wiki/vendor/nicmart/tree/tests/Node/NodeTest.php new file mode 100644 index 00000000..8a701899 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/tests/Node/NodeTest.php @@ -0,0 +1,288 @@ +<?php +/* + * This file is part of Tree. + * + * (c) 2013 Nicolò Martini + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + */ +namespace Tree\Test\Tree; + +use Tree\Node\Node; + +/** + * Unit tests for class FirstClass + */ +class NodeTest extends \PHPUnit_Framework_TestCase +{ + public function setUp() + { + + } + + public function testSetValue() + { + $node = new Node; + + $node->setValue('string value'); + + $this->assertEquals('string value', $node->getValue()); + + $node->setValue($object = new \stdClass()); + $object->foo = 'bar'; + + $this->assertEquals($object, $node->getValue()); + } + + public function testAddAndGetChildren() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ->addChild($child3 = new Node('child3')) + ; + + $this->assertEquals([$child1, $child2, $child3], $root->getChildren()); + } + + public function testAddChildSetParent() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ; + + $this->assertEquals($root, $child1->getParent()); + $this->assertEquals($root, $child2->getParent()); + } + + public function testSetAndGetParent() + { + $root = new Node; + $child = new Node('foo'); + + $child->setParent($root); + + $this->assertEquals($root, $child->getParent()); + } + + public function testSetChildren() + { + $children = [new Node('child1'), new Node('child2'), new Node('child3')]; + + $root = new Node; + + $root->setChildren($children); + + $this->assertEquals($children, $root->getChildren()); + } + + public function testSetChildrenSetParentsReferences() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ; + + $this->assertEquals($root, $child1->getParent()); + $this->assertEquals($root, $child2->getParent()); + } + + public function testRemoveChild() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ->addChild($child3 = new Node('child3')) + ->removeChild($child2) + ; + + $this->assertEquals([$child1, $child3], $root->getChildren()); + } + + public function testRemoveChildRemoveParentReference() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->removeChild($child1) + ; + + $this->assertNull($child1->getParent()); + } + + public function testRemoveAllChildrenRemoveParentReferences() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->removeAllChildren() + ; + + $this->assertNull($child1->getParent()); + } + + public function testRemoveAllChildren() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ->addChild($child3 = new Node('child3')) + ->removeAllChildren() + ; + + $this->assertEmpty($root->getChildren()); + } + + public function testGetAncestors() + { + $root = new Node('r'); + $root->addChild($a = new Node('a')); + $a->addChild($b = new Node('b')); + $b->addChild($c = new Node('c')); + + $this->assertEquals([$root, $a, $b], $c->getAncestors()); + } + + public function testGetAncestorsAndSelf() + { + $root = new Node('r'); + $root->addChild($a = new Node('a')); + $a->addChild($b = new Node('b')); + + $this->assertEquals([$root, $a, $b], $b->getAncestorsAndSelf()); + } + + public function testGetNeighbors() + { + $root = new Node('r'); + $root + ->addChild($a = new Node('a')) + ->addChild($b = new Node('b')) + ->addChild($c = new Node('c')); + + $this->assertEquals([$b, $c], $a->getNeighbors()); + } + + public function testGetNeighborsAndSelf() + { + $root = new Node('r'); + $root + ->addChild($a = new Node('a')) + ->addChild($b = new Node('b')) + ->addChild($c = new Node('c')); + + $this->assertEquals([$a, $b, $c], $a->getNeighborsAndSelf()); + } + + public function testIsLeaf() + { + $root = new Node; + + $this->assertTrue($root->isLeaf()); + + $root->addChild(new Node('child')); + + $this->assertFalse($root->isLeaf()); + } + + public function testRoot() + { + $root = (new Node('root')) + ->addChild( + (new Node('child'))->addChild($grandchild = new Node('grandchild')) + ); + + $this->assertSame($root, $grandchild->root()); + } + + public function testIsRoot() + { + $root = new Node('root'); + $root->addChild($child = new Node('child')); + + $this->assertTrue($root->isRoot()); + $this->assertFalse($child->isRoot()); + } + + public function testIsChild() + { + $root = new Node('root'); + $root->addChild($child = new Node('child')); + + $this->assertTrue($child->isChild()); + $this->assertFalse($root->isChild()); + } + + public function testGetDepth() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ->addChild($child3 = new Node('child3')) + ; + + $child3 + ->addChild($child4 = new Node("a")) + ->addChild(new Node("b")) + ; + + $this->assertEquals(1, $child1->getDepth()); + $this->assertEquals(0, $root->getDepth()); + $this->assertEquals(2, $child4->getDepth()); + } + + public function testGetHeight() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ->addChild($child3 = new Node('child3')) + ; + + $child3 + ->addChild(new Node("a")) + ->addChild(new Node("b")) + ; + + $this->assertEquals(0, $child1->getHeight()); + $this->assertEquals(2, $root->getHeight()); + $this->assertEquals(1, $child3->getHeight()); + } + + + public function testGetSize() + { + $root = new Node; + $root + ->addChild($child1 = new Node('child1')) + ->addChild($child2 = new Node('child2')) + ->addChild($child3 = new Node('child3')) + ; + + $child3 + ->addChild(new Node("a")) + ->addChild($child4 = new Node("b")) + ; + + $child4->addChild($child5 = new Node("c")); + $child5 + ->addChild(new Node("d")) + ->addChild(new Node("f")) + ; + + $this->assertEquals(9, $root->getSize()); + $this->assertEquals(3, $child5->getSize()); + $this->assertEquals(4, $child4->getSize()); + $this->assertEquals(6, $child3->getSize()); + $this->assertEquals(1, $child2->getSize()); + } +}
\ No newline at end of file diff --git a/www/wiki/vendor/nicmart/tree/tests/Visitor/PostOrderVisitorTest.php b/www/wiki/vendor/nicmart/tree/tests/Visitor/PostOrderVisitorTest.php new file mode 100644 index 00000000..c0f2efcb --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/tests/Visitor/PostOrderVisitorTest.php @@ -0,0 +1,135 @@ +<?php + +namespace Tree\Test\Visitor; + +use Tree\Node\Node; +use Tree\Visitor\PostOrderVisitor; + +class PostOrderVisitorTest extends \PHPUnit_Framework_TestCase +{ + public function testImplementsInterface() + { + $visitor = new PostOrderVisitor(); + + $this->assertInstanceOf('Tree\Visitor\Visitor', $visitor); + } + + /** + * root + */ + public function testWalkTreeWithOneNode() + { + $root = new Node('root'); + + $visitor = new PostOrderVisitor(); + + $expected = [ + $root, + ]; + + $this->assertSame($expected, $visitor->visit($root)); + } + + /** + * root + * | + * a + */ + public function testWalkTreeWithTwoNodes() + { + $root = new Node('root'); + + $a = new Node('a'); + + $root->addChild($a); + + $visitor = new PostOrderVisitor(); + + $expected = [ + $a, + $root, + ]; + + $this->assertSame($expected, $visitor->visit($root)); + } + + /** + * root + * /|\ + * a b c + * /| | + * d e f + */ + public function testWalkTreeWithMoreNodes() + { + $root = new Node('root'); + + $a = new Node('a'); + $b = new Node('b'); + $c = new Node('c'); + $d = new Node('d'); + $e = new Node('e'); + $f = new Node('f'); + + $root->addChild($a); + $root->addChild($b); + $root->addChild($c); + + $a->addChild($d); + $a->addChild($e); + + $b->addChild($f); + + $visitor = new PostOrderVisitor(); + + $expected = [ + $d, + $e, + $a, + $f, + $b, + $c, + $root, + ]; + + $this->assertSame($expected, $visitor->visit($root)); + } + + /** + * root + * /|\ + * a b c + * /| | + * d e f + */ + public function testWalkSubTree() + { + $root = new Node('root'); + + $a = new Node('a'); + $b = new Node('b'); + $c = new Node('c'); + $d = new Node('d'); + $e = new Node('e'); + $f = new Node('f'); + + $root->addChild($a); + $root->addChild($b); + $root->addChild($c); + + $a->addChild($d); + $a->addChild($e); + + $b->addChild($f); + + $visitor = new PostOrderVisitor(); + + $expected = [ + $d, + $e, + $a, + ]; + + $this->assertSame($expected, $visitor->visit($a)); + } +} diff --git a/www/wiki/vendor/nicmart/tree/tests/Visitor/PreOrderVisitorTest.php b/www/wiki/vendor/nicmart/tree/tests/Visitor/PreOrderVisitorTest.php new file mode 100644 index 00000000..f193f357 --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/tests/Visitor/PreOrderVisitorTest.php @@ -0,0 +1,135 @@ +<?php + +namespace Tree\Test\Visitor; + +use Tree\Node\Node; +use Tree\Visitor\PreOrderVisitor; + +class PreOrderVisitorTest extends \PHPUnit_Framework_TestCase +{ + public function testImplementsInterface() + { + $visitor = new PreOrderVisitor(); + + $this->assertInstanceOf('Tree\Visitor\Visitor', $visitor); + } + + /** + * root + */ + public function testWalkTreeWithOneNode() + { + $root = new Node('root'); + + $visitor = new PreOrderVisitor(); + + $expected = [ + $root, + ]; + + $this->assertSame($expected, $visitor->visit($root)); + } + + /** + * root + * | + * a + */ + public function testWalkTreeWithTwoNodes() + { + $root = new Node('root'); + + $a = new Node('a'); + + $root->addChild($a); + + $visitor = new PreOrderVisitor(); + + $expected = [ + $root, + $a, + ]; + + $this->assertSame($expected, $visitor->visit($root)); + } + + /** + * root + * /|\ + * a b c + * /| | + * d e f + */ + public function testWalkTreeWithMoreNodes() + { + $root = new Node('root'); + + $a = new Node('a'); + $b = new Node('b'); + $c = new Node('c'); + $d = new Node('d'); + $e = new Node('e'); + $f = new Node('f'); + + $root->addChild($a); + $root->addChild($b); + $root->addChild($c); + + $a->addChild($d); + $a->addChild($e); + + $b->addChild($f); + + $visitor = new PreOrderVisitor(); + + $expected = [ + $root, + $a, + $d, + $e, + $b, + $f, + $c, + ]; + + $this->assertSame($expected, $visitor->visit($root)); + } + + /** + * root + * /|\ + * a b c + * /| | + * d e f + */ + public function testWalkSubTree() + { + $root = new Node('root'); + + $a = new Node('a'); + $b = new Node('b'); + $c = new Node('c'); + $d = new Node('d'); + $e = new Node('e'); + $f = new Node('f'); + + $root->addChild($a); + $root->addChild($b); + $root->addChild($c); + + $a->addChild($d); + $a->addChild($e); + + $b->addChild($f); + + $visitor = new PreOrderVisitor(); + + $expected = [ + $a, + $d, + $e, + ]; + + $this->assertSame($expected, $visitor->visit($a)); + } +} diff --git a/www/wiki/vendor/nicmart/tree/tests/Visitor/YieldVisitorTest.php b/www/wiki/vendor/nicmart/tree/tests/Visitor/YieldVisitorTest.php new file mode 100644 index 00000000..0dca4f6f --- /dev/null +++ b/www/wiki/vendor/nicmart/tree/tests/Visitor/YieldVisitorTest.php @@ -0,0 +1,52 @@ +<?php +/** + * This file is part of Tree + * + * For the full copyright and license information, please view the LICENSE + * file that was distributed with this source code. + * + * @author Nicolò Martini <nicmartnic@gmail.com> + */ + +namespace Tree\Test\Visitor; + +use Tree\Node\Node; +use Tree\Visitor\YieldVisitor; + +class YieldVisitorTest extends \PHPUnit_Framework_TestCase +{ + /** + * root + * / \ + * A B + * / \ + * C D + * | + * E + */ + public function testGetYield() + { + $root = new Node('root'); + $root + ->addChild($a = new Node('A')) + ->addChild($b = new Node('B')); + + $a + ->addChild($c = new Node('C')) + ->addChild($d = new Node('D', [$e = new Node('E')])); + + $visitor = new YieldVisitor(); + + $yield = $root->accept($visitor); + + $this->assertEquals([$c, $e, $b], $yield); + } + + public function testTheYieldOfALeafNodeIsTheNodeItself() + { + $node = new Node('node'); + $visitor = new YieldVisitor; + + $this->assertEquals([$node], $node->accept($visitor)); + } +}
\ No newline at end of file |