System MergeList

Dirac

22710180
Reaction score
147
JASS:
library MergeList
//*********************************************************************************
//      MergeList
//*********************************************************************************
//  MergeList is an efficient method to order your instances
//  depending on a number each one has assigned.

//*********************************************************************************
//  API:
/*
        method insert takes nothing value returns nothing
*/
//      -This method allocates your instance in the struct, you must initialize it's
//      "sort" value before calling Sort
/*
        method delete takes nothing returns nothing
*/
//      -Removes the allocated instance from the list, this completly scrambles
//      the sorting
/*
        method Sort takes nothing returns nothing
*/
//      -Sorts all the instances according to their value, you have to call this
//      manually because it's faster than calling it everytime an instance is
//      allocated
/*
        this<i>
*/
//      -Use this to reffer to instance number <i> on the list of instances.
//      Ex: head<i>.unit
/*
        .position
*/
//      -Returns the position of that instance in the list

//*********************************************************************************
//  How to use:
//
//      -Implement ML at the top of you struct

//      -You must have this method somewhere in your struct, it determines wether
//      it orders the instance by the highest number or the lowest
/*
        private static method compare takes thistype v1,thistype v2 returns boolean
            return v1.yourVariable&lt;v2.yourVariable
        endmethod
*/
//      -Use &lt; for lowest and &gt; for highest

//*********************************************************************************
globals
    private constant integer ARRAY_SIZE=100
endglobals
    module ML
        private thistype array node[ARRAY_SIZE]
        private integer size=0
        private thistype head
        readonly integer position
        
        private method Merge takes integer start,integer split,integer max returns nothing
            local integer k=start
            local integer i=start
            local integer j=split+1
            local thistype array t
            loop
                exitwhen (i&gt;split) or (j&gt;max)
                if compare(.node<i>,.node[j]) then
                    set t[k]=.node<i>
                    set i=i+1
                else
                    set t[k]=.node[j]
                    set j=j+1
                endif
                set k=k+1
            endloop
            loop
                exitwhen (i&gt;split)
                set t[k]=.node<i>
                set i=i+1
                set k=k+1
            endloop
            loop
                exitwhen (j&gt;max)
                set t[k]=.node[j]
                set j=j+1
                set k=k+1
            endloop
            loop
                exitwhen (k==start)
                set k=k-1
                set thistype(t[k]).position=k
                set .node[k]=t[k]
            endloop
        endmethod
    
        method Sort takes nothing returns nothing
            local integer i=1
            local integer j=1
            local integer n=0
            loop
                exitwhen (i&gt;.size)
                    set i=i*2
                    loop
                        exitwhen (n*i&gt;.size)
                        set n=n+1
                        if n*i&lt;=.size then
                            call .Merge(j,(n*i+j)/2,n*i)
                        else
                            call .Merge(j,(n*i+j)/2,.size)
                        endif
                        set j=n*i+1
                    endloop
                    set j=1
                    set n=0
            endloop
        endmethod
        
        method delete takes integer whichOne returns nothing
            set .head.node[whichOne]=.head.node[.size]
            set .head.size=.head.size-1
            call .destroy()
        endmethod
        
        method insert takes nothing returns thistype
            local thistype i=.size+1
            local thistype a=thistype.allocate()
            set a.head=this
            set .size=i
            set .node<i>=a
            return a
        endmethod
        
        method operator[] takes integer i returns thistype
            return .node<i>
        endmethod
        
    endmodule
endlibrary</i></i></i></i></i></i></i></i>
Demonstration
JASS:
scope TEST
    struct someStruct
        private integer value
        
        private static method compare takes thistype v1,thistype v2 returns boolean
            return v1.value&lt;v2.value
        endmethod
        
        implement ML
        
        private static method AfterWait takes nothing returns nothing
            local integer i=1
            
            local thistype array head
            local thistype array d
            
            set head[1]=thistype.create()
            set d[1]=head[1].insert()
            set d[1].value=982
            set d[2]=head[1].insert()
            set d[2].value=594
            set d[3]=head[1].insert()
            set d[3].value=114
            set d[4]=head[1].insert()
            set d[4].value=435
            set d[5]=head[1].insert()
            set d[5].value=84
            set d[6]=head[1].insert()
            set d[6].value=13
            
            set head[2]=thistype.create()
            set d[1]=head[2].insert()
            set d[1].value=1409
            set d[2]=head[2].insert()
            set d[2].value=7655
            set d[3]=head[2].insert()
            set d[3].value=2450
            set d[4]=head[2].insert()
            set d[4].value=2309
            set d[5]=head[2].insert()
            set d[5].value=1943
            
            call head[1].Sort()
            call head[2].Sort()
            
            loop
                exitwhen i&gt;6
                call BJDebugMsg(I2S(head[1]<i>.value))
                set i=i+1
            endloop
            set i=1
            loop
                exitwhen i&gt;5
                call BJDebugMsg(I2S(head[2]<i>.value))
                set i=i+1
            endloop
            //13 - 84 - 114 - 435 - 594 - 982 - 1409 - 1943 - 2309 - 2450 - 7655
        endmethod
        
        //i add this so the debug mesages show up on the message log
        private static method onInit takes nothing returns nothing
            call TimerStart(CreateTimer(),0,false,function thistype.AfterWait)
        endmethod
    endstruct
