Q38278304 - Create a tree - validate nodes

<?php // http://stackoverflow.com/questions/38278304/parse-an-flat-array-to-a-one-that-represents-a-directory-structure

// include __DIR__. '/__bootstrap__.php';

/*
 *  I have added duplicate node to the tree and a completely invalid path
 *
 *
 */
$directoryObjects = [
    [
        'type' => 'file',
        'name' => 'unicorn.jpg',
        'path' => '/',
        'path_array' => []
    ],
    [
        'type' => 'folder',
        'name' => 'animals',
        'path' => '/animals',
        'path_array' => ['animals']
    ],

    [
        'type' => 'folder',
        'name' => 'cat',
        'path' => '/animals/cat',
        'path_array' => ['animals', 'cat']
    ],

    [
        'type' => 'folder',
        'name' => 'images - pretty',
        'path' => '/animals/cat/images',
        'path_array' => ['animals', 'cat', 'images']
    ],

    [
        'type' => 'folder',
        'name' => 'images - some',
        'path' => '/animals/cat/images',
        'path_array' => ['animals', 'cat', 'images']
    ],

    [
        'type' => 'file',
        'name' => 'AtlasX.png',
        'path' => '/animals/cat/images',
        'path_array' => ['animals', 'cat', 'images']
    ],

    [
        'type' => 'file',
        'name' => 'AtlasX.png',
        'path' => '/animals/cat/images',
        'path_array' => ['animals', 'cat', 'images']
    ],
    [
        'type' => 'folder',
        'name' => 'crockery',
        'path' => '/crockery',
        'path_array' => ['crockery']
    ],
    [
        'type' => 'folder',
        'name' => 'cups',
        'path' => '/crockery/cups',
        'path_array' => ['crockery', 'cups']
    ],
    [
        'type' => 'file',
        'name' => 'cup.png',
        'path' => '/crockery/cups',
        'path_array' => ['crockery', 'cups']
    ],
    [
        'type' => 'file',
        'name' => 'crockeryThumb.png',
        'path' => '/crockery',
        'path_array' => ['crockery']
    ],
    [
        'type' => 'folder',
        'name' => 'rubbish',
        'path' => '/rubbish/cat',
        'path_array' => ['rubbish', 'cat']
    ],
    [
        'type' => 'folder',  // will be ignored as I generate one
        'name' => 'root',
        'path' => '/',
        'path_array' => []
    ],
    [
        'type' => 'file',
        'name' => 'rubbishfile.png',
        'path' => '/crockery/foo/bar',
        'path_array' => ['crockery', 'foo', 'bar']
    ],
    [
        'type' => 'file',
        'name' => 'rubbishAgain.png',
        'path' => '/foo/bar/baz',
        'path_array' => ['foo', 'bar', 'baz']
    ],
];



echo '<pre> ', 'Before...', PHP_EOL;
echo 'Directories', PHP_EOL;


/* -----------------------------------------------------------------------------------------------------
 *  Run the code...
 */
$bt = new BuildTree($directoryObjects);

echo '<pre>';
echo 'Sorted Directories', PHP_EOL;
print_r($bt->directories);
echo '</pre>';


$allOk = $bt->buildTree();

echo '<pre>';
echo 'Json', PHP_EOL;
print_r($bt->getJsonTree());
echo '</pre>';


echo '<pre>';
echo 'Errors', PHP_EOL;
foreach ($bt->errors as $result) {
    $bt->printResult($result);
}
echo '</pre>';

echo 'Tree', PHP_EOL;
echo '<pre>';
print_r($bt->tree);
echo '</pre>';



exit;

/* -------------------------------------------------------------------------------------------------------
 * Build the tree folders first
 *
 * a) I am concerned about efficiency on trees with large numbers of files.
 *    To deal with this i keep a list of folder nodes so the file insert will be efficient.
 *
 * b) I am concerned about folder errors such as duplicates or invalid paths so I have attempted to deal with these.
 *
 * c) The root node is optional in the source data. It just creates one.
 *
 * To simplify the tree building logic I will sort the array into some useful order for me.
 *
 * Specifically:
 *
 *   1) Folders
 *      a) path length order
 *
 *   2) Files
 *      b) Path length order
 *
 *   This will make the tree building easier but the cost is a sort plus the cost of the building the tree
 *
 *
 */

