[Snippet] MergeSort

[Dirac]

library MergeSort /* v3.0.1

*/uses/*
*/  LinkedListModule    /* thehelper.net/forums/showthread.php/168775-LinkedListModule

A tool for sorting linked lists inside structs.

***********************************************************************
*
*   textmacro MERGE_SORT takes METHOD_NAME, COMPARE_BOOLEAN
*       -   Run at the end of the struct.
*
***********************************************************************
*
*   DEMONSTRATION
*
*   struct UnitsByLife extends array
*       implement LinkedListModule
*       unit target
*       //! runtextmacro MERGE_SORT ("sort","GetWidgetLife(v1.target)>GetWidgetLife(v2.target)")
*   endstruct
*
*   Assuming that you're going to insert instances to the UnitsByLife's
*   base then you can call UnitsByLife.sort(UnitsByLife.base) to cause
*   instances of the linked list to be sorted depending on each unit's
*   current life. Reffer to the instances as "v1" and "v2"

**********************************************************************/

    //! textmacro MERGE_SORT takes METHOD_NAME, COMPARE_BOOLEAN
        
        //*********************************************************************
        //  Ok this method is entitled to split and merge constatly until there
        //  is nothing left to split.
        private static method $METHOD_NAME$Ex takes thistype v1, thistype end returns thistype
            local thistype v2=v1
            local thistype list=v1
            local thistype result=v1.prev
            
            //*********************************************************************
            //  If the last node (end.prev) of the list is equal to the first node
            //  (v1) then skip.
            if v1==end.prev then
                return v1
            endif
            
            //*********************************************************************
            //  Find the halfway through the list by iterating two pointers forward
            //  one twice as fast as the other.
            loop
                set v2=v2.next
                set list=list.next
                exitwhen list==end
                set list=list.next
                exitwhen list==end
            endloop
            
            //*********************************************************************
            //  Now it calls this function again but for each v2 (from v1 up
            //  to the previous node from the v2 and from the v2 up to the end)
            set v1=$METHOD_NAME$Ex(v1,v2)
            set v2=$METHOD_NAME$Ex(v2,end)
            
            //*********************************************************************
            //  Merges the list using 2 pointers: v1 and v2.
            loop
                if $COMPARE_BOOLEAN$ then
                    
                    //*********************************************************************
                    //  If the pointers pass the compare method it means that v2 needs to
                    //  be placed behind v1.
                    set list=v2.next

                    //*********************************************************************
                    //  So we remove v2 from the list...
                    call v2.removeNode()

                    //*********************************************************************
                    //  ...and place it behind v1.
                    call v1.insertNode(v2)

                    //*********************************************************************
                    //  After that we need v2 to point towards the node that was previously
                    //  pointing to v2.next before, that's why i stored it inside "list" to
                    //  now retreive it.
                    set v2=list
                    exitwhen v2==end
                else
                    
                    //*********************************************************************
                    //  If the value doesn't pass the compare method it means there's no
                    //  need for moving (the list is fine) and moves along
                    set v1=v1.next
                    exitwhen v1==v2
                endif
            endloop
            return result.next
        endmethod
        
        //*********************************************************************
        //  head.next is the first value of the list and 0 the end.
        static method $METHOD_NAME$ takes thistype head returns nothing
            call $METHOD_NAME$Ex(head.next,head)
        endmethod
    //! endtextmacro
    
endlibrary

 

[noob]

It is so good that I did not understand well done

 

[Magtheridon96]

Well, your split function has a lot of overhead, but since I don't know how it can be improved, I'll let it go ;P

A few optimizations:

            local thistype this
            
            //*********************************************************************
            //  Always increment the size, this won't cause issues. This allocation
            //  method is similar to Alloc + linked list config.
            set size=size+1
            if 0==this then
                set this=size
            else
                set this=recycle[0]
                set recycle[0]=recycle[recycle[0]]
            endif

->

            local thistype this = recycle[0]
            
            //*********************************************************************
            //  Always increment the size, this won't cause issues. This allocation
            //  method is similar to Alloc + linked list config.
            set size=size+1
            if 0==this then
                set this=size
            else
                set recycle[0]=recycle[this]
            endif

Also, your allocation method DOES cause problems after allocating 8190 instances. It can skip hundreds or even thousands of indicies.
Try this:

local thistype this = recycle[0]
if this == 0 then
    set count = count + 1
    set this = count
else
    set recycle[0] = recycle[this]
endif

