v2: Added Array.Sort(). #297

jeeswg · 2022-08-25T18:54:27Z

Documentation

Array.Sort([Options] [, Function])

E.g.:
MyArray.Sort()
MyArray.Sort(Options)
MyArray.Sort(Options, Function)
MyArray.Sort(Function)

For comparison:
SortedString := Sort(String [, Options, Function])

In comparison to the Sort function:

Smart parameters. The Options parameter can be omitted. This allows for MyArray.Sort(Function) syntax, common in many programming languages.
Not relevant: D and Z options.
Not implemented: U option.
Custom comparator functions can receive variables (array items) of any type, not just strings, including 'unset' and objects.

Implementation

At present, struct Variant has been made public.
At present, a random array sort is done via GenRandom.

I have zero qualms about any modifications, minor or major, to this code.

Algorithm:

An AutoHotkey Array object, of size n items, consists of n contiguous Variant structs in memory, one struct for each array item.
This PR creates an array of n contiguous address values for each of those structs, and applies qsort to that array of addresses.
Qsort repeatedly sends address values to a comparator function.
The address values are resolved to Variant objects, and the array item info obtained, giving 2 values to be compared, the information is passed to an internal or user comparator function.
The comparator function compares 2 values and returns a value. (The comparator function may also receive an 'offset' value, based on the relative position of 2 items in the original array item order.)
Qsort rearranges the array of addresses based on those return values.
If the array items are considered equal, the address values can be compared (if item 1 appears later than item 2, in the original list, the 'offset' is negative: offset = address2-address1), this allows for a stable sort to occur: in a tiebreaker, when 2 items are considered equal, a comparator function can consider the initial item positions, and return 1 or -1 such that the earlier items remain earlier in the array of addresses.
Once all of the items have been sorted, the array of addresses gives the new order for the array items. A temporary memory block is created, and receives a Variant structure for each array item, and then the whole block is copied over the original memory block, the temporary memory block is then discarded.

Test code

;==================================================

;test code: Array.Sort() (AHK v2)

;==================================================

MsgBox("ready")

;each line is of the form: 'before|after|options|function'
vListTest := " ;continuation section
(Comments
red,yellow,green,blue|blue,green,red,yellow||
red,yellow,green,blue|red,blue,green,yellow||StrCmpLen
q,w,e,r,t,y|y,t,r,e,w,q||StrCmpReverse
1000,200,30,4|1000,200,30,4||
1000,200,30,4|4,30,200,1000|N|
a,a,a,A,a,a|a,a,a,A,a,a|| ;test stable sort
2,4,1,1.0,1.00,0x1,3,5|1,1.0,1.00,0x1,2,3,4,5|N| ;test stable sort
2 d,22 e,222 f,1 a,11 b,111 c|1 a,11 b,111 c,2 d,22 e,222 f|| ;test logical sort
2 d,22 e,222 f,1 a,11 b,111 c|1 a,2 d,11 b,22 e,111 c,222 f|CLogical| ;test logical sort
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,E,F,c,d,g,h,É,é|COn|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,E,F,c,d,g,h,É,é|C1|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,c,d,E,F,g,h,É,é|COff|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,c,d,E,F,g,h,É,é|C0|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,c,d,E,É,é,F,g,h|CLocale|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,2,11,22,A,B,c,d,E,É,é,F,g,h|CLogical|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,E,F,c,d,g,h,É,é|C|
E,F,g,h,A,B,c,d,2,22,1,11,É,é|1,11,2,22,A,B,c,d,E,É,é,F,g,h|CL|
)"

Loop Parse, vListTest, "`n"
{
;if (A_Index = 6)
;continue

	oTemp := StrSplit(A_LoopField, "|")
	if !(oTemp.Length = 4)
		MsgBox("error: test lines must contain exactly 3 pipe characters")
	vListIn := oTemp[1]
	vListOut := oTemp[2]
	vOpt := oTemp[3]
	vFuncName := oTemp[4]
	oFunc := StrLen(vFuncName) ? %vFuncName% : ""

	if IsObject(oFunc)
		vList1 := Sort(vListIn, "D, " vOpt, oFunc)
	else
		vList1 := Sort(vListIn, "D, " vOpt)

	oArray := StrSplit(vListIn, ",")
	if IsObject(oFunc)
		oArray.Sort(vOpt, oFunc)
	else
		oArray.Sort(vOpt)
	vList2 := JEE_StrJoinSimple(",", oArray*)

	try Assert(vList1, vListOut)
	catch
		MsgBox("Sort (string) error: item " A_Index "`r`n" vOpt "`r`n" vFuncName "`r`n" vListOut " (expected)`r`n" vList1)
	try Assert(vList2, vListOut)
	catch
		MsgBox("Sort (array) error: item " A_Index "`r`n" vOpt "`r`n" vFuncName "`r`n" vListOut " (expected)`r`n" vList2)

	;MsgBox(A_LoopField "`r`n`r`n" MyArrToStr(oArray))
}

