Snippet LinkedListModule

Dirac

22710180
Reaction score
147
JASS:
library LinkedListModule /* v2.3.1

Easy implementation of linked lists into structs.

***********************************************************************
*
*   module LinkedList
*
*       -   Implement at the top of your struct, must extend array
*
*       thistype next
*       thistype prev
*       boolean  head
*
*       readonly static thistype base
*           -   Precreated head, useful for non-dynamic lists.
*
*       static method allocate takes nothing returns thistype
*       method deallocate takes nothing returns nothing
*
*       static method createNode takes nothing returns thistype
*           -   Allocates a new node pointing towards itself.
*           -   These nodes are considered "heads" therefore it's head
*           -   boolean member is set to true.
*       method insertNode takes thistype toInsert returns thistype
*           -   Inserts the instance before the node.
*       method removeNode takes nothing returns nothing
*           -   Removes the node from the list.
*       method clearNode takes nothing returns nothing
*           -   Deallocates all the instances within the node's range.
*       method flushNode takes nothing returns nothing
*           -   Clears and deallocates the node.
*
*   module LinkedListLite
*       -   Only has the members and the allocation methods.
*       -   To be used with the provided textmacros.
*
*       textmacro LINKED_LIST_HEAD takes node
*           -   Turns the node into a head.
*       textmacro LINKED_LIST_INSERT takes node, toInsert
*           -   Inserts the instance before the node.
*       textmacro LINKED_LIST_REMOVE takes node
*           -   Removes the node from the list.
*       textmacro LINKED_LIST_CLEAR takes node
*           -   Deallocates all the instances within the node's range.
*       textmacro LINKED_LIST_FLUSH takes node
*           -   Clears and deallocates the node.
*       textmacro LINKED_LIST_MERGE takes nodeA, nodeB
*           -   Merges two lists together (Don't merge loose nodes!)
*
**********************************************************************/
    
    module LinkedListLite

        private static integer instanceCount = 0

        thistype next
        thistype prev
        boolean  head
        
        static method allocate takes nothing returns thistype
            local thistype this = thistype(0).prev
            if this==0 then
                debug if instanceCount==8190 then
                    debug call BJDebugMsg("[LinkedList] Error: attempted to allocate too many instances.")
                    debug return 0
                debug endif
                set instanceCount = instanceCount+1
                return instanceCount
            endif
            set thistype(0).prev = prev
            return this
        endmethod
        
        method deallocate takes nothing returns nothing
            set this.prev=thistype(0).prev
            set thistype(0).prev=this
            set this.head=false
        endmethod

    endmodule

    module LinkedList
        implement LinkedListLite
        
        static method operator base takes nothing returns thistype
            return 8190
        endmethod
        
        static method createNode takes nothing returns thistype
            local thistype this=allocate()
            //! runtextmacro LINKED_LIST_HEAD("this")
            return this
        endmethod
        
        method clearNode takes nothing returns nothing
            //! runtextmacro LINKED_LIST_CLEAR("this")
        endmethod
        
        method flushNode takes nothing returns nothing
            //! runtextmacro LINKED_LIST_FLUSH("this")
        endmethod
        
        method insertNode takes thistype toInsert returns nothing            
            //! runtextmacro LINKED_LIST_INSERT("this","toInsert")
        endmethod
        
        method removeNode takes nothing returns nothing
            //! runtextmacro LINKED_LIST_REMOVE("this")
        endmethod
        
        private static method onInit takes nothing returns nothing
            set thistype(8190).next = 8190
            set thistype(8190).prev = 8190
            set thistype(8190).head = true
        endmethod
        
        static if DEBUG_MODE then
            method print takes nothing returns nothing
                local string s=""
                local thistype exit=this
                loop
                    set s=s+I2S(this)
                    set this = next
                    exitwhen this==exit
                    set s = s+" - "
                endloop
                call BJDebugMsg("[ "+s+" ]")
            endmethod
        endif
        
    endmodule

    //! textmacro LINKED_LIST_HEAD takes node
        set $node$.next = this
        set $node$.prev = this
        set $node$.head = true
    //! endtextmacro
        
    //! textmacro LINKED_LIST_CLEAR takes node
        if $node$!=$node$.next then
            set $node$.next.prev = thistype(0).prev
            set thistype(0).prev = $node$.prev
            set $node$.next = $node$
            set $node$.prev = $node$
        endif
    //! endtextmacro
        
    //! textmacro LINKED_LIST_FLUSH takes node
        set $node$.next.prev = thistype(0).prev
        set thistype(0).prev = $node$
        set $node$.head = false
    //! endtextmacro
        
    //! textmacro LINKED_LIST_INSERT takes node, toInsert
        set $node$.prev.next = $toInsert$
        set $toInsert$.prev = $node$.prev
        set $node$.prev = $toInsert$
        set $toInsert$.next = $node$
    //! endtextmacro
        
    //! textmacro LINKED_LIST_REMOVE takes node
        set $node$.prev.next = $node$.next
        set $node$.next.prev = $node$.prev
    //! endtextmacro

    //! textmacro LINKED_LIST_MERGE takes nodeA, nodeB
        set $nodeA$.next.prev = $nodeB$.prev
        set $nodeB$.prev.next = $nodeA$.next
        set $nodeA$.next = $nodeB$
        set $nodeB$.prev = $nodeA$
    //! endtextmacro