endscope</i></i>

Changelog
Version 0.02
-Allows multiple lists for the same struct
-No longer requires the struct to extend array
 

Nestharus

o-o
Reaction score
84
Bad, just use a compare method >.>

Should just have a sort that's a non static method, nothing else.


Should also expect next and prev pointers.
 

Dirac

22710180
Reaction score
147
next and prev pointers are as easy as typing
[ljass]thistype[this.position+1][/ljass]
i can add them to the system if needed, and maybe i will.

Don't know what you mean with "non static method sort". You wan't this system to support multiple Lists at the time? maybe later.

The compare method is right there

I just found a huge flaw in the system however, and since i made this based on some merge sort tutorials i found, it's hard to fix it. Here's the flaw:
Since the Merge method combines 2 number sequences A[] and B[] into 1 sequence C[] depending on the order, there's a gap in my method.
Examples:
Merge A and B by the lowest
A[]=1,3,5,7
B[]=2,4,6,8
1<2 then C[1]=1
3>2 then C[2]=2
3<4 then C[3]=3
5>4 then C[4]=4
5<6 then C[5]=5
7>6 then C[6]=6
7<8 then C[7]=7
8 is left so C[8]=8
That worked out well. Ok what happens if i sort the following array?
A[]=
1 -- 4 -- 2 -- 6 -- 5 -- 3 -- 7 -- 8
first i split it into 2
A1[]=
1 -- 4 -- 2 -- 6
A2[]=
5 -- 3 -- 7 -- 8
and into 2 again until the array size is 1
A1[]=
1 -- 4
A2[]=
2 -- 6
A3[]=
5 -- 3
A4[]=
7 -- 8
////////
A1[]=1
A2[]=4
A3[]=2
A4[]=6
A5[]=5
A6[]=3
A7[]=7
A8[]=8
Ok now i proceed to Merge those arrays in the following order
A1[] with A2[] turns into the new A1[]
A3[] with A4[] turns into the new A2[]
A5[] with A6[] turns into the new A3[]
A7[] with A8[] turns into the new A4[]
Now
A1[]=
1 -- 4
A2[]=
2 -- 6
A3[]=
3 -- 5 <== this is the only one that changed because 3 is lower than 5
A4[]=
7 -- 8
Ok merge again in the following order
A1[] with A2[] turns into the new A1[]
A3[] with A4[] turns into the new A2[]
Now
A1[]=
1 -- 2 -- 4 -- 6
A2[]=
3 -- 5 -- 7 -- 8
Finally merge the 2 last arrays and we get
A[]=
1 -- 2 -- 3 -- 4 -- 5 -- 6 -- 7 -- 8

