SortUtils

[grim001]

SortUtils allows you sort arrays of reals, units and structs efficiently.

-It uses a QuickSort/InsertionSort hybrid.
-It is based on dynamic arrays and array pointers.
-It can sort a real array from least to greatest. (Read backwards for greatest to least).
-It can sort a unit array or struct array according to the values in a parallel real array.
-It can sort a unit array or struct array according to a SortFunc that can specify any sorting criteria.

The documentation is like a novel; be warned.

JASS:

library SortUtils
//===========================================================================
// Information:
//==============
//
//      SortUtils allows you sort arrays of reals, units and structs efficiently.
//  Many sorting methods were benchmarked, and a QuickSort/InsertionSort hybrid
//  was found to be the most efficient for general purposes. You can sort lists
//  that are several hundred values long without any issues.
//
//===========================================================================
// How to use SortUtils dynamic arrays:
//======================================
//
//      JASS does not natively support dynamic arrays or array pointers. vJASS
//  supports them, but this library does not use those. It uses customized ones
//  that behave a bit differently. How to use them is shown below:
//
//      local RealArray ra = RealArray.create(size)
//      local UnitArray ua = UnitArray.create(size)
//      local StructArray sa = StructArray.create(size)
//
//      When creating an array, you must specify the size you intend to utilize.
//  For example, if ra[0...99] were utilized, the size should be set to 100. The
//  size can go as high as MaxArraySize. When you sort an array, only the indexes
//  within 0...size - 1 will be sorted, so make sure it is accurate. If you want
//  to alter the size after creating an array, you can do so using the .size var-
//  iable. For example: set ra.size = ra.size + 1
//
//      You must use .destroy() on your arrays as well, or you will quickly run
//  out of instances. You can have (8190 / MaxArraySize) simultaneous instances
//  of each array type. When you use .destroy(), all the values up to .size in
//  the array will be zeroed or nulled, so you don't need to worry about non-
//  zero values in newly created arrays, or reference leaks with UnitArrays.
//
//===========================================================================
// How to use SortUtils:
//======================
//
//      SortUtils includes the standard capability to sort a RealArray from least
//  to greatest. (If you want greatest to least, just read the array backwards
//  starting from index .size - 1). You can also sort a UnitArray or StructArray
//  according to a parallel RealArray. This is easy to understand with an example:
//
//  Before sorting:
//  UnitArray:      [Paladin][Archmage][Rifleman][Footman]
//  RealArray:      [ 500.0 ][ 1750.0 ][ 1250.0 ][ 250.0 ]
//
//  After sorting:
//  UnitArray:      [Footman][Paladin][Rifleman][Archmage]
//  RealArray:      [ 250.0 ][ 500.0 ][ 1250.0 ][ 1750.0 ]
//
//      As the values contained in the RealArray were sorted from least to greatest,
//  the same swaps were made on the values in the UnitArray. The result is that the
//  UnitArray is ordered as well. The values in the RealArray may represent anything,
//  such as the distance to a specific point, the current life of a unit, "threat
//  values" in an aggro system, etc.
//
//      However, there is an easier way to sort UnitArrays/StructArrays than using
//  a parallel RealArray, and that is with a SortFunc. A SortFunc takes a unit or
//  struct and returns a real. You can use these functions to specify whatever
//  criteria you wish to use to sort a UnitArray or StructArray by. Example:
//
//  function UnitDistance takes unit u returns real
//      return SquareRoot(Pow(GetUnitX(u) - PointX, 2.) + Pow(GetUnitY(u) - PointY, 2.))
//  endfunction
//
//  function Example takes nothing returns nothing
//      local UnitArray ua = UnitArray.create(4)
//      local RealArray ra
//      local integer i
//           set ua[0] = Paladin
//           set ua[1] = Archmage
//           set ua[2] = Rifleman
//           set ua[3] = Footman
//           set PointX = -423.0 //Transfering data with globals, just like a ForGroup.
//           set PointY = 624.0
//           call SortUnits(ua, UnitDistance) //The units are now sorted according to their 
//                                            //respective distances from PointX, PointY.
//           set ra = GetSortedValues()  //This will return a sorted RealArray containing the
//                                       //distances calculated for each of the units.
//           set i = ra.size - 1 //Reading through the lists backwards- farthest to nearest.
//           loop
//               exitwhen i < 0
//               call BJDebugMsg(GetUnitName(ua[i])+" is "+R2S(ra[i])+" distance away.")
//               set i = i - 1
//           endloop
//  endfunction
//
//===========================================================================
// SortUtils API:
//================
//
//  RealArray.create(size) -> RealArray
//    Create a dynamic real array.
//
//  UnitArray.create(size) -> UnitArray
//    Create a dynamic unit array.
//
//  StructArray.create(size) -> StructArray
//    Create a dynamic struct (integer) array. You should not mix different
//    types of structs within the same StructArray.
//
//  .size -> integer
//    You can alter the size of a dynamic array after creating it. Only indexes
//    up to .size - 1 will be sorted.
//
//  .destroy()
//    You must destroy dynamic arrays when you're done with them. Indexes up to
//    .size - 1 will be automatically zeroed or nulled.
//
//  SortValues(RealArray)
//    Sort the values contained in a RealArray from least to greatest. Read it
//    backwards starting from index .size - 1 if you want greatest to least.
//
//  SortUnitsByValues(UnitArray, RealArray)
//    Sorts the values contained in a UnitArray according to the values contained
//    in a parallel RealArray. As the RealArray is sorted, the same swaps are
//    performed on the UnitArray.
//
//  SortStructsByValues(StructArray, RealArray)
//    Same as above, but sorts a StructArray rather than a UnitArray.
//
//  SortUnits(UnitArray, SortUnitFunc)
//    Sorts a UnitArray by whatever criteria is specified in the SortUnitFunc.
//    A SortUnitFunc must take a unit and return a real.
//
//  SortStructs(StructArray, SortStructFunc)
//    Sorts a StructArray by whatever criteria is specified in the SortStructFunc.
//    A SortStructFunc must take the same kind of struct stored in the StructArray
//    and return a real.
//
//  GetSortedValues() -> RealArray
//    After using SortUnits or SortStructs, this function will return a RealArray
//    containing the ordered values that the units or structs were sorted by.
//
//  Group2UnitArray(group) -> UnitArray
//    This will convert a group into a UnitArray. The group remains unchanged. If
//    you want to sort the contents of a unitgroup, use this to convert it to a
//    UnitArray, which you can then use other SortUtils functions to sort.
//
///===========================================================================
// SortUtils textmacro:
//======================
//
//     If you intend to use SortUtils with a library that makes heavy use of
// dynamic arrays and you are worried about instance limits, a special text-
// macro has been provided to solve that problem. If you use this textmacro
// within a scope or library, the RealArrays/UnitArrays/StructArrays used
// within that scope or library will magically have their own instance limit.
// However, arrays created within the scope or library cannot be used outside
// of it.
//
//     The textmacro must be placed above any calls to the SortUtils API.
// Also, you will be required to declare a private constant integer named
// MaxArraySize within that scope or library, which will be used within it
// rather than the MaxArraySize defined within SortUtils.
//
//     To use the textmacro, type: //! runtextmacro SortUtils("private")
//
///===========================================================================
// Configuration:
//================

