[Snippet] LinkedListModule

Level 6
Joined
Jun 20, 2011
Messages
249
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
 
Last edited:
Level 37
Joined
Sep 26, 2009
Messages
8,446
Please keep in mind that "readonly" can still be set by the struct despite it being in a module (there is no "module readonly" unlike "module private").

To work around this bug you'd need a "private thistype headv" and "method operator head".

It could also be mentioned not to use "deallocate" on an instance if it is the current node on the list while iterating (the "next" value will return something invalid).

Also your BJDebugMsg statements are wrong.
 
Level 6
Joined
Jun 20, 2011
Messages
249
For some reason I forgot i was dealing with a module therefore readonly vars are modifiable outside it
Now that i think about it the deallocate method is quite unsafe and the user needs to be informed on how and when to use it, i'll look into that
There's nothing wrong with the BJDebugMsg, i already tested it, works fine and the code compiles

I was also thinking of making next and prev readonly, but that would make some libraries to require this resource instead of making it optional, i'll need your opinion on this matter.
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
I think they should also be readonly (the way I showed you, with method operators returning the private variables).

The BJDebugMsg's work, but check the text inside of strings. There is something quite wrong with both of them.

You could use the "prev" var instead of the "next" var for recycling. Most people iterate forward, and those people are the ones who are the most vulnerable towards getting that bug.

