Q35484259 - 'TreeWalk' Paths in Array Class

<?php
/**
 *  Interface can be found at:
 */


/*
 * Tree Node:
 *
 * Array(
 *        mixed => mixed
 *      );
 *
 */

/*
 * NodeProcessor:
 *     It is a 'callable' that accepts one parameter
         o An instance of the TreeWalk class

         There are available method that will be useful
 */

/**
 *  Traverse the tree of `nodes` by walking the paths
 *
 *    o Keep a `current path` from Root to the `current node` as an array of `node data`.
 *    o Call the 'nodeProcessor for each node'.
 */

class TreeWalk implements ITreeWalk {

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

    /**
    * Terminate the processing at any node
    *
    * @var boolean $endTreeWalk
    */
    public $endTreeWalk = false;

    /**
    * A reference to the current node so it can be updated
    *
    * @var mixed $currentNode
    */
    public $currentNode = null;

    /**
    * The key of the currentData - readonly
    *
    * @var mixed $currentKey
    */
    public $currentKey = null;

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


    /**
     * Available data to the nodeProcesor
     *
     * @var mixed $processorData
     */
    public $processorData = array();

    /**
     * The Output
     *
     * @var array $processorResults
     */
    public $processorResults = array();


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


    /* internal data */

    private $depth      = 0;