globals
    public constant integer InsertionSortThreshold = 16
    //Sublists with size <= InsertionSortThreshold will be sorted with
    //InsertionSort rather than QuickSort. Benchmarking showed that values
    //between 10 and 20 produced the greatest speed-up.
    private constant integer MaxArraySize = 200
    //The higher this is set, the fewer instances will be available of each
    //dynamic array type. Setting it higher than 500 is probably useless
    //since sorting lists that large may hit the op-limit.
endglobals

//===========================================================================

function interface SortUnitFunc takes unit u returns real
function interface SortStructFunc takes integer i returns real

//! runtextmacro SortUtils("")
//! textmacro SortUtils takes SCOPE
$SCOPE$ struct RealArray
    private real array values[MaxArraySize]
    integer size = 0
    
    static method create takes integer size returns RealArray
        local RealArray this
            if size > MaxArraySize then
                call BJDebugMsg("SortUtils error: Attempted to create RealArray with size larger than "+I2S(MaxArraySize)+".")
                return 0
            endif
            set this = .allocate()
            set .size = size
        return this
    endmethod
    
    method operator []= takes integer i, real value returns nothing
        set .values[i] = value
    endmethod
    
    method operator [] takes integer i returns real
        return .values[i]
    endmethod
    
    method onDestroy takes nothing returns nothing
        local integer i = .size - 1
            loop
                exitwhen i < 0
                set .values[i] = 0.
                set i = i - 1
            endloop
            set .size = 0
    endmethod
