Triggers

//TESH.scrollpos=89
//TESH.alwaysfold=0
//              Merge Sort [GUI Friendly] v1.01
//                    by Flux
//      http://www.hiveworkshop.com/forums/members/flux/
//
//      Merge Sort is an efficient sorting algorithm
//      that has a worst case performance of O(n logn)
//      This system allows you to sort values of an array
//      in either ascending or descending order
//      Additionally, it this system allows you to get the
//      sorted indices of the array values.
//
//      Purely written in JASS and doesn't require anything


function MSort_Display takes nothing returns nothing
    local integer i = udg_MSort_StartIndex
    call BJDebugMsg("========== |cffffcc00[Merge Sort]:|r Data ===============")
    loop
        exitwhen i > udg_MSort_EndIndex
        call BJDebugMsg("MSort_Values[" + I2S(i) + "] = " + R2S(udg_MSort_Values[i]) + ", MSort_Indices[" + I2S(i) + "] = " + I2S(udg_MSort_Indices[i]))
        set i = i + 1
    endloop
    call BJDebugMsg("============== End Display =================\n")
endfunction

function MSort_Merge takes integer leftStart, integer leftEnd, integer rightStart, integer rightEnd returns nothing
    local integer i = leftStart
    local integer j = rightStart
    local integer k = i
    loop
        exitwhen i > leftEnd or j > rightEnd
        if udg_MSort_Ascending then
            if udg_MSort_Left[i] < udg_MSort_Right[j] then
                set udg_MSort_Values[k] = udg_MSort_Left[i]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
                set k = k + 1
                set i = i + 1
            else 
                set udg_MSort_Values[k] = udg_MSort_Right[j]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
                set k = k + 1
                set j = j + 1
            endif
        else
            if udg_MSort_Left[i] > udg_MSort_Right[j] then
                set udg_MSort_Values[k] = udg_MSort_Left[i]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
                set k = k + 1
                set i = i + 1
            else 
                set udg_MSort_Values[k] = udg_MSort_Right[j]
                set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
                set k = k + 1
                set j = j + 1
            endif
        endif
    endloop
    //Fill up remaining
    loop
        exitwhen i > leftEnd
        set udg_MSort_Values[k] = udg_MSort_Left[i]
        set udg_MSort_Indices[k] = udg_MSort_IndexInitial[i]
        set k = k + 1
        set i = i + 1
    endloop
    loop
        exitwhen j > rightEnd
        set udg_MSort_Values[k] = udg_MSort_Right[j]
        set udg_MSort_Indices[k] = udg_MSort_IndexInitial[j]
        set k = k + 1
        set j = j + 1
    endloop
    //Update IndexInitial
    set i = leftStart
    loop
        exitwhen i == k
        set udg_MSort_IndexInitial[i] = udg_MSort_Indices[i]
        set i = i + 1
    endloop
endfunction

//Recursive Function
function MSort_Merge_Sort takes integer start, integer end returns nothing
    local integer i = start
    local integer mid
    if end - start >= 1 then
        set mid = (end + start)/2
        call MSort_Merge_Sort(start, mid)
        call MSort_Merge_Sort(mid+1, end)
        loop
            exitwhen i > mid
            set udg_MSort_Left[i] = udg_MSort_Values[i]
            set i = i + 1
        endloop
        loop
            exitwhen i > end
            set udg_MSort_Right[i] = udg_MSort_Values[i]
            set i = i + 1
        endloop
        call MSort_Merge(start, mid, mid+1, end) 
        //call MSort_Display()
        // ^uncomment to display values
    endif
endfunction


function Trig_Merge_Sort_Main takes nothing returns boolean
    call MSort_Merge_Sort(udg_MSort_StartIndex, udg_MSort_EndIndex)
    return false
endfunction

//===========================================================================
function InitTrig_Merge_Sort takes nothing returns nothing
    set gg_trg_Merge_Sort = CreateTrigger()
    call TriggerAddCondition(gg_trg_Merge_Sort, Condition(function Trig_Merge_Sort_Main))
