Q30299576/AllPaths - TreePaths class

<?php // http://stackoverflow.com/questions/30299576/build-paths-of-all-paths-of-a-tree-structured-array-in-php

/*
 * Tree Node:
 *
 * Array(
 *        "name" => 'Furniture',  // not checked
 *        "slug" => 'furniture',  // optional
 *        "children" => Array( // can be other Tree nodes...
 *                          ),
 *      );
 *
 *  The `children` key is optional, if empty or missing, means it is a `leaf` node
 *
 *  !!! Note: The only array entry checked in here is 'children' !!!
 *
 *  But you will need to overide the default nodeProcessor.
 *
 *  The default `nodeProcessor` uses `name` and `children` only
 */

/*
 * NodeProcessor:
 *   o It is a callable that accepts two parameters
 *     o current path - an array of all the nodes so far in this path
 *     o isTopALeaf   - is the end of the path a 'leaf' node?
 */

/**
 *  Traverse the tree of `nodes`
 *  Generate a list of Paths from Root to every leaf node as an array of `nodes`.
 *  It is a `stack` with the top node being a leaf.
 */
class TreePaths {

    /**
     * The 'current' menu / tree
     *
     * @var array $tree
     */
    private $tree = array();


    /**
     * The Output
     *
     * @var array $allPaths
     */
    private $allPaths = array();

    /**
     * The 'current' stack of nodes in this path
     *
     * This is a 'stack'. The 'path' is all the entries combined.
     *
     * @var array $currentPath
     */
    private $currentPath = array();


    /**
     * The 'callable' to be run for nodes
     *
     * @var callable $nodeProcessor
     */
    private $nodeProcessor = null;


    /**
     * Call All Nodes or Leaf node only
     *
     * @var boolean
     */
    private $callLeafNodesOnly = true;


    /**
     * Build the class but do not run it...
     *
     * Provides a default NodeProcessor if you don't provide one.
     *    o The default processor builds string paths that look like filepaths
     *
     * @param array $tree
     * @param callable $processNode        - optional
     * @param boolean $callLeafNodesOnly  - optional default true
     */
    public function __construct(array $tree,
                                   /* callable */ $processNode = null,
                                   $callLeafNodesOnly = true)
    {
        $this->tree = $tree;
        $this->nodeProcessor = $processNode;
        $this->callLeafNodesOnly = $callLeafNodesOnly;

        // provide a default processor
        if (is_null($this->nodeProcessor)) {
            $this->nodeProcessor = $this->defaultNodeProcessor();
        }
    }

    /**
     * This routine makes this class rather powerful as you can use any callable.
     *
     * @param type $nodeProcessor
     */
    public function setNodeProcessor(/* callable */ $nodeProcessor)
    {
        $this->nodeProcessor = $nodeProcessor;
    }

    /**
     * Return a list of all the paths that were generated by the 'nodeProcessor'
     * @return array
     */
    public function allPaths()
    {
        return $this->allPaths;
    }

    /**
     * The routine that processes one node and recurses as required
     *
     * @param array $node
     * @return void This is all side-effects
     */
    protected function treeWalk($node)
    {
        // always add the node to the currentPath
        array_push($this->currentPath, $node);

        // Always call the node processor and add the path to all paths if required
        $processedPath = $this->callNodeProcessor($this->currentPath,
                                                  $this->isLeafNode($node));
        if (!empty($processedPath)) { // add to all the paths
            $this->allPaths[] = $processedPath;
        }

        // do we recurse?
        if ($this->isLeafNode($node)) { // no we dont...
            array_pop($this->currentPath); // lose leaf node from top of stack
            return; // nothing more to do
        }

        // now process all the children... This will recurse - always
        foreach ($node['children'] as $key => $node) {
            $this->treeWalk($node);
        }
        return; // end of children
    }

    /**
     * Process all the top level nodes.
     *
     * @return void
     */
    public function generate()
    {
        $this->allPaths = array();

        foreach ($this->tree as $key => $node) {
            $this->treeWalk($node);
        }
        return;
    }

    /**
     * End of a path?
     *
     * @param array $node
     * @return boolean
     */
    protected function isLeafNode($node)
    {
        return empty($node['children']);
    }

    /**
     * Are we in the 'middle' of a path?
     *
     * @param array $node
     * @return boolean
     */
    protected function hasChildren($node)
    {
        return !empty($node['children']);
    }


    /**
     * The `callable` to be called.
     *
     * It must accept the two parameters.
     *
     * It can be set after the 'class instance' is created.
     *
     * @param array currentPath to this value
     * @param string nodeType - leaf or children
     *
     * @return mixed if not empty will be added to the paths
     */
    protected function callNodeProcessor(array $currentPath,
                                             $isTopALeaf)
    {

        if ($this->callLeafNodesOnly) {
            if ($isTopALeaf)  {
                return call_user_func($this->nodeProcessor,
                                       $currentPath,
                                       $isTopALeaf);
            }
        }
        else {
            return call_user_func($this->nodeProcessor,
                                   $currentPath,
                                   $isTopALeaf);
        }
    }

    /**
     * If you don't provide a callable to generate paths then this will be used.
     *
     * It generates a string of names separated by '/'. i.e. it looks like a filepath.
     *
     * @return string
     */
    public function defaultNodeProcessor()
    {
        $dnp = function(array $currentPath,
                         $isTopALeaf)  {

                $fullPath = '/';
                foreach($currentPath as $key => $node) {
                    $fullPath .= $node['name'] .'/';
                }
                return rtrim($fullPath, '/');
             };
         return $dnp;
    }
}