endlibrary
 

PurgeandFire

zxcvmkgdfg
Reaction score
509
The naming of insertA and insertB is not clear enough, you should make it more explicit to insertAfter and insertBefore. (using A and B denotes to most two versions of a function)
 

Sevion

The DIY Ninja
Reaction score
424
The Allocation and Deallocation methods are a bit unsafe.

I can see you used Nestharus's/My method of allocation/deallocation.

You could just use Alloc to manage this. It adds like 10 lines of safety and that safety really only occurs in debug mode.
 

Dirac

22710180
Reaction score
147
Yes you have a clever security mechanism.
My allocation method is like 3 lines shorter, perhaps you may want to update Alloc?
Maybe i'll just remove the allocation methods and have the user implement Alloc if wanted. How does that sound?

Also i was thinking of making next, prev and head readonly, but i would have to make this system a not-optional requirement of MergeSort
 

Nestharus

o-o
Reaction score
84
These methods are crap, rewrite them

JASS:

        method clearList takes nothing returns nothing
        
            static if ADDITIONAL_SAFETY then
                if this.head!=this then
                    set this=this.head
                endif
            endif
            
            loop
                exitwhen this==this.next
                call this.next.deallocate()
                set this.next=this.next.next
            endloop
        endmethod
        
        method flushList takes nothing returns nothing
        
            static if ADDITIONAL_SAFETY then
                if this.head!=this then
                    set this=this.head
                endif
            endif
            
            call this.clearList()
            call this.deallocate()
        endmethod


And your allocation is crap for linked lists, redo it.

You should be using the next field for your recycler... from there, clearing an entire list is 4 lines and no loop.


Correct Clear Method
JASS:

set prev.next = thistype(0).next
set thistype(0)..next = next
set next = this
set prev = this


Notice how mine does not have a loop.


Redo some of this and try again ; )



Also, on another note, you can easily move a ranged of nodes from one list to another with 4 lines. With 6 lines, you can swap 2 ranges of nodes with each other.


Also, destroying an entire list should still be 4 lines. If you want the additional head safety, you can increase it to 7 lines (the if statement).
 

Dirac

22710180
Reaction score
147
Nes you just made me realize many many things
I'll work on that

EDIT: pulled off everything you said, except for the swap 2 ranges of nodes (not sure if i did it correctly)
 

Nestharus

o-o
Reaction score
84
Here's swap. You can ignore my extra if statement stuff for safety and working with 0. I didn't have a clear in here, for clear, I did list.link(0,0) ; ).

JASS:

