Jump to content

_FileListToArrayRec Incorrect Sorting


Recommended Posts

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.

#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

 

Link to post
Share on other sites
  • Moderators

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

 

Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see my UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Link to post
Share on other sites
Posted (edited)

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

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 by kurtykurtyboy
Fixed error in the function, slightly faster.
Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...