Jump to content

Sort question in C++


Go to solution Solved by Danyfirex,

Recommended Posts

 

@jugadorI optimized the Jscript code, now it's much faster. These are the timers applied to your computer :
*  10.000 elements should take less than 1s to be sorted on your computer.
* 100.000 elements should take less than 10s, you'll tell us ok ?

Here is the reworked code :

#cs
#include <Array.au3>
Opt("MustDeclareVars", 1)

__Example1()
Func __Example1()
    Local $arry[] = [6, 4, 1, 5, 3, 2]
    _ArrayDisplay($arry, "UNsorted")
    Local $x_Result = __ArraySortJs($arry, 0, True, True) ; col 0, numeric (True), ascending (True)
    _ArrayDisplay($x_Result, "sorted")

    Local $arry[] = ['D0','F0','A0','E0','C0','B0']
    _ArrayDisplay($arry, "UNsorted")
    $x_Result = __ArraySortJs($arry, 0, False, False) ; col 0, string, descending
    _ArrayDisplay($x_Result, "sorted")

    Local $arry[][] = [['D0',6,'DD2'],['F0',4,'FF2'],['A0',1,'A2'],['E0',5,'E2'],['C0',3,'C2'],['B0',2,'B2']]
    Local $iCol_Sort = 2
    _ArrayDisplay($arry, "UNsorted (col " & $iCol_Sort & ")")
    Local $x_Result = __ArraySortJs($arry, $iCol_Sort, False, True) ; col $iCol_Sort, string, ascending
    _ArrayDisplay($x_Result, "sorted (col " & $iCol_Sort & ")")
EndFunc
#ce



#include <Array.au3>
#include "RandomArray.au3" ; LarsJ
Opt("MustDeclareVars", 1)

Global $g_iRows = 10000, $g_iCols = 6, $g_aArray

