SortUtils

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

$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