_FileListToArrayRec Incorrect Sorting

[kurtykurtyboy]

I just noticed an issue with _FileListToArrayRec. When used with the $FLTAR_SORT flag, under certain circumstances the resulting array is sorted incorrectly.
The easiest reproducer is a folder named "New folder" along with another folder "New folder 2". It appears to be an issue with matching partial strings instead of the whole filename. Does anyone have any ideas? Maybe I am using it incorrectly. The algorithm works fine when the file/folder names are more unique.

Below is an example that builds a test folder structure to demonstrate the sorting issue. You can see "New folder 2" is shown before "New folder\New folder 1-1". If you change "New folder" and its sub-directories to "New folder 1", all is well and right with the world.

expandcollapse popup

#include <File.au3>
#include <Array.au3>
Example()

Func Example()
    ;create the directory structure
    If FileExists('_FileListToArrayRec-testfolder') Then
        DirRemove('_FileListToArrayRec-testfolder', 1)
    EndIf

    DirCreate('_FileListToArrayRec-testfolder')
    FileWrite("_FileListToArrayRec-testfolder\root file 1.txt", "")
    FileWrite("_FileListToArrayRec-testfolder\root file 2.txt", "")
    DirCreate('_FileListToArrayRec-testfolder\New folder')
    FileWrite("_FileListToArrayRec-testfolder\New folder\test file 1.txt", "")
    FileWrite("_FileListToArrayRec-testfolder\New folder\test file 2.txt", "")
    DirCreate('_FileListToArrayRec-testfolder\New folder\New folder 1-1')
    FileWrite("_FileListToArrayRec-testfolder\New folder\New folder 1-1\test file 5.txt", "")
    DirCreate('_FileListToArrayRec-testfolder\New folder\New folder 1-2')
    FileWrite("_FileListToArrayRec-testfolder\New folder\New folder 1-2\test file 6.txt", "")
    DirCreate('_FileListToArrayRec-testfolder\New folder 2')
    FileWrite("_FileListToArrayRec-testfolder\New folder 2\test file 3.txt", "")
    FileWrite("_FileListToArrayRec-testfolder\New folder 2\test file 4.txt", "")
    DirCreate('_FileListToArrayRec-testfolder\New folder 3')
    DirCreate('_FileListToArrayRec-testfolder\New folder 4')
    DirCreate('_FileListToArrayRec-testfolder\New folder 5')

    Local $aFileList = _FileListToArrayRec("_FileListToArrayRec-testfolder", "*", $FLTAR_FILESFOLDERS, $FLTAR_RECUR, $FLTAR_NOSORT, $FLTAR_RELPATH)
    If @error Then
        ConsoleWrite("Error: " & @error & @CRLF)
    Else
        _ArrayDisplay($aFileList, "files not sorted")
    EndIf

    $aFileList = _FileListToArrayRec("_FileListToArrayRec-testfolder", "*", $FLTAR_FILESFOLDERS, $FLTAR_RECUR, $FLTAR_SORT, $FLTAR_RELPATH)
    If @error Then
        ConsoleWrite("Error: " & @error & @CRLF)
    Else
        _ArrayDisplay($aFileList, "files sorted incorrectly")
    EndIf
EndFunc   ;==>Example

 

[Melba23]

kurtykurtyboy,

The sort is done on ASCII values in the name string. The " " in "New Folder 2" is 0x20 - the "\" in "New folder\" is 0x5c: QED!

Quote

The algorithm works fine when the file/folder names are more unique

Because there is unlikely to be the " " vs "\" conflict. By all means write a better sort algorithm if you wish, but remember that the sorting is the slowest part of the whole recursive listing. Do you really want to make it even slower?

M23

 

[kurtykurtyboy]

Well, this might not be useful to anyone else, but here is my first attempt at a solution for my specific problem. I replaced every comparison in __ArrayDualPivotSort with this custom function in order to keep folders sorted together.
Obviously the speed depends on how many folders there are and how many levels there are in each folder. From my tests, the results were sometimes pretty close to the regular sort, but sometimes up to 2.5x slower

expandcollapse popup

Func __ArrayDualPivotSortByFolder_Compare($sLeft, $sRight, $bGreater = False, $bIncludeEqual = False)
    Local $aLevelsLeft = StringSplit($sLeft, "\")
    Local $aLevelsRight = StringSplit($sRight, "\")
    $iEnd = ($aLevelsLeft[0] < $aLevelsRight[0]) ? $aLevelsLeft[0] : $aLevelsRight[0]
    ;every path starts with "\", so skip element [1]
    For $i = 2 To $iEnd
        If $aLevelsLeft[0] = $i And $aLevelsRight[0] = $i Then
            ;both sides have no more levels
            If $aLevelsLeft[$i] < $aLevelsRight[$i] Then
                Return Not $bGreater
            Else
                If $bIncludeEqual And $aLevelsLeft[$i] = $aLevelsRight[$i] Then
                    Return 1
                Else
                    Return $bGreater
                EndIf
            EndIf
        ElseIf $aLevelsLeft[0] = $i And $aLevelsRight[0] > $i Then
            ;left side no more levels, right side has more
            If $aLevelsLeft[$i] > $aLevelsRight[$i] Then
                Return $bGreater
            Else
                If $bIncludeEqual And $aLevelsLeft[$i] = $aLevelsRight[$i] Then
                    Return 1
                Else
                    Return Not $bGreater
                EndIf
            EndIf
        ElseIf $aLevelsLeft[0] > $i And $aLevelsRight[0] = $i Then
            ;left side has more levels, right side does not
            If $aLevelsLeft[$i] < $aLevelsRight[$i] Then
                Return Not $bGreater
            Else
                If $bIncludeEqual And $aLevelsLeft[$i] = $aLevelsRight[$i] Then
                    Return 1
                Else
                    Return $bGreater
                EndIf
            EndIf
        Else
            ;both have more levels to check
            If $aLevelsLeft[$i] < $aLevelsRight[$i] Then
                Return Not $bGreater
            ElseIf  $aLevelsLeft[$i] > $aLevelsRight[$i] Then
                Return $bGreater
            Else
                If $bIncludeEqual And $aLevelsLeft[$i] = $aLevelsRight[$i] Then
                    Return 1
                Else
                    ContinueLoop
                EndIf
            EndIf
        EndIf
    Next
EndFunc   ;==>__ArrayDualPivotSortByFolder_Compare

Now to see if I can find a more efficient way to do it...

Edited August 18, 2022 by kurtykurtyboy
Fixed error in the function, slightly faster.