__Example2()
Func __Example2()
    _Generate_All($g_aArray)
    _ArrayDisplay($g_aArray, "UNsorted", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*")
    Local $hTimer2 = TimerInit()
    Local $iCol_Sort = 0
    Local $x_Result2 = __ArraySortJs($g_aArray, $iCol_Sort, False, True) ; col $iCol_Sort, numeric (True), ascending (True)
    If @error Then Exit Msgbox(0, "__ArraySortJs", "error " & @error)
    ConsoleWrite("JScript: sorted in = " & Int(TimerDiff($htimer2)) & " ms" & @crlf)
    _ArrayDisplay($x_Result2, "sorted (col " & $iCol_Sort & ")", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*")
EndFunc

;===========================================
Func _Generate_All(ByRef $g_aArray) ; LarsJ
  ConsoleWrite("$g_iRows = " & $g_iRows & "    $g_iCols = " & $g_iCols & @CRLF)
  $g_aArray = FAS_Random2DArrayAu3($g_iRows, "sifdtr", "abcdefghijklmnopqrstuvwxyz")
EndFunc   ;==>_Generate_All




; #FUNCTION# =============================================================================
; Name...........: __ArraySortJs
; ========================================================================================
Func __ArraySortJs($o_array, $o_Column = 0, $o_Numeric = True, $o_ascending = True)
    ;====
    If Not IsArray($o_array) Then Return SetError(1, 0, -1)
    Local $iNb_Cols = Ubound($o_array, 2)
    If ($iNb_Cols = 1) And ($o_Column > 0) Then Return SetError(1, 0, -1)
    If ($iNb_Cols > 1) And ($o_Column > $iNb_Cols - 1) Then Return SetError(1, 0, -1)
    ;====

    ;====
    Local $o_CBlock = _
    'function GetArray(arr){' & @CRLF & _
        'var oArray = new VBArray(arr)' & @CRLF & _
        'return oArray.toArray()' & @CRLF & _
    '}' & @CRLF & _
    'function NumSort1D(a, b){' & @CRLF & _
        'return a - b' & @CRLF & _
    '}' & @CRLF & _
    'function NumSort2D(a, b){' & @CRLF & _
        'return a[0] - b[0]' & @CRLF & _        ; always [0] +++
    '}' & @CRLF & _
    'function StringSort1D(a, b){' & @CRLF & _
        'if (a === b) {' & @CRLF & _
            'return 0' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return (a < b) ? -1 : 1' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function StringSort2D(a, b){' & @CRLF & _
        'if (a[0] === b[0]) {' & @CRLF & _      ; always [0] +++
            'return 0' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return (a[0] < b[0]) ? -1 : 1' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function ArraySorting1D(arr, oNumeric, oascending){' & @CRLF & _
        'var JsArray = GetArray(arr)' & @CRLF & _
        'if (oNumeric) {' & @CRLF & _
            'JsArray.sort(NumSort1D)' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'JsArray.sort(StringSort1D)' & @CRLF & _
        '}' & @CRLF & _
        'if (oascending) {' & @CRLF & _
            'return JsArray.toString()' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return JsArray.reverse().toString()' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function ArraySorting2D(arr, oNumeric, oascending){' & @CRLF & _
        'var JsArray = GetArray(arr)' & @CRLF & _
        'var JsArr2 = []' & @CRLF & _
        'for (var i=0; i<JsArray.length; i++) {' & @CRLF & _
            'JsArr2[i] = []' & @CRLF & _
            'JsArr2[i][0] = JsArray[i]' & @CRLF & _
            'JsArr2[i][1] = i' & @CRLF & _
        '}' & @CRLF & _
        'if (oNumeric) {' & @CRLF & _
            'JsArr2.sort(NumSort2D)' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'JsArr2.sort(StringSort2D)' & @CRLF & _
        '}' & @CRLF & _
        'if (oascending) {' & @CRLF & _
            'return JsArr2.toString()' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return JsArr2.reverse().toString()' & @CRLF & _
        '}' & @CRLF & _
    '}'
    ;====

    ;====
    Local $ObjErr = ObjEvent("AutoIt.Error", "_ErrorHandler")
    Local $o_Obj = 0
    $o_Obj = ObjCreate("ScriptControl")
    $o_Obj.Language = "JScript"
    $o_Obj.AddCode($o_CBlock)
    ;====

    ;====
    If $iNb_Cols = 0 Then ; when original array is 1D
        Local $o_SortData = $o_Obj.run("ArraySorting1D", $o_array, $o_Numeric, $o_ascending)
        $o_Obj = 0
        Local $o_SortArry = StringSplit($o_SortData, ',', 2) ; comma delim. from JsArray.toString()
        Return $o_SortArry
    EndIf
    ;====

     ; original array is 2D from now on
    ;====
    Local $o_ExtColmn[UBound($o_array)] ; 1D array of UNsorted elements
    For $i = 0 To UBound($o_array) - 1
        $o_ExtColmn[$i] = $o_array[$i][$o_Column]
    Next

    Local $o_SortData = $o_Obj.run("ArraySorting2D", $o_ExtColmn, $o_Numeric, $o_ascending)
    $o_Obj = 0
;   ConsoleWrite("$o_SortData = " & $o_SortData & @lf)
    ;====

    ;====
    Local $o_SortArry = StringSplit($o_SortData, ',', 2)  ; 1D array of sorted elements (+ indexes b4 sort)
;   _ArrayDisplay($o_SortArry, "$o_SortArry")       

    Local $o_Index[Ubound($o_array)][$iNb_Cols]           ; empty 2D array to be filled
                                                          
    Local $iRow = -1
    For $i = 0 To Ubound($o_SortArry) - 1 Step 2
        $iRow += 1
        For $j = 0 To $iNb_Cols - 1
            $o_Index[$iRow][$j] = $o_array[$o_SortArry[$i + 1]][$j]
        Next
    Next
    Return $o_Index
    ;====
EndFunc

Func _ErrorHandler($oError)
EndFunc

A little explanation :

1207112416_3phases.png.b02cc34f9875302bba0ee9f8e79897ec.png

The pic in the middle shows the "links" between the unsorted column 2 and the sorted column 2
For example the cell "A2" WAS placed on the 2nd row before it was sorted, so now it's easy to "grab" all the other columns concerning "A2" after it's sorted, then fill the new empty matrix. Same for "B2" (which was on 5th row) etc...

Hope it helps.

Edited by pixelsearch
Just made a simplification in the code and applied it to the concerned posts of precedent page in this thread.
Link to post
Share on other sites

(optimized Jscript code)  Console output:

$g_iRows = 100    $g_iCols = 6
JScript: sorted in = 14 ms

$g_iRows = 1000    $g_iCols = 6
JScript: sorted in = 64 ms

$g_iRows = 10000    $g_iCols = 6
JScript: sorted in = 457 ms

$g_iRows = 100000    $g_iCols = 6
JScript: sorted in = 5548 ms

$g_iRows = 200000    $g_iCols = 6
JScript: sorted in = 11805 ms

:) Thanks @pixelsearch

Link to post
Share on other sites

@jugador: there is a potential issue with the JavaScript native separator (comma) used in array.toString() to separate rows, with a fatal error in AutoIt script.

For example, imagine there is a comma in any string of the column to be sorted. Let's change the string element "DD2" to "D,D2" and let's run the preceding script, this will happen :

961799866_issuewithJavaScriptcommadelimiter.png.044e742404303d88409a6d2d77e09507.png

The script exits with Fatal error and Autoscript console shows :

$o_SortData = A2,2,B2,5,C2,4,D,D2,0,E2,3,FF2,1

==> Array variable has incorrect number of subscripts or subscript dimension range exceeded.:
$o_Index[$iRow][$j] = $o_array[$o_SortArry[$i + 1]][$j]
^ ERROR

There is now an extra element in the returned string and the pic above reflects it : 13 elements instead of 12 [i.e. 6*2 pairs]

To avoid this, we could use array.join() instead of array.toString() and choose the separator we want. I think Chr(1) is not a bad choice (it shouldn't be found in usual strings) and JS will again return a string, inserting a Chr(1) at the end of each row of the array. This is a pic of the string returned :

959583258_Chr(1)inAutoItconsole.png.b14bb5ee227b124bee2a71b9b776ce07.png

$o_SortData = A2,2�B2,5�C2,4�D,D2,0�E2,3�FF2,1

Then in AutoIt, we'll do same and use StringSplit with Chr(1), leading to these new pics :

1127147163_JavaScriptChr(1)rowdelimiter.png.c5e7c9c6c5e0112df2012a6cfaea78fe.png

Now the results are correct, but the new pics need explanations :
The commas found in the middle pic (for example "A2,2") seem to be always generated by JS to separate the "columns of our 2D pseudo-Array" though there aren't real 2D arrays in JS (after what I read)

What is important for us is the LAST comma of each row, to catch the old index of the element placed after the last comma, for example :
* "A2,2"   had a row of 2 (after the last comma)
* "D,D2,0" had a row of 0 (after the last comma)

So we'll retrieve the old indexes in a new way, using StringInStr() to determine where is the last comma of each string. Here is the new AutoIt code based on Chr(1) separator :

#cs
#include <Array.au3>
Opt("MustDeclareVars", 1)

__Example1()
Func __Example1()
    Local $arry[] = [6, 4, 1, 5, 3, 2]
    _ArrayDisplay($arry, "UNsorted")
    Local $x_Result = __ArraySortJs($arry, 0, True, True) ; col 0, numeric (True), ascending (True)
    _ArrayDisplay($x_Result, "sorted")

    Local $arry[] = ['D,0','F0','A0','E0','C0','B0']
    _ArrayDisplay($arry, "UNsorted")
    Local $x_Result = __ArraySortJs($arry, 0, False, False) ; col 0, string, descending
    _ArrayDisplay($x_Result, "sorted")

    Local $arry[][] = [['D0',6,'D,D2'],['F0',4,'FF2'],['A0',1,'A2'],['E0',5,'E2'],['C0',3,'C2'],['B0',2,'B2']]
    Local $iCol_Sort = 2
    _ArrayDisplay($arry, "UNsorted (col " & $iCol_Sort & ")")
    Local $x_Result = __ArraySortJs($arry, $iCol_Sort, False, True) ; string, ascending
    _ArrayDisplay($x_Result, "sorted (col " & $iCol_Sort & ")")
EndFunc
#ce



#include <Array.au3>
#include "RandomArray.au3" ; LarsJ
Opt("MustDeclareVars", 1)

Global $g_iRows = 10000, $g_iCols = 6, $g_aArray

__Example2()
Func __Example2()
    _Generate_All($g_aArray)
    _ArrayDisplay($g_aArray, "UNsorted", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*")
    Local $hTimer2 = TimerInit()
    Local $iCol_Sort = 0
    Local $x_Result2 = __ArraySortJs($g_aArray, $iCol_Sort, False, True) ; string (False), ascending (True)
    If @error Then Exit Msgbox(0, "__ArraySortJs", "error " & @error)
    ConsoleWrite("JScript: sorted in = " & Int(TimerDiff($htimer2)) & " ms" & @crlf)
    _ArrayDisplay($x_Result2, "sorted (col " & $iCol_Sort & ")", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*")
EndFunc

;===========================================
Func _Generate_All(ByRef $g_aArray) ; LarsJ
  ConsoleWrite("$g_iRows = " & $g_iRows & "    $g_iCols = " & $g_iCols & @CRLF)
  $g_aArray = FAS_Random2DArrayAu3($g_iRows, "sifdtr", "abcdefghijklmnopqrstuvwxyz")
EndFunc   ;==>_Generate_All



; #FUNCTION# =============================================================================
; Name...........: __ArraySortJs
; ========================================================================================
Func __ArraySortJs($o_array, $o_Column = 0, $o_Numeric = True, $o_ascending = True)
    ;====
    If Not IsArray($o_array) Then Return SetError(1, 0, -1)
    Local $iNb_Cols = Ubound($o_array, 2)
    If ($iNb_Cols = 1) And ($o_Column > 0) Then Return SetError(1, 0, -1)
    If ($iNb_Cols > 1) And ($o_Column > $iNb_Cols - 1) Then Return SetError(1, 0, -1)
    ;====

    ;====
    Local $o_CBlock = _
    'function GetArray(arr){' & @CRLF & _
        'var oArray = new VBArray(arr)' & @CRLF & _
        'return oArray.toArray()' & @CRLF & _
    '}' & @CRLF & _
    'function NumSort1D(a, b){' & @CRLF & _
        'return a - b' & @CRLF & _
    '}' & @CRLF & _
    'function NumSort2D(a, b){' & @CRLF & _
        'return a[0] - b[0]' & @CRLF & _        ; always [0] +++
    '}' & @CRLF & _
    'function StringSort1D(a, b){' & @CRLF & _
        'if (a === b) {' & @CRLF & _
            'return 0' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return (a < b) ? -1 : 1' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function StringSort2D(a, b){' & @CRLF & _
        'if (a[0] === b[0]) {' & @CRLF & _      ; always [0] +++
            'return 0' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return (a[0] < b[0]) ? -1 : 1' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function ArraySorting1D(arr, oNumeric, oascending){' & @CRLF & _
        'var JsArray = GetArray(arr)' & @CRLF & _
        'if (oNumeric) {' & @CRLF & _
            'JsArray.sort(NumSort1D)' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'JsArray.sort(StringSort1D)' & @CRLF & _
        '}' & @CRLF & _
        'if (oascending) {' & @CRLF & _
            'return JsArray.join(String.fromCharCode(1))' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return JsArray.reverse().join(String.fromCharCode(1))' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function ArraySorting2D(arr, oNumeric, oascending){' & @CRLF & _
        'var JsArray = GetArray(arr)' & @CRLF & _
        'var JsArr2 = []' & @CRLF & _
        'for (var i=0; i<JsArray.length; i++) {' & @CRLF & _
            'JsArr2[i] = []' & @CRLF & _
            'JsArr2[i][0] = JsArray[i]' & @CRLF & _
            'JsArr2[i][1] = i' & @CRLF & _
        '}' & @CRLF & _
        'if (oNumeric) {' & @CRLF & _
            'JsArr2.sort(NumSort2D)' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'JsArr2.sort(StringSort2D)' & @CRLF & _
        '}' & @CRLF & _
        'if (oascending) {' & @CRLF & _
            'return JsArr2.join(String.fromCharCode(1))' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return JsArr2.reverse().join(String.fromCharCode(1))' & @CRLF & _
        '}' & @CRLF & _
    '}'
    ;====

    ;====
    Local $ObjErr = ObjEvent("AutoIt.Error", "_ErrorHandler")
    Local $o_Obj = 0
    $o_Obj = ObjCreate("ScriptControl")
    $o_Obj.Language = "JScript"
    $o_Obj.AddCode($o_CBlock)
    ;====

    ;====
    If $iNb_Cols = 0 Then ; when original array is 1D
        Local $o_SortData = $o_Obj.run("ArraySorting1D", $o_array, $o_Numeric, $o_ascending)
        $o_Obj = 0
        Local $o_SortArry = StringSplit($o_SortData, Chr(1), 2) ; same separator used in JsArray.join()
        Return $o_SortArry
    EndIf
    ;====

     ; original array is 2D from now on
    ;====
    Local $o_ExtColmn[UBound($o_array)] ; 1D array of UNsorted elements
    For $i = 0 To UBound($o_array) - 1
        $o_ExtColmn[$i] = $o_array[$i][$o_Column]
    Next

    Local $o_SortData = $o_Obj.run("ArraySorting2D", $o_ExtColmn, $o_Numeric, $o_ascending)
    $o_Obj = 0
;   ConsoleWrite("$o_SortData = " & $o_SortData & @lf)
    ;====

    ;====
    Local $o_SortArry = StringSplit($o_SortData, Chr(1), 2) ; 1D array of sorted elements (+ indexes b4 sort)
;   _ArrayDisplay($o_SortArry, "$o_SortArry")

    Local $o_Index[Ubound($o_array)][$iNb_Cols]             ; empty 2D array to be filled
    Local $iIndex_Old

    For $i = 0 To Ubound($o_SortArry) - 1
        $iIndex_Old = StringMid($o_SortArry[$i], _
            1 + StringInStr($o_SortArry[$i], ',', 0, -1))   ; search LAST comma (from the right)
        For $j = 0 To $iNb_Cols - 1
            $o_Index[$i][$j] = $o_array[$iIndex_Old][$j]
        Next
    Next
    Return $o_Index
    ;====
EndFunc

Func _ErrorHandler($oError)
EndFunc

Credits : JavaScript Bible 7th Edition (Goodman-Morrison-Novitski-Rayl)
array.toString() page 353 
array.join(separatorString) pages 337-338

Edited by pixelsearch
Link to post
Share on other sites

A second way to do it in JS, maybe simpler :
* If original array is 1D, then we agree that we must use another separator than native JS comma as explained in the preceding post, because Strings of data are returned from JS to AutoIt (in the way the JS script is written), so it's ok to use Chr(1) as separator when 1D

* If original array is 2D, why are we returning from JS the strings of sorted data + their old indexes ? Wouldn't it be better to return ONLY the old indexes, without the sorted data ?

I just did that in the script below. So if we return only numbers (indexes) from JS, there's no problem with the native JS comma delimiter when 2D arrays. But this requires to create a new array while in JS (array named JsArr3 in the script below) and this new array is created only when the original array is 2D :

1203990170_Chr(1)if1D(stringsreturned)commasif2D(indexreturned).png.120c15ab2bf5d17d4a9b403f175c1526.png

AutoIt console :  $o_SortData = 2,5,4,0,3,1

#cs
#include <Array.au3>
Opt("MustDeclareVars", 1)

__Example1()
Func __Example1()
    Local $arry[] = [6, 4, 1, 5, 3, 2]
    _ArrayDisplay($arry, "UNsorted")
    Local $x_Result = __ArraySortJs($arry, 0, True, True) ; col 0, numeric (True), ascending (True)
    _ArrayDisplay($x_Result, "sorted")

    Local $arry[] = ['D,0','F0','A0','E0','C0','B0']
    _ArrayDisplay($arry, "UNsorted")
    Local $x_Result = __ArraySortJs($arry, 0, False, False) ; col 0, string, descending
    _ArrayDisplay($x_Result, "sorted")

    Local $arry[][] = [['D0',6,'D,D2'],['F0',4,'FF2'],['A0',1,'A2'],['E0',5,'E2'],['C0',3,'C2'],['B0',2,'B2']]
    Local $iCol_Sort = 2
    _ArrayDisplay($arry, "UNsorted (col " & $iCol_Sort & ")")
    Local $x_Result = __ArraySortJs($arry, $iCol_Sort, False, True) ; string, ascending
    _ArrayDisplay($x_Result, "sorted (col " & $iCol_Sort & ")")
EndFunc
#ce



#include <Array.au3>
#include "RandomArray.au3" ; LarsJ
Opt("MustDeclareVars", 1)

Global $g_iRows = 10000, $g_iCols = 6, $g_aArray

__Example2()
Func __Example2()
    _Generate_All($g_aArray)
    _ArrayDisplay($g_aArray, "UNsorted", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*")
    Local $hTimer2 = TimerInit()
    Local $iCol_Sort = 0
    Local $x_Result2 = __ArraySortJs($g_aArray, $iCol_Sort, False, True) ; string (False), ascending (True)
    If @error Then Exit Msgbox(0, "__ArraySortJs", "error " & @error)
    ConsoleWrite("JScript: sorted in = " & Int(TimerDiff($htimer2)) & " ms" & @crlf)
    _ArrayDisplay($x_Result2, "sorted (col " & $iCol_Sort & ")", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*")
EndFunc

;===========================================
Func _Generate_All(ByRef $g_aArray) ; LarsJ
  ConsoleWrite("$g_iRows = " & $g_iRows & "    $g_iCols = " & $g_iCols & @CRLF)
  $g_aArray = FAS_Random2DArrayAu3($g_iRows, "sifdtr", "abcdefghijklmnopqrstuvwxyz")
EndFunc   ;==>_Generate_All



; #FUNCTION# =============================================================================
; Name...........: __ArraySortJs
; ========================================================================================
Func __ArraySortJs($o_array, $o_Column = 0, $o_Numeric = True, $o_ascending = True)
    ;====
    If Not IsArray($o_array) Then Return SetError(1, 0, -1)
    Local $iNb_Cols = Ubound($o_array, 2)
    If ($iNb_Cols = 1) And ($o_Column > 0) Then Return SetError(1, 0, -1)
    If ($iNb_Cols > 1) And ($o_Column > $iNb_Cols - 1) Then Return SetError(1, 0, -1)
    ;====

    ;====
    Local $o_CBlock = _
    'function GetArray(arr){' & @CRLF & _
        'var oArray = new VBArray(arr)' & @CRLF & _
        'return oArray.toArray()' & @CRLF & _
    '}' & @CRLF & _
    'function NumSort1D(a, b){' & @CRLF & _
        'return a - b' & @CRLF & _
    '}' & @CRLF & _
    'function NumSort2D(a, b){' & @CRLF & _
        'return a[0] - b[0]' & @CRLF & _        ; always [0] +++
    '}' & @CRLF & _
    'function StringSort1D(a, b){' & @CRLF & _
        'if (a === b) {' & @CRLF & _
            'return 0' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return (a < b) ? -1 : 1' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function StringSort2D(a, b){' & @CRLF & _
        'if (a[0] === b[0]) {' & @CRLF & _      ; always [0] +++
            'return 0' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return (a[0] < b[0]) ? -1 : 1' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function ArraySorting1D(arr, oNumeric, oascending){' & @CRLF & _
        'var JsArray = GetArray(arr)' & @CRLF & _
        'if (oNumeric) {' & @CRLF & _
            'JsArray.sort(NumSort1D)' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'JsArray.sort(StringSort1D)' & @CRLF & _
        '}' & @CRLF & _
        'if (oascending) {' & @CRLF & _
            'return JsArray.join(String.fromCharCode(1))' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return JsArray.reverse().join(String.fromCharCode(1))' & @CRLF & _
        '}' & @CRLF & _
    '}' & @CRLF & _
    'function ArraySorting2D(arr, oNumeric, oascending){' & @CRLF & _
        'var JsArray = GetArray(arr)' & @CRLF & _
        'var JsArr2 = []' & @CRLF & _
        'for (var i=0; i<JsArray.length; i++) {' & @CRLF & _
            'JsArr2[i] = []' & @CRLF & _
            'JsArr2[i][0] = JsArray[i]' & @CRLF & _
            'JsArr2[i][1] = i' & @CRLF & _
        '}' & @CRLF & _
        'if (oNumeric) {' & @CRLF & _
            'JsArr2.sort(NumSort2D)' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'JsArr2.sort(StringSort2D)' & @CRLF & _
        '}' & @CRLF & _
        'var JsArr3 = []' & @CRLF & _
        'for (var i=0; i<JsArray.length; i++) {' & @CRLF & _
            'JsArr3[i] = JsArr2[i][1]' & @CRLF & _
        '}' & @CRLF & _
        'if (oascending) {' & @CRLF & _
            'return JsArr3.toString()' & @CRLF & _
        '}' & @CRLF & _
        'else {' & @CRLF & _
            'return JsArr3.reverse().toString()' & @CRLF & _
        '}' & @CRLF & _
    '}'
    ;====

    ;====
    Local $ObjErr = ObjEvent("AutoIt.Error", "_ErrorHandler")
    Local $o_Obj = 0
    $o_Obj = ObjCreate("ScriptControl")
    $o_Obj.Language = "JScript"
    $o_Obj.AddCode($o_CBlock)
    ;====

    ;====
    If $iNb_Cols = 0 Then ; when original array is 1D
        Local $o_SortData = $o_Obj.run("ArraySorting1D", $o_array, $o_Numeric, $o_ascending)
        $o_Obj = 0
        Local $o_SortArry = StringSplit($o_SortData, Chr(1), 2) ; same separator used in JsArray.join()
        Return $o_SortArry
    EndIf
    ;====

     ; original array is 2D from now on
    ;====
    Local $o_ExtColmn[UBound($o_array)] ; 1D array of UNsorted elements
    For $i = 0 To UBound($o_array) - 1
        $o_ExtColmn[$i] = $o_array[$i][$o_Column]
    Next

    Local $o_SortData = $o_Obj.run("ArraySorting2D", $o_ExtColmn, $o_Numeric, $o_ascending)
    $o_Obj = 0
;   ConsoleWrite("$o_SortData = " & $o_SortData & @lf)
    ;====

    ;====
    Local $o_SortArry = StringSplit($o_SortData, ',', 2)  ; 1D array of indexes BEFORE sort)
;   _ArrayDisplay($o_SortArry, "$o_SortArry")

    Local $o_Index[Ubound($o_array)][$iNb_Cols]           ; empty 2D array to be filled

    For $i = 0 To Ubound($o_SortArry) - 1
        For $j = 0 To $iNb_Cols - 1
            $o_Index[$i][$j] = $o_array[$o_SortArry[$i]][$j]
        Next
    Next
    Return $o_Index
    ;====
EndFunc

Func _ErrorHandler($oError)
EndFunc

I don't know which script runs faster (this one or the preceding one). Anyway, we have more choices now. Returning only indexes from JS, without any additional data, that looks fine too :)

Edited by pixelsearch
Link to post
Share on other sites

@pixelsearch  I am glad that I asked for help :D  learn new things.

(JS with JsArr3 array) Console output:

$g_iRows = 100    $g_iCols = 6
JScript: sorted in = 14 ms

$g_iRows = 1000    $g_iCols = 6
JScript: sorted in = 43 ms

$g_iRows = 10000    $g_iCols = 6
JScript: sorted in = 394 ms

$g_iRows = 100000    $g_iCols = 6
JScript: sorted in = 5026 ms

$g_iRows = 200000    $g_iCols = 6
JScript: sorted in = 10705 ms

so latest script runs faster :)

Link to post
Share on other sites

Hi everybody,
I'm actually working on the following C++ code to quickly sort a column of strings (or numerals) in an AutoIt array. An empty structure declared in the AutoIt calling script is filled by this C++ code. It will contain the indexes of each sorted element position in the array... before the sort. The splitting of sbigdata is done with basic string instructions to separate each element from the other. Separator used in the calling program is Chr(1) . The C instruction strtok has gone because it caused some random memory issues, I probably used it wrong. Now that it's gone I got no more memory issues, speed is the same as when I was using it... and I learned how to use a vector of structs... at least the very basic part :)

#include <algorithm>    // sort
#include <string>       // string
#include <vector>       // vector

// String sort : functions & structure declaration
int sort_alpha (char* sbigdata, int* struct_indexes, char* sdelim, int irows, int isense);

struct struct_alpha {
    std::string data;
    int index; };

bool sort_alpha_asc (const struct_alpha& v1, const struct_alpha& v2) {
    return v1.data < v2.data; }

bool sort_alpha_desc (const struct_alpha& v1, const struct_alpha& v2) {
    return v1.data > v2.data; }


// Num sort : functions & structure declaration
int sort_num (char* sbigdata, int* struct_indexes, char* sdelim, int irows, int isense);

struct struct_num {
    double data;
    int index; };

bool sort_num_asc (const struct_num& v1, const struct_num& v2) {
    return v1.data < v2.data; }

bool sort_num_desc (const struct_num& v1, const struct_num& v2) {
    return v1.data > v2.data; }


// =================================================================================
// dll entry point (function to call depends on itype parameter)
// itype value already checked by calling function "sortall.au3"

extern "C" __declspec(dllexport) int sortall
    (char* sbigdata, int* struct_indexes, char* sdelim, int irows, int isense, int itype)
{
    int iret0 = 0, iret1 = 0;

    if (itype==0)      iret0 = sort_alpha (sbigdata, struct_indexes, sdelim, irows, isense);
    else if (itype==1) iret1 = sort_num   (sbigdata, struct_indexes, sdelim, irows, isense);

    return (iret0 + iret1); // 0 when no error in any function called
}
// =================================================================================


// String sort
int sort_alpha (char* sbigdata, int* struct_indexes, char* sdelim, int irows, int isense)
{
    std::vector<struct_alpha> vect(irows); // irows (and 2 cols from struct_alpha)
    std::string str = sbigdata;
    size_t ifound = 0; size_t ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        vect[i].data = str.substr(ipos, ifound - ipos); // string
        vect[i].index = i; // row (to remember initial index before data sorting)
        ipos = ifound + 1;
    }

    std::sort(vect.begin(), vect.end(), ((isense == 0) ? sort_alpha_asc : sort_alpha_desc));

    for (int i = 0; i < irows; i++)
        *(struct_indexes + i) = vect[i].index; // index of sorted data... before data sorting

    // swap trick to release memory used by the string (str = "" wouldn't release anything)
    std::string("").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<struct_alpha>().swap(vect);

    return 0;
}


// Numeric sort
int sort_num (char* sbigdata, int* struct_indexes, char* sdelim, int irows, int isense)
{
    std::vector<struct_num> vect(irows); // irows (and 2 cols from struct_num)
    std::string str = sbigdata;
    std::string sfound;
    size_t ifound = 0; size_t ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        sfound = str.substr(ipos, ifound - ipos);
        vect[i].data = atof(sfound.c_str()); // convert string to double
                                             // .c_str() for this atof() or compile error
        vect[i].index = i; // row (to remember initial index before data sorting)
        ipos = ifound + 1;
    }

    std::sort(vect.begin(), vect.end(), ((isense == 0) ? sort_num_asc : sort_num_desc));

    for (int i = 0; i < irows; i++)
        *(struct_indexes + i) = vect[i].index; // index of sorted data... before data sorting

    // swap trick to release memory used by the string (str = "" wouldn't release anything)
    std::string("").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<struct_num>().swap(vect);

    return 0;
}

I hope the arguments are passed correctly from sortall() , which is the dll entry point, to the called functions sort_alpha() and sort_num() . No argument is passed by reference because the 5 arguments passed from sortall() are 3 pointers and 2 integers. If you guys think it's not correct, please let me know, thank you.

Next step should be to add, in this same dll, a function for Natural sort... if possible.
Concerning the Natural sort, I found 2 interesting C / C++ codes on the web, one from Martin Pool, the other one from Dave Koelle (reworked by Dirk Jagdmann), we'll see.

Edited by pixelsearch
typo
Link to post
Share on other sites

Hi everybody :)
Here are 2 working AutoIt scripts related to the C++ code of the preceding post :