A library should only require this if it can't be inlined in the first place. I don't really see any of this code as optional (save for some of the surplus operations which don't technically need to be there). A normal, static linked list which uses "0" as the head should just be typed out manually.
 
Level 6
Joined
Jun 20, 2011
Messages
249
prev, next and head are now readonly members
Fixed the debug msgs
I'm not going to use prev for iterating the recycle as i now added safety mechanisms that prevent the user from deallocating nodes inside functional linked lists.
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
If you are going to make all of your safety debug-only, you should add protection against doubly-inserting a node into the list.

If this wasn't a module I would say to make safety always-on (speedfreaks can delete the lines of code) but since it is a module having the safety on could really produce a ton of excess text.
 
Level 6
Joined
Jun 20, 2011
Messages
249
Safety isn't debug-only, it's activated by the constant boolean configurable at the top of the script, the debug messages are debug though.

Added protection from adding the same node twice (performs an iteration through the list when it's cleared)
 
Level 6
Joined
Jun 20, 2011
Messages
249
Bribe remember that thistype(0).next is used for recycling, therefore all nodes attached to that list (the list 0) are marked for recycling. I detach all the nodes from the list and attach them to the 0 list (this concept was brought to me by nestharus in the most hideous way)

I'm not sure of what you say with "multiple structs" ... if you mean multiple lists, then no, this would bug if a node were stored in multiple lists (sadly) and there are safety mechanisms that prevent that, if you want to store the same node in another list then use a pointer.
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
Wow it points the entire list to the trash can, I would have never thought of that. Nestharus wins at thinking outside the box.

Well you could make a "emptyList" function which just calls "remove" on everything. This would be useful if you are storing nodes created by a different allocator like a unit indexer for example. But the naming here could be easy to mix up. But then again it would be easy enough for the user to code it if he/she wants to. In case you want to use it (you don't have to of course, especially like I said because of the naming clash):

JASS:
method emptyList takes nothing returns nothing
    loop
        set this = this.next
        exitwhen this.head
        call this.remove()
    endloop
endmethod

Then again, you could name that method "clearList" and you could name your existing one "purgeList".
 
Level 6
Joined
Jun 20, 2011
Messages
249
EDIT: i had to change this whole post because i meant something else
If you're using different allocators (such as unit indexer) it would cause major bugs: Inserting values from different allocators to the same list would cause huge conflicts

It would also cause conflicts if you use the allocation method and insert non allocated values to the list (such as unit indexes)

Instead of looping through the entire list i would set it's next and prev to itself

If a linked list intended to link unit indexes i advise you to use pointers for the list.

TL;DR
Multiple allocators for same linked list -> huge no.
 
Last edited:
Level 6
Joined
Jun 20, 2011
Messages
249
While working on a circular linked list with the module i came across with some issues: toying with the head is hard, which is good, makes difficult for the user to screw up, but it also makes impossible to code a safe circular linked list out of it. So i wrote this module, which allows easy circular list creations, but has no safety mechanisms (so far)
JASS:
    module CircularLinkedList
        private static integer instanceCount = 0
        
        private thistype nextp
        private thistype prevp
        
        method operator next takes nothing returns thistype
            return this.nextp
        endmethod
        
        method operator prev takes nothing returns thistype
            return this.prevp
        endmethod
        
        static method allocate takes nothing returns thistype
            local thistype this=thistype(0).nextp
            if this==0 then
                set instanceCount=instanceCount+1
                return instanceCount
            endif
            set thistype(0).nextp=this.nextp
            return this
        endmethod
        
        method deallocate takes nothing returns nothing
            set this.nextp=thistype(0).nextp
            set thistype(0).nextp=this
        endmethod
                
        method insert takes thistype toInsert returns thistype
            if this==0 then
                set toInsert.nextp=this
                set toInsert.prevp=this
            else
                set this.nextp.prevp=toInsert
                set toInsert.nextp=this.nextp
                set this.nextp=toInsert
                set toInsert.prevp=this
            endif
            return toInsert
        endmethod
        
        method deleteList takes nothing returns nothing
            set this.prevp.nextp=thistype(0).nextp
            set thistype(0).nextp=this
        endmethod
        
        method remove takes nothing returns thistype
            static if ADDITIONAL_SAFETY then
                set this.safetyCheck=false
            endif
            if this==this.nextp then
                call this.deallocate()
                return 0
            else
                set this.prevp.nextp=this.nextp
                set this.nextp.prevp=this.prevp
                return this.nextp
            endif
        endmethod
    endmodule
I think it's worth adding it to the snippet.
 
This linked list implementation seems a bit odd. (well, not really odd, it just doesn't have too many features)

What is the point of moveAfter and moveBefore?

Also (even if this is a light linked list), in my opinion it should store the tail node as well. (size would also be useful in some cases) But I suppose the real question is, is this meant to be a light list implementation or a powerful list implementation?
 
Level 6
Joined
Jun 20, 2011
Messages
249
moveAfter and moveBefore takes a segment of any list and moves it after/before the given node.

Mind telling me what's the "tail" node in a list? you mean the last one? (head.prev)
Also, whats the difference between light and powerful lists?
 
Level 6
Joined
Jun 20, 2011
Messages
249
This would be light list then, but how am i supposed to add search to it? the user should be the one that adds search capacities to the list along with the variables he sets to it.

Also, i'm not going to do that "last" or "first" operators because when you do this...
set ListHead = thistype.newList()
To access the list members you only have to
local thistype this = ListHead.next
The only difference between a head and any other node is that the head can't be removed (and it should be counted as a null instace)
 
Level 6
Joined
Jun 20, 2011
Messages
249
Ok this is going to be hard to explain but i'll give it a shot.

Suppose you have this unit, and you want this unit to store multiple values for it's index, so you use a circular linked list to store a value.
JASS:
struct UnitStorage extends array
    implement CircularLinkedList
    integer value
    integer node
endstruct
Node would point towards any node of the circular linked list, by default it points to 0, so the next node inserted to it would be inserted to itself (this.next and this.prev = to this) after that nodes inserted to it would create a circular linked list.
Example: suppose that node points towards value 3 in a circular linked list of 4 nodes
2 - 3 - 5 - 7 - 2 - 3...
if you insert a value to node and set node to that value you would be successfully allocating a linked list. it's very important for "node" to not be pointing towards a deallocated value from the list.
When you remove a node and that node is the last one from the list it would return 0, otherwise it would return the node's next node. This is made this way to allow the user to keep track if the list is empty or not and to prevent the pointer to the list to not point towards a deallocated value.
 
Level 31
Joined
Jul 10, 2007
Messages
6,307
Ok... insert seems a little too over the top

JASS:
        method insertNode takes thistype toInsert returns thistype
        
            static if ADDITIONAL_SAFETY then
                if toInsert.safetyCheck then
                    debug call BJDebugMsg("[LinkedList] ERROR: attempted to insert a node twice")
                    return 0
                endif
                set toInsert.safetyCheck=true
            endif
            
            if this==0 then
                set toInsert.nextp=toInsert
                set toInsert.prevp=toInsert
            else
                set this.nextp.prevp=toInsert
                set toInsert.nextp=this.nextp
                set this.nextp=toInsert
                set toInsert.prevp=this
            endif
            return toInsert
        endmethod

Just make it a simple insert?
JASS:
                set this.nextp.prevp=toInsert
                set toInsert.nextp=this.nextp
                set this.nextp=toInsert
                set toInsert.prevp=this

Seriously, there has never been a point where I have passed in a node other than the head for that stuff, lol... why would you one of the nodes on the list rather than the list head? : )


For remove, it should just be the regular simple two lines ^)^.


You can also have a clear at 4 lines and you can make destroy just a siple two lines : ).



I just think that you can make this lighter than what you have at the moment ; P.
 
Level 6
Joined
Jun 20, 2011
Messages
249
Well that method is for the CircularLinkedList module which works a little different from the regular one.
The reason i check if this==0
-Imagine that you have a struct that keeps a random pointer towards a circular linked list, if the pointer equals 0 that means the list it points to is non-existant or empty, therefore if you do something like set this.pointer=this.pointer.insertNode(allocate()) you would be inserting new nodes to a circular linked list the pointer points to and you wouldn't have to worry about the list existing or not or having a head for it (if the list is empty it allocates a new node whose next and prev pointers point towards itself, otherwise it would be commonly inserted into it)
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
I have no idea what you are trying to do there with the new LinkedList thing, it's not what I meant.

I meant to have a dynamic linked list like what you made, but without the position-shifting and inserting at arbitrary points - make it append or prepend only, to keep the method count low. That way the only four methods are allocate, deallocate, add and remove.

The way it currently is the LinkedList module you added is nowhere near as cool as the dynamic linked list. You should delete that one and restore the original name.

Ideally I just want a linked list per struct instance, but without having 50 different ways to add to the list (I just need 1, and I recommend it be an append and not a prepend because that gives it more flexibility).
 
Level 6
Joined
Jun 20, 2011
Messages
249
Well by having 4 methods you can't have dynamic lists, therefore the new module, if you wish to append a node you can do the following

local thistype this = head.insertAfter(allocate())

I didn't add an allocation method to it because the user should code it one himself because static linked lists use 0 as the head, so i can't use it for recycling, also it allows you to have linked lists of other allocators (such as unit indexes)
 
Level 31
Joined
Jul 10, 2007
Messages
6,307
Ok Dirac, remove all of your extra stuff... we want just a simple Linked List, the kind that we'd otherwise have to code from scratch all the time : ).


Simple add (always add after the node being added to).
Simple remove (two lines)
Simple clear
Simple create
Simple destroy


That's it. Add should be 4 lines. Clear should be 4 lines. Destroy should be 2 lines. Remove should be 2 lines.


Don't need a swap or anything like that... it'd also be nice to have a link method, which just links 2 nodes together, like nodeAfter.prev = nodeBefore and nodeBefore.next = nodeAfter.
 
Level 6
Joined
Jun 20, 2011
Messages
249
Nes please understand me here.
If a list is meant to be dynamic it needs to have methods to create a or destroy heads. Most linked lists aren't dynamic, and implementing the Dynamic module would result in a lot of overhead and the need to allocate a single head for the entire list.
Non dynamic lists (static lists) are the most common type, they use the "0" instance as the head, and they can't have allocation methods because there's no room to store the deallocated instances and there's no way to create or destroy heads
 
Level 31
Joined
Jul 10, 2007
Messages
6,307
I know about this -.-.... dude, who do you think taught you more about linked lists... I wrote stuff on linked lists way before you were even around.


Here, since you don't seem to understand what I am saying, I'll just show you the resource >.>.

JASS:
module LinkedList
	private static integer ic = 0		//instance count
	readonly thistype next
	readonly thistype prev

	//Create a single node that can act as a head.
	static method create takes nothing returns thistype
		local thistype this = thistype(0).next
		if (0 == this) then
			set this = ic + 1
			set ic = this
		else
			set thistype(0).next = next
		endif

		set next = this
		set prev = this

		return this
	endmethod

	//Add a single node. Adding to itself does nothing.
	method add takes thistype node returns nothing
		set node.prev = this
		set node.next = next
		set next.prev = node
		set next = node
	endmethod

	//Turns a node into a head. Useful when removing nodes and wanting to turn them into lists.
	method toHead takes nothing returns nothing
		set next = this
		set prev = this
	endmethod

	//Remove a single node. Removing from itself does nothing.
	method remove takes nothing returns nothing
		set prev.next = next
		set next.prev = prev
	endmethod

	//Clear a single node or clear a list of nodes
	method clear takes nothing returns nothing
		if (this != prev) then
			set prev.next = thistype(0).next
			set thistype(0).next = next
			set next = this
			set prev = this
		endif
	endmethod

	//Destroy single node or destroy a range of nodes
	method destroy takes nothing returns nothing
		set prev.next = thistype(0).next
		set thistype(0).next = this
	endmethod
endmodule


Please use the above.. it works perfectly... it's semi safe (no double destroy detection)... every node can either be a node or a head... >.<


Also, you can easily add in ranged operations like remove range, swap range, etc, but I have never seen the need for ranged operations so those seem somewhat pointless ; ). Perhaps adding a link method that takes 2 nodes (very simple) and then making an additional optional module for ranged operations would be a good idea.