//! textmacro DEQUEUE_LINK takes NAMESPACE, NODE_HEAD, NODE_REF_1, NODE_REF_2
    //this can result if head.next == head.previous, in cases where there is only one node
    //without doing this, this type of link would result in an infinite list in which the
    //node pointed to itself.
    
    //cases of 0, 0 are not dangerous
    if $NODE_REF_1$ == 0 or $NODE_REF_1$ != $NODE_REF_2$ then
        //if node ref 1 is null, link head.next to node ref 2
        if $NODE_REF_1$ == 0 then
            set $NODE_HEAD$.next$NAMESPACE$ = $NODE_REF_2$
        else //otherwise normal link
            set $NODE_REF_1$.next$NAMESPACE$ = $NODE_REF_2$
        endif
        
        //if node ref 2 is null, link head.previous to node ref 1
        if $NODE_REF_2$ == 0 then
            set $NODE_HEAD$.previous$NAMESPACE$  = $NODE_REF_1$
        else //otherwise normal link
            set $NODE_REF_2$.previous$NAMESPACE$ = $NODE_REF_1$
        endif
    endif
//! endtextmacro

//used for temporarily copying 2 nodes. Useful for swapping operations
//! textmacro DEQUEUE_TMP_COPY takes NODE_REF_1, NODE_REF_2
    set $NODE_REF_1$.previousTemp = $NODE_REF_1$
    set $NODE_REF_1$.nextTemp = $NODE_REF_2$
//! endtextmacro

//ini dequeue head
//! textmacro DEQUEUE_INI_HEAD takes NAMESPACE, HEAD
    set $HEAD$.previous$NAMESPACE$ = 0 //head.previous = 0
    set $HEAD$.next$NAMESPACE$ = 0 //head.next = 0
//! endtextmacro