1) SortAll.au3 : it's an include file with 1 function SortAll() which is called when a script needs a fast sorting.

#include-once

#include "AutoItConstants.au3"
#include "MsgBoxConstants.au3"

;==================================================================
Func SortAll(ByRef $aArray, $iSortCol = 0, $iType = 1, $iSense = 0)

    If $iSortCol = Default Then $iSortCol = 0 ; 1st column = 0
    If $iType = Default Then $iType = 1 ; 0 = String sort, 1 = Numeric sort
    If $iSense = Default Then $iSense = 0 ; 0 = ascending, 1 = descending

    If Not IsArray($aArray) Then
        MsgBox($MB_TOPMOST, "Error : variable $aArray is not an Array", _
            "Its type is : " & VarGetType($aArray))
        Return SetError(1, 0, 0)
    EndIf

    Local $iDims = UBound($aArray, $UBOUND_DIMENSIONS)
    If $iDims < 1 Or $iDims > 2 Then
        MsgBox($MB_TOPMOST, "Error : Dimensions = " & $iDims, _
            "Array is not 1D or 2D")
        Return SetError(2, 0, 0)
    EndIf

    Local $iRows = UBound($aArray, $UBOUND_ROWS)
    If $iRows < 2 Then
        MsgBox($MB_TOPMOST, "Nothing to sort", _
            "Array doesn't have 2 rows") ; no matter 1D or 2D
        Return 1 ; success anyway
    EndIf

    Local $iCols = UBound($aArray, $UBOUND_COLUMNS) ; always 0 for 1D array.
    If $iDims = 2 Then
        If $iCols = 0 Then
            MsgBox($MB_TOPMOST, "Error", _
                "2D Array got 0 columns")
            Return SetError(3, 0, 0)
        ElseIf $iSortCol < 0 Or $iSortCol > $iCols - 1 Then
            MsgBox($MB_TOPMOST, "Error : sort column " & $iSortCol, _
                "Please choose between 0 and " & $iCols - 1)
            Return SetError(4, 0, 0)
        EndIf
    EndIf

    If $iType < 0 Or $iType > 1 Then
        MsgBox($MB_TOPMOST, "Unknown Type of sort " & $iType, _
            "It should be : 0 = String sort, 1 = Numeric sort")
        Return SetError(5, 0, 0)
    EndIf

    If $iSense < 0 Or $iSense > 1 Then
        MsgBox($MB_TOPMOST, "Unknown Sense of sort " & $iSense, _
            "It should be : 0 = Ascending, 1 = Descending")
        Return SetError(6, 0, 0)
    EndIf

    Local $hDLLSort = DllOpen("sortall.dll") ; as no path indicated, dll is searched first in path environment, then in script path.
                                             ; if path is indicated (@ScriptDir for example), then it's the contrary.
    If $hDLLSort = -1 Then
        MsgBox($MB_TOPMOST, "Error", _
            "sortall.dll can't be opened")
        Return SetError(20, 0, 0)
    EndIf

    Local $tStruct2 = DllStructCreate("int[" & $iRows & "]") ; will be filled by dll
    If @error Then
        MsgBox($MB_TOPMOST, "DllStructCreate : error " & @error, _
            "Check AutoIt help file for this error")
        DllClose($hDLLSort)
        Return SetError(21, 0, 0)
    EndIf

    Local $sData = "", $sDelim = Chr(1) ; don't change Chr(1), it's used in the dll too

    If $iDims = 1 Then ; 1D
        If $iType = 1 And StringLeft(StringStripWS($aArray[0], 1), 2) = "0x" Then ; $STR_STRIPLEADING = 1
            For $i = 0 To $iRows - 1
                $sData &= Number(StringStripWS($aArray[$i], 1)) & $sDelim ; $sDelim also at end of string (used by dll +++)
            Next
        Else
            For $i = 0 To $iRows - 1
                $sData &= $aArray[$i] & $sDelim
            Next
        EndIf
    Else ; 2D
        If $iType = 1 And StringLeft(StringStripWS($aArray[0][$iSortCol], 1), 2) = "0x" Then
            For $i = 0 To $iRows - 1
                $sData &= Number(StringStripWS($aArray[$i][$iSortCol], 1)) & $sDelim
            Next
        Else
            For $i = 0 To $iRows - 1
                $sData &= $aArray[$i][$iSortCol] & $sDelim
            Next
        EndIf
    EndIf

    Local $aBackup = $aArray ; backup the array before the sort (extremely fast !)

    Local $aRet = DllCall($hDLLSort, "int:cdecl", "sortall", "str", $sData, "ptr", DllStructGetPtr($tStruct2), _
        "str", $sDelim, "int", $iRows, "int", $iSense, "int", $iType)

    If @error Then
        MsgBox($MB_TOPMOST, "DllCall : error " & @error, _
            "Check AutoIt help file for this error")
        DllClose($hDLLSort)
        Return SetError(22, 0, 0)
    EndIf

    If $aRet[0] <> 0 Then
        MsgBox($MB_TOPMOST, "sortall.dll : error " & $aRet[0], _
            "Check C++ code in dll")
        DllClose($hDLLSort)
        Return SetError(23, 0, 0)
    EndIf

    Local $iIndex
    If $iDims = 1 Then ; 1D
        For $i = 0 To $iRows - 1
            $iIndex = DllStructGetData($tStruct2, 1, $i + 1) ; row index before sorting
            ; If $i <> $iIndex Then ; test not really useful when original array is 1D
                $aArray[$i] = $aBackup[$iIndex]
            ; EndIf
        Next
    Else ; 2D
        For $i = 0 To $iRows - 1
            $iIndex = DllStructGetData($tStruct2, 1, $i + 1) ; row index before sorting
            If $i <> $iIndex Then
                For $j = 0 To $iCols - 1
                    $aArray[$i][$j] = $aBackup[$iIndex][$j]
                Next
            EndIf
        Next
    EndIf

    DllClose($hDLLSort)
    Return 1 ; success