Also, there is no point in returning the next node... that just adds more overhead -.-. The user can easily access the next node if they need it.



Now, I want you to also notice how very simple the code in mine is compared to the code in yours and I want you to notice that mine doesn't have any issues except for someone being stupid by destroying an already destroyed or not allocated node ;D. Well, they could also add a node on one list to another list, thus breaking the first list ; P, but yea...


Now, if you want the boolean for looping (the isHead or w/e), you'll have to give up some functionality, like any node being able to be a head : ).

JASS:
module LinkedList
	private static integer ic = 0		//instance count
	readonly thistype next
	readonly thistype prev
	readonly boolean head

	//Create a single node that can act as a head.
	static method create takes boolean isHead returns thistype
		local thistype this = thistype(0).next
		if (0 == this) then
			set this = ic + 1
			set ic = this
		else
			set thistype(0).next = next
		endif

		set next = this
		set prev = this
		set head = isHead

		return this
	endmethod

	//Add a single node. Adding to itself does nothing.
	method add takes thistype node returns nothing
		set node.prev = this
		set node.next = next
		set next.prev = node
		set next = node
	endmethod

	//Remove a single node. Removing from itself does nothing.
	method remove takes nothing returns nothing
		set prev.next = next
		set next.prev = prev
	endmethod

	//Clear a single node or clear a list of nodes
	method clear takes nothing returns nothing
		if (this != prev) then
			set prev.next = thistype(0).next
			set thistype(0).next = next
			set next = this
			set prev = this
		endif
	endmethod

	//Destroy single node or destroy a range of nodes
	method destroy takes nothing returns nothing
		set prev.next = thistype(0).next
		set thistype(0).next = this
		set head = false
	endmethod