class BuildTree
{
    /**
     *  The source data
     *
     *  @var array
     */
    private $directories = array();

    /**
    * References to the folders in the directory list.
    * Makes adding files a lot more efficient
    *
    * @var array
    */
    private $nodeRefs = array();

    /**
    * Invalid nodes - there is am error message as to why it failed
    *
    * @var array
    */
    private $errors = array();

    /**
    * The tree - all the nodes are references rather than copies of the data
    *
    * @var array
    */
    private $tree = null;

    /**
    * The root node to make the tree complete
    *
    * @var array
    */
    private $rootNode = array(
                        'type' => 'folder',
                        'name' => 'root',
                        'path' => '/',
                        'path_array' => array(),
                        'children' => array(),
                        );

    /**
    * The start index of the first file in the sorted input
    *
    * @var integer
    */
    private $firstFile = -1;


    /**
    * Sort the directory input in folders by length and then files
    *
    * @param array $directories
    *
    * @return void
    */
    public function __construct($directories)
    {

        $this->sort($directories);
        $this->directories = $directories;
        $this->tree = &$this->rootNode; // make the tree a 'complete tree' - simplifies the addNode logic
    }

    /**
    * Just executes the:
    *   1) the process folders (build the tree of directory nodes
    *   2) adds the files to the correct nodes
    *
    * @return boolean eorros or not
    */
    public function buildTree()
    {
        $this->buildFolderTree();
        $this->addFiles();
        return count($this->errors) <= 0;
    }


   /**
    * All the folders are at the top of the directories list
    *
    * Read through the list and add all the folders into the tree
    *
    * Foreach folder:
    *   1) Find the parent
    *   2) if valid add to the tree
    *   3) record the reference to it so we can add files easily later
    *
    * @return void
    */
    public function buildFolderTree()
    {
        // add rootnode to the list
        $this->nodeRefs[$this->tree['path']] =& $this->tree;

        foreach ($this->directories as $idx => &$node) {

            if ($node['type'] !== 'folder') { // record the index of the first file
                $this->firstFile = $idx; // needed for processing the files efficiently
                break;
            }

            if (empty($node['path_array'])) { // you passed a root anyway - ignore it ;-/
                continue;
            }

            $node['children'] = array();  // needed for adding nodes to the tree
            $result = $this->findParent($node, $this->tree);

            if ($result['isError'] || !$result['isParent']) { // ignore as invalid...
                $this->errors[] = $result;
                continue;
            }

            // add to the tree as a reference...

            $parent =& $result['treeNode'];
            $parent['children'][] =& $this->directories[$idx]; // reference to the original node

            // fast lookup later... when we add files
            $this->nodeRefs[$node['path']] =& $node;
        }
        unset($node); // magic - 'cos we used a reference in a foreach loop.
    }


    /**
    * This does not need to do a treewalk to find the parent.
    *
    * All the parents are in the $nodeRefs array with a key of the `path`
    *
    * This makes inserting the files quick
    *
    * @return void
    */
    public function addFiles()
    {
        foreach (array_slice($this->directories, $this->firstFile) as $idx => $file)  {

            if (isset($this->nodeRefs[$file['path']])) { // add to the children

                $this->nodeRefs[$file['path']]['children'][] = $file;
            }
            else { // make an error and add to the reject pile.
                $result =  array('isError'      => false,
                                 'isParent'     => false,
                                 'treeNode'     => null,
                                 'node'         => $file,
                                 'message'      => 'invalid folder path');
                $this->errors[] = $result;
            }
        }
    }