EndFunc   ;==>SortAll

2) Test.au3 : a test on a 1D array of 100.000 numeric  elements (integers, floats or doubles)

#include <Array.au3>
#include <SortAll.au3> ; pixelsearch's sortall.dll

Opt("MustDeclareVars", 1)

Local $iRows = 100000, $aArray[$iRows]
ConsoleWrite("$iRows = " & $iRows & @CRLF)

;~ GenerateArrayInt($aArray, $iRows)
GenerateArrayDouble($aArray, $iRows)
;~ GenerateArrayFloat($aArray, $iRows)

_ArrayDisplay($aArray, "UNsorted", Default, Default, Default, _
    "Numbers*") ; * at end of header means numeric sort

;====================================
Local $hTimer = TimerInit()

Local $iSortCol = 0 ; value not important when 1D
Local $iRet = SortAll($aArray, $iSortCol, 1, 0) ; numeric sort, ascending

If $iRet Then ; 1 = success, 0 = fail with @error > 0
    ConsoleWrite("Generating sorted 1D array = " & Int(TimerDiff($htimer)) & " ms" & @crlf)

    _ArrayDisplay($aArray, "sorted (col " & $iSortCol & ")", Default, Default, Default, _
        "Numbers*") ; * at end of header means numeric sort
EndIf