endmodule

Notice that I removed the toHead method. Again, the code is extremely simple granted that the user doesn't do stupid things ; P. Notice again that the code is simple and small. The above is directly what I code from scratch whenever I need a linked list. Well, sometimes I don't use the head boolean, like in Catalog ; ).
 
Level 6
Joined
Jun 20, 2011
Messages
249
Nes i don't know from where you got the idea that i doubt on your linked list knowledge.

Ok i'll do those changes to the DynamicLinkedList module.
The reason the LinkedList module exists i already explained in the post before.

It doesn't return the "next" node, it returns the same node it takes in the argument to avoid a few lines of code
JASS:
local thistype this = allocate()
call head.addNode(this)
->
JASS:
local thistype this=head.addNode(allocate())

Also remember that all those extra lines are OPTIONAL the user can turn them all off in the ADDITIONAL_SAFETY boolean at the top of the script, they wont compile if false, but you already knew this, i don't know why are you asking me to delete them.
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
This is the list structure I need. It does a lot less but it doesn't add a bunch of features that I don't want.

This is the list structure I need. It does a lot less but it doesn't add a bunch of features that I don't want.

JASS:
module BList //Bribe's List
    private static integer indexN = 0
    private static integer array n_xt
    private static integer array prev
    private static boolean array head
    debug private static boolean array live
    
    method operator next takes nothing returns thistype
        return .n_xt[this]
    endmethod
    
    method operator isHead takes nothing returns boolean
        return .head[this]
    endmethod
    
    static method create takes integer from returns thistype
        local integer this = .prev[0]
        if this == 0 then
            set this = .indexN + 1
            set .indexN = this
            debug if .indexN > 8190 then
            debug     call BJDebugMsg("[BList] Created too many nodes!!")
            debug endif
        else
            set .prev[0] = .prev[this]
        endif
        if from == 0 then
            set .head[this] = true
            set .n_xt[this] = this
            set .prev[this] = this
        else
            debug if not .head[from] then
            debug     call BJDebugMsg("[BList] Linking node to invalid list head: " + I2S(from))
            debug endif
            debug set .live[this] = true
            set .prev[this] = .prev[from]
            set .n_xt[.prev[from]] = this
            set .prev[from] = this
            set .n_xt[this] = from
        endif
        return this
    endmethod
    
    method destroy takes nothing returns nothing
        if .head[this] then
            set .head[this] = false
            debug loop
            debug     set this = this.next
            debug     exitwhen .head[this]
            debug     set .live[this] = false
            debug endloop
            set .prev[.n_xt[this]] = .prev[0]
        else
            debug if .live[this] then
            debug     set .live[this] = false
            debug else
            debug     call BJDebugMsg("[BList] Destroying invalid instance: " + I2S(this) + "!!")
            debug endif
            set .n_xt[.prev[this]] = .n_xt[this]
            set .prev[.n_xt[this]] = .prev[this]
            set .prev[this] = .prev[0]
        endif
        set .prev[0] = this
    endmethod