endstruct

$SCOPE$ struct UnitArray 
    private unit array values[MaxArraySize]
    integer size = 0
    
    static method create takes integer size returns UnitArray
        local UnitArray this
            if size > MaxArraySize then
                call BJDebugMsg("SortUtils error: Attempted to create UnitArray with size larger than "+I2S(MaxArraySize)+".")
                return 0
            endif
            set this = .allocate()
            set .size = size
        return this
    endmethod
    
    method operator []= takes integer i, unit value returns nothing
        set .values[i] = value
    endmethod
    
    method operator [] takes integer i returns unit
        return .values[i]
    endmethod
    
    method onDestroy takes nothing returns nothing
        local integer i = .size - 1
            loop
                exitwhen i < 0
                set .values[i] = null
                set i = i - 1
            endloop
            set .size = 0
    endmethod
endstruct

$SCOPE$ struct StructArray 
    private integer array values[MaxArraySize]
    integer size = 0
    
    static method create takes integer size returns StructArray
        local StructArray this
            if size > MaxArraySize then
                call BJDebugMsg("SortUtils error: Attempted to create StructArray with size larger than "+I2S(MaxArraySize)+".")
                return 0
            endif
            set this = .allocate()
            set .size = size
        return this
    endmethod
    
    method operator []= takes integer i, integer value returns nothing
        set .values[i] = value
    endmethod
    
    method operator [] takes integer i returns integer
        return .values[i]
    endmethod
    
    method onDestroy takes nothing returns nothing
        local integer i = .size - 1
            loop
                exitwhen i < 0
                set .values[i] = 0
                set i = i - 1
            endloop
            set .size = 0
    endmethod
endstruct

//===========================================================================

private function SortValues_Sub takes RealArray values, integer left, integer right returns nothing
    local integer pivot = GetRandomInt(left, right)
    local real value = values[pivot]
    local integer i = left
    local integer j = left
    local real swap
        set values[pivot] = values[right]
        set values[right] = value
        loop
            exitwhen j >= right
            if values[j] < value then
                set swap = values[j]
                set values[j] = values[i]
                set values[i] = swap
                set i = i + 1
            endif
            set j = j + 1
        endloop
        set values[right] = values[i]
        set values[i] = value
        if right - (i + 1) > SortUtils_InsertionSortThreshold then
            call SortValues_Sub(values, i + 1, right)
        endif
        if (i - 1) - left > SortUtils_InsertionSortThreshold then
            call SortValues_Sub(values, left, i - 1)
        endif
endfunction

$SCOPE$ function SortValues takes RealArray values returns nothing
    local integer left = 1
    local integer right = values.size - 1
    local real value
    local integer j
        call SortValues_Sub(values, 0, right)
        loop
            exitwhen left > right
            set value = values[left]
            set j = left - 1
            loop
                exitwhen j < 0 or values[j] < value
                set values[j + 1] = values[j]
                set j = j - 1
            endloop
            set values[j + 1] = value
            set left = left + 1
        endloop
endfunction

//===========================================================================

private function SortUnitsByValues_Sub takes UnitArray units, RealArray values, integer left, integer right returns nothing
    local integer pivot = GetRandomInt(left, right)
    local real value = values[pivot]
    local unit u = units[pivot]
    local integer i = left
    local integer j = left
    local real swap
    local unit swapu
        set values[pivot] = values[right]
        set units[pivot] = units[right]
        set values[right] = value
        set units[right] = u
        loop
            exitwhen j >= right
            if values[j] < value then
                set swap = values[j]
                set swapu = units[j]
                set values[j] = values[i]
                set units[j] = units[i]
                set values[i] = swap
                set units[i] = swapu
                set i = i + 1
            endif
            set j = j + 1
        endloop
        set values[right] = values[i]
        set units[right] = units[i]
        set values[i] = value
        set units[i] = u
        if right - (i + 1) > SortUtils_InsertionSortThreshold then
            call SortUnitsByValues_Sub(units, values, i + 1, right)
        endif
        if (i - 1) - left > SortUtils_InsertionSortThreshold then
            call SortUnitsByValues_Sub(units, values, left, i - 1)
        endif
    set u = null
    set swapu = null