;====================================
Func GenerateArrayInt(ByRef $aArray, $iRows)
    For $i = 0 To $iRows - 1
        $aArray[$i] = Random(-1000000, +1000000, 1)
    Next
EndFunc   ;==>GenerateArrayInt

;====================================
Func GenerateArrayDouble(ByRef $aArray, $iRows)
    For $i = 0 To $iRows - 1
        $aArray[$i] = Random(-1000000, +1000000)
        ; $aArray[$i] = Random(-1, 1)
    Next
EndFunc   ;==>GenerateArrayDouble

;====================================
Func GenerateArrayFloat(ByRef $aArray, $iRows)
    For $i = 0 To $iRows - 1
        $aArray[$i] = Number("" & Random(-1000000, +1000000, 1) & "." & Random(0,99,1), 3)
    Next
EndFunc   ;==>GenerateArrayFloat

980801391_sortallinaction.png.d77d571b2e5b6a7fa52eda5a6ae41049.png

Console :

$iRows = 100000
Generating sorted 1D array = 3058 ms

Timer to be divided by 5 (or more) if your computer is recent =>
less than 1s to rewrite a whole 1D sorted array of 100.000 elements, yes !

For readers who are interested and got a compiler, you should be able to compile the C++ code of the preceding post, then place the resulting dll (named "sortall.dll") in one of the folders of your PATH environment (or in the folder of the test file "test.au3")
If the dll isn't found in one of these folders, then this error will appear when you run the test file :

248880870_messagewhensortall.dllnotfound.png.64955ce80e7749a6a4847ea78edfdf03.png

Personally, I placed the dll in my Windows folder (which isn't really recommended) and the include file... in AutoIt's include files folder, which isn't recommended either ! I'll probably change that soon.

Good luck.

Edited by pixelsearch
less code in user's test.au3, more code in include file SortAll.au3, great !
Link to post
Share on other sites

Good news, the part concerning the C++ natural sort is ready. Natural means you want your sort to go like this :

a1
a4
a10
a20
a100

and not like that :

a1
a10
a100
a20
a4

Now the C++ code calls directly the Windows function StrCmpLogicalW (found in "shlwapi.dll"), it's incredibly fast and amazing.

I started slowly with 5 hard-coded elements and a basic console output in CodeBlocks IDE, to see if I was able to do it, with the code below, named "blood, sweat & tears" (for the connection with the function StrCmpLogicalW)  :sweating:

#include <windows.h>
#include <algorithm>    // sort
#include <string>
#include <vector>
#include <iostream>

/* Original StrCmpLogicalW function found in shlwapi.dll
    int StrCmpLogicalW(
    [in] PCWSTR psz1,
    [in] PCWSTR psz2
    );
*/

// create a matching typedef for the function pointer
// typedef INT (CALLBACK* LPFNDLLFUNC1)(PCWSTR, PCWSTR);

typedef int (__stdcall* pfunc)(const wchar_t*, const wchar_t*);
HINSTANCE hDLL;         // Handle to DLL
pfunc StrCmpLogicalW;   // Function pointer
// PCWSTR par1, par2;   // Parameters of the function
// INT returnval;       // Function return


bool naturalcomp(const std::wstring& v1, const std::wstring& v2)
{
    return StrCmpLogicalW(v1.c_str(), v2.c_str()) < 0;
}


int main()
{
    hDLL = LoadLibrary("shlwapi.dll");
    if (hDLL == NULL)
    {
        std::cout << "Can't open shlwapi.dll \n";
        return - 1;
    }

    StrCmpLogicalW = (pfunc)GetProcAddress(hDLL, "StrCmpLogicalW");
    if (!StrCmpLogicalW)
    {
        std::cout << "Function 'StrCmpLogicalW' not found in shlwapi.dll \n";
        FreeLibrary(hDLL);
        return - 2;
    }

    int irows = 5;
    std::vector<std::wstring> vect(irows);

    vect[0] = L"a10";
    vect[1] = L"a1";
    vect[2] = L"a100";
    vect[3] = L"a20";
    vect[4] = L"a4";

    std::sort(vect.begin(), vect.end(), naturalcomp);

    for (int i=0; i<irows; i++)
        std::wcout << vect[i] << std::endl;

    // Console :  a1  a4  a10  a20  a100    <===== yes !

    // swap trick to release memory used by the vector :
    std::vector<std::wstring>().swap(vect);

    FreeLibrary(hDLL);
    return 0;
}

When I saw that the 5 elements were correctly "naturally" sorted, then bingo, let's move a step further and prepare a dll for that. The function returns to AutoIt a structure containing only indexes (the "old" rows of each string, before the sort takes place). Here is the C++ code for creating the dll, based on a vector of structure 1 member named "data" takes care of the wide strings wchar_t [mandatory for StrCmpLogicalW], the 2nd member named "index" takes care of... the indexes.

#include <windows.h>
#include <algorithm>    // sort
#include <string>       // string
#include <vector>       // vector

/* Original StrCmpLogicalW function found in shlwapi.dll
    int StrCmpLogicalW(
    [in] PCWSTR psz1,
    [in] PCWSTR psz2
    );
*/

// create a matching typedef for the function pointer
// typedef INT (CALLBACK* LPFNDLLFUNC1)(PCWSTR, PCWSTR);

typedef int (__stdcall* pfunc)(const wchar_t*, const wchar_t*);
HINSTANCE hDLL;         // Handle to DLL
pfunc StrCmpLogicalW;   // Function pointer


struct struct_natural {
    std::wstring data;
    int index; };

bool sort_natural_asc (const struct_natural& v1, const struct_natural& v2)
{
    return StrCmpLogicalW(v1.data.c_str(), v2.data.c_str()) < 0;
}

bool sort_natural_desc (const struct_natural& v1, const struct_natural& v2)
{
    return StrCmpLogicalW(v1.data.c_str(), v2.data.c_str()) > 0;
}


extern "C" __declspec(dllexport) int NaturalSort_03
    (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows, int isense)
{
    hDLL = LoadLibrary("shlwapi.dll");
    if (hDLL == NULL) return - 1;

    StrCmpLogicalW = (pfunc)GetProcAddress(hDLL, "StrCmpLogicalW");
    if (!StrCmpLogicalW)
    {
        FreeLibrary(hDLL);
        return - 2;
    }

    std::vector<struct_natural> vect(irows); // irows (and 2 cols from struct_natural)
    std::wstring str = sbigdata;
    size_t ifound = 0, ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        vect[i].data = str.substr(ipos, ifound - ipos); // wide string
        vect[i].index = i; // row (to remember initial index before data sorting)
        ipos = ifound + 1;
    }

    std::sort(vect.begin(), vect.end(),
        ((isense == 0) ? sort_natural_asc : sort_natural_desc));

    for (int i = 0; i < irows; i++)
        *(struct_indexes + i) = vect[i].index; // index of sorted data... before data sorting

    //swap trick to release memory used by the string (str = L"" wouldn't release anything)
    std::wstring(L"").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<struct_natural>().swap(vect);

    FreeLibrary(hDLL);
    return 0;
}