endmodule
 
Level 6
Joined
Jun 20, 2011
Messages
249
I liked Nes's way.
The system still has an issue: People that have no interest in dynamism are obliged to create a head for the list even when it doesn't need one, this would be in case the struct already has it's own allocator (such as Alloc). I was thinking that maybe to solve this issue i could use the instance (1) as a default head for Lists and have it created with module initialization.

EDIT: i just added the "base" static head, useful for when the user doesn't need dynamism
JASS:
local thistype this=allocate()
call base.insertNode(this)
Saves the user from checking if the head already exists
 
Last edited:
Honestly, Bribe's version is the best. It doesn't add useless features like a previous operator, a clear method, and a search method. People use lists for iteration, so why should we create resources that go beyond that? They're never going to use these 'cool' features you're implementing. A search method is really easy to inline anyway. It wouldn't be a problem if the user needed one. You may think "But what if he does it wrong?". Well, if he does it wrong, he shouldn't even be here.

Then again, these simple lists are pretty easy to inline.. They could be useful for beginners though.

And another thing: Multiple lists per struct? When am I going to need that?
I know they could be useful, but if you're going to support multiple lists, you should go ahead and make it a struct because making it a module would increase the size of the map-script.
 
Level 6
Joined
Jun 20, 2011
Messages
249
Jesus mag you really didn't get why this resource is so important.
If i wanted 1 list per sturct i just would go ahead and code a list using 0 as the head, after all, there would be no sense in methods for flushing the list since there's only 1 list.

The real beauty of this is being able to navigate along the 8190 instances for real dynamism, it's a way of having "array" variables inside each instance, but you can only have as many up to the sum of them all until it reaches 8190, that will almost never happen.
Of course static lists are easy to inline, this system provides dynamic list.
The prev method is important because: if you added elements to your list following a given order and you want to iterate backwards you can go through prev (This would be in case you use my merge sort library that always sorts from smallest to greatest, but if you want greatest to smallest you navigate using prev) another reason is because there's no insertBefore method anymore, the user can do node.prev.insertNode(this).

Also, Bribe's implementation doesn't allow you to insert nodes that were created by other allocators, such as unit indexes, so being able to say what node to insert is quite important.

EDIT: Another reason of why Bribe's approach is less effective is because now there really isn't a way to flush lists, you can create lists using 0 as the head, throwing everything out the window
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
Dirac, you didn't understand my approach.

