#include-once

; #INDEX# =======================================================================================================================
; Title .........: _ArraySortStable2D
; AutoIt Version : 3.3.14.2
; Date ..........: 30.03.2018
; Language ......: English
; Description ...: A function two sort a two dimensional array with a stable sorting algorithm (MergeSort).
; Author(s) .....: alpines
; ===============================================================================================================================

; #CURRENT# =====================================================================================================================
; _ArraySortStable2D
; ===============================================================================================================================

; #INTERNAL_USE_ONLY#============================================================================================================
; __ArraySortStable2D_Sort
; __ArraySortStable2D_Merge
; __ArraySortStable2D_Compare
; ===============================================================================================================================

; #FUNCTION# ====================================================================================================================
; Name ..........: _ArraySortStable2D
; Description ...: Sorts a valid two dimensional array with a stable mergesort implementation
; Syntax ........: _ArraySortStable2D(ByRef $aArray, $iCol[, $iStart = Default[, $iEnd = Default[, $bDescending = False]]])
; Parameters ....: $aArray              - [in/out] An array of values to sort.
;                  $iCol                - The column to sort and perform the equality check on.
;                  $iStart              - [optional] Start row of the sorting. Default is Default (Begin).
;                  $iEnd                - [optional] End row of the sorting. Default is Default (End).
;                  $bDescending         - [optional] Decides whether the array should be sorted descending. Default is False (Ascending).
; Return values .: True on success
;				   False on bad input and sets @error to non-zero.
;					@error:	1 - Array is not two dimensional.
;							2 - Start index is invalid (smaller than 0 or greater than size the size of the array)
;							3 - End index is invalid (smaller than 0 or greater than the size of the array)
;							4 - Start index is bigger or equal the end index
;							5 - Column index is invalid (smaller than 0 or greater than the second dimension of the array)
; Author ........: alpines
; Modified ......:
; Remarks .......: This algorithmn uses a stable MergeSort implementation where the item exchanges are also performed on the other indices.
;				   If this algorithm sorts data differently than others it is most likely due to the internal __ArraySortStable2D_Compare function which
;				   compares two strings and says which one is comes first in the order process.
; Related .......:
; Link ..........: autoit.de
; Example .......: No
; ===============================================================================================================================
Func _ArraySortStable2D(ByRef $aArray, $iCol, $iStart = Default, $iEnd = Default, $bDescending = False)
	If UBound($aArray, 0) <> 2 Then Return SetError(1, 0, False)

	If $iStart = Default Then $iStart = 0
	If $iEnd = Default Then $iEnd = UBound($aArray) - 1

	If $iStart < 0 or $iStart >= UBound($aArray) Then Return SetError(2, 0, False)
	If $iEnd >= UBound($aArray) or $iEnd < 0 Then Return SetError(3, 0, False)
	If $iStart >= $iEnd Then Return SetError(4, 0, False)

	If $iCol < 0 or $iCol >= UBound($aArray, 2) Then SetError(5, 0, False)

	Local $aCopyArray[$iEnd - $iStart + 1][UBound($aArray, 2)]
	For $i = $iStart To $iEnd
		For $j = 0 To UBound($aArray, 2) - 1
			$aCopyArray[$i - $iStart][$j] = $aArray[$i][$j]
		Next
	Next

	__ArraySortStable2D_Sort($aCopyArray, $iCol, $bDescending)
	For $i = $iStart To $iEnd
		For $j = 0 To UBound($aArray, 2) - 1
			$aArray[$i][$j] = $aCopyArray[$i - $iStart][$j]
		Next
	Next

	Return True
EndFunc

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __ArraySortStable2D_Sort
; Description ...: The recursive function to sort the array given to _ArraySortStable2D
; Syntax ........: __ArraySortStable2D_Sort(Byref $aArray, $iCol, $bDescending)
; Parameters ....: $aArray              - [in/out] an array of values to sort
;                  $iCol                - The column to sort and perform the equality check on.
;                  $bDescending         - Decides whether the array should be sorted descending. Default is False (Ascending).
; Return values .: None
; Author ........: alpines
; Modified ......:
; Remarks .......: AutoIt might prevent excessive stack recursion levels so be careful how much data you want to sort.
; Related .......:
; Link ..........: autoit.de
; Example .......: No
; ===============================================================================================================================
Func __ArraySortStable2D_Sort(ByRef $aArray, $iCol, $bDescending)
	If UBound($aArray) <= 1 Then Return $aArray

	Local $aSplitLeft[Floor(UBound($aArray) / 2)][UBound($aArray, 2)]
	Local $aSplitRight[Ceiling(UBound($aArray) / 2)][UBound($aArray, 2)]

	For $i = 0 To UBound($aArray) - 1
		If $i < UBound($aSplitLeft) Then
			For $j = 0 To UBound($aArray, 2) - 1
				$aSplitLeft[$i][$j] = $aArray[$i][$j]
			Next
		Else
			For $j = 0 To UBound($aArray, 2) - 1
				$aSplitRight[$i - UBound($aSplitLeft)][$j] = $aArray[$i][$j]
			Next
		EndIf
	Next

	__ArraySortStable2D_Sort($aSplitLeft, $iCol, $bDescending)
	__ArraySortStable2D_Sort($aSplitRight, $iCol, $bDescending)

	$aArray = __ArraySortStable2D_Merge($aSplitLeft, $aSplitRight, $iCol, $bDescending)