Next (and last) step should be to combine the 3 kind of sorts (string, numeric, natural) in the same dll named "sortall.dll", which is related to the include file "sortall.au3" as discussed in the precedent post. Actually "sortall.dll" contains 2 kind of sorts (string and numeric), let's add the 3rd kind, the natural one.

Hope it will be useful to some readers :bye:
 

Edited by pixelsearch
Link to post
Share on other sites

Hi everybody :)

And we're done... all sort code is gathered and operational.
Below is the final C++ code taking care of the three ways of sorting, the corresponding include file "SortAll.au3" and a file test2.au3 for trying (after you compile the C++ code)

If I had to do any further modification, I'll do it in this very post, indicating the reason of the change.

1) C++ code to generate "SortAll.dll"

#include <algorithm>
#include <string>
#include <vector>
#include <windows.h>

// =======================================================================================
// STRING Sort (0)
// =======================================================================================

struct struct_alpha {
    std::wstring data;
    int index; };

bool sort_alpha_asc (const struct_alpha& v1, const struct_alpha& v2) {
    return v1.data < v2.data; } // no .c_str() or sort fails (tested)

int sort_alpha (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows, int istable)
{
    std::vector<struct_alpha> vect(irows); // irows (and 2 cols from struct_alpha)
    std::wstring str = sbigdata;
    size_t ifound = 0, ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        vect[i].data = str.substr(ipos, ifound - ipos); // wide string
        vect[i].index = i; // row (to remember initial index before data sorting)
        ipos = ifound + 1;
    }

    if (istable == 0) std::sort(vect.begin(), vect.end(), sort_alpha_asc);
    else std::stable_sort(vect.begin(), vect.end(), sort_alpha_asc);

    for (int i = 0; i < irows; i++)
        *(struct_indexes + i) = vect[i].index; // index of sorted data... before data sorting

    //swap trick to release memory used by the string (str = L"" wouldn't release anything)
    std::wstring(L"").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<struct_alpha>().swap(vect);

    return 0;
}

// =======================================================================================
// NUMERIC Sort (1)
// =======================================================================================

struct struct_num {
    double data;
    int index; };

bool sort_num_asc (const struct_num& v1, const struct_num& v2) {
    return v1.data < v2.data; }

int sort_num (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows, int istable)
{
    std::vector<struct_num> vect(irows); // irows (and 2 cols from struct_num)
    std::wstring str = sbigdata;
    std::wstring sfound;
    size_t ifound = 0, ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        sfound = str.substr(ipos, ifound - ipos);
        vect[i].data = wcstod (sfound.c_str(), NULL); // wide string to double.
                                                      // .c_str() mandatory here.
        vect[i].index = i; // row (to remember initial index before data sorting)
        ipos = ifound + 1;
    }

    if (istable == 0) std::sort(vect.begin(), vect.end(), sort_num_asc);
    else std::stable_sort(vect.begin(), vect.end(), sort_num_asc);

    for (int i = 0; i < irows; i++)
        *(struct_indexes + i) = vect[i].index; // index of sorted data... before data sorting

    //swap trick to release memory used by the string (str = L"" wouldn't release anything)
    std::wstring(L"").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<struct_num>().swap(vect);

    return 0;
}

// =======================================================================================
// NATURAL Sort (2)
// =======================================================================================

/* Original StrCmpLogicalW function found in shlwapi.dll
    int StrCmpLogicalW(
    [in] PCWSTR psz1,
    [in] PCWSTR psz2
    );
*/

// create a matching typedef for the function pointer
// typedef INT (CALLBACK* LPFNDLLFUNC1)(PCWSTR, PCWSTR);

typedef int (__stdcall* pfunc)(const wchar_t*, const wchar_t*);
HINSTANCE hDLL;         // Handle to DLL
pfunc StrCmpLogicalW;   // Function pointer

struct struct_natural {
    std::wstring data;
    int index; };

bool sort_natural_asc (const struct_natural& v1, const struct_natural& v2) {
    return StrCmpLogicalW(v1.data.c_str(), v2.data.c_str()) < 0; }

int sort_natural (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows, int istable)
{
    hDLL = LoadLibrary("shlwapi.dll");
    if (hDLL == NULL) return - 1;

    StrCmpLogicalW = (pfunc)GetProcAddress(hDLL, "StrCmpLogicalW");
    if (!StrCmpLogicalW)
    {
        FreeLibrary(hDLL);
        return - 2;
    }

    std::vector<struct_natural> vect(irows); // irows (and 2 cols from struct_natural)
    std::wstring str = sbigdata;
    size_t ifound = 0, ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        vect[i].data = str.substr(ipos, ifound - ipos); // wide string
        vect[i].index = i; // row (to remember initial index before data sorting)
        ipos = ifound + 1;
    }

    if (istable == 0) std::sort(vect.begin(), vect.end(), sort_natural_asc);
    else std::stable_sort(vect.begin(), vect.end(), sort_natural_asc);

    for (int i = 0; i < irows; i++)
        *(struct_indexes + i) = vect[i].index; // index of sorted data... before data sorting

    //swap trick to release memory used by the string (str = L"" wouldn't release anything)
    std::wstring(L"").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<struct_natural>().swap(vect);

    FreeLibrary(hDLL);
    return 0;
}

// =======================================================================================
// NATURAL Sort (3a) LarsJ's way, to match AutoIt ArrayDisplay output (UNSTABLE sort)
// =======================================================================================

// 3 next lines already defined before => commented here :
// typedef int (__stdcall* pfunc)(const wchar_t*, const wchar_t*);
// HINSTANCE hDLL;         // Handle to DLL
// pfunc StrCmpLogicalW;   // Function pointer

int sort_natural3a_asc (const std::wstring& v1, const std::wstring& v2) {
    return StrCmpLogicalW(v1.c_str(), v2.c_str()); } // 0, -1, 1

