- Joined
- Nov 7, 2014
- Messages
- 571
This is a follow up of Sorty loops which is "Not open for further replies".
I don't know why I didn't think of this earlier but it's very easy to go one step further and make the user do the swapping themselves. This way we avoid the copying from the user's arrays to ours. It also simplifies the implementation:
The above fits on a single page (sort of =)) and it's generic in the sense that it can sort any array/struct of any type with any kind of comparison logic (with a bit of help from the user):
Not exactly a one liner but... it is simple. It doesn't require you to use function pointers, functors, lambdas, operator< overloading, implementing 'IComparable' or some other "advanced" language machinery. It also has the advantage of being able to sort parallel arrays easily (try that with your favourite sort implementation).
There's one big down side though... it's slower. It uses insertion sort (which is slow) translated into a state machine (which makes it even slower).
The examples from the other thread but using the new implementation:
I don't know why I didn't think of this earlier but it's very easy to go one step further and make the user do the swapping themselves. This way we avoid the copying from the user's arrays to ours. It also simplifies the implementation:
JASS:
globals
integer sortstate
integer sortinita
integer sortinitb
integer sorta
integer sortb
integer sortcmp
integer sortIdxA
integer sortIdxB
endglobals
// sorts the range [a, b)
function sortBegin takes integer a, integer b returns nothing
set sortstate = 1
set sortinita = a
set sortinitb = b
set sorta = a
endfunction
// uses insertion sort, which is slow for big arrays, but easy-ish to translate
// to a state machine
function sortDone takes nothing returns boolean
loop
if 1 == sortstate then
if sorta == sortinitb then
return true
else
set sortb = sorta
set sortstate = 2
// continue
endif
elseif 2 == sortstate then
if sortb <= sortinita then
set sorta = sorta + 1
set sortstate = 1
// continue
else
set sortIdxA = sortb - 1
set sortIdxB = sortb
set sortstate = 3
// let the user use the indices 'sortIdxA, sortIdxB' and call 'sortSwap'
// with the result of the comparison
return false
endif
elseif 3 == sortstate then
if sortcmp <= 0 then
set sorta = sorta + 1
set sortstate = 1
else
// because sortcmp > 0 at this point the user should've swapped
// the values at indices 'sortIdxA' and 'sortIdxB'
set sortb = sortb - 1
set sortstate = 2
endif
// continue
endif
endloop
endfunction
// returns true if the values at indices 'sortIdxA' and 'sortIdxB' need to be swapped
function sortSwap takes integer cmp returns boolean
set sortcmp = cmp
return cmp > 0
endfunction
The above fits on a single page (sort of =)) and it's generic in the sense that it can sort any array/struct of any type with any kind of comparison logic (with a bit of help from the user):
JASS:
function sortIntegers takes nothing returns nothing
local integer array xs
local integer nxs
local integer tmpi
local integer cmp
local integer a
set nxs = 10
// get some array of integers
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
set xs[a] = GetRandomInt(-5, 5)
endloop
// sort it
call sortBegin(0, nxs)
loop
exitwhen sortDone()
if xs[sortIdxA] < xs[sortIdxB] then
set cmp = -1
elseif xs[sortIdxA] > xs[sortIdxB] then
set cmp = 1
else
set cmp = 0
endif
if sortSwap(cmp) then
set tmpi = xs[sortIdxA]
set xs[sortIdxA] = xs[sortIdxB]
set xs[sortIdxB] = tmpi
endif
endloop
endfunction
Not exactly a one liner but... it is simple. It doesn't require you to use function pointers, functors, lambdas, operator< overloading, implementing 'IComparable' or some other "advanced" language machinery. It also has the advantage of being able to sort parallel arrays easily (try that with your favourite sort implementation).
There's one big down side though... it's slower. It uses insertion sort (which is slow) translated into a state machine (which makes it even slower).
The examples from the other thread but using the new implementation:
JASS:
function writeln takes string s returns nothing
call DisplayTimedTextToPlayer(GetLocalPlayer(), 0.0, 0.0, 10.0, s)
endfunction
globals
integer nxs
endglobals
globals
integer array xsi
endglobals
function printXsi takes nothing returns nothing
local string s = "["
local integer a
local boolean sep = false
if nxs == 0 then
call writeln("[]")
return
endif
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
if sep then
set s = s + ", "
endif
set sep = true
set s = s + I2S(xsi[a])
endloop
set s = s + "]"
call writeln(s)
endfunction
function testSortInts takes nothing returns nothing
local integer tmpi
local integer cmp
local integer a
set nxs = 10
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
set xsi[a] = GetRandomInt(-5, 5)
endloop
call printXsi()
call sortBegin(0, nxs)
loop
exitwhen sortDone()
if xsi[sortIdxA] < xsi[sortIdxB] then
set cmp = -1
elseif xsi[sortIdxA] > xsi[sortIdxB] then
set cmp = 1
else
set cmp = 0
endif
if sortSwap(cmp) then
set tmpi = xsi[sortIdxA]
set xsi[sortIdxA] = xsi[sortIdxB]
set xsi[sortIdxB] = tmpi
endif
endloop
call printXsi()
endfunction
globals
real array xsr
endglobals
function printXsr takes nothing returns nothing
local string s = "["
local integer a
local boolean sep = false
if nxs == 0 then
call writeln("[]")
return
endif
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
if sep then
set s = s + ", "
endif
set sep = true
set s = s + R2S(xsr[a])
endloop
set s = s + "]"
call writeln(s)
endfunction
function testSortReals takes nothing returns nothing
local real tmpr
local integer cmp
local integer a
set nxs = 10
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
set xsr[a] = GetRandomReal(-100.0, 100.0)
endloop
call printXsr()
call sortBegin(0, nxs)
loop
exitwhen sortDone()
if xsr[sortIdxA] < xsr[sortIdxB] then
set cmp = -1
elseif xsr[sortIdxA] > xsr[sortIdxB] then
set cmp = 1
else
set cmp = 0
endif
if sortSwap(cmp) then
set tmpr = xsr[sortIdxA]
set xsr[sortIdxA] = xsr[sortIdxB]
set xsr[sortIdxB] = tmpr
endif
endloop
call printXsr()
endfunction
globals
string array xss
endglobals
function printXss takes nothing returns nothing
local string s = "["
local integer a
local boolean sep = false
if nxs == 0 then
call writeln("[]")
return
endif
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
if sep then
set s = s + ", "
endif
set sep = true
set s = s + "'" + xss[a] + "'"
endloop
set s = s + "]"
call writeln(s)
endfunction
function testSortStrings takes nothing returns nothing
local string tmps
local integer cmp
local integer uid
local unit u
local integer a
set nxs = 5
set a = 0
loop
exitwhen a == nxs
set uid = ChooseRandomCreep(GetRandomInt(0, 10))
if uid != 0 then
set u = CreateUnit(Player(0), uid, 0.0, 0.0, 0.0)
set xss[a] = GetUnitName(u)
call RemoveUnit(u)
set a = a + 1
endif
endloop
call printXss()
call sortBegin(0, nxs)
loop
exitwhen sortDone()
if StringLength(xss[sortIdxA]) < StringLength(xss[sortIdxB]) then
set cmp = -1
elseif StringLength(xss[sortIdxA]) > StringLength(xss[sortIdxB]) then
set cmp = 1
else
set cmp = 0
endif
if sortSwap(cmp) then
set tmps = xss[sortIdxA]
set xss[sortIdxA] = xss[sortIdxB]
set xss[sortIdxB] = tmps
endif
endloop
call printXss()
endfunction
globals
unit array xsu
endglobals
function printXsu takes nothing returns nothing
local string s = "["
local integer a
local boolean sep = false
if nxs == 0 then
call writeln("[]")
return
endif
set a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
if sep then
set s = s + ", "
endif
set sep = true
set s = s + GetUnitName(xsu[a])
endloop
set s = s + "]"
call writeln(s)
endfunction
function removeXsu takes nothing returns nothing
local integer a = 0 - 1
loop
set a = a + 1
exitwhen a == nxs
call RemoveUnit(xsu[a])
set xsu[a] = null
endloop
endfunction
function testSortUnits takes nothing returns nothing
local player p = Player(0)
local unit ua
local unit ub
local integer ra
local integer rb
local integer cmp
local unit tmpu
local integer a
set xsu[0] = CreateUnit(p, 'opeo', 0.0, 0.0, 270.0)
set xsu[1] = CreateUnit(p, 'Ulic', 0.0, 0.0, 270.0)
set xsu[2] = CreateUnit(p, 'ewsp', 0.0, 0.0, 270.0)
set xsu[3] = CreateUnit(p, 'Obla', 0.0, 0.0, 270.0)
set xsu[4] = CreateUnit(p, 'Udre', 0.0, 0.0, 270.0)
set xsu[5] = CreateUnit(p, 'ugho', 0.0, 0.0, 270.0)
set xsu[6] = CreateUnit(p, 'Emoo', 0.0, 0.0, 270.0)
set xsu[7] = CreateUnit(p, 'Ofar', 0.0, 0.0, 270.0)
set xsu[8] = CreateUnit(p, 'uaco', 0.0, 0.0, 270.0)
set xsu[9] = CreateUnit(p, 'Edem', 0.0, 0.0, 270.0)
set xsu[10] = CreateUnit(p, 'hfoo', 0.0, 0.0, 270.0)
set xsu[11] = CreateUnit(p, 'Hpal', 0.0, 0.0, 270.0)
set xsu[12] = CreateUnit(p, 'ogru', 0.0, 0.0, 270.0)
set xsu[13] = CreateUnit(p, 'earc', 0.0, 0.0, 270.0)
set xsu[14] = CreateUnit(p, 'Hblm', 0.0, 0.0, 270.0)
set xsu[15] = CreateUnit(p, 'hpea', 0.0, 0.0, 270.0)
set nxs = 16
call printXsu()
// heroes come first, then units
// also sort by race: human, orc, undead, nightelf
//
call sortBegin(0, nxs)
loop
exitwhen sortDone()
set ua = xsu[sortIdxA]
set ub = xsu[sortIdxB]
if IsUnitType(ua, UNIT_TYPE_HERO) and IsUnitType(ub, UNIT_TYPE_HERO) then
set ra = GetHandleId(GetUnitRace(ua))
set rb = GetHandleId(GetUnitRace(ub))
if ra < rb then
set cmp = -1
elseif ra > rb then
set cmp = 1
else
set cmp = 0
endif
else
if IsUnitType(ua, UNIT_TYPE_HERO) then
set cmp = -1
elseif IsUnitType(ub, UNIT_TYPE_HERO) then
set cmp = 1
else
set ra = GetHandleId(GetUnitRace(ua))
set rb = GetHandleId(GetUnitRace(ub))
if ra < rb then
set cmp = -1
elseif ra > rb then
set cmp = 1
else
set cmp = 0
endif
endif
endif
if sortSwap(cmp) then
set tmpu = xsu[sortIdxA]
set xsu[sortIdxA] = xsu[sortIdxB]
set xsu[sortIdxB] = tmpu
endif
endloop
call printXsu()
call removeXsu()
endfunction
Last edited: