[v2 Function]Sort function - replace the built in one with something useable

Post your working scripts, libraries and tools
User avatar
nnnik
Posts: 3881
Joined: 30 Sep 2013, 01:01
Location: Germany

[v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 10:09

Sort()

Updates:
v1.0 available - now it's using Quicksort


Lexikos recently released an update for AK v2 which good me into the mood to play around with AHK v2 a bit.
One thing I see a lot in other languages is a sort function that looks and works similar to this:

Code: Select all

Arr.sort( compareFunction := defaultSortFunction )
Sort( arr, compareFunction := defaultSortFunction )
The function accepts 2 parameters. First is the array whose data should be sorted. Second is a function that compares 1 of the arrays values to the other and returns that value.
We do have a sort function in AHK. But we do not talk about this one.
Anyways with this I have started to replicate this function:

Code: Select all

/* written by nnnik 
	https://autohotkey.com/boards/viewtopic.php?f=6&t=46260
	v1.0.0
	Changelog:
	v0.1.0 Implemented an example using insertion sort
	v1.0.0 It now uses quick sort
*/


sort( arr, compareFn := "" ) {
	if !compareFn
		compareFn := func( "standardCompare" )
	layer := 0
	quickSort( arr.MinIndex(), arr.MaxIndex() )
	return arr
	
	quickSort( firstIndex, lastIndex ) {
		
		if lastIndex-firstIndex < 100
			return insertSort( firstIndex, lastIndex )
		
		leftIndex  := firstIndex
		rightIndex := lastIndex
		pivotIndex := floor( ( rightIndex - leftIndex ) / 2 ) + leftIndex
		pivotValue := arr[ pivotIndex ]
		
		if layer > 15
			Msgbox leftIndex "`n" pivotIndex "`n" rightIndex
		
		Loop {
			While( leftIndex < pivotIndex && cmp := compareFn.Call( arr[ leftIndex ], pivotValue ) <= 0 )
				leftIndex++
			if ( pivotIndex <= leftIndex ) {
				pivotIndex := leftIndex
				break
			}
			While( rightIndex > pivotIndex && compareFn.Call( arr[ rightIndex ], pivotValue ) >= 0 )
				rightIndex--
			if ( pivotIndex >= rightIndex ) {
				pivotIndex := rightIndex
				break
			}
			swap( leftIndex, rightIndex )
			leftIndex++
			rightIndex--
		}
		
		if ( leftIndex = pivotIndex ) {
			if ( rightIndex > pivotIndex ) {
				while ( rightIndex > pivotIndex ) {
					if ( compareFn.Call( arr[ rightIndex ], pivotValue ) < 0 ) {
						move( rightindex, pivotIndex ), pivotIndex++
					} else
						rightIndex--
				}
			}
		}
		else if ( rightIndex = pivotIndex ) {
			while ( leftIndex < pivotIndex ) {
				if ( compareFn.Call( arr[ leftIndex ], pivotValue ) > 0 ) {
					move( leftIndex, pivotIndex ), pivotIndex--
				} else
					leftIndex++
			}
		}
		
		quickSort( firstIndex, pivotIndex - 1 )
		quickSort( pivotIndex + 1, lastIndex )
	}
	
	insertSort( firstIndex, lastIndex ) {
		Loop lastIndex - firstIndex {
			currentIndex := firstIndex + A_Index
			currentValue := arr[ currentIndex ]
			Loop {
				currentCompareIndex := currentIndex - A_Index
			}Until currentCompareIndex < firstIndex || compareFn.Call( currentValue, arr[currentCompareIndex] ) >= 0 
			move( currentIndex, currentCompareIndex + 1 )
		}
	}
	
	standardCompare( compareVal1, compareVal2 ) {
		if ( compareVal1 = compareVal2 )
			return 0
		minStrLen := min( compareLen1 := StrLen( compareVal1 ), StrLen( compareVal2 ) )
		Loop minStrLen {
			compareChr1 := ord( subStr( compareVal1, A_Index, 1 ) )
			compareChr2 := ord( subStr( compareVal2, A_Index, 1 ) )
			if ( compareChr1 != compareChr2 )
				return compareChr1 - compareChr2
		}
		return ( ( compareLen1 = minStrLen ) && -1 )
	}
	
	swap( index1, index2 ) {
		temp := arr[ index1 ]
		arr[ index1 ] := arr[ index2 ]
		arr[ index2 ] := temp
	}
	
	move( srcIndex, targetIndex ) {
		if srcIndex != targetIndex
			arr.insertAt( targetIndex, arr.RemoveAt( srcIndex ) )
	}
}

The arguments are the same. The compare function is also optional. The default compare function is standardCompare. Here you can see how a compare function should look like:

It should accept 2 values and return which of the values is larger/smaller. If the first value is smaller return a negative number - if it's the second return a positive number - if they are the same return 0.
The sort function will then sort the array according to the order set by the compare function.
By default the function sorts by how the string of the value looks like.

This is a first draft as to how the syntax should look like - it currently uses a quick sort algorythm which is actually pretty fast.
I hope that this will be a thing in AutoHotkey natively in the future.
Here are some examples:

Code: Select all

#Include sort.ahk

MsgboxDispObj( sort( ["c", "b", "a", "d", "D"] ) )           ;[ "a", "b", "c", "d", "D" ]
MsgboxDispObj( sort( [3, 5, 1, 4, 2, 11 ] ) )                ;[ "1", "11", "2", "3", "4", "5" ]
MsgboxDispObj( sort( [3, 5, 1, 4, 2, 11 ], (a,b) => a-b  ) ) ;[ "1", "2", "3", "4", "5", "11" ]
MsgboxDispObj( sort( [3, 5, 1, 4, 2, 11 ], (a,b) => b-a  ) ) ;[ "11", "5", "4", "3", "2", "1" ]

MsgboxDispObj( obj ) {
	resultStr := "[ "
	for each, val in obj
		resultStr .= "`"" val "`", " 
	resultStr := subStr( resultStr, 1, -2 ) . " ]"
	msgbox( resultStr  )
	return resultStr
}

Code: Select all

#Include sort.ahk

toSort := []
Loop 100000
	toSort.Push( random( -0x80000000, 0x7FFFFFFF ) )
FileDispObj( "sort.log", sort( toSort, (a,b) => a-b ) )

FileDispObj( fileName, obj ) {
	resultStr := ""
	for each, val in obj
		resultStr .= val "`n" 
	fileOpen( fileName, "w" ).write( resultStr )
	return resultStr
}
Recommends AHK Studio
User avatar
kczx3
Posts: 734
Joined: 06 Oct 2015, 21:39

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 11:16

Thanks for this. As a JavaScript developer, I certainly prefer using sort as a method on the Array/Object prototype versus just a function.

On a somewhat related note, what does using nested functions gain in this scenario? Or were you just trying to showcase the new stuff in the latest v2 build?
User avatar
nnnik
Posts: 3881
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 11:44

Well I will add more nested functions as time goes on and I don't want to waste global function name space.
I'm currently trying to implement quickSort.
Recommends AHK Studio
User avatar
kczx3
Posts: 734
Joined: 06 Oct 2015, 21:39

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 11:57

Ok, that makes sense. Though I suppose you could also create a class instead of using nested functions. Good Work as usual.
User avatar
nnnik
Posts: 3881
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 13:00

I added a quicksort algorythm.
It's now a lot faster - you can check the speed with the second example I added.
Recommends AHK Studio
Helgef
Posts: 3528
Joined: 17 Jul 2016, 01:02
Contact:

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 13:49

Nice, nnnik, thanks for sharing.

There was another quick sort implementation here: Sort dense arrays or matrices. I've used qsort (msdn) for comobjarrays in the past, I made a version for ahk arrays. To note, it copies the array, but it is a very simple implementation.

Code: Select all

; qsort
qsort(arr, cmpfn){
	static VT_UI4 := 0x13
	static sizeofInt := 4
	local r := [] ; return array
	local l := arr.length()
	if !l
		return r
	r.setcapacity(l)
	; Create index array
	local da := comobjarray(VT_UI4, l) ; array of l uints
	loop l
		da[a_index-1] := a_index
	; Get pointer to the index array
	local SAFEARRAY := ComObjValue(da)
	local pvData := NumGet(SAFEARRAY, 12+(A_PtrSize=4?0:4), "Ptr")
	; dllcall qsort
	local pcmp := callbackcreate("cmp", "cdecl f", 2)
	DllCall("MSVCRT.dll\qsort", "Ptr", pvData, "Ptr", l, "Ptr", sizeofInt, "Ptr", pcmp, "cdecl")
	callbackfree(pcmp)
	; assemble result
	local k
	for k in da
		r[a_index] := arr[k]
	return r
	cmp(a,b){	; go between function
		return cmpfn.call(arr[ numget(a, "uint") ], arr[ numget(b, "uint") ])
	}
}
; test
stringcasesense c:=["on", "off", "locale"][random(1,3)]
for k, v in qsort(["x", "a", "B", "Ö", "o", "ö"], (a, b) => a < b ? -1 : a > b ? 1 : 0)
	str .= v "`n" 
msgbox str "`n`n`ncase:`t" c 
Cheers
User avatar
nnnik
Posts: 3881
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 14:02

Well yeah I can't use a version thats dedicated for matrices. Also my version would be best with C++ arrays rather than AHK objects.
But yeah using MSDNs quicksort might be faster at a specific stage.

I also plan to further enhacne it's speed but I don't want to do more today.
A little bit of reading:
http://algo2.iti.kit.edu/sanders/papers/KalSan06.pdf
Recommends AHK Studio
User avatar
BGM
Posts: 435
Joined: 20 Nov 2013, 20:56
GitHub: bgmCoder
Contact:

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 14:12

Here are my three favourites that I use - I learned them from a language called BCX and now I recreate them in any language in which I write any code.

LEFT and RIGHT with a little twist I call "shift"

Code: Select all

;returns the rightmost number of characters
;if shift is true, then return the string with the number of characters removed
;example := right(123abc, 2, true)
;result:  bc
;example := right(123abc, 2, false)
;result: 123a
right(whattext, numchars=1, shift=false){
	StringLen, thislen, whattext
	numchars := abs(numchars) ;remove the negativity!
	if(shift){
		thisstring := substr(whattext, 1, thislen - numchars)
	}else{
		thisstring := substr(whattext, thislen - numchars +1, thislen)
	}
	return thisstring
}

Code: Select all

;returns the leftmost number of characters
;if shift is true, then return the string with the number of characters removed - that is, shift = trim
left(whattext, numchars=1, shift=false){
	StringLen, thislen, whattext
	numchars := abs(numchars) ;remove the negativity!
	if(shift){
		thisstring := substr(whattext, numchars+1, thislen)
	}else{
		thisstring := substr(whattext, 1, numchars)
	}
	return thisstring
}
And for this one, well, no, nobody really needs a wrapper for msgboxes. But after I got used to javascript, I wanted to use alertfor everything. So I sort of customized msgbox to do my typical routines.
alert("bob was here")

Code: Select all

/*!
	Function: alert(whatmessage, whaticon="", whattitle="", whattimeout="")
		A Wrapper for messagebox with intuitive parameters
	Parameters:
		whatmessage - What you want to say
		whaticon - The icon you like.  Leave blank for no icon.  
			You can specify: "asterisk", "exclamation", "warning", "hand", "stop", "error", "question", "help", "okay" or blank.
		whattitle - Your custom title for the messagebox window
		whattimeout - When you want the messagebox to disappear on it own; leave blank to have it not disappear.
	Returns: none
	Notes: If the original window is topmost, this messagebox will also be topmost
*/
alert(whatmessage, whaticon="", whattitle="", whattimeout=""){
	if(!whattitle){	;use the apptitle variable if it is defined
		wingettitle, whattitle, A
	}
	if(whaticon = "asterisk")
		theseoptions := 64
	else if(whaticon = "exclamation" || whaticon = "warning")
		theseoptions := 48
	else if(whaticon = "hand" || whaticon = "stop" || whaticon = "error")
		theseoptions := 16
	else if(whaticon = "help" || whaticon = "question")
		theseoptions := 32
	else if(whaticon = "okay")
		theseoptions := 0
	else
		theseoptions := 0
		
	;if the original window is topmost, make this here msgbox topmost, too, so it doesn't disappear behind the window
	WinGet, ExStyle, ExStyle, a
	if (ExStyle & 0x8){  ; 0x8 is WS_EX_TOPMOST.
		theseoptions := theseoptions + 4096
	}	
	
	;the "options" number must be a forced expression
	msgbox, % theseoptions, %whattitle%, %whatmessage%, %whattimeout%			;%
}
User avatar
nnnik
Posts: 3881
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

29 Mar 2018, 09:43

Hm yeah looks good.
I think I'm going to add another one:

Code: Select all

Select( arr, selectionFn ) {
	local
	toRemove := []
	for key, element in arr
		if !selectionFn.call( element )
			toRemove.insertAt( 1, key )
	for each, key in toRemove
		arr.removeAt( key )
	return arr
}
Example:

Code: Select all

#Include Select.ahk
MsgboxDispObj( Select( [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], (nr)=>!mod(nr, 3) ) ) ;[ "3", "6", "9", "0" ]

MsgboxDispObj( obj ) {
	resultStr := "[ "
	for each, val in obj
		resultStr .= "`"" val "`", " 
	resultStr := subStr( resultStr, 1, -2 ) . " ]"
	msgbox( resultStr )
	return resultStr
}
Recommends AHK Studio
User avatar
nnnik
Posts: 3881
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

29 Mar 2018, 10:54

Yeah. Select comes from SQL though
Recommends AHK Studio

Return to “Scripts and Functions”

Who is online

Users browsing this forum: No registered users and 26 guests