int sort_natural3a (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows)
{
    hDLL = LoadLibrary("shlwapi.dll");
    if (hDLL == NULL) return - 1;

    StrCmpLogicalW = (pfunc)GetProcAddress(hDLL, "StrCmpLogicalW");
    if (!StrCmpLogicalW)
    {
        FreeLibrary(hDLL);
        return - 2;
    }

    std::vector<std::wstring> vect(irows);
    std::wstring str = sbigdata;
    size_t ifound = 0, ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        vect[i] = str.substr(ipos, ifound - ipos); // wide string
        ipos = ifound + 1;
    }

    int lo=0, hi=0, mi=0, r=0;

    for (int i = 1; i < irows; i++)
    {
        lo = 0;
		hi = i - 1;

        do
        {
            mi = (lo + hi) / 2;
            r = sort_natural3a_asc(vect[i], vect[*(struct_indexes + mi)]);

            if (r == -1) hi = mi - 1;
            else if (r == 1) lo = mi + 1;
            else break;
        }
        while (lo <= hi);

        memmove(struct_indexes + mi + 1, struct_indexes + mi, (i - mi) * 4);
        *(struct_indexes + mi + (lo == (mi + 1))) = i;
    }

    //swap trick to release memory used by the string (str = L"" wouldn't release anything)
    std::wstring(L"").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<std::wstring>().swap(vect);

    FreeLibrary(hDLL);
    return 0;
}

// =======================================================================================
// NATURAL Sort (3b) LarsJ's way + STABLE sort (mine)
// =======================================================================================

// 3 next lines already defined before => commented here :
// typedef int (__stdcall* pfunc)(const wchar_t*, const wchar_t*);
// HINSTANCE hDLL;         // Handle to DLL
// pfunc StrCmpLogicalW;   // Function pointer

int sort_natural3b_asc (const std::wstring& v1, const std::wstring& v2) {
    return StrCmpLogicalW(v1.c_str(), v2.c_str()); } // 0, -1, 1

int sort_natural3b (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows)
{
    hDLL = LoadLibrary("shlwapi.dll");
    if (hDLL == NULL) return - 1;

    StrCmpLogicalW = (pfunc)GetProcAddress(hDLL, "StrCmpLogicalW");
    if (!StrCmpLogicalW)
    {
        FreeLibrary(hDLL);
        return - 2;
    }

    std::vector<std::wstring> vect(irows);
    std::wstring str = sbigdata;
    size_t ifound = 0, ipos = 0;

    for (int i = 0; i < irows; i++)
    {
        ifound = str.find(sdelim, ipos);
        vect[i] = str.substr(ipos, ifound - ipos); // wide string
        ipos = ifound + 1;
    }

    std::vector<std::vector<int> > adupe(irows, std::vector<int>(3)); // irows and 3 cols
    int idupe, indx, irank, inb_elem, idiff, j;
    int lo=0, hi=0, mi=0, r=0;

    for (int i = 1; i < irows; i++)
    {
        lo = 0;
		hi = i - 1;

        do
        {
            mi = (lo + hi) / 2;
            r = sort_natural3b_asc(vect[i], vect[*(struct_indexes + mi)]);

            if (r == -1) hi = mi - 1;
            else if (r == 1) lo = mi + 1;
            else break;
        }
        while (lo <= hi);

		if (r == 0)
        {
            indx = *(struct_indexes + mi);
            idupe = adupe[indx][0];

            if (idupe == 0)
            {
				adupe[indx][0] = i;
				adupe[indx][1] = 1;

				adupe[i][0] = i;
				adupe[i][1] = 2;
				adupe[i][2] = 2;

                memmove(struct_indexes + mi + 1, struct_indexes + mi, (i - mi) * 4);
                *(struct_indexes + mi + 1) = i;
            }
            else
            {
                irank = adupe[indx][1];
                inb_elem = adupe[idupe][2];
                idiff = inb_elem - irank;
                j = mi + 1 + idiff;

                memmove(struct_indexes + j + 1, struct_indexes + j, (i - j) * 4);
				*(struct_indexes + j) = i;

				adupe[i][0] = idupe;
				adupe[i][1] = inb_elem + 1;
				adupe[idupe][2] = inb_elem + 1;
            }
        }
        else
        {
            memmove(struct_indexes + mi + 1, struct_indexes + mi, (i - mi) * 4);
            *(struct_indexes + mi + (lo == (mi + 1))) = i;
        }
    }

    //swap trick to release memory used by the string (str = L"" wouldn't release anything)
    std::wstring(L"").swap(str);

    // swap trick to release memory used by the vector :
    std::vector<std::wstring>().swap(vect);

    // swap trick to release memory used by the 2D vector :
    std::vector<std::vector<int> >().swap(adupe);

    FreeLibrary(hDLL);
    return 0;
}

// =======================================================================================
// dll entry point for any of the sorting types (function to call depends on itype)
// itype value checked by calling script "sortall.au3" (0=string, 1=num, 2 and 3 = natural)
// =======================================================================================

extern "C" __declspec(dllexport) int sortall
    (wchar_t* sbigdata, int* struct_indexes, wchar_t* sdelim, int irows, int istable, int itype)
{
    int iret = 0;
    switch(itype)
    {
        case 0:
            iret = sort_alpha   (sbigdata, struct_indexes, sdelim, irows, istable);
            break;
        case 1:
            iret = sort_num     (sbigdata, struct_indexes, sdelim, irows, istable);
            break;
        case 2:
            iret = sort_natural (sbigdata, struct_indexes, sdelim, irows, istable);
            break;
        case 3:  // natural sort LarsJ's way : unstable sort OR stable sort (mine)
            if (istable==0) iret = sort_natural3a (sbigdata, struct_indexes, sdelim, irows);
            else            iret = sort_natural3b (sbigdata, struct_indexes, sdelim, irows);
            break;
        default:       // impossible (itype value checked by calling script "sortall.au3")
            iret = -3; // return 'error' -3 (error value not used in the functions above)
    }
    return iret; // 0 when no error in any function called.
}

2) Include file "SortAll.au3"

#include-once

#include "AutoItConstants.au3"
#include "MsgBoxConstants.au3"