endfunction

$SCOPE$ function SortUnitsByValues takes UnitArray units, RealArray values returns nothing
    local integer left = 1
    local integer right = values.size - 1
    local real value
    local unit u
    local integer j
        call SortUnitsByValues_Sub(units, values, 0, right)
        loop
            exitwhen left > right
            set value = values[left]
            set u = units[left]
            set j = left - 1
            loop
                exitwhen j < 0 or values[j] < value
                set values[j + 1] = values[j]
                set units[j + 1] = units[j]
                set j = j - 1
            endloop
            set values[j + 1] = value
            set units[j + 1] = u
            set left = left + 1
        endloop
endfunction

//===========================================================================

private function SortStructsByValues_Sub takes StructArray structs, RealArray values, integer left, integer right returns nothing
    local integer pivot = GetRandomInt(left, right)
    local real value = values[pivot]
    local integer s = structs[pivot]
    local integer i = left
    local integer j = left
    local real swap
    local integer swaps
        set values[pivot] = values[right]
        set structs[pivot] = structs[right]
        set values[right] = value
        set structs[right] = s
        loop
            exitwhen j >= right
            if values[j] < value then
                set swap = values[j]
                set swaps = structs[j]
                set values[j] = values[i]
                set structs[j] = structs[i]
                set values[i] = swap
                set structs[i] = swaps
                set i = i + 1
            endif
            set j = j + 1
        endloop
        set values[right] = values[i]
        set structs[right] = structs[i]
        set values[i] = value
        set structs[i] = s
        if right - (i + 1) > SortUtils_InsertionSortThreshold then
            call SortStructsByValues_Sub(structs, values, i + 1, right)
        endif
        if (i - 1) - left > SortUtils_InsertionSortThreshold then
            call SortStructsByValues_Sub(structs, values, left, i - 1)
        endif
endfunction

$SCOPE$ function SortStructsByValues takes StructArray structs, RealArray values returns nothing
    local integer left = 1
    local integer right = values.size - 1
    local real value
    local integer s
    local integer j
        call SortStructsByValues_Sub(structs, values, 0, right)
        loop
            exitwhen left > right
            set value = values[left]
            set s = structs[left]
            set j = left - 1
            loop
                exitwhen j < 0 or values[j] < value
                set values[j + 1] = values[j]
                set structs[j + 1] = structs[j]
                set j = j - 1
            endloop
            set values[j + 1] = value
            set structs[j + 1] = s
            set left = left + 1
        endloop
endfunction

//===========================================================================

globals
    private UnitArray UnitArrayUnits
endglobals

private function PopulateUnitArray takes nothing returns nothing
    set UnitArrayUnits[bj_groupCountUnits] = GetEnumUnit()
    set bj_groupCountUnits = bj_groupCountUnits + 1
endfunction

$SCOPE$ function Group2UnitArray takes group g returns UnitArray
        set UnitArrayUnits = UnitArray.create(0)
        set bj_groupCountUnits = 0
        call ForGroup(g, function PopulateUnitArray)
        set UnitArrayUnits.size = bj_groupCountUnits
    return UnitArrayUnits
endfunction

//===========================================================================

$SCOPE$ function SortUnits takes UnitArray objects, SortUnitFunc sort returns nothing
    local integer i = objects.size - 1
        if SortUtils_Values != 0 then
            call RealArray(SortUtils_Values).destroy()
        endif
        set SortUtils_Values = RealArray.create(i + 1)
        loop
            exitwhen i < 0
            set RealArray(SortUtils_Values)[i] = sort.evaluate(objects[i])
            set i = i - 1
        endloop
        call SortUnitsByValues(objects, SortUtils_Values)