First, you said that using a different allocator is suckage because the instance IDs will clash (I suppose that's why you made your allocator-free version).

When you pass "0" to the create method rather than adding to a list it creates a new list using itself as the head. I am still only using 0 for deallocation, I am not linking anything else to it, same as what you did.

I only need dynamic lists that loop forward. I have no reason to loop backward. And using my system if you destroy the head it destroys the entire list, and if you destroy a node it simply removes it from the list.

I don't want a list which doesn't have allocators because then I might as well inline it because the structure is simple enough to understand.
 
You know, if you create a list struct using Table instances for all your data, you'll be able to support 2^32 - 1 instances (Negative numbers can work too)

edit
Actually, if you're going to use Table arrays, then you can support about 4 million instances with 1000 nodes per list. (Which is a lot)
You can make the max nodes per list configurable and based on that value, you can use a Table:
prev[MAX_NODES * this + x]
next[MAX_NODES * this + x]
 
Level 6
Joined
Jun 20, 2011
Messages
249
@Bribe
I'm sorry for the confusion, still your version wouldn't support circular lists without heads.
Also it provides no control of the nodes, i've found myself several times allocating new instances and inserting them to nodes after a few process because i want to "insert only instances that follow a criteria" or maybe because "i want to merge sort my list"

@Mag
And why would someone need that? The API would be terrible and you would need to declare things as if you were in C
You're basically saying that Bribe's LinkedList (the Table version) is a better approach when it simply isn't.
The whole idea of this is to use linked lists to simulate arrays inside structs to avoid the use of hashtables (which basically are array variables for structs)
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
Dirac,

And if I don't care about those things, looks like I have to suffer the overhead of extra methods which I have no use for.

Take this example:

  • A projectile struct has 100 live projectiles.
  • There are 10 targets in total, and there are 10 projectiles per target.
  • If I want a spell or behavior to affect all projectiles on a single target, and I don't want to have to O(N) the entire projectile tree, then I want a simple iterable list for all targets on a single projectile.
  • I only need to iterate through the list. I don't need any "swap position" or "insertAtPosition" methods, nor a previous method, I just need to be able to insert and remove to the list and iterate forwards through it.
  • Your entire LinkedList library doesn't contain a single module that does only what I want without adding features I don't want.
 
Level 6
Joined
Jun 20, 2011
Messages
249
Bribe if anything there's only 1 extra method, the insertNode method.
This is how your system would work compared to mine (1 extra line)
JASS:
//Bribe's
local thistype this=create(thistype(GetUnitUserData(unit)).pointer)
JASS:
//Dirac's
local thistype this=allocate()
call thistype(GetUnitUserData(unit)).pointer).insertNode(this)
It's not that hard, and the amount of choices you gain and the amount of unnecessary if checks makes up for the fact of having to write 1 single more line.

The deleteList or flushList methods are completely necesary, what a better way to deallocate full lists instead of having to iterate through the list? Your system deallocates the whole list, what if you want to save the head? You would have to allocate a new one (and if the head was attached to a var it would have to reassign that var) : /.
Also your idea of using "prev" instead of next makes no sense, by doing this you're buggin the list, you think that messing up with prev wont cause issues, but the reason prev is there is because you need it to remove nodes from the list (which sometimes you just want to remove, not deallocate), with your current deallocation method the list would break.
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
Dirac you are being stubborn to the point of making completely weird arguments.

My list recycles using "prev" and yours uses "next". I simply reversed the recycling behavior. Why should mine break when yours doesn't? Well it's because mine doesn't break.

Recycing using "prev" is smarter because you can take off from the list while iterating from it, without breaking.

The "destroy" method I wrote will either destroy a list or destroy an instance of it. I don't need to recycle heads.

I have no need to remove from the list without deallocating.
 
Level 6
Joined
Jun 20, 2011
Messages
249
It breaks because you're not making it properly and i though it was because you though my code has a lot of over head due using next for recycling, when it doesn't.
Your deallocation method
JASS:
set .prev[.n_xt[this]] = .prev[0]
My deallocation method
JASS:
set this.prevp.nextp=thistype(0).nextp
set thistype(0).nextp=this.nextp
set this.nextp=this
set this.prevp=this
Your list breaks.

The fact that you don't have to recycle heads doesn't apply to people who do want to recycle a head. With my version you can avoid recycling the head with clearList

You're as stubborn as me by sticking to a version with less flexibility
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
You missed the part after the endblock where I set .prev[0] = this. Setting the variables back to itself is not important if the list is being destroyed and not simply being emptied.

You're being stubborn with a version that has too much flexibility at the cost of code bloat, I have been simply arguing why I want less code and you don't understand it.
 
Level 6
Joined
Jun 20, 2011
Messages
249
With the current version you can create a static list (dynamic would bug) of other allocators (such as unit custom values) using the "base" head, if i wanted to do that with your version i would have to initialize a head at initialization and use pointers for the other allocator's instances.
If i were to implement your idea i would have to make prev and next public due the occasional need of extra methods, methods that would do stuff like
  • Move nodes from one list to another
  • Insert nodes after or before other nodes
  • Recycle the head
  • Only remove the node from the list to prevent it from being iterated, but keeping the data safe if the user wishes to later re-enable it