;================================================================================
Func SortAll(ByRef $aArray, $iSortCol = 0, $iType = 2, $iSense = 0, $iStable = 0)

    If $iSortCol = Default Then $iSortCol = 0 ; first column = 0
    If $iType = Default Then $iType = 2 ; 0 = String sort, 1 = Numeric sort, 2/3 = Natural sort
    If $iSense = Default Then $iSense = 0 ; 0 = ascending, 1 = descending
    If $iStable = Default Then $iStable = 0 ; 0 = unstable sort, 1 = stable sort

    If Not IsArray($aArray) Then
        MsgBox($MB_TOPMOST, "Error : Variable $aArray is not an Array", _
            "Its type is : " & VarGetType($aArray))
        Return SetError(1, 0, 0)
    EndIf

    Local $iDims = UBound($aArray, $UBOUND_DIMENSIONS)
    If $iDims < 1 Or $iDims > 2 Then
        MsgBox($MB_TOPMOST, "Error : Dimensions = " & $iDims, _
            "Array is not 1D or 2D")
        Return SetError(2, 0, 0)
    EndIf

    Local $iRows = UBound($aArray, $UBOUND_ROWS)
    If $iRows = 0 Then
        MsgBox($MB_TOPMOST, "Nothing to sort", _
            "Array got 0 row")
        Return SetError(3, 0, 0)
    EndIf

    Local $iCols = UBound($aArray, $UBOUND_COLUMNS) ; always 0 for 1D array.
    If $iDims = 2 Then
        If $iCols = 0 Then
            MsgBox($MB_TOPMOST, "Error", _
                "2D Array got 0 columns")
            Return SetError(4, 0, 0)
        ElseIf $iSortCol < 0 Or $iSortCol > $iCols - 1 Then
            MsgBox($MB_TOPMOST, "Error : Sort column " & $iSortCol, _
                "Please choose column between 0 and " & $iCols - 1)
            Return SetError(5, 0, 0)
        EndIf
    EndIf

    If $iType < 0 Or $iType > 3 Then
        MsgBox($MB_TOPMOST, "Unknown Sort Type " & $iType, _
            "It should be : 0 = String sort, 1 = Numeric sort, 2/3 = Natural sort")
        Return SetError(6, 0, 0)
    EndIf

    If $iSense < 0 Or $iSense > 1 Then
        MsgBox($MB_TOPMOST, "Unknown Sort Sense" & $iSense, _
            "It should be : 0 = Ascending, 1 = Descending")
        Return SetError(7, 0, 0)
    EndIf

    If $iStable < 0 Or $iStable > 1 Then
        MsgBox($MB_TOPMOST, "Unknown Sort Stability " & $iStable, _
            "It should be : 0 = Unstable sort, 1 = Stable sort")
        Return SetError(8, 0, 0)
    EndIf

    Local $hDLLSort = DllOpen("sortall.dll") ; as no path indicated, dll is searched first in path environment, then in script path.
                                             ; if path is indicated (@ScriptDir for example), then it's the contrary.
    If $hDLLSort = -1 Then
        MsgBox($MB_TOPMOST, "Error", _
            "sortall.dll can't be opened")
        Return SetError(20, 0, 0)
    EndIf

    Local $tStruct2 = DllStructCreate("int[" & $iRows & "]") ; will be filled by dll
    If @error Then
        MsgBox($MB_TOPMOST, "DllStructCreate $tStruct2 : error " & @error, _
            "Check AutoIt help file for this error")
        DllClose($hDLLSort)
        Return SetError(21, 0, 0)
    EndIf

    Local $sData = "", $sDelim = Chr(1)

    If $iDims = 1 Then ; 1D
        If $iType = 1 And StringLeft(StringStripWS($aArray[0], 1), 2) = "0x" Then ; $STR_STRIPLEADING = 1
            For $i = 0 To $iRows - 1
                $sData &= Number(StringStripWS($aArray[$i], 1)) & $sDelim ; $sDelim also at end of string (used by dll +++)
            Next
        Else
            For $i = 0 To $iRows - 1
                $sData &= $aArray[$i] & $sDelim
            Next
        EndIf
    Else ; 2D
        If $iType = 1 And StringLeft(StringStripWS($aArray[0][$iSortCol], 1), 2) = "0x" Then
            For $i = 0 To $iRows - 1
                $sData &= Number(StringStripWS($aArray[$i][$iSortCol], 1)) & $sDelim
            Next
        Else
            For $i = 0 To $iRows - 1
                $sData &= $aArray[$i][$iSortCol] & $sDelim
            Next
        EndIf
    EndIf

    Local $aBackup = $aArray ; backup the array before the sort (needed below, extremely fast !)

    Local $aRet = DllCall($hDLLSort, "int:cdecl", "sortall", "wstr", $sData, "ptr", DllStructGetPtr($tStruct2), _
        "wstr", $sDelim, "int", $iRows, "int", $iStable, "int", $iType)

    If @error Then
        MsgBox($MB_TOPMOST, "DllCall : error " & @error, _
            "Check AutoIt help file for this error")
        $tStruct2 = 0
        DllClose($hDLLSort)
        Return SetError(22, 0, 0)
    EndIf

    If $aRet[0] <> 0 Then
        Switch $aRet[0]
            Case - 1 ; as programmed in "sortall.dll" (Natural sort part)
                MsgBox($MB_TOPMOST, "Natural sort : error " & $aRet[0], _
                    "shlwapi.dll not found on your system")
                $tStruct2 = 0
                DllClose($hDLLSort)
                Return SetError(23, 0, 0)

            Case - 2 ; as programmed in "sortall.dll" (Natural sort part)
                MsgBox($MB_TOPMOST, "Natural sort : error " & $aRet[0], _
                    "Function StrCmpLogicalW not found in shlwapi.dll")
                $tStruct2 = 0
                DllClose($hDLLSort)
                Return SetError(24, 0, 0)

            Case Else ; no other error programmed (for now) in "sortall.dll", for any sort.
                MsgBox($MB_TOPMOST, "sortall.dll : impossible error " & $aRet[0], _
                    "This should never happen")
                $tStruct2 = 0
                DllClose($hDLLSort)
                Return SetError(25, 0, 0)
        EndSwitch
    EndIf

    If $iDims = 1 Then ; 1D
        If $iSense = 0 Then ; ascending
            For $i = 1 To $iRows
                $aArray[$i - 1] = $aBackup[DllStructGetData($tStruct2, 1, $i)]
            Next
        Else ; descending
            For $i = 1 To $iRows
                $aArray[$iRows - $i] = $aBackup[DllStructGetData($tStruct2, 1, $i)]
            Next
        EndIf
    Else ; 2D
        Local $iIndex
        If $iSense = 0 Then ; ascending
            For $i = 1 To $iRows
                $iIndex = DllStructGetData($tStruct2, 1, $i) ; row index before sorting
                For $j = 0 To $iCols - 1
                    $aArray[$i - 1][$j] = $aBackup[$iIndex][$j]
                Next
            Next
        Else ; descending
            For $i = 1 To $iRows
                $iIndex = DllStructGetData($tStruct2, 1, $i) ; row index before sorting
                For $j = 0 To $iCols - 1
                    $aArray[$iRows - $i][$j] = $aBackup[$iIndex][$j]
                Next
            Next
        EndIf
    EndIf

    $tStruct2 = 0 ; release the resources used by the structure.
    DllClose($hDLLSort)
    Return 1 ; success

EndFunc   ;==>SortAll

3) "Test2.au3

#include <Array.au3>
#include <SortAll.au3> ; pixelsearch's sortall.dll
#include "RandomArray.au3" ; LarsJ

Opt("MustDeclareVars", 1)

Local $iRows = 100000, $iCols = 6, $aArray ; 6 related to _Generate_All()
_Generate_All($aArray, $iRows, $iCols)

_ArrayDisplay($aArray, "UNsorted", Default, Default, Default, _
    "Strings|Integers*|Floats*|Dates*|Times*|R/C*") ; * at end of any header means numeric sort for the concerned column.

;====================================
Local $hTimer = TimerInit()

Local $iSortCol = 0 ; (first column = 0) (value not important when 1D)
Local $iType    = 2 ; (0 = String sort, 1 = Numeric sort, 2/3 = Natural sort)
Local $iSense   = 0 ; (0 = ascending, 1 = descending)
Local $iStable  = 0 ; (0 = unstable sort, 1 = stable sort)

Local $iRet = SortAll($aArray, $iSortCol, $iType, $iSense, $iStable)

If $iRet Then ; 1 = success, 0 = fail with @error > 0
    ConsoleWrite("Generating sorted 2D array = " & Int(TimerDiff($htimer)) & " ms" & @crlf)

    _ArrayDisplay($aArray, "sorted (col " & $iSortCol & ")", Default, Default, Default, _
        "Strings|Integers*|Floats*|Dates*|Times*|R/C*") ; * at end of any header means numeric sort for the concerned column.
EndIf

;====================================
Func _Generate_All(ByRef $aArray, $iRows, $iCols)
    ConsoleWrite("$iRows = " & $iRows & "    $iCols = " & $iCols & @CRLF)
    ; $aArray = FAS_Random2DArrayAu3($iRows, "sifdtr", "abcdefghijklmnopqrstuvwxyz")
    $aArray = FAS_Random2DArrayAu3($iRows, "sifdtr", "abcdefghijklmnopqrstuvwxyz0123456789.")
EndFunc   ;==>_Generate_All

Though all the above has nothing to do with _ArrayDisplay beta (which uses a virtual listview), I personally "linked" a part of it to _ArrayDisplay, so I can also sort in ArrayDisplay 10 times faster than the beta, when clicking on a column header to create the appropriate sort index.

@jpm, in case you're interested, I'll present you by PM the code I added. Basically, in case of calling __ArrayDisplay_SortArrayStruct() to return the index (as in the original beta), I call a new function named __ArrayDisplay_SortArrayStruct2() to return the same index, through the dll.

If for any reason the index can't be created (maybe the dll is missing), then there is an automatical transition to your function, so it looks safe. Any @error returned by __ArrayDisplay_SortArrayStruct2() will chain to the original function __ArrayDisplay_SortArrayStruct() . During my tests it didn't happen, I had to force errors to get the "smooth transition".

Func __ArrayDisplay_GetSortColStruct(Const ByRef $aArray, $iCol)
    
    ...
;~  Return __ArrayDisplay_SortArrayStruct($aArray, $iCol)

    Local $tIndex = __ArrayDisplay_SortArrayStruct2($aArray, $iCol)
    If VarGetType($tIndex) = "DLLStruct" Then
        Return $tIndex
    Else ; any @error returned involving sortall.dll
        Return __ArrayDisplay_SortArrayStruct($aArray, $iCol) ; chain smoothly with jpm's original function
    EndIf

EndFunc   ;==>__ArrayDisplay_GetSortColStruct

Thanks for reading and have a great day :bye:

Edit: I forgot... hats off to the developer(s) who scripted DebugArrayDisplay.
It helped me a lot, by copying the sorted data generated by the dll, place it in a text file a.txt

Then a click on a column header to have it sorted again, but now through the original code of the beta, copying the new sorted data and placing it in a text file b.txt

Finally comparing both text files a.txt and b.txt to make sure the sortings were correct.
So bravo to anyone who was involved in the creation of DebugArrayDisplay :thumbsup:

Let's not forget LarsJ's "RandomArray.au3" which is a big help when tests are needed.

Update: Feb 22, 2022 :
* Default Sort type changed from Numeric to Natural
* Fixed String sort involving Unicode characters
* Stable Sort in C++ code (instead of Unstable Sort)
* Only 1 DllCall in SortAll.au3
* Only 1 point of entry in SortAll.dll

Update: Feb 26, 2022 :
* Warning when sort requested and array got 0 row
* Release the resources used by structure $tStruct2

Update: Mar 6, 2022 :
* User can choose between C++ Unstable / Stable Sort (new parameter)

Update: Mar 19, 2022 :
* Added a 2nd way for Natural sorting (LarsJ's index creation adapted to C++)

Edited by pixelsearch
Code updated (details above)
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...