the issue starts here
If the initial array size is 6 there is an array that remains isolated, and i don't know how to fix it
A[]=
2 -- 5 -- 4 -- 3 -- 1 -- 6
///////
A1[]=
2 -- 5 -- 4 -- 3
A2[]=
1 -- 6 <== isolated array
///////
A1[]=
2 -- 5
A2[]=
4 -- 3
A3[]=
1 -- 6
///////
A1[]=2
A2[]=5
A3[]=4
A4[]=3
A5[]=1
A6[]=6
///////
Merge once
A1[]=
2 -- 5
A2[]=
3 -- 4
A3[]=
1 -- 6
Merge again
A1[]=
2 -- 3 -- 4 -- 5
A2[]=
1 -- 6 <== isolated array
The new A[] is
2 -- 3 -- 4 -- 5 -- 1 -- 6
If Split it turns into
A1[]=
2 -- 3 -- 4
A2[]=
5 -- 1 -- 6
then merge those 2
A[]
2 -- 3 -- 4 -- 5 -- 1 -- 6
DIDNT WORK OUT :(
Reason? A2[]'s first number can't be bigger than the second, see how 5 is higher than 1, breaks the whole thing
 

Nestharus

o-o
Reaction score
84
You 100% didn't seem to get my suggestion : p.


Get rid of your 2 modules and only have 1 that uses a compare method. See my Binary Heap stuff to see what I mean.


The linked list needs to be multi instantiable and there should only be a sort method. It should depend on list module with next/prev pointers that allow writes.


And I shouldn't need to point this out (since you should be removing allocate/deallocate), but your allocation and deallocation suck. You are using an indexed array, which will end up breaking the pointers... if someone points to a node, their pointer can become corrupt (pointing to a different piece of data).


Otherwise nice attempt at merge sort.
 

Dirac

22710180
Reaction score
147
If you mean that the compare method is the one that sets the type (real or integer) that can't be done, plus your Binary Heap snippet works only with integers.

My allocation and deallocation sucks because i made impossible for the user to modify nodes (made them private), the only way to access them is through the operator [], if deleted the instance is recycled but the list must be sorted again.

I should remove the allocate and deallocate method? maybe, but that would cause you to manually set the value of that instance for later sorting. It would be impossible to add a safety mechanism to that.

I've never seen a struct that allows more than 1 linked list at the time, is that even necessary?
 

Dirac

22710180
Reaction score
147
Update!

-Fixed the huge flaw the system had when ordering lists whose size wasn't a multiple of 4
 

Nestharus

o-o
Reaction score
84
My binary heap doesn't only work with integers... it works with any type and any type of comparison...

jeezes -.-, you really don't get it.


Just use the compare method. The integers are pointers to structs >.<, and those structs can have anything in them. They can also be used as direct integer values (like I did in demo).


Some comparisons are of multiple types.



So yes, compare method can easily set the type... that is easily done >.>. I did it in Binary Heap, so don't tell me it can't be done because I've already done it -.-.

I've never seen a struct that allows more than 1 linked list at the time, is that even necessary?

I use structs with multiple lists all the time... It's rarer for me to use a non instantiable list >.<.
 

Dirac

22710180
Reaction score
147
Ok i get the whole "compare method" suggestion, the only problem is that it forces the user to create the compareable variable. As in
JASS:
struct test
  implement ML
  real someReal
  private static method compare takes thistype v1, thistype v2 returns boolean
    return v1.someReal&gt;v2.someReal
  endmethod
endstruct

But i guess that won't be a problem (for most people)
I'll start working on the multi instanceable list, but i think it would make almost impossible to use position in list to get to the instances. Ex
JASS:
call BJDebugMsg(I2S(thistype[3].value)) // this wont be possible anymore, you would have to use this.next or this.prev and i don&#039;t like the idea
 

Nestharus

o-o
Reaction score
84
I'll start working on the multi instanceable list, but i think it would make almost impossible to use position in list to get to the instances. Ex

That's how it should be, lol.

And that example you provided wouldn't matter because you break it with your indexed array stuff anyways, so using the indexes like that is bad..

And rather than using an index, you'd use a node pointer, so your complain is mute : P, that is unless you meant getting the third item in a list regardless of what it is. In that case, then yea, you'd need to go through the pointers =P.


On another note, I say to use a Linked List module because there are many different things you can have on lists and many different types of sorting... having a different linked list implementation for every type of sorting doesn't really make sense. It makes more sense to have a sort that just uses a list, so all sorts can use 1 list ; P. For that, you'd need a standardized list API.


My idea for that is-
JASS:

readonly boolean head
readonly List next
readonly List prev


And then a few methods- swap, remove, add, allocate, deallocate

And for sorting, a compare method.


For non instantiable lists, 0 would be used.
 

Dirac

22710180
Reaction score
147
In that case, then yea, you'd need to go through the pointers =P.
Yes, that's what i want.

I share this with you nes, this system is incomplete, but right now it's very useful. Merge Sort is really fast and this can be very helpful to people that need to sort instances like AIDS structs or anything that it comes to their head.

I intend to do as you ask, but needs time.
 

Dirac

22710180
Reaction score
147
Update
Version 0.02
-Allows multiple lists for the same struct
-No longer requires the struct to extend array
The only thing that bothers me is that the struct can't extend array now, it's because the linked lists are based off a random instance you set, not instance 0. If required i'll upload a module that allows you to implement this in array structs, but won't work with multiple lists.
 

Nestharus

o-o
Reaction score
84
They can still extend arrays >.>


Also, your algorithm is still bad. You can do this with 1 loop with 2 nested loops, that is your hint. Should also only be 1 method for sorting.


Until you only have 1 outer loop with 2 nested loops and 1 method for sorting, your algorithm will continue to be bad ; P
 

GFreak45

I didnt slap you, i high 5'd your face.
Reaction score
130
your algorithm will continue to be bad ; P

damn nestharus a little harsh man :p

if you feel the need to say things like that at least give it 2 ratings, an overall and a gradual improvement rating (if followed from the start) so he knows where hes at as far as the system
 

Dirac

22710180
Reaction score
147
As a matter of fact i'm currently trying to learn C++ but i don't have a compiler neither for mac nor PC. It would be great help if you help me with that one
 

KaerfNomekop

Swim, fishies. Swim through the veil of steel.
Reaction score
612
I was using this one in my classes a few months back. It really helped me in my understanding of JASS.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top