edit
Ok, I just noticed you're decreasing the size by 1 in the deallocate method.
If you remove that, my method will work.
Your method has more overhead than mine.

edit

        static method Sort takes nothing returns nothing
            call split(thistype(0).next,0,size)
        endmethod

Change the name of this static method to sort (To follow jass convention)

You know what, why don't you make this sort of like a BST instead. (Binary Search Tree)

When you allocate (insert a value), you'd position it into the list (This way, you don't need a sort function)
Deallocation can be similar to the delete method of Nestharus' AVL Tree (AVL trees are BSTs)

 

[Dirac]

but since I don't know how it can be improved

You can't. I just checked with Nes, he says it's good.

I add/remove to size every allocation to keep track of the amount of nodes the list has, there's no way around it, can't change it.

I'm not sure if users would like to get their list sorted everytime you add a node, makes no sense to me.

Since the method is static i would rather have it with PascalCase because it looks prettier to call Sort() to call sort(). However i'm planing on updating this so you can have multiple lists per struct and sort each list whenever you want (sort would no longer be static) which i already coded, i'm just not sure about the API.

 

[Magtheridon96]

Well, I guess the naming would be ok, but a problem arises when someone does this:
call thistype.Sort()
I wouldn't tap that ;D (trololololololol)

I'm not sure if users would like to get their list sorted everytime you add a node, makes no sense to me.

It's a slight speed gain, you won't need to call Sort
Infact, you wouldn't need sort ^_^
But, I guess you could keep it the way it is because otherwise you'd have to create a node struct with members like:
thistype left
thistype right
thistype parent
etc..

edit

Oh and you could at least change your allocate method to something like this then:

            local thistype this = recycle[0]
            
            //*********************************************************************
            //  Always increment the size, this won't cause issues. This allocation
            //  method is similar to Alloc + linked list config.
            set size=size+1
            if this == 0 then
                set this=size
            else
                set recycle[0]=recycle[this]
            endif

Speedgain FTW ;D

 

[Dirac]

Mag, sorting everytime you add a node would cause a huge speed loss, this isn't a binary tree.
About the alloc method it would be better to return size instead of set this=size. But i'm not going to do that anyways because i'll upload a new version that supports multiple linked lists inside each struct. The new API would look like this

/**********************************************************************
*
*   static method compare takes thistype v1, thistype v2 returns boolean
*
*   module MS
*
*       -   Implement at the top of your struct, below the compare
*       -   method, must extend array.
*
*       thistype next
*       thistype prev
*
*       thistype parent
*           -   The parent of the given instance
*       integer size
*           -   The size of the given list
*
*       static method create takes nothing returns thistype
*           -   Allocates a new list.
*       method clear takes nothing returns nothing
*           -   Clears the given list.
*       method insert takes nothing returns thistype
*           -   Allocates a new node for the given list.
*       method remove takes nothing returns nothing
*           -   Deallocates the given instance
*       method Sort takes nothing returns nothing
*           -   Sorts every instance for the given list.
*
***********************************************************************/

And i'll be adding Alloc as a requirement.

 

[Bribe]

Multiple linked lists inside a struct should be using LinkedList as it doesn't affect your instance count.

And just because Nestharus says it is good doesn't mean anything. For one, safety being "debug-only" just for the sake of speed is completely unorthodox. If someone cares about speed they should manually edit the code to remove the safety, because your system should be set to "Does Not Explode" by default.

For two, the module should be named MergeSort.

For three, Alloc should just be merged into your script, and your allocate and deallocate methods respectively should include all the basic allocation behavior like adding to linked list and adjusting the "size" property.

 

[Magtheridon96]

About the alloc method it would be better to return size instead of set this=size

I know you changed your script, but doing that would've been a bad idea because then the instance wouldn't have been inserted in the linked list.

And I agree with Bribe:
- Module name: MergeSort (MS could mean anything. It could mean MovementSpeed)
- Allocate/Deallocate the instances yourself

edit
Oh and I'd suggest using static arrays for the linked lists if you aren't going to
use Bribe's LinkedList because I find those lists more understandable.

 

[Dirac]

Well i finished a MergeSort for Bribe's LinkedList, however i've had the following issues:
-Its hard to add a compare method without the use of function interfaces (help me out here)
-Bribe's linked list doesn't support prev[0] so i had to allocate a new local for the function.

@Mag
This type of linked list are similar to C style so i wont use static arrays
this = this -> next