EndFunc

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __ArraySortStable2D_Merge
; Description ...: The merge function two merge two split arrays together in an ascending or descending order
; Syntax ........: __ArraySortStable2D_Merge(Byref $aLeftArray, Byref $aRightArray, $iCol, $bDescending)
; Parameters ....: $aLeftArray          - [in/out] The left side of the merging process list.
;                  $aRightArray         - [in/out] The right side of the merging process list.
;                  $iCol                - The column two sort and perform the equality check on.
;                  $bDescending         - Decides whether the array should be sorted descending. Default is False (Ascending).
; Return values .: The combined ordered array or the two lists.
; Author ........: alpines
; Modified ......:
; Remarks .......:
; Related .......:
; Link ..........: autoit.de
; Example .......: No
; ===============================================================================================================================
Func __ArraySortStable2D_Merge(ByRef $aLeftArray, ByRef $aRightArray, $iCol, $bDescending)
	Local $aReturnArray[UBound($aLeftArray) + UBound($aRightArray)][UBound($aLeftArray, 2)]
	Local $iLeftIndex = 0, $iRightIndex = 0

	While $iLeftIndex < UBound($aLeftArray) and $iRightIndex < UBound($aRightArray)
		Local $iCompare = __ArraySortStable2D_Compare($aLeftArray[$iLeftIndex][$iCol], $aRightArray[$iRightIndex][$iCol])

		If (($iCompare = -1 or $iCompare = 0) and Not $bDescending) or (($iCompare = 1 or $iCompare = 0) and $bDescending) Then
			For $i = 0 To UBound($aLeftArray, 2) - 1
				$aReturnArray[$iLeftIndex + $iRightIndex][$i] = $aLeftArray[$iLeftIndex][$i]
			Next
			$iLeftIndex += 1
		ElseIf (($iCompare = 1 or $iCompare = 0) and Not $bDescending) or (($iCompare = -1 or $iCompare = 0) and $bDescending) Then
			For $i = 0 To UBound($aRightArray, 2) - 1
				$aReturnArray[$iLeftIndex + $iRightIndex][$i] = $aRightArray[$iRightIndex][$i]
			Next
			$iRightIndex += 1
		EndIf
	WEnd

	While $iLeftIndex < UBound($aLeftArray)
		For $i = 0 To UBound($aLeftArray, 2) - 1
			$aReturnArray[$iLeftIndex + $iRightIndex][$i] = $aLeftArray[$iLeftIndex][$i]
		Next
		$iLeftIndex += 1
	WEnd

	While $iRightIndex < UBound($aRightArray)
		For $i = 0 To UBound($aRightArray, 2) - 1
			$aReturnArray[$iLeftIndex + $iRightIndex][$i] = $aRightArray[$iRightIndex][$i]
		Next
		$iRightIndex += 1
	WEnd

	Return $aReturnArray
EndFunc

; #INTERNAL_USE_ONLY# ===========================================================================================================
; Name ..........: __ArraySortStable2D_Compare
; Description ...: The internal compare function which determines which of the two values should come first in the list.
; Syntax ........: __ArraySortStable2D_Compare($L, $R)
; Parameters ....: $L                   - A value from the left array of a merge process.
;                  $R                   - A value from the right array of a merge process.
; Return values .: -1 - The left item should come first.
;				    0 - Both items are equal.
;				    1 - The right item should come first.
; Author ........: alpines
; Modified ......:
; Remarks .......:
; Related .......:
; Link ..........: autoit.de
; Example .......: No
; ===============================================================================================================================
Func __ArraySortStable2D_Compare($L, $R)
	Local $iLen1 = StringLen($L)
	Local $iLen2 = StringLen($R)
	Local $iSmallLen = $iLen1 < $iLen2 ? $iLen1 : $iLen2

	For $x = 1 To $iSmallLen
		If AscW(StringMid(StringUpper($L), $x, 1)) < AscW(StringMid(StringUpper($R), $x, 1)) Then Return -1
		If AscW(StringMid(StringUpper($L), $x, 1)) > AscW(StringMid(StringUpper($R), $x, 1)) Then Return 1
	Next

	Return $iLen1 < $iLen2 ? -1 : $iLen1 > $iLen2 ? 1 : 0
EndFunc