Array sorting insanity

Help! I've got a mental block and it's slowly driving me insane. I'm sure the answer is staring me in the face but I just can't see it.

I need to display some values in a tree structure similar to how the old Windows File Manager used to work so each value has an associated parent, so you might have an array that looks something like this:

            [0] => Array
                    [id] => 7
                    [name] => first
                    [parent_id] => 0
          
            [1] => Array
                    [id] => 5
                    [name] => second
                    [parent_id] => 0
          
            [2] => Array
                    [id] => 2
                    [name] => child
                    [parent_id] => 7

Code (markup):

In this case the element named 'child' is the child of the one called first (linked by its parent_id). In order for my funky display to work I need this array of values to be sorted such that the children of a particular element follow it in the array, so the above would become:

            [0] => Array
                    [id] => 7
                    [name] => first
                    [parent_id] => 0
          
            [1] => Array
                    [id] => 2
                    [name] => child
                    [parent_id] => 7
          
            [2] => Array
                    [id] => 5
                    [name] => second
                    [parent_id] => 0

Code (markup):

The real thing is more complex (obviously) because there are multiple levels (child itself will have children that should follow it in the array). So essentially I want to step through the array and say for each element, 'Do you have any children' and if so, drop them into the new array being built at that point. If any of those new insertions have children, they need to be poked in at the same time and so on and so on, potentially endlessly. For this reason I'm considering it may need to built 'backwards'.

I'm not sure I've explained this very well but I'm sure it should be simple, I just can't get my head round it.

If anyone can understand this and can offer any ideas you may well stop me jumping out the window.

Jon

 

There are multiple ways to solve this, although it sounds interesting, i can't code it for you, i just can offer you few hints...

You should simplify your problem and work with only few elements (like you are doing right now )

I would first write function which would sort all elements after their parent_id.

After that you write function which finds all children for given parent_id.

I would then create new array and loop through the first array, adding each element and calling find_children($parent_id) to find and insert it's children.

Working fine? Not exactly, because it considers only the first "layer" of elements. You need to modify find_children($parent_id) function and make it work in recursive fashion.

These would be basic steps how i would proceed, it would probably not work immediatelly, that's why is there a big part of "trial & error" involved

Maybe there are simplier solutions, i hope this was helpful for you. If it doesn't work out and you really need this desperatelly, let me know, maybe i will code it for you, just for a challenge...

 

Hi Hogan, thanks for the reply. Your suggestion is actually what I've kind of come up with myself - I think !

My plan (I haven't tried this yet - I'll tackle it tomorrow) is to first marry up the parent with it's respective children, then group the parents together. I've an image in my head of how this'd work and it'll probably involve unsetting various elements of the source array so it'll be a little like putting together a jigsaw.

As you've identified, the key problem here is not the sort itself but the flexibility to allow any number of 'child' levels so the solution must be able to handle anything from 0 levels (no children for any parent) up to a fairly high number (in practical terms, unlikely to be more than 10).

Thanks for your input - it's one of those problems that's just rattling around in my head and the solution will probably seem easy once it's written but it'll be a lot easier having chatted it over. Thanks again.

Jon

 

$arr_family_tree = array(); // holds relations

foreach($arr_YOUR_ARRAY as $value){
$parent = $value['parent_id']; // get parent
$me = $value['id'] // this id
$arr_family_tree[$parent][$me] = $value['name'];
}


That's the simplest way I can think of at this hour (11:25p) that will give you an organized array with a proper hierarchy. You might have to work a few bugs out of my pseudo-code but you should see where I'm going with it.

Hope that help you get to the next step.

 

Hi itsme (and hogan), thanks for the input. The job's done now and, as I suspected, it wasn't that onerous.

The solution was essentially an iteration on the levels of the hierachy, starting with the lowest level (furthest child) and working backwards. Starting with a 'master' array of all the levels, I reverse this, then use array_shift to split off the last (first) two levels - the furthest children. I then step through the 'parent' of these two, adding the parent values to a third temporary array until the specific parent of the child list is reached, then add all these values, the iteration then continues, adding the remaining parents. Once the parent list is complete, this newly built temporary array is pushed onto the end of the master array and the whole thing repeats.

Eventually, you're left with a single value in the master array - the combined list, in the right order and the loop exits on the test of count.

Maybe not explained very well but it works well and is actually only a few lines of code.

Thanks for the help - it pointed me in the right direction.

Jon