How to sort data with an unlimited hierarchy?

[amonkey]

The below code will sort the provided data into a hierarchy… Only 4 levels deep. What logic would I need to use to sort data an unlimited number of levels.

expandcollapse popup

#include <Array.au3>
Local $array[10][03] = [["01", "Cat01", "0"],["02", "Cat02", "01"],["03", "Cat03", "0"],["04", "Cat04", "03"],["05", "Cat05", "01"],["06", "Cat06", "05"],["07", "Cat07", "01"],["08", "Cat08", "06"],["09", "Cat09", "04"],["010", "Cat010", "08"]]
Local $icount
Local $arraysort[1]
For $a = 0 To UBound($array) - 1
If $array[$a][2] = '0' Then
$icount += 1
_ArrayInsert($arraysort, $icount, $array[$a][1])
$array[$a][2] = ""
For $b = 0 To UBound($array) - 1
If $array[$b][2] = $array[$a][0] Then
$icount += 1
_ArrayInsert($arraysort, $icount, "- " & $array[$b][1])
$array[$b][2] = ""
For $c = 1 To UBound($array) - 1
     If $array[$c][2] = $array[$b][0] Then
     $icount += 1
     _ArrayInsert($arraysort, $icount, "- - " & $array[$c][1])
     $array[$c][2] = ""
     For $d = 1 To UBound($array) - 1
     If $array[$d][2] = $array[$c][0] Then
     $icount += 1
     _ArrayInsert($arraysort, $icount, "- - - " & $array[$d][1])
     $array[$d][2] = ""
     For $e = 1 To UBound($array) - 1
         If $array[$e][2] = $array[$d][0] Then
         $icount += 1
         _ArrayInsert($arraysort, $icount, "- - - - " & $array[$e][1])
         $array[$e][2] = ""
         EndIf
     Next
     EndIf
     Next
     EndIf
Next
EndIf
Next
EndIf
Next
_ArrayDisplay($arraysort, "$arraysort")

Edited October 28, 2012 by amonkey

[Melba23]

amonkey,

Welcome to the AutoIt forum.

And a complicated little question to start with.

A few questions:

- I take it the third element of each section is the parent under which the element should be placed?

- Do you want the array format you have now for the output - i.e. with simple dashes to indicate the level?

- How do you generate the intial array? There might be scope to do something there to simplify the problem when it comes to the later sorting.

I wil take a look now but some early answers might prevent a lot of nugatory work.

M23

[czardas]

I'm not exactly clear what this is meant to do. However, after a cursory glance at the code, I think this is a job for a recursive function (calling itself from within itself). This will allow unlimited levels (restricted only by available memory)

[Melba23]

amonkey,

That was easier than I thought it would be. Here is a script to order your array as you wish - it should work on unlimited levels:

expandcollapse popup

#include <Array.au3>

Global $aArray[10][3] = [["01", "Cat01", "0"], ["02", "Cat02", "01"], ["03", "Cat03", "0"], ["04", "Cat04", "03"], ["05", "Cat05", "01"], _
                         ["06", "Cat06", "05"], ["07", "Cat07", "01"], ["08", "Cat08", "06"], ["09", "Cat09", "04"], ["010", "Cat010", "08"]]

;Create an array to hold the sorted data - we already know the size
Global $iCount = UBound($aArray)
Global $aSorted_Array[$iCount]

; Now we start a function to run through the array - initially looking for base level entries which will be at level 0
_Find_Level("0", 0, $aSorted_Array)

; And this is what we get when we return
_ArrayDisplay($aSorted_Array)

Func _Find_Level($sParent, $iLevel, ByRef $aSorted_Array)

    ; This is the index of the array we will load next
    Static $iLoad_Index = 0

    ; Look for entries that have this parent
    For $i = 0 To $iCount - 1
        If $aArray[$i][2] = $sParent Then
            ; Found an entry with the correct parent
            ; Add the required number of "-"
            $sItem = $aArray[$i][1]
            For $j = 1 To $iLevel
                $sItem = "-" & $sItem
            Next
            ; And load int into the array - increasing the load index
            $aSorted_Array[$iLoad_Index] = $sItem
            $iLoad_Index += 1
            ; Now run the function again look for any items that have this item as parent
            _Find_Level($aArray[$i][0], $iLevel + 1, $aSorted_Array)
        EndIf
    Next

EndFunc   ;==>_Find_Level

As czardas mentioned above the function is used recursively - if you are not used to doing this, may I recommend reading the Recursion tutorial in the Wiki to find out more.

You will also notice that I sized the array before we started. Changing the size of an array (which is what you were doing with _ArrayInsert) uses ReDim which is amazingly slow. So avoiding that function should be done at all costs. You will see that I just kept track of where the next entry should be inserted.

Please ask if you have any questions.

M23

[amonkey]

Thank you for this. Implemented and working flawlessly. It is much appreciated!

I did not know about recursive functions. After reading the wiki, I believe I have a grasp around how they operate.

Also, thank you for the information about ReDim being slow.

[Melba23]

amonkey,

Delighted that I could help and that the script works so well.

M23

[Thopaga]

Very nice Melba23, you're a genious.

If someone wants a little more functionality you could try this script:

Thanks.