An implementation of tree data structure
Clone or download

README.md

Latest Stable Version Total Downloads Build Status Scrutinizer Code Quality Code Coverage Mutation testing badge License

PhpTree

Description

A PHP implementation of tree data structure.

5 different trees implementations:

  • Node: The base class.
  • N-ary node: (or K-ary tree) extends the base class and allows you to specify the capacity of a node, the maximum children a node can have.
  • Value node: extends the N-ary node and allows you to attach a value to the node.
  • KeyValue node: extends the Value node and allows you to attach a key and a value to the node.
  • Trie node: extends the KeyValue node, a simple Trie tree.

4 trees traversals algorithm:

  • In order
  • Post order
  • Pre order
  • Breadth first

Exporters and importers:

  • Graph: Export a tree into a graph using the graphp/graphp library.
  • Text: Export a tree into a simple string.
  • Ascii: Export a tree into an ascii graphic.

Modifier:

  • A modifier "Reverse" to reverse a tree.

Documentation

API documentation is automatically generated with APIGen and available at this address.

Blog post: https://not-a-number.io/2018/phptree-a-fast-tree-implementation

Requirements

  • PHP >= 7.1

Installation

composer require drupol/phptree

Optional packages

Usage

<?php

declare(strict_types = 1);

use Graphp\GraphViz\GraphViz;
use drupol\phptree\Exporter\Graph;
use drupol\phptree\Node\ValueNode;
use drupol\phptree\Exporter\Text;

include './vendor/autoload.php';

// Create the root node.
$tree = new ValueNode('root', 2);

$nodes = [];
foreach (\range('A', 'Z') as $v) {
    $nodes[] = new ValueNode($v);
}

// Add children to the root node.
$tree->add(...$nodes);

// Export to an image.
$graphViz = new GraphViz();
$graphExporter = new Graph();
$graphViz->display($graphExporter->export($tree));

// Export to text.
$textExporter = new Text();
echo $textExporter->export($tree); // [root [A [C [G [O] [P]] [H [Q] [R]]] [D [I [S] [T]] [J [U] [V]]]] [B [E [K [W] [X]] [L [Y] [Z]]] [F [M] [N]]]]⏎

Code quality, tests and benchmarks

Every time changes are introduced into the library, Travis CI run the tests and the benchmarks.

The library has tests written with PHPSpec. Feel free to check them out in the spec directory. Run composer phpspec to trigger the tests.

Before each commit some inspections are executed with GrumPHP, run ./vendor/bin/grumphp run to check manually.

PHPBench is used to benchmark the library, to run the benchmarks: composer bench

PHPInfection is used to ensure that your code is properly tested, run composer infection to test your code.

Contributing

Feel free to contribute to this library by sending Github pull requests. I'm quite reactive :-)