#include-once #include ;~ ; Content: ;~ --------------- Funktionen für dynamische Arrays ----------------------------------- ;~ _DynArrayPush - neuen Wert ans Ende anhängen (vgl. Stack) ;~ _DynArrayPop - letzten Wert zurückgeben und aus dem Array entfernen (vgl. Stack) ;~ _DynArrayEnqueue - Wert ans Ende des Arrays hinzufügen (vgl. Queue) ;~ _DynArrayDequeue - ersten Wert des Arrays entfernen und zurückgeben (vgl. Queue) ;~ _DynArrayInsert - einen oder mehrere Werte innerhalb des Arrays einfügen ;~ _DynArrayDelete - einen oder mehrere Werte innerhalb des Arrays entfernen ;~ _DynArrayFromArray - Konvertiert ein normales Array in ein dynamisches Array ;~ _DynArrayToArray - Konvertiert ein dynamisches Array in ein normales Array ;~ _DynArrayFromString - Erzeugt ein dynamisches Array aus einem String ;~ _DynArrayToString - Konvertiert ein dynamisches Array in einen String, getrennt durch ein Trennzeichen ;~ _DynArraySearch - Werte in einem unsortierten Array finden ;~ _DynArrayBinarySearch - Werte in einem sortierten Array finden ;~ _DynArraySort - Array sortieren ;~ _DynArrayIsSorted - prüft ob ein dynamisches Array bereits nach einer freien Sortierfunktion sortiert wurde ;~ _DynArrayUnique - entfernt doppelte Einträge aus einem dynamischen Array ;~ _DynArrayMap - Wendet eine Funktion auf alle Elemente eines dynamischen Arrays an ;~ _DynArrayFilter - Filtert die Werte eines dynamischen Arrays anhand einer externen Funktion ;~ _DynArrayReduce - Reduziert die Elemente eines dynamischen Arrays auf einen Wert mit Hilfe einer externen Funktion ;~ _DynArrayFileList - Dateiauflistung in Ordnern+Unterordnern mit frei individualisierbarer Filterfunktion ;~ ----------- Hilfsfunktionen und allgemein verwendbare Funktionen -------------------------- ;~ _ArrayMap - Wendet eine Funktion auf alle Elemente eines Arrays an ;~ _ArrayFilter - Filtert die Werte eines Arrays anhand einer externen Funktion ;~ _ArrayReduce - Reduziert die Elemente eines Arrays auf einen Wert mit Hilfe einer externen Funktion ;~ __DynArrayIsValid - Prüft ob ein Array einem korrekten dynamischen Array entspricht ;~ __DynArrayRepair - versucht ein korrumpiertes dynamisches Array zu reparieren ;~ __DynArrayIsPowerOfTwo - Prüft ob eine Zahl eine Zweierpotenz ist ;~ __DynArrayGetNextPowerOfTwo - gibt die nächste aufgerundete Zweierpotenz zu einer Zahl zurück ;~ __DynArrayGetPreviousPowerOfTwo - gibt die vorhergehende abgerundete Zweierpotenz zu einer Zahl zurück ;~ _ArraySortFlexible - Sortiert ein Array mit einer beliebigen Vergleichsfunktion ;~ _ArraySortInsertion - Sortiert ein Array mit einer beliebigen Vergleichsfunktion per Insertion-Sort ;~ _ArrayHeapSortBinary - Sortiert ein Array mit einer beliebigen Vergleichsfunktion per Binary-Min-Heap-Sort ;~ _ArrayHeapSortTernary - Sortiert ein Array mit einer beliebigen Vergleichsfunktion per Ternary-Min-Heap-Sort ;~ __ArrayDualPivotQuicksort - Sortiert ein Array mit einer beliebigen Vergleichsfunktion per Dual-Pivot-Quicksort ;~ _ArraySortWithList - Sortiert ein Array über die Sortierfunktion des Arraylist-COM-Objektes ;~ _ArrayGetNthBiggestElement - gibt das n-größte Element in einem unsortierten Array ohne es zu sortieren (z.B. für Median) ;~ _ArrayAinATo2d - konvertiert ein "Arrays in Array"-Konstrukt in ein 2D-Array ;~ _Array2dToAinA - konvertiert ein 2D-Array in ein "Arrays-in-Array"-Konstrukt ;~ _ArrayGetMax - ermittelt den Maximalwert in einem Array (auch mit eigener Vergleichsfunktion möglich) ;~ _ArrayGetMin - ermittelt den Minimalwert in einem Array (auch mit eigener Vergleichsfunktion möglich) ;~ _ArrayBinarySearchFlex - führt eine binäre Suche in einem Array mit Hilfe einer eigenen Vergleichsfunktion durch ;~ _ArrayIsSorted - prüft ob ein Array bereits nach einer freien Sortierfunktion sortiert wurde ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayFromArray() ; Description ...: creates a semi-dynamic array from a conventional array ; Syntax ........: _DynArrayFromArray(ByRef $a_Array, Const $b_Overwrite = True, Const $b_Withcount = False) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_Withcount - Set true if the number of elements is written in $a_Array[0] (Array is 1-based) ; Return values .: Success: $b_Overwrite=True: True; Else: the converted semi-dynamic array ; Failure: False ; @error = 1: $a_Array is'nt an array ; Author ........: AspirinJunkie ; ================================================================================================= Func _DynArrayFromArray(ByRef $a_Array, Const $b_Overwrite = True, Const $b_Withcount = False) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local $N = UBound($a_Array) If $b_Withcount Then Return __DynArrayRepair($a_Array, $b_Overwrite) If $b_Overwrite Then ReDim $a_Array[__DynArrayGetNextPowerOfTwo($N + 1)] For $i = $N To 1 Step -1 $a_Array[$i] = $a_Array[$i - 1] Next $a_Array[0] = $N Return True Else Local $a_Ret[__DynArrayGetNextPowerOfTwo($N + 1)] For $i = $N To 1 Step -1 $a_Ret[$i] = $a_Array[$i - 1] Next $a_Ret[0] = $N Return $a_Ret EndIf EndFunc ;==>_DynArrayFromArray ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayToArray() ; Description ...: convert a semi-dynamic array to a conventional array ; Syntax ........: _DynArrayToArray(ByRef $a_Array, Const $b_Overwrite = True, Const $b_Withcount = False) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_Withcount - Set true if the number of elements should written in the first element of the output value ; Return values .: Success: $b_Overwrite=True: True; Else: the converted semi-dynamic array ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array size isn't power of two (characteristic of the implemented semi-dynamic arrays) ; Author ........: AspirinJunkie ; ================================================================================================= Func _DynArrayToArray(ByRef $a_Array, Const $b_Overwrite = True, Const $b_Withcount = False) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local Const $N = $a_Array[0] If $b_Withcount Then If $b_Overwrite Then ReDim $a_Array[$N + 1] Return True Else Local $a_Ret = $a_Array ReDim $a_Ret[$N + 1] Return $a_Ret EndIf Else If $b_Overwrite Then For $i = 0 To $N - 1 $a_Array[$i] = $a_Array[$i + 1] Next ReDim $a_Array[$N] Return True Else Local $a_Ret[$N] For $i = 0 To $N - 1 $a_Ret[$i] = $a_Array[$i + 1] Next Return $a_Ret EndIf EndIf EndFunc ;==>_DynArrayToArray ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayFromString ; Description ...: creates an semi-dynamic-array from a string ; Syntax ........: _DynArrayFromString(ByRef Const $s_String, Const $s_Delim = "|", Const $flag = 0) ; Parameters ....: $s_String - the string with the future elements separated by $s_Delim ; $s_Delim - the delimiter char[s] (see help for StringSplit) ; $flag - see help for StringSplit (value 2 is without influence) ; $cb_Func - udf for convert the elements (e.g. "Int" to make the elements integer values instead of strings) ; Return values .: Success: the semi-dynamic array made out of the string ; Failure: False ; @error = 1: see help for StringSplit - @extended=@error of stringsplit ; 2: see UDF for _DynArrayFromArray - @extended=@error of _DynArrayFromArray ; Author ........: AspirinJunkie ; Related .......: _DynArrayFromArray() ; ================================================================================================= Func _DynArrayFromString(ByRef Const $s_String, Const $s_Delim = "|", $cb_Func = Default, Const $flag = 0) Local $a_Ret = StringSplit($s_String, $s_Delim, $flag) If $cb_Func <> Default Then ; if $cb_func is setted apply user defined conversion function For $i = (BitAND($flag, 2) ? 1 : 0) To UBound($a_Ret) - 1 $a_Ret[$i] = $cb_Func($a_Ret[$i]) Next EndIf If @error Then Return SetError(1, @error, False) _DynArrayFromArray($a_Ret, True, (BitAND($flag, 2) ? False : True)) If @error Then Return SetError(2, @error, False) Return $a_Ret EndFunc ;==>_DynArrayFromString ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayToString ; Description ...: convert a semi-dynamic array into a string with it's elements separated by an delimiter ; Syntax ........: _DynArrayToString(ByRef $a_Array, [Const $s_Delim = "|"]) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $s_Delim - the delimiter char[s] ; Return values .: Success: the string created out of the array ; Failure: False and sets @error ; Author ........: AspirinJunkie ; Related .......: __DynArrayIsValid() ; ================================================================================================= Func _DynArrayToString(ByRef $a_Array, Const $s_Delim = "|") If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local Const $N = $a_Array[0] If $N < 1 Then Return "" Local $s_Ret = $a_Array[1] For $i = 2 To $N $s_Ret &= $s_Delim & $a_Array[$i] Next Return $s_Ret EndFunc ;==>_DynArrayToString ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayInsert() ; Description ...: insert single or multiple values at the given index to an semi-dynamic array ; Syntax ........: _DynArrayInsert(ByRef $a_Array, $value, $pos) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $value - the value[s] which should be inserted at the given index (single value or array) ; $pos - the index where the value[s] should inserted ; Return values .: Success: True ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: invalid value for $pos ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; that makes it much more performant for adding/deleting/inserting etc. ; ================================================================================================= Func _DynArrayInsert(ByRef $a_Array, $value, $pos) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local $N = $a_Array[0] ; number of elements in $a_Array Local $w = UBound($a_Array) ; size of $a_Array (including empty values at the end) If $N > $w Or (Not IsInt($N)) Or $N < 0 Then Return SetError(2, 0, False) If $pos < 1 Or $pos > $N Then Return SetError(3, $pos, False) ; sensless values for $pos Local $n_v = (IsArray($value)) ? UBound($value) : 1 ; number of inserting values If $N + $n_v + 1 >= $w Then ReDim $a_Array[__DynArrayGetNextPowerOfTwo($N + $n_v + 1)] ; resize if necessary For $x = $N To $pos Step -1 ; move old trailing elements $a_Array[$x + $n_v] = $a_Array[$x] Next ; Insert new elements: If $n_v > 1 Then ; $value = array For $x = 0 To $n_v - 1 $a_Array[$pos + $x] = $value[$x] Next Else ; $value = single value $a_Array[$pos] = $value EndIf $a_Array[0] += $n_v ; set new numbers of elements Return True EndFunc ;==>_DynArrayInsert ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayDelete() ; Description ...: deletes single or multiple values at the given index from an semi-dynamic array ; Syntax ........: _DynArrayDelete(ByRef $a_Array, Const $index, Const $d_NumElements = 1) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $index - the [start]-index where the value[s] should be deleted ; $d_NumElements - the number of elements which should be deleted ; Return values .: Success: True ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: invalid value in $index ; 4: invalid value for the combination of $index + $d_NumElements ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; that makes it much more performant for adding/deleting/inserting etc. ; ================================================================================================= Func _DynArrayDelete(ByRef $a_Array, Const $index, Const $d_NumElements = 1) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local $N = $a_Array[0] ; number of elements in $a_Array Local $w = UBound($a_Array) ; size of $a_Array (including empty values at the end) If $N > $w Or (Not IsInt($N)) Or $N <= 0 Then Return SetError(2, 0, False) If $index < 1 Or $index > $N Or Not IsInt($index) Then Return SetError(3, $index, False) If $index + $d_NumElements > $N Then Return SetError(4, $d_NumElements, False) $N -= $d_NumElements For $i = $index To $N ; move trailing elements (=overwrite old elements) $a_Array[$i] = $a_Array[$i + $d_NumElements] Next Local $dP = __DynArrayGetNextPowerOfTwo($N + 1) If $w <> $dP Then ReDim $a_Array[$dP] $w = $dP EndIf For $i = $N + 1 To ($a_Array[0] <= $w - 1) ? $a_Array[0] : $w - 1 ; delete old trailing values $a_Array[$i] = "" Next $a_Array[0] = $N ; set new numbers of elements Return True EndFunc ;==>_DynArrayDelete #Region Stack functionality ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayPush() ; Description ...: append the given value at the end of the given "semi-dynamic"-Array ; Syntax ........: _DynArrayPush(ByRef $a_Array, $value) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $value - the value which should be appended to the array ; Return values .: Success: True ; Failure: False ; @error = 1: parameter is'nt an array ; 2: invalid value in $a_Array[0]; ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; ================================================================================================= Func _DynArrayPush(ByRef $a_Array, $value) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local $w = UBound($a_Array) $a_Array[0] += 1 Local $N = $a_Array[0] If $N > $w Or (Not IsInt($N)) Or $N < 0 Then Return SetError(2, 0, False) If $N = $w Then ReDim $a_Array[2 * $w] ; double if array size is reached $a_Array[$N] = $value Return True EndFunc ;==>_DynArrayPush ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayPop() ; Description ...: Removes and return the last element of a "semi-dynamic" array ; Syntax ........: _DynArrayPop(ByRef $a_Array) ; Parameters ....: ByRef $a_Array -the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; Return values .: Success: the value of the last element ; @error = 0 ; Failure: False ; @error = 1: parameter is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array is empty; ; 4: Ubound(Array) is uneven; ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; ================================================================================================= Func _DynArrayPop(ByRef $a_Array) If Not IsArray($a_Array) Then Return SetError(1, 0, "") Local $w = UBound($a_Array) If Mod($w, 2) <> 0 Then Return SetError(4, $w, "") Local $N = $a_Array[0] If $N = 0 And $w = 1 Then Return SetError(3, 0, "") If $N <= 0 Or (Not IsInt($N)) Or $N > $w Then Return SetError(2, $N, "") $a_Array[0] -= 1 Local $a_Element = $a_Array[$N] $a_Array[$N] = "" If $N = $w / 2 Then ReDim $a_Array[$w / 2] ; double if array size is reached Return $a_Element EndFunc ;==>_DynArrayPop #EndRegion Stack functionality #Region Queue functionality ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayEnqueue() ; Description ...: add value to the end of a semi-dynamic array used as a queue ; Syntax ........: _DynArrayEnqueue(ByRef $a_Array, $value) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $value - the value[s] which should be enqueued ; Return values .: Success: True ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array size isn't power of two (characteristic of the implemented semi-dynamic arrays) ; Author ........: AspirinJunkie ; ================================================================================================= Func _DynArrayEnqueue(ByRef $a_Array, $value) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local $b_Ret = _DynArrayPush($a_Array, $value) Return SetError(@error, @extended, $b_Ret) EndFunc ;==>_DynArrayEnqueue ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayDequeue () ; Description ...: dequeues the first value from a semi-dynamic array used as a queue and returns the value ; Syntax ........: _DynArrayDequeue(ByRef $a_Array) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; Return values .: Success: The dropped first value of the queue ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array size isn't power of two (characteristic of the implemented semi-dynamic arrays) ; 5: Queue is empty - no elements left ; Author ........: AspirinJunkie ; ================================================================================================= Func _DynArrayDequeue(ByRef $a_Array) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) If $a_Array[0] = 0 Then Return SetError(5, 0, False) Local $a_RetVal = $a_Array[1] $a_Array[0] -= 1 For $i = 1 To $a_Array[0] $a_Array[$i] = $a_Array[$i + 1] Next If __DynArrayIsPowerOfTwo($a_Array[0] + 1) Then ReDim $a_Array[$a_Array[0] + 1] Else $a_Array[$a_Array[0] + 1] = "" EndIf Return $a_RetVal EndFunc ;==>_DynArrayDequeue #EndRegion Queue functionality ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArraySearch() ; Description ...: Finds an entry within a semi-dynamic-array (a wrapper for _ArraySearch()) ; Syntax ........: _DynArraySearch(ByRef $a_Array, Const $value, Const $iCase = 0, Const $iCompare = 0, Const $iForward = 1) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $value - What to search $a_Array for ; [...] - search autoit-help for "_ArraySearch" ; Return values .: search autoit-help for "_ArraySearch" ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; that makes it much more performant for adding/deleting/inserting etc. ; ================================================================================================= Func _DynArraySearch(ByRef $a_Array, Const $value, Const $iCase = 0, Const $iCompare = 0, Const $iForward = 1) Local $d_Ret = _ArraySearch($a_Array, $value, 1, $a_Array[0], $iCase, $iCompare, $iForward) Return SetError(@error, @extended, $d_Ret) EndFunc ;==>_DynArraySearch ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayBinarySearch() ; Description ...: Uses the binary search algorithm to search through a semi-dynamic-array (a wrapper for _ArrayBinarySearch()) ; Syntax ........: _DynArrayBinarySearch(ByRef $a_Array, Const $value) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $value - What to search $a_Array for ; Return values .: search autoit-help for "_ArrayBinarySearch" ; Author ........: AspirinJunkie ; Remarks .......: $a_Array has to be sorted ; a "semi-dynamic" array only doubles and halve it's size when it's necessary ; that makes it much more performant for adding/deleting/inserting etc. ; ================================================================================================= Func _DynArrayBinarySearch(ByRef $a_Array, Const $value) Local $d_Ret = _ArrayBinarySearch($a_Array, $value, 1, $a_Array[0]) Return SetError(@error, @extended, $d_Ret) EndFunc ;==>_DynArrayBinarySearch ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayBinarySearchFlex ; Description ...: performs a binary search for an appropriately sorted array using an individual comparison function ; Syntax ........: _ArrayBinarySearchFlex(ByRef $A, $cb_Func, $sS, [$iMi = 0, [$iMa = UBound($A) - 1]]) ; Parameters ....: $a_Array - The sorted array to search in ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; The function has two tasks: ; * Check whether the second parameter corresponds to a defined pattern (then ret value = 0). ; * Check whether a pattern searched for would be greater or smaller than the second parameter. ; the first parameter a value can be passed to the function through $sS to make it more dynamic. ; $sS - a value to be passed to $cb_Func to make it more dynamic ; $iMi - the start index of the search area ; $iMa - the end index of the search area ; Return values .: Success: Array with matches + index of first match in @extended ; Failure: empty array if no match ( + @error = 1), else undefined + @error ; @error = 1: No match found (return value = empty array) ; 2: invalid return value of cb_Func ; 3: invalid value for $A (no array) ; 4: invalid value for $$cb_Func (no function) ; 5: invalid value for $iMi ; 6: invalid value for $iMa ; 7: $iMa < $iMi ; Author ........: AspirinJunkie ; Example: Local $a_Array = ["BASF", "Allianz", "Volkswagen", "BMW", "Bayer", "Telekom", "Post", "Linde"] ; _ArraySortFlexible($a_Array) ; ; $a_Founds = _ArrayBinarySearchFlex($a_Array, _myCompare, "B") ; If Not @error Then _ArrayDisplay($a_Founds) ; ; Func _myCompare(Const $sS, Const $sO) ; Return StringRegExp($sO, '^' & $sS) = 1 ? 0 : -StringCompare($sO, $sS) ; EndFunc ;==>_myCompare ; ================================================================================================= Func _ArrayBinarySearchFlex(ByRef $A, $cb_Func, $sS, $iMi = 0, $iMa = UBound($A) - 1) Local $i, $e Local $aP[3] = ['CallArgArray', $sS] If Not IsArray($A) Then Return SetError(3) If Not IsFunc($cb_Func) Then Return SetError(4) If Not IsInt($iMi) Or $iMi < 0 Or $iMi >= UBound($A) Then Return SetError(5, $iMi) If Not IsInt($iMa) Or $iMa < 0 Or $iMa >= UBound($A) Then Return SetError(6, $iMa) If $iMa < $iMi Then Return SetError(7) While $iMi <= $iMa $i = Floor(($iMa + $iMi) / 2) $e = $A[$i] $aP[2] = $e Switch Call($cb_Func, $aP) Case 0 ; match! ; now lookaround to see if there are more matches $iMi = $i Do $iMi -= 1 If $iMi < 0 Then ExitLoop $aP[2] = $A[$iMi] Until Call($cb_Func, $aP) <> 0 $iMi += 1 $iMa = $i Do $iMa += 1 If $iMa >= UBound($A) Then ExitLoop $aP[2] = $A[$iMa] Until Call($cb_Func, $aP) <> 0 $iMa -= 1 ; build return array Local $aR[$iMa - $iMi + 1] For $i = 0 To UBound($aR) - 1 $aR[$i] = $A[$iMi] $iMi += 1 Next Return SetExtended($iMi, $aR) Case -1 $iMa = $i - 1 Case 1 $iMi = $i + 1 Case Else Return SetError(2) EndSwitch WEnd Local $aR = [] Return SetError(1, 0, $aR) EndFunc ;==>_ArrayBinarySearchFlex ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArraySort() ; Description ...: sorts a semi-dynamic-array with the ability of a user defined sorting rule ; Syntax ........: _DynArraySort(ByRef $a_Array, [Const $cb_Func = Default, [Const $iDescending = 0, [Const $b_Overwrite = True]]]) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; $iDescending - search autoit-help for "_ArraySort" ; $b_Overwrite - if false: $a_Array don't get touched - return a sorted copy of $a_Array ; Return values .: Success: If $cb_Func = Default: search autoit-help for "_ArraySort" ; Else: True if $b_Overwrite=True; sorted copy of $a_Array if $b_Overwrite=False ; Failure: False ; @error = 7: invalid value in $a_Array[0] ; @error = 8: cb_func isn't a function variable ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; that makes it much more performant for adding/deleting/inserting etc. ; ================================================================================================= Func _DynArraySort(ByRef $a_Array, Const $cb_Func = Default, Const $iDescending = 0, Const $b_Overwrite = True) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local $N = $a_Array[0] ; number of elements in $a_Array Local $w = UBound($a_Array) ; size of $a_Array (including empty values at the end) If $N > $w Or (Not IsInt($N)) Or $N < 0 Then Return SetError(7, 0, False) If $cb_Func = Default Then If $b_Overwrite Then Local $d_Ret = _ArraySort($a_Array, $iDescending, 1, $a_Array[0], 0, 1) Return SetError(@error, @extended, $d_Ret) Else Local $a_Temp = $a_Array Local $d_Ret = _ArraySort($a_Temp, $iDescending, 1, $a_Array[0], 0, 1) Return SetError(@error, $d_Ret, $a_Temp) EndIf Else If Not IsFunc($cb_Func) Then Return SetError(8, 0, False) If $b_Overwrite Then Local $b_Ret = _ArraySortFlexible($a_Array, $cb_Func, 1, $N) Return SetError(@error, @extended, $b_Ret) Else Local $a_Temp = $a_Array Local $b_Ret = _ArraySortFlexible($a_Temp, $cb_Func, 1, $N) Return SetError(@error, $b_Ret, $a_Temp) EndIf EndIf EndFunc ;==>_DynArraySort ; #FUNCTION# ====================================================================================== ; Name ..........: _ArraySortFlexible ; Description ...: sort an array with a user-defined sorting rule by choosing from Quicksort/Dual-Pivot-Quicksort/Insertion-Sort ; Syntax ........:_ArraySortFlexible(ByRef $a_Array, [$cb_Func = Default, [Const $i_Min = 0, [Const $i_Max = UBound($a_Array) - 1, [Const $b_MedianPivot = True, [Const $b_InsSort = True, [Const $d_SmallThreshold = 25, {Const $b_First = True}]]]]]]) ; Parameters ....: $a_Array - the array which should be sorted (by reference means direct manipulating of the array - no copy) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a UBound($a_Array) - 1 Then Return SetError(3, $i_Min, False) If $i_Min > $i_Max Then Return SetError(4, $i_Max - $i_Min, False) If Not IsFunc($cb_Func) Then Return SetError(5, 0, False) EndIf ; choose the sorting-algorithm: If $b_DualPivot Then ; Dual-Pivot-Quicksort __ArrayDualPivotQuicksort($a_Array, $cb_Func, $i_Min, $i_Max) ElseIf $b_InsSort And (($i_Max - $i_Min) < $d_SmallThreshold) Then ; insertion-sort: Switch $i_Max - $i_Min + 1 Case 2 __2Sort($cb_Func, $a_Array[$i_Min], $a_Array[$i_Max]) Case 3 __3Sort($cb_Func, $a_Array[$i_Min], $a_Array[$i_Min + 1], $a_Array[$i_Max]) Case 4 __4Sort($cb_Func, $a_Array[$i_Min], $a_Array[$i_Min + 1], $a_Array[$i_Min + 2], $a_Array[$i_Max]) Case 5 __5Sort($cb_Func, $a_Array[$i_Min], $a_Array[$i_Min + 1], $a_Array[$i_Min + 2], $a_Array[$i_Min + 3], $a_Array[$i_Max]) Case Else ; Insertion Sort Local $t1, $t2 For $i = $i_Min + 1 To $i_Max $t1 = $a_Array[$i] For $j = $i - 1 To $i_Min Step -1 $t2 = $a_Array[$j] If $cb_Func($t1, $t2) <> -1 Then ExitLoop $a_Array[$j + 1] = $t2 Next $a_Array[$j + 1] = $t1 Next EndSwitch Else ; Quicksort: ; the pivot element which divides the list in two separate lists (values < pivot -> left list, values > pivot -> right list); here pivot=list[random] to minimize the probability of worst case. Other solution is median(iMin, iMiddle, iMax) Das Trennelement (alles was kleiner ist - links davon, alles was größer ist - rechts davon), Hier Random damit Worst-Case unwahrscheinlich wird If $b_MedianPivot Then ; pivot = median(iMin, iMiddle, iMax) Local Const $iMiddle = Floor(($i_Max + $i_Min) / 2) Local Const $A = $a_Array[$i_Min], $b = $a_Array[$i_Max], $c = $a_Array[$iMiddle] Local $p_Value = $cb_Func($A, $b) = 1 ? $cb_Func($A, $c) = 1 ? $cb_Func($c, $b) = 1 ? $c : $b : $A : $cb_Func($A, $c) = 1 ? $A : $cb_Func($c, $b) = 1 ? $b : $c ; = Median(a,b,c) Local $p_Index = $p_Value = $A ? $i_Min : $p_Value = $b ? $i_Max : $iMiddle ; = Index(p_Value) Else ; pivot=list[random] Local $p_Index = Random($i_Min, $i_Max, 1) Local $p_Value = $a_Array[$p_Index] EndIf ; move the pivot-element to the end of the array If $p_Index < $i_Max Then $a_Array[$p_Index] = $a_Array[$i_Max] $a_Array[$i_Max] = $p_Value EndIf Local $i = __PartitionHoare($a_Array, $i_Min, $i_Max, $p_Value, $cb_Func) ; sort the left list (if length > 1) : If $i_Min < $i - 1 Then _ArraySortFlexible($a_Array, $cb_Func, $i_Min, $i - 1, False, False) ; recursively sort the right list (if length > 1): If $i_Max > $i + 1 Then _ArraySortFlexible($a_Array, $cb_Func, $i + 1, $i_Max, False, False) EndIf If $b_First And $2D Then $a_Array = _ArrayAinATo2d($a_Array) Return True EndFunc ;==>_ArraySortFlexible ; #FUNCTION# ====================================================================================== ; Name ..........: __ArrayDualPivotQuicksort ; Description ...: sort an array with the Dual-Pivot-Quicksort from Vladimir Yaroslavskiy ; Syntax ........:__ArrayDualPivotQuicksort(ByRef $A, [$cb_Func = Default, [Const $left = 0, [Const $right = UBound($a_Array) - 1, Const $d_SmThr = 25, [Const $b_MedQuant = True, {Const $b_First = True}]]]]]) ; Parameters ....: $A - the array which should be sorted (by reference means direct manipulating of the array - no copy) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a UBound($A) - 1 Then Return SetError(3, $right, False) If $left >= $right Then Return SetError(4, $right - $left, False) If Not IsFunc($cb_Func) Then Return SetError(5, 0, False) EndIf ;~ ; other sort-methods if range is small enough: Switch $d_Len + 1 Case 2 If $cb_Func($A[$left], $A[$right]) = 1 Then Local $t = $A[$right] $A[$right] = $A[$left] $A[$left] = $t EndIf Return True Case 3 __3Sort($cb_Func, $A[$left], $A[$left + 1], $A[$right]) Return True Case 4 __4Sort($cb_Func, $A[$left], $A[$left + 1], $A[$left + 2], $A[$right]) Return True Case 5 __5Sort($cb_Func, $A[$left], $A[$left + 1], $A[$left + 2], $A[$left + 3], $A[$right]) Return True Case 6 To $d_SmThr ; Insertion Sort For $i = $left + 1 To $right $t1 = $A[$i] For $j = $i - 1 To $left Step -1 $t2 = $A[$j] If $cb_Func($t1, $t2) <> -1 Then ExitLoop $A[$j + 1] = $t2 Next $A[$j + 1] = $t1 Next Return True EndSwitch ; ------------ estimate the two pivot-elements -------------------------- If $b_MedQuant And $d_Len > $d_SmThr Then ; by 25% and 75%-quantiles of five Local $d_third = Floor($d_Len / 3) ; Estimate the 25% / 75% -quantils better: Local $aIn[5] = [$left, Floor($left + $d_third), Floor($left + 0.5 * $d_Len), Floor($right - $d_third), $right] Local $aMp[5] = [$A[$aIn[0]], $A[$aIn[1]], $A[$aIn[2]], $A[$aIn[3]], $A[$aIn[4]]] ___5Sort($cb_Func, $aMp) ; find indices in source-array for sorted 5-array: For $i = 0 To 4 If $cb_Func($A[$aIn[$i]], $aMp[1]) = 0 Then Local $m1 = $aIn[$i] If $cb_Func($A[$aIn[$i]], $aMp[3]) = 0 Then Local $m2 = $aIn[$i] Next Else ; simple by choosing at actual index 25% and 75% Local $d_third = Floor($d_Len / $div) ;"medians" (at index 25% and 75%) Local $m1 = $left + $d_third Local $m2 = $right - $d_third If $m1 <= $left Then $m1 = $left + 1 If $m2 >= $right Then $m2 = $right - 1 EndIf ; ensure that m1 < m2 and move them to the outer fields If $cb_Func($A[$m1], $A[$m2]) = -1 Then __swap($A, $m1, $left) __swap($A, $m2, $right) Else __swap($A, $m1, $right) __swap($A, $m2, $left) EndIf ; pivots: Local $pivot1 = $A[$left] Local $pivot2 = $A[$right] ; pointers: Local $less = $left + 1 Local $great = $right - 1 ; sorting: $k = $less Do ; move elements < pivot1 to the beginning of the array If $cb_Func($A[$k], $pivot1) = -1 Then ; __swap($A, $k, $less) $t = $A[$k] $A[$k] = $A[$less] $A[$less] = $t $less += 1 ; move elements > pivot1 to the end of the array ElseIf $cb_Func($A[$k], $pivot2) = 1 Then While $k < $great And $cb_Func($A[$great], $pivot2) = 1 $great -= 1 WEnd ;__swap($A, $k, $great) $t = $A[$k] $A[$k] = $A[$great] $A[$great] = $t $great -= 1 If $cb_Func($A[$k], $pivot1) = -1 Then ;__swap($A, $k, $less) $t = $A[$k] $A[$k] = $A[$less] $A[$less] = $t $less += 1 EndIf EndIf $k += 1 Until $k > $great ; swaps Local $dist = $great - $less If $dist < 13 Then $div += 1 __swap($A, $less - 1, $left) __swap($A, $great + 1, $right) ; subarrays If ($less - 2 - $left) > 0 Then __ArrayDualPivotQuicksort($A, $cb_Func, $left, $less - 2, $div, $d_SmThr, $b_MedQuant, False) If ($right - ($great + 2)) > 0 Then __ArrayDualPivotQuicksort($A, $cb_Func, $great + 2, $right, $div, $d_SmThr, $b_MedQuant, False) ; equal elements If ($dist > ($d_Len - 13)) And ($cb_Func($pivot2, $pivot1) <> 0) Then $k = $less Do If $cb_Func($A[$k], $pivot1) = 0 Then ;__swap($A, $k, $less) $t = $A[$k] $A[$k] = $A[$less] $A[$less] = $t $less += 1 ElseIf $cb_Func($A[$k], $pivot2) = 0 Then ;__swap($A, $k, $great) $t = $A[$k] $A[$k] = $A[$great] $A[$great] = $t $great -= 1 If $cb_Func($A[$k], $pivot1) = 0 Then ;__swap($A, $k, $less) $t = $A[$k] $A[$k] = $A[$less] $A[$less] = $t $less += 1 EndIf EndIf $k += 1 Until $k > $great EndIf ; the middle subarray If $cb_Func($pivot1, $pivot2) = -1 And $great - $less > 0 Then __ArrayDualPivotQuicksort($A, $cb_Func, $less, $great, $div, $d_SmThr, $b_MedQuant, False) Return True EndFunc ;==>__ArrayDualPivotQuicksort ; #FUNCTION# ====================================================================================== ; Name ..........: _ArraySortInsertion ; Description ...: sort an array with a user-defined sorting rule with the insertion-sort algorithm ; Syntax ........:_ArraySortInsertion(ByRef $A, [$cb_Func = Default, [Const $i_Min = 0, [Const $i_Max = UBound($a_Array) - 1,{Const $b_First = True}]]]) ; Parameters ....: $a_Array - the array which should be sorted (by reference means direct manipulating of the array - no copy) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a -1 Then ExitLoop $A[$j + 1] = $t2 Next $A[$j + 1] = $t1 Next Return True EndFunc ;==>_ArraySortInsertion ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayHeapSortBinary ; Description ...: sort an array with Binary-Min-Heap-Sort algorithm ; Syntax ........: _ArrayHeapSortBinary(ByRef $A, [$cb_Func = Default, [$iMax = UBound($A) - 1]]) ; Parameters ....: $A - the [0]-based array which should be sorted ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a= UBound($A) Then Return SetError(2, 0, False) If Not IsFunc($cb_Func) Then Return SetError(3, 0, False) For $i = Floor($N / 2) To 0 Step -1 $j = $i ; ------------ create a binary heap for the range i-n: $k = $i * 2 + 1 $s = $A[$i] While $k < $N If $k + 1 < $N And $cb_Func($A[$k], $A[$k + 1]) = -1 Then $k += 1 If $cb_Func($s, $A[$k]) <> -1 Then ExitLoop $A[$j] = $A[$k] $j = $k $k = $j * 2 + 1 WEnd $A[$j] = $s Next For $N = $N - 1 To 0 Step -1 $s = $A[$N] $A[$N] = $A[0] $A[0] = $s ; ------------ create a binary heap for the the range 0-n: $j = 0 $k = 1 While $k < $N If $k + 1 < $N And $cb_Func($A[$k], $A[$k + 1]) = -1 Then $k += 1 If $cb_Func($s, $A[$k]) <> -1 Then ExitLoop $A[$j] = $A[$k] $j = $k $k = $j * 2 + 1 WEnd $A[$j] = $s Next Return True EndFunc ;==>_ArrayHeapSortBinary ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayHeapSortTernary ; Description ...: sort an array with Ternary-Min-Heap-Sort algorithm ; Syntax ........: _ArrayHeapSortTernary(ByRef $A, [$cb_Func = Default, [$iMax = UBound($A) - 1]]) ; Parameters ....: $A - the [0]-based array which should be sorted ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a= UBound($A) Then Return SetError(2, 0, False) If Not IsFunc($cb_Func) Then Return SetError(3, 0, False) For $i = Floor($N / 3) To 0 Step -1 ;----- Heapify($A, $i, $n) ------- $j = $i $k = $i * 3 + 1 $s = $A[$j] While $k < $N $m = $k + 1 $r = $m + 1 $x = $A[$k] If $r < $N Then $y = $A[$m] $z = $A[$r] $k = $cb_Func($x, $y) <> -1 ? $cb_Func($x, $z) <> -1 ? $k : $r : $cb_Func($y, $z) <> -1 ? $m : $r ; max child of i ElseIf $m < $N Then If $cb_Func($x, $A[$m]) = -1 Then $k = $m EndIf If $cb_Func($s, $A[$k]) <> -1 Then ExitLoop $A[$j] = $A[$k] $j = $k $k = $j * 3 + 1 WEnd $A[$j] = $s Next For $N = $N - 1 To 0 Step -1 ; swap(A, 0, i) $s = $A[$N] $A[$N] = $A[0] $A[0] = $s ;-------- Heapify($A, 0, $n) --------- $i = 0 $k = 1 While $k < $N $m = $k + 1 $r = $m + 1 $x = $A[$k] If $r < $N Then $y = $A[$m] $z = $A[$r] $k = $cb_Func($x, $y) <> -1 ? $cb_Func($x, $z) <> -1 ? $k : $r : $cb_Func($y, $z) <> -1 ? $m : $r ; max child of i ElseIf $m < $N Then If $cb_Func($x, $A[$m]) = -1 Then $k = $m EndIf If $cb_Func($s, $A[$k]) <> -1 Then ExitLoop $A[$i] = $A[$k] $i = $k $k = $i * 3 + 1 WEnd $A[$i] = $s Next EndFunc ;==>_ArrayHeapSortTernary ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayGetMax ; Description ...: determine the element with the maximum value by using a user comparison function ; Syntax ........: _ArrayGetMax(ByRef $a_A, [Const $cb_Func = Default, [Const $d_Start = 0, [Const $d_End = UBound($a_A) - 1]]]) ; Parameters ....: $a_A - the array (1D or 2D) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a$d_end) ; 3: $d_End > Array size ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayGetMax(ByRef $a_A, Const $cb_Func = Default, Const $d_Start = 0, Const $d_End = UBound($a_A) - 1) If $cb_Func = Default Then Return _ArrayMax($a_A) If (Not IsArray($a_A)) Or ($d_End = -1) Then Return SetError(1, UBound($a_A), -1) If $d_Start < 0 Or $d_Start > $d_End Then Return SetError(2, $d_Start, -1) If $d_End > (UBound($a_A) - 1) Then Return SetError(3, $d_Start, -1) If UBound($a_A, 2) > 1 Then ; 2D-Array should be convert into an array-in-array for better handling in $cb_Func Local $a_B = _Array2dToAinA($a_A) Local $a_Max = $a_B[$d_Start] For $i = $d_Start + 1 To $d_End If $cb_Func($a_B[$i], $a_Max) = 1 Then $a_Max = $a_B[$i] Next Else Local $a_Max = $a_A[0] For $i = $d_Start + 1 To $d_End If $cb_Func($a_A[$i], $a_Max) = 1 Then $a_Max = $a_A[$i] Next EndIf Return $a_Max EndFunc ;==>_ArrayGetMax ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayGetMin ; Description ...: determine the element with the minimum value by using a user comparison function ; Syntax ........: _ArrayGetMin(ByRef $a_A, [Const $cb_Func = Default, [Const $d_Start = 0, [Const $d_End = UBound($a_A) - 1]]]) ; Parameters ....: $a_A - the array (1D or 2D) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a$d_end) ; 3: $d_End > Array size ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayGetMin(ByRef $a_A, Const $cb_Func = Default, Const $d_Start = 0, Const $d_End = UBound($a_A) - 1) If $cb_Func = Default Then Return _ArrayMin($a_A) If (Not IsArray($a_A)) Or ($d_End = -1) Then Return SetError(1, UBound($a_A), -1) If $d_Start < 0 Or $d_Start > $d_End Then Return SetError(2, $d_Start, -1) If $d_End > (UBound($a_A) - 1) Then Return SetError(3, $d_Start, -1) If UBound($a_A, 2) > 1 Then ; 2D-Array should be convert into an array-in-array for better handling in $cb_Func Local $a_B = _Array2dToAinA($a_A) Local $a_Min = $a_B[$d_Start] For $i = $d_Start + 1 To $d_End If $cb_Func($a_B[$i], $a_Min) = -1 Then $a_Min = $a_B[$i] Next Else Local $a_Min = $a_A[0] For $i = $d_Start + 1 To $d_End If $cb_Func($a_A[$i], $a_Min) = -1 Then $a_Min = $a_A[$i] Next EndIf Return $a_Min EndFunc ;==>_ArrayGetMin ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayGetNthBiggestElement ; Description ...: determine the nth biggest element in an unsorted array without sorting it (faster) ; one possible application is the fast calculation of the median-value ; Syntax ........: _ArrayGetNthBiggestElement(ByRef $a_A, $d_Nth, $i_Min, $i_Max, Const $cb_Func) ; Parameters ....: $a_A - the array ; $d_Nth - the theoretical position of the wanted value if the array is sorted ; $i_Min - the start index for the partitioning range in the array ; $i_Max - the end index for the partitioning range in the array ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a $b ? $A > $c ? $c > $b ? $c : $b : $A : $A > $c ? $A : $c > $b ? $b : $c ; = Median(a,b,c) Local $p_Index = $p_Value = $A ? $i_Min : $p_Value = $b ? $i_Max : $iMiddle ; = Index(p_Value) ; move the pivot-element to the end of the array If $p_Index < $i_Max Then $a_A[$p_Index] = $a_A[$i_Max] $a_A[$i_Max] = $p_Value EndIf Local $i_PivotPos = __PartitionHoare($a_A, $i_Min, $i_Max, $p_Value) If $i_PivotPos = $d_Nth Then Return $a_A[$i_PivotPos] ElseIf $i_PivotPos > $d_Nth Then $i_Max = $i_PivotPos - 1 Else $i_Min = $i_PivotPos + 1 EndIf Until 0 Else ; if using a individual comparison function Do Local $iMiddle = Floor(($i_Max + $i_Min) / 2) Local $A = $a_A[$i_Min], $b = $a_A[$i_Max], $c = $a_A[$iMiddle] ; calculate the pivot element by median(Array[min], Array[middle], Array[max]) Local $p_Value = $cb_Func($A, $b) = 1 ? $cb_Func($A, $c) = 1 ? $cb_Func($c, $b) = 1 ? $c : $b : $A : $cb_Func($A, $c) = 1 ? $A : $cb_Func($c, $b) = 1 ? $b : $c ; = Median(a,b,c) Local $p_Index = $cb_Func($p_Value, $A) = 0 ? $i_Min : $cb_Func($p_Value, $b) = 0 ? $i_Max : $iMiddle ; = Index(p_Value) ; move the pivot-element to the end of the array If $p_Index < $i_Max Then $a_A[$p_Index] = $a_A[$i_Max] $a_A[$i_Max] = $p_Value EndIf Local $i_PivotPos = __PartitionHoare($a_A, $i_Min, $i_Max, $p_Value, $cb_Func) If $i_PivotPos = $d_Nth Then Return $a_A[$i_PivotPos] ElseIf $i_PivotPos > $d_Nth Then $i_Max = $i_PivotPos - 1 Else $i_Min = $i_PivotPos + 1 EndIf Until 0 EndIf EndFunc ;==>_ArrayGetNthBiggestElement ; #FUNCTION# ====================================================================================== ; Name ..........: _Dyn_ArrayIsSorted() ; Description ...: checks whether a semi-dynamic-array is already sorted with the ability of a user-defined sorting rule ; Syntax ........: _Dyn_ArrayIsSorted(ByRef $a_Array, [$cb_Func = Default]) ; Parameters ....: ByRef $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; Return values .: Success: True if array is already sorted - False if not ; Failure: @error is setted ; Author ........: AspirinJunkie ; Remarks .......: a "semi-dynamic" array only doubles and halve it's size when it's necessary ; that makes it much more performant for adding/deleting/inserting etc. ; ================================================================================================= Func _DynArrayIsSorted(ByRef $a_Array, $cb_Func = Default) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Return _ArrayIsSorted($a_Array, 1, $a_Array[0], $cb_Func) EndFunc ;==>_DynArrayIsSorted ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayIsSorted ; Description ...: checks whether an Array is already sorted ; Syntax ........: _ArrayIsSorted(ByRef $a_Array, [Const $i_Min = 0, [Const $i_Max = UBound($a_Array) - 1)]]) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form "function(ByRef Reduced-Value, value)" ; the function incrementally change the ReduceValue with the values ; $b_Withcount - Set true if the number of elements are written in the first element of $a_Array ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_EndIndex - the end index until the elements should be processed ; Return values .: Success: the reduced value ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid array size ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayIsSorted(ByRef $a_Array, Const $i_Min = 0, Const $i_Max = UBound($a_Array) - 1, $cb_Func = Default) If Not IsArray($a_Array) Then Return SetError(1, 0, False) If $i_Min > $i_Max Then Return SetError(2, $i_Max - $i_Min, False) If Not IsInt($i_Min) Or $i_Min < 0 Then Return SetError(3, $i_Min, False) If Not IsInt($i_Max) Or $i_Max > UBound($a_Array) - 1 Then Return SetError(4, $i_Min, False) If UBound($a_Array, 0) = 2 Then Local $2D = True $a_Array = _Array2dToAinA($a_Array) Else Local $2D = False EndIf For $i = $i_Min + 1 To $i_Max If $cb_Func = Default Then ; normal autoit-comparison If $a_Array[$i] < $a_Array[$i - 1] Then Return False Else ; user-defined comparison If $cb_Func($a_Array[$i], $a_Array[$i - 1]) = -1 Then Return False EndIf Next If $2D Then $a_Array = _ArrayAinATo2d($a_Array) Return True EndFunc ;==>_ArrayIsSorted ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayUnique ; Description ...: delete double elements from a dynamic array ; Syntax ........: _DynArrayUnique(Const ByRef $aA) ; Parameters ....: $aA - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; Return values .: Success: True ; Failure: False and set @error to none zero ; Author ........: AspirinJunkie ; ================================================================================================= Func _DynArrayUnique(ByRef $aA) ; by AspirinJunkie If Not __DynArrayIsValid($aA) Then Return SetError(@error, 0, False) Local $oD = ObjCreate('Scripting.Dictionary') For $i In $aA $oD($i) = 0 Next $aA = $oD.Keys() _DynArrayFromArray($aA, True, True) Return True EndFunc ;==>_DynArrayUnique ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayMap ; Description ...: apply a function to every element of a array ("map" the function) ; Syntax ........: _DynArrayMap(ByRef $a_Array, Const $cb_Func, Const $b_Overwrite = True, Const $b_CBWithIndex = False) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form function($value) or if $b_CBWithIndex: function($value, $index) ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_CBWithIndex - If true: $cb_Func has the form "function(element-value, element-index)" ; Return values .: Success: $b_Overwrite=True: True; Else: the converted semi-dynamic array ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array size isn't power of two (characteristic of the implemented semi-dynamic arrays) ; Author ........: AspirinJunkie ; Remarks .......: a semi-dynamic-array wrapper for the functiion _ArrayMap() ; ================================================================================================= Func _DynArrayMap(ByRef $a_Array, Const $cb_Func, Const $b_Overwrite = True, Const $b_CBWithIndex = False) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local Const $N = $a_Array[0] Return _ArrayMap($a_Array, $cb_Func, True, $b_Overwrite, $b_CBWithIndex, $N) EndFunc ;==>_DynArrayMap ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayMap ; Description ...: apply a function to every element of a array ("map" the function) ; Syntax ........: _ArrayMap(ByRef $a_Array, Const $cb_Func, Const $b_Withcount = False, Const $b_Overwrite = True, Const $b_CBWithIndex = False, $d_EndIndex = Default) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form function($value) or if $b_CBWithIndex: function($value, $index) ; $b_Withcount - Set true if the number of elements are written in the first element of $a_Array ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_CBWithIndex - If true: $cb_Func has the form "function(element-value, element-index)" ; $b_EndIndex - the end index until the elements should be processed ; Return values .: Success: $b_Overwrite=True: True; Else: the converted semi-dynamic array ; Failure: False ; @error = 1: $a_Array is'nt an array ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayMap(ByRef $a_Array, Const $cb_Func, Const $b_Withcount = False, Const $b_Overwrite = True, Const $b_CBWithIndex = False, $d_EndIndex = Default) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local Const $d_Start = $b_Withcount ? 1 : 0 If $d_EndIndex = Default Then $d_EndIndex = UBound($a_Array) - 1 If $b_CBWithIndex Then If $b_Overwrite Then For $i = $d_Start To $d_EndIndex $a_Array[$i] = $cb_Func($a_Array[$i], $i) Next Return True Else Local $a_Ret[UBound($a_Array)] = [$a_Array[0]] For $i = $d_Start To $d_EndIndex $a_Ret[$i] = $cb_Func($a_Array[$i], $i) Next Return $a_Ret EndIf Else If $b_Overwrite Then For $i = $d_Start To $d_EndIndex $a_Array[$i] = $cb_Func($a_Array[$i]) Next Return True Else Local $a_Ret[UBound($a_Array)] = [$a_Array[0]] For $i = $d_Start To $d_EndIndex $a_Ret[$i] = $cb_Func($a_Array[$i]) Next Return $a_Ret EndIf EndIf EndFunc ;==>_ArrayMap ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayFilter ; Description ...: filter the elements of an array with a external function ; Syntax ........: _DynArrayFilter(ByRef $a_Array, Const $cb_Func, Const $b_Overwrite = True) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form function($value) ; the function return True for the elements which should retain in the array ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; Return values .: Success: $b_Overwrite=True: True; Else: the filtered array ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array size isn't power of two (characteristic of the implemented semi-dynamic arrays) ; Author ........: AspirinJunkie ; Remarks .......: a semi-dynamic-array wrapper function for _ArrayFilter() ; ================================================================================================= Func _DynArrayFilter(ByRef $a_Array, Const $cb_Func, Const $b_Overwrite = True) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local Const $N = $a_Array[0] Return _ArrayFilter($a_Array, $cb_Func, True, $b_Overwrite, $N, True) EndFunc ;==>_DynArrayFilter ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayFilter ; Description ...: filter the elements of an array with a external function ; Syntax ........: _ArrayFilter(ByRef $a_Array, Const $cb_Func, Const $b_Withcount = False, Const $b_Overwrite = True, $d_EndIndex = Default, Const $b_IsDynArray = False) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form function($value) ; the function return True for the elements which should retain in the array ; $b_Withcount - Set true if the number of elements are written in the first element of $a_Array ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_EndIndex - the end index until the elements should be processed ; $b_IsDynArray - internal help parameter for _DynArrayMap() - if true a semi-dynamic-array is returned ; Return values .: Success: $b_Overwrite=True: True; Else: the filtered array ; Failure: False ; @error = 1: $a_Array is'nt an array ; 5: invalid value for $d_EndIndex ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayFilter(ByRef $a_Array, Const $cb_Func, Const $b_Withcount = False, Const $b_Overwrite = True, $d_EndIndex = Default, Const $b_IsDynArray = False) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local Const $w = UBound($a_Array) Local $d_Start = Int(Not ($b_Withcount = False)) Local $d_x = $d_Start ; counter for filtered elements If $d_EndIndex = Default Then $d_EndIndex = $w - 1 $d_EndIndex = Int($d_EndIndex) If $d_EndIndex < 1 Or $d_EndIndex >= $w Then Return SetError(5, 0, False) If $b_Overwrite Then For $i = $d_Start To $d_EndIndex If $cb_Func($a_Array[$i]) Then If $i > $d_x Then $a_Array[$d_x] = $a_Array[$i] $d_x += 1 EndIf Next If $b_Withcount Then $a_Array[0] = $d_x - 1 If $b_IsDynArray Then Local $d_v = __DynArrayGetNextPowerOfTwo($d_x) ReDim $a_Array[$d_v] For $i = $d_x To $d_v - 1 ; delete unused values $a_Array[$i] = "" Next Return True Else ReDim $a_Array[$d_x] EndIf Else Local $a_Ret[$w] For $i = $d_Start To $d_EndIndex If $cb_Func($a_Array[$i]) Then $a_Ret[$d_x] = $a_Array[$i] $d_x += 1 EndIf Next If $b_Withcount Then $a_Ret[0] = $d_x - 1 If $b_IsDynArray Then Local $d_v = __DynArrayGetNextPowerOfTwo($d_x) ReDim $a_Ret[$d_v] Else ReDim $a_Ret[$d_x] EndIf Return $a_Ret EndIf EndFunc ;==>_ArrayFilter ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayReduce ; Description ...: reduce the elements of a array to one value with an external function ; Syntax ........: _DynArrayReduce(ByRef $a_Array, Const $cb_Func) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $cb_Func - function variable points to a function of a form "function(ByRef Reduced-Value, value)" ; the function incrementally change the ReduceValue with the values ; Return values .: Success: the reduced value ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value in $a_Array[0]; ; 3: Array size isn't power of two (characteristic of the implemented semi-dynamic arrays) ; Author ........: AspirinJunkie ; Remarks .......: a semi-dynamic-array wrapper for _ArrayReduce() ; ================================================================================================= Func _DynArrayReduce(ByRef $a_Array, Const $cb_Func) If Not __DynArrayIsValid($a_Array) Then Return SetError(@error, 0, False) Local Const $N = $a_Array[0] Return _ArrayReduce($a_Array, $cb_Func, True, $N) EndFunc ;==>_DynArrayReduce ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayReduce ; Description ...: reduce the elements of a array to one value with an external function ; Syntax ........: _ArrayReduce(ByRef Const $a_Array, Const $cb_Func, Const $b_Withcount = False, $d_EndIndex = Default) ; Parameters ....: $a_Array - the array ; $cb_Func - function variable points to a function of a form "function(ByRef Reduced-Value, value)" ; the function incrementally change the ReduceValue with the values ; $b_Withcount - Set true if the number of elements are written in the first element of $a_Array ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; $b_EndIndex - the end index until the elements should be processed ; Return values .: Success: the reduced value ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid array size ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayReduce(ByRef Const $a_Array, Const $cb_Func, Const $b_Withcount = False, $d_EndIndex = Default) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local Const $w = UBound($a_Array) Local $d_Start = Int(Not ($b_Withcount = False)) If $w < $d_Start Then Return SetError(2, 0, False) Local $f_x = $a_Array[$d_Start] If $d_EndIndex = Default Then $d_EndIndex = $w - 1 $d_EndIndex = Int($d_EndIndex) If $d_EndIndex < 1 Or $d_EndIndex >= $w Then Return SetError(2, 0, False) For $i = $d_Start To $d_EndIndex $cb_Func($f_x, $a_Array[$i]) Next Return $f_x EndFunc ;==>_ArrayReduce ; #FUNCTION# ====================================================================================== ; Name ..........: _DynArrayFileList() ; Description ...: Lists files/folders under a folder with RegEx-filter-ability or fully customizable by an own Callback-Function ; Syntax ........: _DynArrayFileList($sSD, Const[ $sPat = '', Const[ $iF = 3]]) ; Parameters ....: $sSD - start folder (if more than one separate folders with '|') ; Const $sPat - [optional] regular pattern for file/folder-name match (default:'') ; alternative: a function-variable which leads to a custom function of the form "True/False <- Function(FilePath)" ; Const $iF - [optional] 1=only files, 2=only folders, 3=files+folders (default:3) ; Return values .: Success - Return a semi-dynamic array with absolute file/folder-paths ; Failure - Return "" and set @error ; Author ........: AspirinJunkie ; Remarks .......: traversing is iterative - not recursive ; Example .......: Yes ; #include "DynArray.au3" ; $a_Ret = _DynArrayFileList(@TempDir) ; _ArrayDisplay($a_Ret) ; ================================================================================================= Func _DynArrayFileList($sSD, Const $sPat = '', Const $iF = 3) ;by AspirinJunkie Local $aSubD[] = [0] For $i In StringSplit($sSD, '|', 2) If StringRight($i, 1) = '\' Then $i = StringTrimRight($i, 1) If Not FileExists($i) Then Return SetError(2, 0, "") _DynArrayPush($aSubD, $i) Next Local $FFFF, $FFNF, $sDir, $sRet = "" Local $hDLL = DllOpen('kernel32.dll') Local $p_F = DllCall($hDLL, "ptr", "GetProcAddress", "handle", DllCall($hDLL, "handle", "GetModuleHandleW", "wstr", "kernel32.dll")[0], "str", "GetFileAttributesW")[0] ; get the function address of GetModuleHandleW If Not ($iF = 3 Or $iF = 1 Or $iF = 2) Then Return SetError(3, 0, "") If IsFunc($sPat) Then While $aSubD[0] > 0 $sDir = _DynArrayPop($aSubD) $FFFF = FileFindFirstFile($sDir & '\*') If $FFFF <> -1 Then Do $FFNF = FileFindNextFile($FFFF) If @error Then ExitLoop If @extended Then If BitAND($iF, 2) Then If $sPat($sDir & '\' & $FFNF) Then $sRet &= $sDir & '\' & $FFNF & '|' EndIf If Not BitAND(DllCallAddress('dword', $p_F, 'wstr', $sDir & '\' & $FFNF)[0], 0x400) Then _DynArrayPush($aSubD, $sDir & '\' & $FFNF) ElseIf BitAND($iF, 1) Then If $sPat($sDir & '\' & $FFNF) Then $sRet &= $sDir & '\' & $FFNF & '|' EndIf Until 0 FileClose($FFFF) EndIf WEnd Else While $aSubD[0] > 0 $sDir = _DynArrayPop($aSubD) $FFFF = FileFindFirstFile($sDir & '\*') If $FFFF <> -1 Then Do $FFNF = FileFindNextFile($FFFF) If @error Then ExitLoop If @extended Then If BitAND($iF, 2) Then If StringRegExp($FFNF, $sPat) Then $sRet &= $sDir & '\' & $FFNF & '|' EndIf If Not BitAND(DllCallAddress('dword', $p_F, 'wstr', $sDir & '\' & $FFNF)[0], 0x400) Then _DynArrayPush($aSubD, $sDir & '\' & $FFNF) ElseIf BitAND($iF, 1) Then If StringRegExp($FFNF, $sPat) Then $sRet &= $sDir & '\' & $FFNF & '|' EndIf Until 0 FileClose($FFFF) EndIf WEnd EndIf DllClose($hDLL) Local $aRet = StringSplit(StringTrimRight($sRet, 1), '|', 1) ReDim $aRet[__DynArrayGetNextPowerOfTwo($aRet[0] + 1)] Return $aRet EndFunc ;==>_DynArrayFileList #Region helper functions ; #FUNCTION# ====================================================================================== ; Name ..........: __DynArrayIsValid() ; Description ...: checks if $a_Array is a correct semi-dynamic array ; Syntax ........: __DynArrayIsValid(ByRef $a_Array) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; Return values .: Success: True if $a_Array is valid ; Failure: False if $a_Array is not valid ; @error = 1: $a_Array is'nt an array ; Author ........: AspirinJunkie ; ================================================================================================= Func __DynArrayIsValid(ByRef $a_Array) If Not IsArray($a_Array) Then Return SetError(1, 0, False) Local $N = $a_Array[0] ; number of elements in $a_Array Local $w = UBound($a_Array) ; size of $a_Array (including empty values at the end) If $N > $w Or (Not IsInt($N)) Or $N < 0 Then Return SetError(2, 0, False) ; wrong value in $a_Array[0] If __DynArrayGetNextPowerOfTwo($N + 1) <> $w Then Return SetError(3, 0, False) ; unoptimal array dimension for element count Return True EndFunc ;==>__DynArrayIsValid ; #FUNCTION# ====================================================================================== ; Name ..........: __DynArrayRepair() ; Description ...: tries to fix a corrupted semi-dynamic array ; Syntax ........: __DynArrayRepair(ByRef $a_Array, Const $b_Overwrite = True) ; Parameters ....: $a_Array - the "semi-dynamic"-Array (needs an array with number of elements in $a_Array[0]) ; $b_Overwrite - If true: $a_Array gets overwritten; If false: no changes to $a_Array - new array will returned ; Return values .: Success: $b_Overwrite=True: True; Else: the repaired semi-dynamic array ; Failure: False if $a_Array could'nt repaired ; @error = 1: $a_Array is'nt an array ; Author ........: AspirinJunkie ; ================================================================================================= Func __DynArrayRepair(ByRef $a_Array, Const $b_Overwrite = True) If __DynArrayIsValid($a_Array) Then Return $b_Overwrite ? True : $a_Array If @error = 1 Then Return SetError(@error, 0, False) For $i = UBound($a_Array) - 1 To 1 Step -1 If $a_Array[$i] <> "" Then ExitLoop Next If $b_Overwrite Then $a_Array[0] = $i ReDim $a_Array[__DynArrayGetNextPowerOfTwo($i + 1)] Return True Else Local $a_Ret = $a_Array ReDim $a_Ret[__DynArrayGetNextPowerOfTwo($i + 1)] $a_Ret[0] = $i Return $a_Ret EndIf EndFunc ;==>__DynArrayRepair ; #FUNCTION# ====================================================================================== ; Name ..........: __DynArrayIsPowerOfTwo() ; Description ...: checks if a number is a power of two ; Syntax ........: __DynArrayIsPowerOfTwo($d_N) ; Parameters ....: $d_N - the number to which should be checked ; Return values .: Success: $d_N is power of two: True; Else: False ; Failure: False and set @error ; @error = 1: $d_N isn't a number datatype ; = 2: $d_N isn't a integer value ; = 3: $d_N is < 1 - invalid range for $d_N ; Author ........: AspirinJunkie ; ================================================================================================= Func __DynArrayIsPowerOfTwo($d_N) If Not IsNumber($d_N) Then Return SetError(1, 0, False) ; check for number If Not (Int($d_N) = $d_N) Then Return SetError(2, 0, False) ; check for integer $d_N = Int($d_N) If $d_N < 1 Then Return SetError(3, 0, False) ; check for valid range of values Return $d_N And Not BitAND($d_N, $d_N - 1) EndFunc ;==>__DynArrayIsPowerOfTwo ; #FUNCTION# ====================================================================================== ; Name ..........: __DynArrayGetNextPowerOfTwo() ; Description ...: rounds up to the next power of two of a given number ; Syntax ........: __DynArrayGetNextPowerOfTwo($d_N) ; Parameters ....: $d_N - the number to which should be checked ; Return values .: Success: the next rounded up power of two of $d_N ; Failure: False and set @error ; @error = 1: $d_N isn't a number datatype ; = 2: $d_N < 1 ; Author ........: AspirinJunkie ; ================================================================================================= Func __DynArrayGetNextPowerOfTwo($d_N) If Not IsNumber($d_N) Then Return SetError(1, 0, False) ; check for number If $d_N < 1 Then Return SetError(2, 0, 1) ; normally error but can be valid sometimes If Not IsInt($d_N) Then $d_N = Int(Ceiling($d_N)) If Not BitAND($d_N, $d_N - 1) Then Return $d_N While BitAND($d_N, $d_N - 1) $d_N = BitAND($d_N, $d_N - 1) WEnd Return BitShift($d_N, -1) EndFunc ;==>__DynArrayGetNextPowerOfTwo ; #FUNCTION# ====================================================================================== ; Name ..........: __DynArrayGetPreviousPowerOfTwo() ; Description ...: rounds down to the previous power of two of a given number ; Syntax ........: __DynArrayGetPreviousPowerOfTwo($d_N) ; Parameters ....: $d_N - the number to which should be checked ; Return values .: Success: the previous rounded down power of two of $d_N ; Failure: False and set @error ; @error = 1: $d_N isn't a number datatype ; = 2: $d_N < 1 ; Author ........: AspirinJunkie ; ================================================================================================= Func __DynArrayGetPreviousPowerOfTwo($d_N) If Not IsNumber($d_N) Then Return SetError(1, 0, False) ; check for number If $d_N < 1 Then Return SetError(2, 0, 1) ; normally error but can be valid sometimes If Not IsInt($d_N) Then $d_N = Int(Ceiling($d_N)) If Not BitAND($d_N, $d_N - 1) Then Return $d_N While BitAND($d_N, $d_N - 1) $d_N = BitAND($d_N, $d_N - 1) WEnd Return BitShift($d_N, -1) / 2 EndFunc ;==>__DynArrayGetPreviousPowerOfTwo ; #FUNCTION# ====================================================================================== ; Name ..........: __cb_NormalComparison ; Description ...: helper function which provides a standard AutoIt-comparison for flexible sorting ; Syntax ........: __cb_NormalComparison(ByRef Const $a, ByRef Const $b) ; Parameters ....: $a - the first value ; $b - the second value ; Return values .: 1: a > b ; 0: a = b ; -1: a < b ; Author ........: AspirinJunkie ; ================================================================================================= Func __cb_NormalComparison(ByRef Const $A, ByRef Const $b) Return $A > $b ? 1 : $A = $b ? 0 : -1 EndFunc ;==>__cb_NormalComparison ; #FUNCTION# ====================================================================================== ; Name ..........: __swap ; Description ...: helper function for swap two values inside an array ; Syntax ........: __swap(ByRef Const $a, ByRef Const $b) ; Parameters ....: $a - the array ; $i - index of value 1 ; $j - index of value 2 ; Return values .: - ; Author ........: AspirinJunkie ; ================================================================================================= Func __swap(ByRef $A, Const $i, Const $j) Local Const $t = $A[$i] $A[$i] = $A[$j] $A[$j] = $t EndFunc ;==>__swap ; #FUNCTION# ====================================================================================== ; Name ..........: __PartitionHoare ; Description ...: helper function for partitioning inside the quicksort-function ; there exists several algorithms for this. ; Syntax ........: __PartitionHoare(ByRef $a_Array, Const $i_Min, Const $i_Max, Const $p_Value, Const $cb_Func) ; Parameters ....: $a_Array - the array ; $i_Min - the start index for the partitioning range in the array ; $i_Max - the end index for the partitioning range in the array ; $p_Value - the value of the pivot-element ; $cb_Func - function variable points to a function of a form "[1|0|-1] function(value, value)" ; the function compares two values a,and b for a>b/a=b/a $p_Value Or $i = $i_Max ; swap if elements are on the wrong side of the lists If $i < $j Then $t = $a_Array[$j] $a_Array[$j] = $a_Array[$i] $a_Array[$i] = $t EndIf Until $i >= $j ; swap with pivot-element if pivot is at the wrong list-side: If $a_Array[$i] > $p_Value Then $a_Array[$i_Max] = $a_Array[$i] $a_Array[$i] = $p_Value EndIf Else ; if using a individual comparison function Do ; start from right and go left until the next element which is smaller than pivot: Do $j -= 1 Until $cb_Func($a_Array[$j], $p_Value) = -1 Or $j = $i_Min ; start from left and go right until the next element which is greater than pivot: Do $i += 1 Until $cb_Func($a_Array[$i], $p_Value) = 1 Or $i = $i_Max ; swap if elements are on the wrong side of the lists If $i < $j Then $t = $a_Array[$j] $a_Array[$j] = $a_Array[$i] $a_Array[$i] = $t EndIf Until $i >= $j ; swap with pivot-element if pivot is at the wrong list-side: If $cb_Func($a_Array[$i], $p_Value) = 1 Then $a_Array[$i_Max] = $a_Array[$i] $a_Array[$i] = $p_Value EndIf EndIf Return $i EndFunc ;==>__PartitionHoare ; #FUNCTION# ====================================================================================== ; Name ..........: _Array2dToAinA() ; Description ...: Convert a 2D array into a Arrays in Array ; Syntax ........: _Array2dToAinA(ByRef $A) ; Parameters ....: $A - the 2D-Array which should be converted ; Return values .: Success: a Arrays in Array build from the input array ; Failure: False ; @error = 1: $A is'nt an 2D array ; Author ........: AspirinJunkie ; ================================================================================================= Func _Array2dToAinA(ByRef $A) If UBound($A, 0) <> 2 Then Return SetError(1, UBound($A, 0), False) Local $N = UBound($A), $u = UBound($A, 2) Local $a_Ret[$N] For $i = 0 To $N - 1 Local $t[$u] For $j = 0 To $u - 1 $t[$j] = $A[$i][$j] Next $a_Ret[$i] = $t Next Return $a_Ret EndFunc ;==>_Array2dToAinA ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayAinATo2d() ; Description ...: Convert a Arrays in Array into a 2D array ; Syntax ........: _ArrayAinATo2d(ByRef $A) ; Parameters ....: $A - the arrays in array which should be converted ; Return values .: Success: a 2D Array build from the input array ; Failure: False ; @error = 1: $A is'nt an 1D array ; = 2: $A is empty ; = 3: first element isn't a array ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayAinATo2d(ByRef $A) If UBound($A, 0) <> 1 Then Return SetError(1, UBound($A, 0), False) Local $N = UBound($A) If $N < 1 Then Return SetError(2, $N, False) Local $u = UBound($A[0]) If $u < 1 Then Return SetError(3, $u, False) Local $a_Ret[$N][$u] For $i = 0 To $N - 1 Local $t = $A[$i] If UBound($t) > $u Then ReDim $a_Ret[$N][UBound($t)] For $j = 0 To UBound($t) - 1 $a_Ret[$i][$j] = $t[$j] Next Next Return $a_Ret EndFunc ;==>_ArrayAinATo2d ; #FUNCTION# ====================================================================================== ; Name ..........: _2Sort() ; Description ...: sorts two values with minimal count of comparisons ; Syntax ........: _2Sort(ByRef $A, ByRef $B) ; Parameters ....: $A, $B - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func _2Sort(ByRef $A, ByRef $b) If $A > $b Then Local $t = $b $b = $A $A = $t EndIf EndFunc ;==>_2Sort ; #FUNCTION# ====================================================================================== ; Name ..........: __2Sort() ; Description ...: sorts two values with minimal count of comparisons and custom comparison function ; Syntax ........:__2Sort(Const $f, ByRef $A, ByRef $b) ; Parameters ....: $A, $B - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func __2Sort(Const $f, ByRef $A, ByRef $b) If $f($A, $b) = 1 Then Local $t = $b $b = $A $A = $t EndIf EndFunc ;==>__2Sort ; #FUNCTION# ====================================================================================== ; Name ..........: _3Sort() ; Description ...: sorts three values with minimal count of comparisons ; Syntax ........: _3Sort(ByRef $A, ByRef $B, ByRef $C) ; Parameters ....: $A, $B, $C - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func _3Sort(ByRef $A, ByRef $b, ByRef $c) Local $t If $b > $A Then If $b > $c Then If $c > $A Then ; (A, C, B) $t = $b $b = $c $c = $t Else ; (C, A, B) $t = $A $A = $c $c = $b $b = $t EndIf EndIf Else If $c > $A Then ; (B, A, C) $t = $A $A = $b $b = $t ElseIf $c > $b Then ; (B, C, A) $t = $A $A = $b $b = $c $c = $t Else ; (C, B, A) $t = $A $A = $c $c = $t EndIf EndIf EndFunc ;==>_3Sort ; #FUNCTION# ====================================================================================== ; Name ..........: __3Sort() ; Description ...: sorts three values with minimal count of comparisons and custom comparison function ; Syntax ........: __3Sort(Const $f, ByRef $A, ByRef $b, ByRef $c) ; Parameters ....: $f - the comparison function ; $A, $B, $C - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func __3Sort(Const $f, ByRef $A, ByRef $b, ByRef $c) Local $t If $f($b, $A) = 1 Then If $f($b, $c) = 1 Then If $f($c, $A) = 1 Then ; (A, C, B) $t = $b $b = $c $c = $t Else ; (C, A, B) $t = $A $A = $c $c = $b $b = $t EndIf EndIf Else If $f($c, $A) = 1 Then ; (B, A, C) $t = $A $A = $b $b = $t ElseIf $f($c, $b) = 1 Then ; (B, C, A) $t = $A $A = $b $b = $c $c = $t Else ; (C, B, A) $t = $A $A = $c $c = $t EndIf EndIf EndFunc ;==>__3Sort ; #FUNCTION# ====================================================================================== ; Name ..........: _4Sort() ; Description ...: sorts four values with minimal count of comparisons ; Syntax ........: _4Sort(ByRef $A, ByRef $B, ByRef $C, ByRef $D) ; Parameters ....: $A, $B, $C, $D - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func _4Sort(ByRef $A, ByRef $b, ByRef $c, ByRef $d) Local $t If $A > $c Then $t = $c $c = $A $A = $t EndIf If $b > $d Then $t = $b $b = $d $d = $t EndIf If $A > $b Then $t = $A $A = $b $b = $t EndIf If $c > $d Then $t = $c $c = $d $d = $t EndIf If $b > $c Then $t = $c $c = $b $b = $t EndIf EndFunc ;==>_4Sort ; #FUNCTION# ====================================================================================== ; Name ..........: __4Sort() ; Description ...: sorts four values with minimal count of comparisons and custom comparison function ; Syntax ........: __4Sort(Const $f, ByRef $A, ByRef $b, ByRef $c, ByRef $D) ; Parameters ....: $f - the comparison function ; $A, $B, $C, $D - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func __4Sort(Const $f, ByRef $A, ByRef $b, ByRef $c, ByRef $d) Local $t If $f($A, $c) = 1 Then $t = $c $c = $A $A = $t EndIf If $f($b, $d) = 1 Then $t = $b $b = $d $d = $t EndIf If $f($A, $b) = 1 Then $t = $A $A = $b $b = $t EndIf If $f($c, $d) = 1 Then $t = $c $c = $d $d = $t EndIf If $f($b, $c) = 1 Then $t = $c $c = $b $b = $t EndIf EndFunc ;==>__4Sort ; #FUNCTION# ====================================================================================== ; Name ..........: _5Sort() ; Description ...: sorts five values with minimal count of comparisons ; Syntax ........: _5Sort(ByRef $A, ByRef $B, ByRef $C, ByRef $D, ByRef $E) ; Parameters ....: $A, $B, $C, $D, $D - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func _5Sort(ByRef $A, ByRef $b, ByRef $c, ByRef $d, ByRef $e) Local $t If $A < $b Then ; if a < b: a, b = b, a $t = $b $b = $A $A = $t EndIf If $c < $d Then ; if c < d: c, d = d, c $t = $c $c = $d $d = $t EndIf If $A < $c Then ; if a < c: a, b, c, d = c, d, a, b $t = $c $c = $A $A = $t $t = $d $d = $b $b = $t EndIf If $e < $c Then ;~ if e < c: If $e > $d Then ; if e > d: d, e = e, d $t = $d $d = $e $e = $t EndIf ElseIf $e < $A Then ; if e < a: c, d, e = e, c, d $t = $c $c = $e $e = $d $d = $t Else ;~ else: a, c, d, e = e, a, c, d $t = $A $A = $e $e = $d $d = $c $c = $t EndIf If $b < $d Then ; if b < d: If $b < $e Then ; if b < e: return b, e, d, c, a $t = $A $A = $b $b = $e $e = $t $t = $c $c = $d $d = $t Else ; else: return e, b, d, c, a $t = $A $A = $e $e = $t $t = $c $c = $d $d = $t EndIf Else If $b < $c Then ; if b < c: return e, d, b, c, a $t = $A $A = $e $e = $t $t = $b $b = $d $d = $c $c = $t Else ; else: return e, d, c, b, a $t = $A $A = $e $e = $t $t = $b $b = $d $d = $t EndIf EndIf EndFunc ;==>_5Sort ; #FUNCTION# ====================================================================================== ; Name ..........: __5Sort() ; Description ...: sorts five values with minimal count of comparisons and custom comparison function ; Syntax ........: __5Sort(Const $f, ByRef $A, ByRef $b, ByRef $c, ByRef $D, ByRef $E) ; Parameters ....: $f - the comparison function ; $A, $B, $C, $D, $D - the values to be sorted ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func __5Sort(Const $f, ByRef $A, ByRef $b, ByRef $c, ByRef $d, ByRef $e) Local $t If $f($A, $b) = -1 Then ; if a < b: a, b = b, a $t = $b $b = $A $A = $t EndIf If $f($c, $d) = -1 Then ; if c < d: c, d = d, c $t = $c $c = $d $d = $t EndIf If $f($A, $c) = -1 Then ; if a < c: a, b, c, d = c, d, a, b $t = $c $c = $A $A = $t $t = $d $d = $b $b = $t EndIf If $f($e, $c) = -1 Then ;~ if e < c: If $f($e, $d) = 1 Then ; if e > d: d, e = e, d $t = $d $d = $e $e = $t EndIf ElseIf $f($e, $A) = -1 Then ; if e < a: c, d, e = e, c, d $t = $c $c = $e $e = $d $d = $t Else ;~ else: a, c, d, e = e, a, c, d $t = $A $A = $e $e = $d $d = $c $c = $t EndIf If $f($b, $d) = -1 Then ; if b < d: If $f($b, $e) = -1 Then ; if b < e: return b, e, d, c, a $t = $A $A = $b $b = $e $e = $t $t = $c $c = $d $d = $t Else ; else: return e, b, d, c, a $t = $A $A = $e $e = $t $t = $c $c = $d $d = $t EndIf Else If $f($b, $c) = -1 Then ; if b < c: return e, d, b, c, a $t = $A $A = $e $e = $t $t = $b $b = $d $d = $c $c = $t Else ; else: return e, d, c, b, a $t = $A $A = $e $e = $t $t = $b $b = $d $d = $t EndIf EndIf EndFunc ;==>__5Sort ; #FUNCTION# ====================================================================================== ; Name ..........: ___5Sort() ; Description ...: sorts an 5-value Array with minimal count of comparisons and custom comparison function ; Syntax ........: ___5Sort(Const $f, ByRef $A) ; Parameters ....: $f - the comparison function ; $A - the 5 element array ; Return values .: Success: - ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func ___5Sort(Const $f, ByRef $A) Local $t If $f($A[0], $A[1]) = -1 Then ; if a < b: a, b = b, a $t = $A[1] $A[1] = $A[0] $A[0] = $t EndIf If $f($A[2], $A[3]) = -1 Then ; if c < d: c, d = d, c $t = $A[2] $A[2] = $A[3] $A[3] = $t EndIf If $f($A[0], $A[2]) = -1 Then ; if a < c: a, b, c, d = c, d, a, b $t = $A[2] $A[2] = $A[0] $A[0] = $t $t = $A[3] $A[3] = $A[1] $A[1] = $t EndIf If $f($A[4], $A[2]) = -1 Then ;~ if e < c: If $f($A[4], $A[3]) = 1 Then ; if e > d: d, e = e, d $t = $A[3] $A[3] = $A[4] $A[4] = $t EndIf ElseIf $f($A[4], $A[0]) = -1 Then ; if e < a: c, d, e = e, c, d $t = $A[2] $A[2] = $A[4] $A[4] = $A[3] $A[3] = $t Else ;~ else: a, c, d, e = e, a, c, d $t = $A[0] $A[0] = $A[4] $A[4] = $A[3] $A[3] = $A[2] $A[2] = $t EndIf If $f($A[1], $A[3]) = -1 Then ; if b < d: If $f($A[1], $A[4]) = -1 Then ; if b < e: return b, e, d, c, a Local $b[5] = [$A[1], $A[4], $A[3], $A[2], $A[0]] $A = $b Else ; else: return e, b, d, c, a Local $b[5] = [$A[4], $A[1], $A[3], $A[2], $A[0]] $A = $b EndIf Else If $f($A[1], $A[2]) = -1 Then ; if b < c: return e, d, b, c, a Local $b[5] = [$A[4], $A[3], $A[1], $A[2], $A[0]] $A = $b Else ; else: return e, d, c, b, a Local $b[5] = [$A[4], $A[3], $A[2], $A[1], $A[0]] $A = $b EndIf EndIf EndFunc ;==>___5Sort ; #FUNCTION# ====================================================================================== ; Name ..........: _ArraySortWithList ; Description ...: sort an array with by using the COM-Object ArrayList ; Syntax ........: _ArraySortWithList(ByRef $A, $b_Desc = False) ; Parameters ....: $A - the [0]-based array which should be sorted ; $b_Desc - set True if sort order should be descending ; Return values .: Success: - array is sorted now ; Failure: - ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArraySortWithList(ByRef $A, $b_Desc = False) Local $AL = ObjCreate("System.Collections.ArrayList") ; convert AutoIt-Array into System.Collections.ArrayList $AL.Capacity = UBound($A) For $i In $A $AL.Add($i) Next $AL.Sort If $b_Desc Then $AL.Reverse() $A = $AL.ToArray() EndFunc ;==>_ArraySortWithList #EndRegion helper functions #Region also interesting functions ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayHeapSortBinary_Native ; Description ...: sort an array with Binary-Heap-Sort algorithm ; Syntax ........: _ArrayHeapSortBinary_Native(ByRef $A) ; Parameters ....: $A - the [0]-based array which should be sorted ; $iMax - the end index until the array should get sorted ; Return values .: Success: True - array is sorted now ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value for $iMax ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayHeapSortBinary_Native(ByRef $A, $iMax = UBound($A) - 1) Local $N = $iMax + 1 Local $k, $s, $j ; error-handling: If Not IsArray($A) Then Return SetError(1, 0, False) If $iMax >= UBound($A) Then Return SetError(2, 0, False) For $i = Floor($N / 2) To 0 Step -1 $j = $i ; ------------ create a binary heap for the range i-n: $k = $i * 2 + 1 $s = $A[$i] While $k < $N If $k + 1 < $N And $A[$k] < $A[$k + 1] Then $k += 1 If $s >= $A[$k] Then ExitLoop $A[$j] = $A[$k] $j = $k $k = $j * 2 + 1 WEnd $A[$j] = $s Next For $N = $N - 1 To 0 Step -1 $s = $A[$N] $A[$N] = $A[0] $A[0] = $s ; ------------ create a binary heap for the the range 0-n: $j = 0 $k = 1 While $k < $N If $k + 1 < $N And $A[$k] < $A[$k + 1] Then $k += 1 If $s >= $A[$k] Then ExitLoop $A[$j] = $A[$k] $j = $k $k = $j * 2 + 1 WEnd $A[$j] = $s Next Return True EndFunc ;==>_ArrayHeapSortBinary_Native ; #FUNCTION# ====================================================================================== ; Name ..........: _ArrayHeapSortTernary_Native ; Description ...: sort an array with Ternary-Heap-Sort algorithm ; Syntax ........: _ArrayHeapSortTernary_Native(ByRef $A) ; Parameters ....: $A - the [0]-based array which should be sorted ; $iMax - the end index until the array should get sorted ; Return values .: Success: True - array is sorted now ; Failure: False ; @error = 1: $a_Array is'nt an array ; 2: invalid value for $iMaxnc ; Author ........: AspirinJunkie ; ================================================================================================= Func _ArrayHeapSortTernary_Native(ByRef $A, $iMax = UBound($A) - 1) Local $N = $iMax + 1 Local $i, $j, $s Local $k, $m, $r, $x, $y, $z ; error-handling: If Not IsArray($A) Then Return SetError(1, 0, False) If $iMax >= UBound($A) Then Return SetError(2, 0, False) For $i = Floor($N / 3) To 0 Step -1 ;----- Heapify($A, $i, $n) ------- $j = $i $k = $i * 3 + 1 $s = $A[$j] While $k < $N $m = $k + 1 $r = $m + 1 $x = $A[$k] If $r < $N Then $y = $A[$m] $z = $A[$r] $k = $x > $y ? $x > $z ? $k : $r : $y > $z ? $m : $r ; max child of i ElseIf $m < $N Then If $x < $A[$m] Then $k = $m EndIf If $s >= $A[$k] Then ExitLoop $A[$j] = $A[$k] $j = $k $k = $j * 3 + 1 WEnd $A[$j] = $s Next For $N = $N - 1 To 0 Step -1 ; swap(A, 0, i) $s = $A[$N] $A[$N] = $A[0] $A[0] = $s ;-------- Heapify($A, 0, $n) --------- $i = 0 $k = 1 While $k < $N $m = $k + 1 $r = $m + 1 $x = $A[$k] If $r < $N Then $y = $A[$m] $z = $A[$r] $k = $x > $y ? $x > $z ? $k : $r : $y > $z ? $m : $r ; max child of i ElseIf $m < $N Then If $x < $A[$m] Then $k = $m EndIf If $s >= $A[$k] Then ExitLoop $A[$i] = $A[$k] $i = $k $k = $i * 3 + 1 WEnd $A[$i] = $s Next EndFunc ;==>_ArrayHeapSortTernary_Native #EndRegion also interesting functions