Recursively iterate through array and create an array based on it's "path"

Question

I'm having a very difficult time figuring out how I can recursively iterate through an array and create an array of it's "path"

I have two arrays. One is an array of a directory tree that looks something like this:

$directoryTree = [

    'accounting' => [

        'documents' => [
        ],

        'losses' => [
        ],

        'profit' => [
        ]               

    ],
    'legal' => [

        'documents' => [
        ]
    ]
];

Another is a list of files that specify which directory "path" the file should reside:

$fileList = [

    [
        'name' => 'Overview.doc',
        'dir_path' => []
    ],

    [
        'name' => 'Incorporation.doc',
        'dir_path' => []
    ],  

    [
        'name' => 'Profit And Loss.xls',
        'dir_path' => ['accounting']
    ],

    [
        'name' => 'Profit 1.xls',
        'dir_path' => ['accounting', 'profit']
    ],

    [
        'name' => 'Loss 1.xls',
        'dir_path' => ['accounting', 'losses']
    ],

    [
        'name' => 'TOS Draft.doc',
        'dir_path' => ['legal', 'documents']
    ]

    [
        'name' => 'Accounting Doc.pdf',
        'dir_path' => ['accounting', 'documents']
    ],      
];

Essentially what I am trying to do is iterate through the $directoryTree and see if there are any elements in the $fileList that has the "path" where the iterator is. If there is the element should be added there.

The final array should look something like this:

$finalOutput = [
    'accounting' => [

        'documents' => [
            'Accounting Doc.pdf'
        ],

        'losses' => [
            'Loss 1.xls'
        ],

        'profit' => [
            'Profit 1.xls'
        ],

        'Profit And Loss.xls'

    ],
    'legal' => [

        'documents' => [
            'TOS Draft.Doc'
        ]
    ],

    'Overview.doc',
    'Incorporation.doc',

];

I'm also including this image just to clarify further:

The attempt I've made haven't really gotten me very far. I keep getting stuck while trying to traverse the array recursively and am not sure how to approach the problem next.

Tail recursion, pass along a variable that keeps the names of the elements previously traversed, and append the next one as you search down. — Keith Tyler, Jul 08 '16 at 00:39
What do you do when a path doesn't exist in your tree? Create it or not adding the file? (Also you probably want to do something like this: https://3v4l.org/Ai9Uh) — Rizier123, Jul 08 '16 at 00:50
There should always be a path. If the path does not exist I will probably want an exception thrown. Please post your solution as an answer so I can accept it after I test it — Zaki Aziz, Jul 08 '16 at 03:02

score 1 · Answer 1 · answered Jul 08 '16 at 06:45

the following code should solve the problem. Consider it pseudocode though. Its really a combination of javascript, java, and words haha.

@stck is an array of strings, keeps track of the path

//function should return an empty $fileList signaling all files have been processed
function treeTraversal($directoryTree, $fileList, stck) {

    //begins by processing all the files that are children of the root directory 
    //e.g. those with dir_name =[]
    //removes them from $fileList so we don't have to keep iterating over them
    if(stck.length == 0) {// == 0 only once, when processing first child of root
        for(var i = 0; i < $fileList.length; i ++) {
            if($fileList[i].dir_name.length == 0) {
                $directoryTree.push($fileList[i]);
                $fileList.removeElementAtIndex(i)
            }
        }
    }

    // now recursively traverse the tree. Record the path in var called stck
    for(var i = 0; i < $directoryTree.length; i++) {
        stck.push($directoryTree[i]); // $directoryTree[i] refers to name of directory not its contents
        if($directoryTree[i] is array)
            $fileList = treeTraversal($directoryTree[i], $fileList, stck);
    for(var j = 0; j < $fileList.length; j++) {
        if($fileList[j].dir_path == stck) {
            $directoryTree.push($fileList[j]);
            $fileList.removeElementAtIndex(j);
        }
    }
    stck.pop();
    return $fileList
}

score 1 · Answer 2 · answered Jul 08 '16 at 07:29

Wouldn't it be easier to iterate through the $fileList and put them in under the right directory array instead? e.g.

$finalOutput = $directoryTree;
foreach ($fileList as $file) {
    $current_dir &= $finalOutput;
    foreach ($file['dir_path'] as $dir) {
        if (isset($current_dir[$dir])) {
            $current_dir &= $current_dir[$dir];
        } else {
            $current_dir = null;
            break;
        }
    }
    if (is_array($current_dir)) {
        $current_dir[] = $file['name'];
    } else {
        // do you want to do anything if dir is not there?
    }
}

Note: I haven't run the code, but should give you an idea how it would work.

If, for some unstated reason, you must iterate through $directoryTree anyway, you should be careful to make sure the logic runs in O(n) (or thereabouts) and not in O(n^2) time. One simple algorithm would be as follows:

run through $fileList and generate a map of all directory -> files
now run through $directoryTree and fill with files from the map

score 0 · Answer 3 · edited May 23 '17 at 12:30

Interesting problem. My answer doesn't actually answer the question in terms of "how to do", but it shows that you need to divide the complex problem into simpler once that can be solved easier, and possibly these small solutions can be reused later.

Basically, you need the ability to set the value for "nested key". I have come across the questions (and faced this myself) about getting a value of "nested key".

So I decided to implement array access class that hides away the recursion and helps to use array-like keys to get nested values. You can check out the repo. The explanation of the code actually fits the domain of the question, but as it is quite long I cannot explain it here. The main point is array access methods hide away the recursion.

Given this class, your problem can be reduced to simple loop over the $fileList:

$directoryTree = new CompositeKeyArray($directoryTree);

foreach ($fileList as $file) {
    if (
        !empty($file['dir_path'])
        && !isset($directoryTree[$file['dir_path']])
    ) {
        throw new Exception;
    }

    array_push($file['dir_path'], []);
    $directoryTree[$file['dir_path']] = $file['name'];
}

var_dump($directoryTree->toArray());

In one of the comments, you have mentioned that you want an exception to be thrown on a non-existent path. The if part handles this.

Here is working demo.

Recursively iterate through array and create an array based on it's "path"

3 Answers3