endfunction

//TESH.scrollpos=28
//TESH.alwaysfold=0
//
//      MERGE SORT READ ME
//
//          ***********************************************
//          ************** HOW TO IMPORT ******************
//          ***********************************************
//
//       1. Copy the Merge Sort Variable Creator in your map.
//          Make sure you set the "Automatically create unknown variables
//          while pasting trigger data" in Files -> Preferences.
//          After copying, delete Merge Sort Variable Creator
//       2. Copy the 'Merge Sort' trigger to your map.
//
//
//
//          **********************************************
//          *************** HOW TO USE *******************
//          **********************************************
//
//      1. Store the values you want to sort to MSort_Values
//         and initialize MSort_IndexInitial[n] = n
//       Example:
//        MSort_Values[0] = 3
//        MSort_IndexInitial[0] = 0
//        MSort_Values[1] = 9
//        MSort_IndexInitial[1] = 1
//        MSort_Values[2] = 4
//        MSort_IndexInitial[2] = 2
//        MSort_Values[3] = 5
//        MSort_IndexInitial[3] = 3
//        MSort_Values[4] = 2
//        MSort_IndexInitial[4] = 4
//
//      2. Set MSort_Ascending, MSort_StartIndex, MSort_EndIndex
//       Example:
//        MSort_Ascending = true 
//        MSort_StartIndex = 0
//        MSort_EndIndex = 4
//
//      3. Run Merge Sort <gen> (checking Conditions)
//      
//      4. The Array new values are now:
//
//        MSort_Values[0] = 2
//        MSort_Values[1] = 3
//        MSort_Values[2] = 4
//        MSort_Values[3] = 5
//        MSort_Values[4] = 9
//
//        MSort_Indices[0] = 4    ; from MSort_Values[4] = 2
//        MSort_Indices[1] = 0    ; from MSort_Values[0] = 3
//        MSort_Indices[2] = 2    ; from MSort_Values[2] = 4
//        MSort_Indices[3] = 3    ; from MSort_Values[3] = 5
//        MSort_Indices[4] = 1    ; from MSort_Values[1] = 9
//

//TESH.scrollpos=0
//TESH.alwaysfold=0
scope Test initializer OnInit
    
//  If you do not have JNGP, do not enable this trigger
    
// Uncomment call MSort_Display() 
// in Merge Sort to analyze the algorithm
    
    globals
        private integer array unsorted
    endglobals
    
    private function Test takes nothing returns nothing   
        local integer i = 0
        //Tells the system to sort in ascending order
        set udg_MSort_Ascending = TRUE
        //Tells the system to starting sorting at index 0
        set udg_MSort_StartIndex = 0
        //Tells the system to end sorting at index 9
        set udg_MSort_EndIndex = 9
        //Transfer the unsorted array to mergeSortValues array
        loop
            exitwhen i > udg_MSort_EndIndex
            set udg_MSort_Values[i] = unsorted[i]
            set i = i + 1
        endloop
        //Run the Trigger to sort the values
        call TriggerEvaluate(gg_trg_Merge_Sort)
        call DestroyTimer(GetExpiredTimer())
        call BJDebugMsg("vJASS Demo Ends")
    endfunction
    
    //Create a delay so that is is stored in Message Log
    private function OnInit takes nothing returns nothing
        //Initialize unsorted array
        set unsorted[0] = 69
        set unsorted[1] = 9
        set unsorted[2] = 31
        set unsorted[3] = 5
        set unsorted[4] = -8
        set unsorted[5] = 78
        set unsorted[6] = 69
        set unsorted[7] = 512
        set unsorted[8] = 32
        set unsorted[9] = 53
        call TimerStart(CreateTimer(), 1.0, false, function Test)
        call BJDebugMsg("vJASS Demo will start in 1 second\n")
    endfunction
    
endscope