    /**
     * 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  array paths
     *
     * @param array $tree
     * @param callable $processNode        - optional
     * @param processorData                - optional
     */
    public function __construct(array &$tree,
                                /* callable */ $processNode = null,
                                /* mixed    */ $processorData = null)
    {
        if (empty($tree)) {
            throw new \Exception('Empty tree is not very interesting.', 500);
        }

        $this->tree =& $tree;
        $this->nodeProcessor = $processNode;

        $this->processorData = $processorData;

        // provide a default processor
        if (!$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;
    }

    public function setProcessorData($data)
    {
        $this->processorData = $data;
    }

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

    /**
     * Process all the  nodes.
     *
     * @return void
     */
    public function treeWalk($processorData = null)
    {
        if (!is_null($processorData)) {
            $this->processorData = $processData;
        }
        $this->processorResults = array();
        $this->endTreeWalk = false;

        array_push($this->currentPath, array('key' => 'root', 'data' => $this->tree));
        $this->walk('root', $this->tree);
        array_pop($this->currentPath);
        return;
    }


    /**
     * The routine that processes one node and recurses as required
     *
     * @param array $node
     * @return void This is all side-effects
     */
    protected function walk($nodeKey, &$nodeData)
    {
        if ($this->endTreeWalk) { return; } // nothing to do but let the tree unwind

        // now process all the children...
        if (is_array($nodeData) && !empty($nodeData)) { // process the array

            foreach ($nodeData as $key => &$nextData) {
                if ($this->endTreeWalk) { break; } // nothing to do but let the tree unwind

                $this->currentNode =& $nextData;
                $this->currentKey  =  $key;



                if (is_array($nextData) && !empty($nextData)) { // nest one level

                    $this->depth++;
                    array_push($this->currentPath, array('key' => $key, 'data' => $nextData));

                    $this->callNodeProcessor(); // process the node
                    if ($this->endTreeWalk) { break; } // nothing to do but let the tree unwind

                    $this->walk($key, $nextData); // recurse
                    array_pop($this->currentPath);
                    $this->depth--;
                    continue; // all done with this entry
                }

                array_push($this->currentPath, array('key' => $key, 'data' => $nextData));
                $this->callNodeProcessor(); // process the node
                array_pop($this->currentPath); // lose  node from top of stack
            }

            unset($nextData);
            unset($this->currentNode); // remove all reference so if will be garbage collected
        }
        else { // node data will not be an array with values
            if ($this->endTreeWalk) { return; } // nothing to do but let the tree unwind

            $this->currentNode =& $nodeData;
            $this->currentKey  =  $nodeKey;

            array_push($this->currentPath, array('key' => $nodeKey, 'data' => $nodeData));
            $this->callNodeProcessor();
            array_pop($this->currentPath); // lose node from top of stack

            unset($this->currentNode); // remove all reference so it will be garbage collected
        }

        return; // end of children
    }

    /**
     * The `callable` to be called.
     *
     * It must accept one parameter.
     *
     * It can be set after the 'class instance' is created.
     *
     * @param object instance of this class
     *
     * @return mixed if not empty will be added added to the result
     */
    protected function callNodeProcessor()
    {
        $result = call_user_func($this->nodeProcessor,
                                        $this);

        if (!empty($result)) { // add to the result array
            $this->processorResults[] = $result;
        }
        return;
    }

    /**
     * If you don't provide a callable to generate paths then this will be used.
     *
     * It generates a list string paths to all the leaf nodes.
     *
     * It deliberately uses the current node data - it is part of testing really
     *
     * @return string
     */
    public function defaultNodeProcessor()
    {
        $dnp = function (TreeWalk $tree) {

                  if (is_array($tree->currentNode) && !empty($tree->currentNode)) {
                      return ''; // not a leaf node
                  }

                  return $tree->showCurrentPath();
               };

        return $dnp;
    }

    /**
    * show the current path as text  -- it is a little clumsy - hopefully easy to debug :)
    *
    * What if you don't use `foreach` - is it easier to understand? It is for me...
    *
    * Path stucture:
    *   1) root node                                       (required)
    *   2) an iteration of intermediate nodes              (optional) - makes sense
    *   3) end data node                                   (optional) !
    *        - what? yes - what if path is just the root ;-/
    *
    * @return string
    */
    public function showCurrentPath()
    {
        $textPath = ''; // output text path
        $curIdx = 0;    // which entry we are playing with
        $path = $this->currentPath; // simplify the code in here - is readonly so is cheap


        // I need to know which is the last node...
        $lastIndex = count($path) - 1;

        $textPath = $path[$curIdx]['key']; // build the output starting at the root
        $curIdx++;                // start of the path proper

        // use $curIdx - process 'path' nodes but not the last one as that has data
        //               that needs to be treated differently
        for (/* already set */; $curIdx < $lastIndex; $curIdx++ ) {
            $textPath .= '['. $path[$curIdx]['key'] . ']';
        }

        // the last node has various conditions... does it exist?
        if ($curIdx === $lastIndex) { // ok - process the last node

            $textPath .= '['. $path[$curIdx]['key'] . ']'; // key to the data in this node

            $data = $path[$curIdx]['data']; // simplify `data` processing code - no other reason

            if (is_array($data)) {
                if (!empty($data)) {
                        $textPath .= ' -'. 'array' . '- ';
                }
                else {
                    $textPath .= ' -'. 'empty array' . '- ';
                }
            }
            else {
                $textPath .= ' -'. $data . '- ';
            }
        }
        return rtrim($textPath);
    }

  /* ----------------------------------------------------------------------------------------
   * Path routines - worth refactoring to separate class? maybe - not now...
   */

   /**
    * How many items on the path??
    *
    * @return integer
    */
   public function pathDepth()
    {
        return count($this->currentPath);
    }

   /**
    * The key of the item on the path
    *
    * return top of stack as default
    *
    * @param integer $idx
    *
    * @return mixed
    */
    public function pathKey($idx = -1)
    {
        $idx = max(min($this->pathDepth() - 1, $idx), 0); // in range

        if (isset($this->currentPath[$idx])) {
            return $this->currentPath[$idx]['key'];
        }
    }

   /**
    * The data available at that entry in the path
    *
    * return top of stack as default
    *
    * @param integer $idx
    *
    * @return mixed
    */
    public function pathData($idx = -1)
    {
        $idx = max(min($this->pathDepth() - 1, $idx), 0); // in range

        if (isset($this->currentPath[$idx])) {
            return $this->currentPath[$idx]['data'];
        }
        return null;
    }

   /**
    * is the path entry set?
    *
    * @param integer $idx
    *
    * @return boolean
    */
    public function issetPath($idx = -1)
    {
        $idx = max(min($this->pathDepth() - 1, $idx), 0); // in range

        return isset($this->currentPath[$idx]);
    }
}