And i've already encountered myself many times in need of these methods
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
Great for you, but like I said which you still don't accept is that I don't need that overhead, what I built is exactly what I want.

I am not talking about the "one list for all ends and means", maybe I have given you that impression, but that's why I named it BribeList and which is why I said (or, what I think I said) I'd probably just end up inlining it into my own resource as-needed.

Since you already have 3 types of LinkedList mine would be "just another type" which is why I even bothered to write it and share it with you.
 
Level 37
Joined
Sep 26, 2009
Messages
8,446
No I haven't, but now that I see it, it's much worse than the linked lists you had before because now the user has to suffer tons of extra methods when you used to have a lighter version in there somewhere.

JASS:
            set thistype(8191).nextp=8191
            set thistype(8191).prevp=8191
            set thistype(8191).headp=true

You know the value 8191 bugs with saved games?
 
Level 6
Joined
Jun 20, 2011
Messages
249
No I haven't, but now that I see it, it's much worse than the linked lists you had before because now the user has to suffer tons of extra methods when you used to have a lighter version in there somewhere.
Actually no, the light version was a static list based on 0 and had no allocation methods, with the current module you can use "base" as head and insert nodes to it.

Now i see why did you complain about code bloat, the previous version did have a lot of unnecessary methods, which i have removed because lists are already flexible enough.

You know the value 8191 bugs with saved games?
W3 is full of bugs, i'll make the head 8190 instead.

Here I coded this demo to show proper linked list usage
It's pretty simple, if a unit has the backpack abilities it can store and drop items from a stash
JASS:
library Backpack uses LinkedListModule, SpellEffectEvent, UnitIndexer

    globals
        private constant integer    BACKPACK_PICK_ABILITY   = 'A006'
        private constant integer    BACKPACK_DROP_ABILITY   = 'A005'
        private constant integer    BACKPACK_DEFAULT_SIZE   = 8
        private constant real       ITEM_DROP_RADIUS        = 100
    endglobals
    
    private struct Backpack extends array
        implement LinkedList
        
        integer itemId
        
        integer size
        integer count
        thistype list
        
        static method onDrop takes nothing returns nothing
            local unit u=GetTriggerUnit()
            local thistype index=GetUnitUserData(u)
            local thistype this=index.list.next
            local integer i=0
            local real a=GetUnitFacing(u)*bj_DEGTORAD
            local real x=GetUnitX(u)
            local real y=GetUnitY(u)
            loop
                exitwhen head
                call CreateItem(itemId,x+ITEM_DROP_RADIUS*Cos(bj_PI*2*i/index.count+a),y+ITEM_DROP_RADIUS*Sin(bj_PI*2*i/index.count+a))
                set i=i+1
                set this=next
            endloop
            call index.list.clearNode()
            set index.count=0
        endmethod
        
        static method onPick takes nothing returns nothing
            local unit u=GetTriggerUnit()
            local item i=GetSpellTargetItem()
            local thistype index=GetUnitUserData(u)
            local thistype this
            if index.count<index.size then
                set this=allocate()
                call index.list.insertNode(this)
                set index.count=index.count+1
                set this.itemId=GetItemTypeId(i)
                call RemoveItem(i)
            endif
            set i=null
            set u=null
        endmethod
        
        method index takes nothing returns nothing
            set this.size=BACKPACK_DEFAULT_SIZE
            set this.list=createNode()
        endmethod
        
        static method filter takes unit u returns boolean
            return GetUnitAbilityLevel(u,BACKPACK_PICK_ABILITY)!=0
        endmethod
        
        static method onInit takes nothing returns nothing
            call RegisterSpellEffectEvent(BACKPACK_PICK_ABILITY,function thistype.onPick)
            call RegisterSpellEffectEvent(BACKPACK_DROP_ABILITY,function thistype.onDrop)
        endmethod
        
        implement UnitIndexStruct
    endstruct

endlibrary

EDIT: updated to v2.1.0
-"base" now points towards 8190 to avoid conflict with other allocators
-createNode now takes no arguments, nodes created this way are considered heads.
 
Top