EDIT: just checked out kenny's linked list module, it's missing the insertBefore and instertAfter methods... fail
@Bribe
I'm not sure of why are you using hashtable for LinkedList... 8191 is quite a large number and many instances fit there, also you're making of next and prev methods, which breaks compability with ALL linked lists. IMO if you're going to use hashtable, allocate all the instances inside the same child / parent key and have them linked together.

 

[Bribe]

8191 is a large number of LinkedLists but then you must think what you are going to do with all the data inside of those lists ... if you have 100 linked lists, each list can contain about 80 instances. If you have 1000 lists, each list can contain about 81 instances. It really hinders the potential.

Sure a static list with next/prev nodes should be done whenever possible, and in the end the more I look at this I don't know why you'd want to support sorting linked lists inside of each individual struct instance (why would you even want to sort a linked list in the first place?)

 

[Dirac]

I find sorting linked lists the easiest way to sort values inside arrays because of warcraft's inability to allocate arrays.
Updated the snippet and added a version to sort Bribe's LinkedList using a function interface i don't know how to avoid.

 

[Bribe]

Well I don't think the "compare" method needs to be there. I think you should just sort smallest to largest by default and if the user wants it differently you can flip the list which is a pretty easy operation.

 

[Dirac]

Remember that because it's a linked list you can loop by this.next or this.prev, if the list is sorted from smallest to greatest then looping though prev would give you greatest to smallest.
But you're missing something
If there was no compare method then how would the module or the function know which value to sort the list with? This isn't C or Java, you can't pass an array as an argument

 

[Bribe]

I suppose there could be some more complex sorting than just equal to or greater than.

 

[Magtheridon96]

Here's an idea:

method operator < takes thistype other returns boolean
    // this would allow advanced sorting hurrhurrhurrdurr
endmethod

You could use something like this to allow the user to sort instances by some attached value or anything else.

 

[Dirac]

Thanks for the idea mag, but i can't see how is that different from "static method compare".

In the demo map there are 2 tests, one of them explain how to sort lists using different methods (by the use of different structs with different comparisons). Adding any other way to do it would result in a huge speed loss (function interfaces, trigger evaluations) except for a textmacro, but the API would turn so ugly it wouldn't be worth it (or maybe i would?)

 

[Bribe]

The difference is syntactical sugar. Many things in vJass are there for such a reason.

 

[Dirac]

How about this textmacro?

//! textmacro MERGE_SORT takes COMPARE
    
    //*********************************************************************
    //  Ok this method is entitled to split and merge constatly until there
    //  is nothing left to split.
    private static method $COMPARE$MergeSortSplit takes thistype start, thistype end returns thistype
        local thistype half=start
        local thistype list=start
        local thistype result=start.prev
        
        local integer s=0
        
        //*********************************************************************
        //  If the last node (end.prev) of the list is equal to the first node
        //  (start) then skip.
        if start==end.prev then
            return start
        endif
        
        //*********************************************************************
        //  Looks for the value placed at the half of the list.
        loop
            set half=half.next
            set list=list.next
            exitwhen list==end
            set list=list.next
            exitwhen list==end
        endloop
        
        //*********************************************************************
        //  Now it calls this function again but for each half (from start up
        //  to the previous node from the half and from the half up to the end)
        set start=$COMPARE$MergeSortSplit(start,half)
        set half=$COMPARE$MergeSortSplit(half,end)
        
        //*********************************************************************
        //  Merges the list using 2 pointers: start and half.
        loop
            exitwhen start==end or half==end or start==half
            if $COMPARE$(start,half) then
                
                //*********************************************************************
                //  If the pointers pass the compare method it means that the half node
                //  needs to be placed behind the start node.
                set s=half.next

                //*********************************************************************
                //  So we remove the half node from the list...
                set half.prev.next=half.next
                set half.next.prev=half.prev

                //*********************************************************************
                //  ...and place it behind the start node.
                set start.prev.next=half
                set half.prev=start.prev
                set start.prev=half
                set half.next=start

                //*********************************************************************
                //  After that we need half to point towards the node that was
                //  previously pointing half.next before, that's why i stored it
                //  inside "s" and now retreive it.
                set half=s
            else
                
                //*********************************************************************
                //  If the value doesn't pass the compare method it means there's no
                //  need for moving (the list is fine) and moves along
                set start=start.next
            endif
        endloop
        return result.next
    endmethod
    
    //*********************************************************************
    //  head.next is the first value of the list and 0 the end.
    static method $COMPARE$MergeSort takes thistype head returns nothing
        call $COMPARE$MergeSortSplit(head.next,head)
    endmethod