;==============================

;additional commented out tests:

oArray := [1, 2.3, "abc", []]
;oArray.Sort(, StrCmpTestType)

;test function as param 1:
oArray := StrSplit("abcdefghij")
;oArray.Sort(, StrCmpReverse)
oArray.Sort(StrCmpReverse)
;MyPrintArray(oArray)

;oArray.Sort(, []) ;Error:  This value of type "Array" has no method named "Call".
;oArray.Sort([]) ;Error:  This value of type "Array" has no method named "Call".

vListIn := " ;continuation section
(Join,
A:\Q
B:\W
C:\E
D:\R
E:\T
F:\Y
)"
vList1 := Sort(vListIn, "D, \")
oArray := StrSplit(vListIn, ",")
oArray.Sort("\")
vList2 := JEE_StrJoinSimple(",", oArray*)
if !(vList1 == vList2)
	MsgBox("error: \")
;MsgBox(vList1)

vListIn := "1,2,3,4,5,6,7,8,9,10"
oArray := StrSplit(vListIn, ",")
Loop 10
{
	;MsgBox(Sort(vListIn, "D, Random"))
	oArray.Sort("Random")
	;MyPrintArray(oArray)
}

/*
;test for memory leak (check memory usage in Task Manager):
oArray := []
Loop 100000
	oArray.Push("abc")
MsgBox("memory leak test")
Loop 100
{
	ToolTip(A_Index)
	oArray.Sort()
}
*/

;check that Sort can handle parameter permutations without crashing:
oArray := [1, 2, 3, 4]
oArray.Sort()
oArray.Sort(StrCmpLen)
oArray.Sort("N")
oArray.Sort(, StrCmpLen)
oArray.Sort("", StrCmpLen)

;test unset values:
oArray := [1,, 3]
;oArray := [1, 2, 3]
;oArray.Sort()
oArray.Sort(StrCmpLen)
;MyPrintArray(oArray)

;==============================

MsgBox("done")
return

;==================================================

JEE_StrJoinSimple(vSep, oArray*)
{
	vOutput := ""
	for _, vValue in oArray
		vOutput .= vValue vSep
	return SubStr(vOutput, 1, -StrLen(vSep))
}

StrCmpTestType(vItem1, vItem2, vOffset)
{
	vType1 := Type(vItem1)
	vType2 := Type(vItem2)
	if IsObject(vItem1)
		vItem1 := ""
	if IsObject(vItem2)
		vItem2 := ""
	MsgBox(vType1 " " vItem1 "`r`n" vType2 " " vItem2)
	return 0
}

;note: assigning default blank strings enables this function to accept unset parameters:
StrCmpLen(vText1:="", vText2:="", vOffset:=0)
{
	vLen1 := StrLen(vText1)
	vLen2 := StrLen(vText2)
	return (vLen1 - vLen2)
}

StrCmpReverse(vTextA, vTextB, vOffset:=0) ;for use with AHK's Sort function
{
	return vOffset
}

MyArrToStr(oArray)
{
	vOutput := ""
	for vKey, vValue in oArray
		vOutput .= vKey " " (IsSet(vValue) ? vValue : "unset") "`r`n"
	return vOutput
}

MyPrintArray(oArray)
{
	MsgBox(MyArrToStr(oArray))
}

Assert(vValue1, vValue2)
{
	;Clipboard := vValue1
	;return

	if !(vValue1 == vValue2)
		throw Error("Assert mismatch.`r`n" "Return value: " vValue1 "`r`n" "Expected value: " vValue2, -1)
}

;==================================================

Animan8000 · 2022-12-22T09:14:41Z

I personally like the idea of being able to sort arrays. Seems something basic for a language that will come handy in some places without the need of using a library or own function for that purpose. Also several people in the AutoHotkey Discord would like having the ability to sort arrays as a built-in feature and it could be maybe a worthy addition to v2.1 or later.

Added Array.Sort().

7666c79

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

v2: Added Array.Sort(). #297

v2: Added Array.Sort(). #297

jeeswg commented Aug 25, 2022 •

edited

Loading

Animan8000 commented Dec 22, 2022

v2: Added Array.Sort(). #297

Are you sure you want to change the base?

v2: Added Array.Sort(). #297

Conversation

jeeswg commented Aug 25, 2022 • edited Loading

Documentation

Implementation

Test code

Animan8000 commented Dec 22, 2022

jeeswg commented Aug 25, 2022 •

edited

Loading