Zaki Aziz
Reputation: 3852
Parse an "flat" array to a one that represents a directory structure
I have a list of "directory objects" that look something like this:
$directoryObjects = [
[
'type' => 'folder',
'name' => 'animals',
'path' => '/animals',
'path_array' => ['animals']
],
[
'type' => 'folder',
'name' => 'cat',
'path' => '/animals/cat',
'path_array' => ['animals', 'cat']
],
[
'type' => 'folder',
'name' => 'images',
'path' => '/animals/cat/images',
'path_array' => ['animals', 'cat', 'images']
],
[
'type' => 'file',
'name' => 'cat001.png',
'path' => '/animals/cat/images',
'path_array' => ['animals', 'cat', 'images']
],
[
'type' => 'file',
'name' => 'cat002.png',
'path' => '/animals/cat/images',
'path_array' => ['animals', 'cat', 'images']
]
];
This is outputted by my SQL database but it has to be formatted in my API responseas a tree structure. I've decided the best way to represent this tree structure is outlined in the question of this thread: Convert a directory structure in the filesystem to JSON with Node.js. Doing a print_r(json_decode($jsonTreeStructure)) outputs this:
Array
(
[0] => stdClass Object
(
[type] => folder
[name] => animals
[path] => /animals
[children] => Array
(
[0] => stdClass Object
(
[type] => folder
[name] => cat
[path] => /animals/cat
[children] => Array
(
[0] => stdClass Object
(
[type] => folder
[name] => images
[path] => /animals/cat/images
[children] => Array
(
[0] => stdClass Object
(
[type] => file
[name] => cat001.jpg
[path] => /animals/cat/images/cat001.jpg
)
[1] => stdClass Object
(
[type] => file
[name] => cat001.jpg
[path] => /animals/cat/images/cat002.jpg
)
)
)
)
)
)
)
)
I'd like my $directoryObjects to be formatted to the output above. When I do a json_encode($output) it should output in the format shown in the thread linked above
[
{
type: "folder",
name: "animals",
path: "/animals",
children: [
{
type: "folder",
name: "cat",
path: "/animals/cat",
children: [
{
type: "folder",
name: "images",
path: "/animals/cat/images",
children: [
{
type: "file",
name: "cat001.jpg",
path: "/animals/cat/images/cat001.jpg"
}, {
type: "file",
name: "cat001.jpg",
path: "/animals/cat/images/cat002.jpg"
}
]
}
]
}
]
}
];
I'm having a hard time getting off the ground. I'm embarrassed to post what I have done so far, but this is it:
$jsonDir = [];
foreach($directoryObjects as $i => $dirObj)
{
$cur = &$jsonDir;
foreach ($dirObj['path_array'] as $i => $dirName)
{
$cur = &$jsonDir[$i];
}
$cur[] = $dirObj;
}
I'm having a difficult time getting to a child node and appending $dirObjthe correct place.
Upvotes: 1
Views: 728
Answers (2)
Ryan Vincent
Reputation: 4513
This is a tree walk. However, I realised that it would be slow for large lists of files. And, what about invalid paths? The end result of trying to address these issues is provided here.
Demonstration of the code and data at eval.in
The code is documented to explain why and how it goes about doing things. Some of it is 'clumsy'. i.e. the FindParent as it has to recognize errors.
Explanation:
The issues:
1) There are no array keys, based on the data, used in the output tree. This means all the tree has to searched to find any particular parent. I suspect it could get slow for large trees. I thought it was worthwhile doing extra work to avoid that.
2) I wondered how much extra complexity there would be to identify trying to identify invalid nodes being added to the tree.
Folders:
- Build the tree of folders first - recursively
Ok, need to ensure the folders are in the correct order and are first in the list.
sort the directories so that folders are first and sorted by path length.
Add the folders to the tree.
For each folder:
find the parent node - return an error if one cannot be found.
Add it to the tree and add it to a separate array (
$nodeRefs) using the path as the array key. This is useful as we can find the parent of a file quickly later.invalid parents get added to an
$errorsarray for reporting later.
Files:
These are sorted as well but it actually isn't that important as we can find the parent quickly by using the 'path' as the key to lookup the parent in $nodeRefs.
Any files not found in $nodeRefs must be errors.
The BuildTree Class:
/* -------------------------------------------------------------------------------------------------------
* 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;
};
}
}
Run the code:
$bt = new BuildTree($directoryObjects);
$allOk = $bt->buildTree();
$json = $bt->getJsonTree();
To see the tree and errors:
print_r($bt->tree);
foreach ($bt->errors as $result) {
$bt->printResult($result);
}
Sample errors
Errors
---------
type =>folder
name =>rubbish
path =>/rubbish/cat
message =>i am confused
path_array =>rubbish, cat
---------
type =>folder
name =>images - some
path =>/animals/cat/images
message =>duplicate
path_array =>animals, cat, images
---------
type =>file
name =>rubbishfile.png
path =>/crockery/foo/bar
message =>invalid folder path
path_array =>crockery, foo, bar
---------
type =>file
name =>rubbishAgain.png
path =>/foo/bar/baz
message =>invalid folder path
path_array =>foo, bar, baz
Sample tree:
Array
(
[type] => folder
[name] => root
[path] => /
[path_array] => Array
(
)
[children] => Array
(
[0] => Array
(
[type] => folder
[name] => animals
[path] => /animals
[path_array] => Array
(
[0] => animals
)
[children] => Array
(
[0] => Array
(
[type] => folder
[name] => cat
[path] => /animals/cat
[path_array] => Array
(
[0] => animals
[1] => cat
)
[children] => Array
(
[0] => Array
(
[type] => folder
[name] => images - pretty
[path] => /animals/cat/images
[path_array] => Array
(
[0] => animals
[1] => cat
[2] => images
)
[children] => Array
(
[0] => Array
(
[type] => file
[name] => AtlasX.png
[path] => /animals/cat/images
[path_array] => Array
(
[0] => animals
[1] => cat
[2] => images
)
)
[1] => Array
(
[type] => file
[name] => AtlasX.png
[path] => /animals/cat/images
[path_array] => Array
(
[0] => animals
[1] => cat
[2] => images
)
)
)
)
)
)
)
)
[1] => Array
(
[type] => folder
[name] => crockery
[path] => /crockery
[path_array] => Array
(
[0] => crockery
)
[children] => Array
(
[0] => Array
(
[type] => folder
[name] => cups
[path] => /crockery/cups
[path_array] => Array
(
[0] => crockery
[1] => cups
)
[children] => Array
(
[0] => Array
(
[type] => file
[name] => cup.png
[path] => /crockery/cups
[path_array] => Array
(
[0] => crockery
[1] => cups
)
)
)
)
[1] => Array
(
[type] => file
[name] => crockeryThumb.png
[path] => /crockery
[path_array] => Array
(
[0] => crockery
)
)
)
)
[2] => Array
(
[type] => file
[name] => unicorn.jpg
[path] => /
[path_array] => Array
(
)
)
)
)
Test Data- including errors
$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']
],
];
Upvotes: 1
Edu
Reputation: 2520
I like your question and I'd time to code something... but this assumes that your array of directories are ordered by path from top to bottom
<?php
$directoriesArray = [
[
'type' => 'folder',
'name' => 'animals',
'path' => '/animals',
'path_array' => ['animals']
],
[
'type' => 'folder',
'name' => 'cat',
'path' => '/animals/cat',
'path_array' => ['animals', 'cat']
],
[
'type' => 'folder',
'name' => 'images',
'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']
]
];
class fileObj
{
public $type;
public $name;
public $path;
public function __construct( array $directoryArray )
{
$this->name = $directoryArray['name'];
$this->type = $directoryArray['type'];
$this->path = $directoryArray['path'];
}
}
class directoryObj
{
public $type;
public $name;
public $path;
public $children = array();
public function __construct( array $directoryArray )
{
$this->name = $directoryArray['name'];
$this->type = $directoryArray['type'];
$this->path = $directoryArray['path'];
}
public function addChild( $child, $directory = null ){
if( !count($this->children) ){
$this->createAndAddToChildren($child);
return;
}
$sameChild = array_filter(
$this->children,
function( $savedChild ) use ( $child ){
switch($savedChild->type){
case 'folder':
return array_search($savedChild->name, $child['path_array']) !== false;
break;
case 'file':
return $savedChild->name == $child['name'] ;
break;
}
}
);
if(count($sameChild)){
$myChild = array_shift($sameChild);
if( $myChild->type == 'folder' ){
$myChild->addChild($child);
}
}
else{
$this->createAndAddToChildren($child);
}
}
private function createAndAddToChildren($child){
switch($child['type']){
case 'folder':
echo 'addedDirectory <br/>';
$this->children[] = new directoryObj($child);
break;
case 'file':
echo 'addedFile <br/>';
$this->children[] = new fileObj($child);
break;
}
}
}
$mainDirectory = new directoryObj(array_shift($directoriesArray));
foreach( $directoriesArray as $directoryArray ){
$mainDirectory->addChild($directoryArray);
}
Hope this help :-)
Good luck
Upvotes: 1
Related Questions
- Array of file objects to tree structure
- Build directory tree from flat array of paths in PHP
- PHP create json file tree structure from flat array
- How to build a array that contains a folder structure?
- Json array in php as a tree format
- Tree(or hierarchy) array to two dimensional structured array in php
- PHP: Convert an array with a path attribute to a tree structure
- Convert PHP array to JSON tree
- Parse Directory Structure (Strings) to JSON using PHP
- Converting array to a tree-like JSON structure