//! endtextmacro

Implementation

scope PressEsc
    
    struct Sort
        integer value
        thistype next
        thistype prev
        
        static method create takes nothing returns thistype
            local thistype this=thistype.allocate()
            set thistype(0).next.prev=this
            set this.next=thistype(0).next
            set thistype(0).next=this
            set this.prev=0
            return this
        endmethod
        
        method destroy takes nothing returns nothing
            set this.next.prev=this.prev
            set this.prev.next=this.next
            call .deallocate()
        endmethod
        
        static method smallestToGreatest takes thistype v1, thistype v2 returns boolean
            return v1.value>v2.value
        endmethod
        
        static method greatestToSmallest takes thistype v1, thistype v2 returns boolean
            return v1.value<v2.value
        endmethod
        
        //! runtextmacro MERGE_SORT("smallestToGreatest")
        //! runtextmacro MERGE_SORT("greatestToSmallest")
    endstruct
    
    
    struct Initialization extends array
        private static method after takes nothing returns boolean
            local integer i=GetRandomInt(5,20)
            local string s
            local Sort this
            
            loop
                set Sort.create().value=GetRandomInt(-100,100)
                set i=i-1
                exitwhen 0==i
            endloop

            call Sort.smallestToGreatestMergeSort(0)
            
            set s=""
            set this=Sort(0).next
            loop
                set s=s+I2S(this.value)
                set this=this.next
                exitwhen 0==this
                set s=s+" < "
            endloop
            call BJDebugMsg("Sorted [ "+s+" ]")
            
            call Sort.greatestToSmallestMergeSort(0)
            
            set s=""
            set this=Sort(0).next
            loop
                set s=s+I2S(this.value)
                set this=this.next
                exitwhen 0==this
                set s=s+" < "
            endloop
            call BJDebugMsg("Sorted [ "+s+" ]")
            
            return false
        endmethod
        
        private static method onInit takes nothing returns nothing
            local trigger trig=CreateTrigger()
            call BJDebugMsg("Press Esc to sort 2 random lists at the same time")
            call TriggerRegisterPlayerEvent(trig,Player(0),EVENT_PLAYER_END_CINEMATIC)
            call TriggerAddCondition(trig,Condition(function thistype.after))
            set trig=null
        endmethod
    endstruct
endscope

 

[Bribe]

That's not so bad.

 

[Dirac]

Changed almost everything.
The system now has the following improvements:
-Multiple MergeSorts per struct
-Custom compare methods for each sort
-Simple sorting of list by variable
-Avoids the use of trigger evaluations

 

[Magtheridon96]

local thistype half=start
local thistype list=start

->

local thistype half=start
local thistype list=half

I know.. I know.. I'm crazy >:O

 

[Bribe]

Good sorting module. Approved.

 

[Dirac]

I was thinking just now, maybe there's a good way to consolidate the two textmacros into a more efficient, friendly new textmacro that would go like this
//! textmacro MERGE_SORT takes METHOD_NAME, COPARE
The user would run it inside a struct in the following manner
//! runtextmacro MERGE_SORT ("SortUnitsByHP","GetWidgetLife(v1.unit)>GetWidgetLife(v2.unit)")
... or if a method were used to compare ...
//! runtextmacro MERGE_SORT ("SortUnitsByHP","thistype.compareUnitLife(v1.unit,v2.unit)")
Later on if he wants to run the sorting method created the only thing to do would be
call SortUnitsByHP(head)
I think it's a lot better this way, is anyone with me?

EDIT: Just updated it to v3.0.0 including the changes described in this post, i'll update the demo map soon (for those who didn't fully understand the vague explanation on how to use in the script)

 

[Dirac]

v3.0.1
-Fixed it to work with the newest version of LinkedListModule (v2.2.0)

Also, some reasons why use MergeSort over other sorting algorithms
-MergeSort happens to be a very stable sorting method where the worst and best case happen to have the same complexity O(n log n) which is better than the best case of some of the other sorting algorithms and better than the best worst case among every other.
-The reason why its so stable is because of it's memory use (2n), compared to other sorting algorithms is high, but this doesn't matter in a w3 evironment.
-The algorithm used by this snippet can't be improved.

 

[Bribe]

Too bad I have no need to sort things, otherwise I would use this.

 

[yuvixadun]

Don't know vJass indepth, but isn't QuickSort faster than MergeSort? Or is it difficult to implement that in vJass?

 

[Dirac]

In post 24 I explained why is better to use this.