    /**
    * Get as close to the folder as you can
    *
    * Return the node as a reference as we want to update it in some way
    *
    * 1) folder:
    *
    *    a) You get to the parent where the new folder will be
    *       i.e. treeNode depth is one less than the new node depth
    *
    *    b) the node already exists so nothing to do
    *       i.e. treeNode depth = new node depth
    *
    *    c) there is a node missing from the path - wrong name etc.
    *       i.e. treeNode depth is 2 or more less than the new node depth
    *
    *     *
    * @param array $node
    * @param array $treeNode
    * @param integer $level
    *
    * @return treeNode
    */
    public function findParent(&$node, &$treeNode, $level = 0)
    {
        $nodePathLength      = count($node['path_array']);  // keep track of these for now to ease debugging

        $treeNodeParentLevel = $nodePathLength - 1;         // the tree must match to here the tree node to be a parent
                                                            // i.e. less or more than this and the node is an error

        $treeNodePathLength = count($treeNode['path_array']); // this must be one less for it to be a true parent



        // All the useful information you need about the parent and it's possible child
        $result =  array('isError'      => false,
                         'isParent'     => false,
                         'treeNode'     => &$treeNode,
                         'node'         => &$node,
                         'message'      => '');

        // these are always correct by definition
        if ($nodePathLength <= 1) { // the root is always the parent of the first level
            $result['isParent']    = true;
            $result['message']     = 'root or first child';
            return $result;
        }


        if ($level > $treeNodeParentLevel) { // this path already exists in the tree
            $result['isError']     = true;
            $result['isParent']    = false;
            $result['message']     = 'duplicate';
            return $result;
        }

        // we are looking for this in the current treeNode Children
        $nodeDir      = $node['path_array'][$level];


        foreach ($treeNode['children'] as $idx => &$tnode) {

            $tnodeDir  = $tnode['path_array'][$level];

            if ($nodeDir === $tnodeDir) { // match at this level - check the next one

                return $this->findParent($node, $tnode, $level + 1);
            }
        }
        unset($tnode); // do this when using references in foreach loops


        // can only get to here if the current nodeDir was not found in the children
        if ($level == $treeNodeParentLevel) {

            $result['isParent']    = true;
            $result['message']     = 'matched path';
        }
        else { // someone has gotten really confused...

            $result['isError']  = true;
            $result['message'] = 'i am confused';
        }

        return $result;
    }



    /**
    * Sort folders to the top in increasing path length
    *      then files in increasing path length
    *
    * @return void
    */
    public function sort(&$directories)
    {
        usort($directories,  function ($node1, $node2) {
                                if ($node1['type'] === $node2['type']) { // same type - check path length
                                    $n1pl = count($node1['path_array']);
                                    $n2pl = count($node2['path_array']);

                                    if ($n1pl > $n2pl) { // higher counts sort after
                                        return +1;
                                    }
                                    if ($n1pl < $n2pl) { // lower counts sort earlier
                                        return -1;
                                    }
                                    return $node1['path'] < $node2['path']   ? -1 : +1; // lower name - sort earlier
                                }

                                return $node1['type'] === 'folder' ? -1 : +1; // folders sort before files
                            });
    }


    public function getErrors()
    {
        return $this->errors;
    }


    public function getTree()
    {
        return $this->tree['children'];
    }


    public function getJsonTree()
    {
        return json_encode($this->getTree());
    }

    // get any of the properties directly if you wish
    public function __get($name)
    {
        return $this->$name;
    }

    // Cheap and cheerful disply of the errors
    public function printResult($result)
    {
        $node = $result['node'];
        echo PHP_EOL, '---------', PHP_EOL;
        echo 'type       =>', $node['type'], PHP_EOL;
        echo 'name       =>', $node['name'], PHP_EOL;
        echo 'path       =>', $node['path'], PHP_EOL;
        echo 'message   =>', $result['message'], PHP_EOL;

        if (!empty($node['path_array'])) {
            echo 'path_array =>', implode(', ', $node['path_array']), PHP_EOL;
        }

        if (isset($node['children']) && count($node['children'])> 0) {
            echo 'children count => ', count($node['children']), PHP_EOL;
        };
    }
}