/*
struct Test extends array
    //! runtextmacro MALLOC_FIELDS("")
    //! runtextmacro DEQUEUE_FIELDS("")
    
    //toList.move(args)
    public method move takes thistype node1, thistype node2, thistype toNode1, thistype toNode2 returns nothing
        //toNode1 <-> node1 <-> ...
        //! runtextmacro DEQUEUE_LINK("", "this", "toNode1", "node1")
        //... <-> node2 <-> toNode2
        //! runtextmacro DEQUEUE_LINK("", "this", "node2", "toNode2")
    endmethod
    
    //linking nodes allows for destruction, clearing, adding, moving, and swapping
    //the move operation is actually 2 links
    public method link takes thistype node1, thistype node2 returns nothing
        //node1 <-> node2
        //! runtextmacro DEQUEUE_LINK("", "this", "node1", "node2")
    endmethod
    
    //creates a head and sets it's next and previous to 0
    public static method create takes nothing returns thistype
        local thistype this
        
        //! runtextmacro MALLOC_ALLOCATE_FREED("", "this")
        else
            //! runtextmacro MALLOC_ALLOCATE_NEW("", "this")
        endif
        
        //! runtextmacro DEQUEUE_INI_HEAD("", "this")
        
        return this
    endmethod
    
    //swap node1 and node2 part of head with toNode1 and toNode2 part of toHead
    public static method swap takes thistype head, thistype node1, thistype node2, thistype toHead, thistype toNode1, thistype toNode2 returns nothing
        //cpy node1_1.previous to previousTemp
        //cpy node1_2.next to nextTemp
        //! runtextmacro DEQUEUE_TMP_COPY("node1.previous", "node2.next")
        
        //node2_1.previous <-> node1_1 <-> node1_2 <-> node2_2.next
        //! runtextmacro DEQUEUE_LINK("", "toHead", "toNode1.previous.next", "node1")
        //! runtextmacro DEQUEUE_LINK("", "toHead", "node2", "toNode2.next.previous")
        
        //previousTemp <-> node2_1 <-> node2_2 <-> nextTemp
        //! runtextmacro DEQUEUE_LINK("", "head", "previousTemp", "toNode1")
        //! runtextmacro DEQUEUE_LINK("", "head", "toNode2", "nextTemp")
    endmethod
endstruct


So it should actually be 9 lines total for swap.


Also, your head stuff... is pointless. Because you are moving ranges around, you are only moving some of the head.


Only the head of the list should have the head marked. For that, you might as well use a boolean that marks it as the head. That is how I created linked lists now ^)^. The boolean will also be faster for looping.

So without the head thing there, your swap will end up being 9 lines of code, which is what I said it should be ; ).


In your destroy or w/e, unmark the head as a head. In create, mark the head as a head. Make sure the head field is a public readonly boolean.
 

tooltiperror

Super Moderator
Reaction score
231
For structs needing a linked list module, you can use Kenny's module script. For procderural programming, use Ammorth's LinkedList. This is just yet another approach at something that has already been done.

I really fail to see what this does that is so special, besides insertBefore, which is the same as link.insertAfter(link.prev, data).
 

Dirac

22710180
Reaction score
147
Kenny's module is broadly incomplete.
Ammorth's is only one list for all the structs (if heavily used will cause bugs) and it uses keywords.
Bribe's list is similar to Ammorth's but it uses hashtable, and it's API is very annoying, and because of the way it's coded it looks more into a stack with search capacities than a linked list.

The special thing about this is that it works. And since Nes's suggestions is now faster, more intuitive and useful than others, again i HAD to code this in order to have MergeSort working right
 

Bribe

vJass errors are legion
Reaction score
67
Bribe's LinkedList is only useful because it does not risk surpassing the 8190 array value.

I don't recommend it for things that can easily avoid it, it is meant to be used for really complex and dynamic data referencing.

How do you get the idea to say "looks like a stack with search capabilities than a linked list". You don't use a linked list for searching, you use associative arrays for that. You use a linked list for storage, iteration and in more complex cases you can benefit from its simple removal techniques.
 

Dirac

22710180
Reaction score
147
And now my question:
On which scenario are you going to need 8190 nodes in a single struct?
Your list would make sense if the only alternative is Ammorth's, but since you can make it a module it's virtually impossible to hit the 8190 limit, using your same philosophy i would use hashtables for every variable type because anything can surpass the 8190 limit.

@Nes
Is your swap safe when dealing with nodes that touch each other?
 

Bribe

vJass errors are legion
Reaction score
67
I did not write that system to beat modules or any other sane, array-using alternative. In fact there was just one situation where need presented itself for me to write it up.

If you have a look at Berb's Custom Projectiles, he uses hashtables to create "Projectile Groups". I got the idea to use projectile groups to store all the projectiles homing in on one target, so that if the target wanted to do something like "reverse all projectiles targetting me" then I could just iterate the projectile group.

LinkedList was created as a dynamic, modular and optimized alternative to his projectile group.
 

Dirac

22710180
Reaction score
147
Well in that case you could just create a circular linked list and have the size of the list stored in a var, iteration from 1 random element of the list through it's next value "size" times would result in enumerating every projectile.
You'll have to convince me that your list must be used for certain cases, within possible, were it does things this kind of lists cant
 

Bribe

vJass errors are legion
Reaction score
67
That is a much better approach when you bring it to my attention. With your way you are not limiting yourself by saying "projectile can have max of X targets otherwise it won't fit into the array" because you'd just be storing a circularly linked list, like you have here, inside the struct itself, as no way a combination of projectiles and targets is going to reach unsafe array bounds.

That's what thinking outside of the box gives you. You should submit this to the hive as well, and then I can graveyard LinkedList.
 

Dirac

22710180
Reaction score
147
Just submitted it to the hive.

Regarding circular lists with this snippet:
Remember that the head of the list is also an allocated instance of your struct, so setting values it's perfectly fine.
However clearing the list wont deallocate the head, it must be deallocated manually
 

Sevion

The DIY Ninja
Reaction score
424
Yes you have a clever security mechanism.
My allocation method is like 3 lines shorter, perhaps you may want to update Alloc?

Sorry, meant to get back to this earlier, but forgot about it. Why would I update Alloc to use a less secure method? Sacrifice security to gain what? 2 lines (yes it really is only 2 lines).

The minute efficiency gain is not worth the security loss.
 

Dirac

22710180
Reaction score
147
I've got to admit that Alloc's security mechanisms had shown me some errors.
Anyways I tried to recode Alloc my own way and it turned out to be the same exact number of lines (if you take into account the security mechanism)
The beauty of this system is that it can deallocate whole lists without iterating through it. The bad thing about it is that it's not very safe (the additional safety makes up for these issues, but it causes great speed loss)
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Staff online

      Members online

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top