endfunction

$SCOPE$ function SortStructs takes StructArray objects, SortStructFunc sort returns nothing
    local integer i = objects.size - 1
        if SortUtils_Values != 0 then
            call RealArray(SortUtils_Values).destroy()
        endif
        set SortUtils_Values = RealArray.create(i + 1)
        loop
            exitwhen i < 0
            set RealArray(SortUtils_Values)[i] = sort.evaluate(objects[i])
            set i = i - 1
        endloop
        call SortStructsByValues(objects, SortUtils_Values)
endfunction
//! endtextmacro

//===========================================================================

globals
    public integer Values = 0
endglobals

function GetSortedValues takes nothing returns integer
    local integer values = Values
        set Values = 0
    return values
endfunction

endlibrary

[Rising_Dusk]

I was going over this and it is actually rather cool. I don't have the time to verify that it does all of the things that it says it does, but if you respond to this and say that it does, that'll be good enough.

Once you do that, I think I will approve this. I really like the API and it could prove incredibly useful for people. I also really like how thorough the documentation is, I know exactly how to use this library after having read it.

[Anachron]

This is kinda cool, I see many uses right now, just think about it:

An system to sort for best players (in a hero arena or in general)
For closest distance units.
... and even more.

This might be in my new AoS, if it works without bugs.

[grim001]

I originally created this because I needed fast distance sorting for an aura system, but eventually I came up with this way to generalize it, so I'm happy with the way it turned out.

I did try partially-recursive and non-recursive variations on quicksort, and it didn't do any better than this recursive implementation in benchmarks. I always assumed that recursive algorithms would be slow in JASS, but they seem to do alright.

I tested it heavily so I know that each function does what it says it does. There shouldn't be any bugs, as they'd wind up being incredibly apparent given the nature of this library.

[Rising_Dusk]

Then I do declare this approved.

[grim001]

Updated.

• If you intend to use SortUtils with a library that makes heavy use of dynamic arrays and you are worried about instance limits, a special textmacro has been provided to solve that problem. If you use this textmacro within a scope or library, the RealArrays/UnitArrays/StructArrays used within that scope or library will magically have their own instance limit. The textmacro must be placed above any calls to the SortUtils API. Also, you will be required to declare a private constant integer MaxArraySize within that scope or library, which will be used within it.

[grim001]

Updated.

• Documentation, code and efficiency improvements.

Nested textmacros will let me cut the size of the library in half, so it will probably get another update once those come out.

[Tot]

SortUtils-Code:

$SCOPE$ struct UnitArray 
    private unit array values[MaxArraySize]
    integer size = 0
    
    static method create takes integer size returns UnitArray
        local UnitArray this
            if size > MaxArraySize then
                call BJDebugMsg("SortUtils error: Attempted to create #RealArray# with size larger than "+I2S(MaxArraySize)+".")
                return 0
            endif
            set this = .allocate()
            set .size = size
        return this
    endmethod

$SCOPE$ struct StructArray 
    private integer array values[MaxArraySize]
    integer size = 0
    
    static method create takes integer size returns StructArray
        local StructArray this
            if size > MaxArraySize then
                call BJDebugMsg("SortUtils error: Attempted to create #RealArray# with size larger than "+I2S(MaxArraySize)+".")
                return 0
            endif
            set this = .allocate()
            set .size = size
        return this
    endmethod

hasn't it to be UnitArray/StructArray?


anyway, this is really cool, but I'd make a textmacro to let the user sort every thing from integer to lightnings and back
some kind of //! textmacro SortUtils takes TYPE, NULL, SCOPE
you're using introsort and I've read on wikipedia, that it works best with a Threshold of 16

[grim001]

Originally Posted by Tot

I'd make a textmacro to let the user sort every thing from integer to lightnings and back

If you want to sort stuff other than reals or units, that's what StructArrays are for. The whole point of this is to not be one of those lame textmacro-based sorting libraries.

Also, updated.

• Altered the sorting algorithm. Everything sorts about 15% faster now.
• Set the default threshold to 16 for some reason.

[SanKakU]

i like this. should save me time with the computer sorting things for me :)