• Listen to a special audio message from Bill Roper to the Hive Workshop community (Bill is a former Vice President of Blizzard Entertainment, Producer, Designer, Musician, Voice Actor) 🔗Click here to hear his message!
  • Read Evilhog's interview with Gregory Alper, the original composer of the music for WarCraft: Orcs & Humans 🔗Click here to read the full interview.

[Snippet] LinkedList Object

Level 11
Joined
Mar 6, 2008
Messages
898
Hiho,

this is my creation for a LinkedList object.
Until now I only noticed that there are LinkedList modules which you have to implement in your struct, scope or library but I thought that some people may need an object of a LinkedList and that's why I made this small snippet.

I hope you like it and that nobody else already made something very similar to this. :p

JASS:
library LinkedList /* v1.0.0
**************************************************************************************************
*   A library which gives user the possibility to create LinkedList objects with all
*   basic functionalities. It also provides an easy way to define custom LinkedList
*   of non-native objects data.
**************************************************************************************************
*
*   As LinkedList objects are very flexible all examples are made with the unit data type!
*
*   Please give me credits if you use this in your maps.
*
**************************************************************************************************
*   API:
*       - create
*           Creates a new LinkedList object
*
*       - destroy
*           Destroyes this LinkedList object and all its LinkedListElements.
*           Runtime: O(n)
*
*       - add
*           Adds a new element to this LinkedList object
*           Runtime: O(1)
*
*       - remove
*           Removes an element from this LinkedList object
*           Runtime: O(n)
*
*       - has
*           Checks if this LinkedList object contains the given element
*           Runtime: O(n)
*
*       - get
*           Returns the LinkedListElement object of the given element
*           Runtime: O(n)
*
*       - getHead
*           Returns the first element of this LinkedList object
*           Runtime: O(1)
*
*       - getSize
*           Returns the total amount of elements stored in this LinkedList object
*           Runtime: O(1)
*
*       - isEmpty
*           Checks if this LinkedList object contains no elements
*           Runtime: O(1)
**************************************************************************************************
*
**************************************************************************************************
*   If you want to create a new LinkedUnitList object you have to type in the following:
*       call LinkedUnitList list = LinkedUnitList.create()
*
*   Adding a new unit to the list is also very simpel:
*       call list.add(udg_myUnit)
*       Note: udg_myUnit is just a default variable of type 'unit'!
*
*   To check if you LinkedUnitList is empty just type in the following:
*       local boolean empty = list.isEmpty()
*
*   The rest of the API should be self-explanatory.
**************************************************************************************************
*
**************************************************************************************************
*   You can add new LinkedList types (for example for your own object types)
*   by extending the text macro in the end of this code snippet.
*   Be sure that the FINALIZE parameter is set to "null" if you aren't using native types!
**************************************************************************************************
*/

//! textmacro LinkedListE takes TYPE, NAME, FINALIZE
private struct Linked$NAME$ListElement
    public $TYPE$ element
    private thistype previous
    private thistype next

    method destroy takes nothing returns nothing
        set .element = $FINALIZE$
        set .previous = 0
        set .next = 0
        call .deallocate()
    endmethod

    public method hasNext takes nothing returns boolean
        return .next != null
    endmethod

    public method hasPrevious takes nothing returns boolean
        return .previous != null
    endmethod

    public method getNext takes nothing returns thistype
        return .next
    endmethod

    public method getPrevious takes nothing returns thistype
        return .previous
    endmethod

    method setNext takes thistype n returns nothing
        set .next = n
    endmethod

    method setPrevious takes thistype p returns nothing
        set .previous = p
    endmethod

    static method create takes $TYPE$ h returns thistype
        local thistype this = thistype.allocate()
        set .element = h
        set .previous = 0
        set .next = 0
        return this
    endmethod
endstruct

struct Linked$NAME$List
    private Linked$NAME$ListElement head
    private integer size

    public method destroy takes nothing returns nothing
        local Linked$NAME$ListElement cur = .head
        loop
            exitwhen cur == 0
            call cur.destroy()
            set cur = cur.getNext()
        endloop
        set .head = 0
        set .size = 0
        call .deallocate()
    endmethod

    public method getHead takes nothing returns Linked$NAME$ListElement
        return .head
    endmethod

    public method has takes $TYPE$ h returns boolean
        local Linked$NAME$ListElement cur
        if h != null and not .isEmpty() then
            set cur = .head
            loop
                exitwhen cur == 0
                if cur.element == h then
                    return true
                endif
                set cur = cur.getNext()
            endloop
        endif
        return false
    endmethod

    public method get takes $TYPE$ h returns Linked$NAME$ListElement
        local Linked$NAME$ListElement cur
        if h != null then
            set cur = .head
            loop
                exitwhen cur == 0
                if cur.element == h then
                    return cur
                endif
                set cur = cur.getNext()
            endloop
        endif
        return 0
    endmethod

    public method add takes $TYPE$ h returns boolean
        local Linked$NAME$ListElement e
        local Linked$NAME$ListElement cur
        if h != null and not .has(h) then
            set e = Linked$NAME$ListElement.create(h)
            if .isEmpty() then
                set .head = e
            else
                set cur = .head
                set .head = e
                call .head.setNext(cur)
            endif
            set .size = .size + 1
            return true
        endif
        return false
    endmethod

    public method remove takes $TYPE$ h returns boolean
        local Linked$NAME$ListElement e
        local Linked$NAME$ListElement prv
        local Linked$NAME$ListElement nxt
        if h != null and .has(h) then
            set e = .get(h)
            set prv = e.getPrevious()
            set nxt = e.getNext()
            call prv.setNext(nxt)
            call nxt.setPrevious(prv)
            call e.destroy()
            set .size = .size - 1
            return true
        endif
        return false
    endmethod

    public method getSize takes nothing returns integer
        return .size
    endmethod

    public method isEmpty takes nothing returns boolean
        return .size == 0
    endmethod

    public static method create takes nothing returns thistype
        local thistype this = thistype.allocate()
        set .head = 0
        set .size = 0
        return this
    endmethod
endstruct
//! endtextmacro

//! runtextmacro LinkedListE("integer", "Integer", "0")
//! runtextmacro LinkedListE("real", "Real", "0")

//! runtextmacro LinkedListE("handle", "Handle", "null")
//! runtextmacro LinkedListE("player", "Player", "null")
//! runtextmacro LinkedListE("unit", "Unit", "null")
//! runtextmacro LinkedListE("item", "Item", "null")
//! runtextmacro LinkedListE("destructable", "Destructable", "null")
//! runtextmacro LinkedListE("location", "Location", "null")
//! runtextmacro LinkedListE("trigger", "Trigger", "null")
//! runtextmacro LinkedListE("effect", "Effect", "null")
//! runtextmacro LinkedListE("rect", "Rect", "null")
//! runtextmacro LinkedListE("region", "Region", "null")
//! runtextmacro LinkedListE("texttag", "Texttag", "null")
//! runtextmacro LinkedListE("trackable", "Trackable", "null")
//! runtextmacro LinkedListE("timer", "Timer", "null")
//! runtextmacro LinkedListE("timerdialog", "Timerdialog", "null")
//! runtextmacro LinkedListE("group", "Group", "null")
//! runtextmacro LinkedListE("force", "Force", "null")

endlibrary

Robbepop
 
hasNext and hasPrevious should probably check if the integer is equal to 0. iirc, integer arrays default 0, so hasNext and hasPrevious will always return true.

Unless you check if .next.element != null, but since 0 represents a null struct it should be fine if you check .next or .prev != 0.

Also, you can place has below the get method, and simplify it to:
JASS:
return this.get(h) != 0
It does not matter a whole lot, but since you use a textmacro that is ran several times, it might help shed a few lines without too much sacrifice in speed.

Also, in your add method, I don't ever see you assign a prev value? Unless I am mistaken. You might also want to note in the documentation that it is adding to the front of the list instead of the tail/in front of the head.

In your destroy for the LinkedList, you set head and size to 0, so I don't think you have to set them to 0 in the create method.
 
Level 11
Joined
Mar 6, 2008
Messages
898
Hiho,

@Magtheridon96: could you please give me a link to a LinkedList resource where all functions run in O(1)? I can only find LinkedList modules or one LinkedList object in wc3c.net which you can only use for integers or custom types.

@PurgeandFire111: thank you for your hints and suggestions. =)

Robbepop
 
Poorly coded and ugly syntax. Not much more to say.

Deallocation can be done in O(1) for a linked list if you do it correctly. You didn't do it correctly, so you are doing it in O(n).

As mag said, this has been done to death. Even if we ignore that point, the algorithms you use are bad.

Also, I don't see where you are doing your linking in the add method... sure, you set the next, but you don't finish the link... did you event test this?

This also appears to be a circular linked list, but nowhere do you state that. I had to look in the remove method to find out that it was a circular (looked at how you did removal). And wtf is up with your locals?

JASS:
        local Linked$NAME$ListElement prv
        local Linked$NAME$ListElement nxt

Furthermore, learn to use method operators or readonly fields. Your methods make this look very ugly.

edit
The general stance of THW is minimalism. Your count field is not part of the minimalist approach. A linked list if fully operational w/o a count. As such, it should be removed. If you want a count, put it in a higher level linked list that uses this one.
 
Level 11
Joined
Mar 6, 2008
Messages
898
Hiho,

"thank" you for your criticism.
however, you could also say me how to improve things instead of just saying that everything I wrote just sucks ...

For example. How do you plan to deallocate a linked list if you want (and need) to destroy all linked list elements?
And what is so bad about my locale variables? - okay I use more than I have to, but this is for readability.
I heard that readonly is bugged or not working properly and that's why I don't use it - btw, what's wrong with my fields? Nothing can be abused, or have you find something that is abusable?
And I really don't get what you want to tell me with your "count" ...

Robbepop
 
For example. How do you plan to deallocate a linked list if you want (and need) to destroy all linked list elements?

You can do that in O(1). There are plenty of code examples on THW.

I heard that readonly is bugged or not working properly and that's why I don't use it

In modules. You are using macros.

And what is so bad about my locale variables?

They make the code less readable than this... this is a standard remove method. Yours looks like an abomination.

JASS:
set prev.next = next
set next.prev = prev
call deallocate()

And I really don't get what you want to tell me with your "count" ...

count isn't needed, so it shouldn't be included.


My recommendation is that you research into regular linked list code and redo everything. Furthermore, there is a reason modules are used instead of structs and there is a reason struct resources were never submitted. There is a use for structs as they can be general lists, but the same thing can be accomplished with modules abstracting to different list types.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
To deallocate a whole linked list in O(1) it needs a custom allocator without any safety, and you will leave handle variables not nulled, which could lead soon or late to hande id leaks.
Seriously O(N) is not that bad here ...
At least when we are talking about destroy a whole linked list.
 
To deallocate a whole linked list in O(1) it needs a custom allocator without any safety, and you will leave handle variables not nulled, which could lead soon or late to hande id leaks.
Seriously O(N) is not that bad here ...
At least when we are talking about destroy a whole linked list.

O(n) for debug, O(1) for non-debug. How's that?
 

Dr Super Good

Spell Reviewer
Level 64
Joined
Jan 18, 2005
Messages
27,259
O(n) for debug, O(1) for non-debug. How's that?
You can't be sure that you catch all the bugs.
And what about handle id leak ?
Comprimise?

Destroyed lists are added to a "garbage collection list". Doing this should be O(1) as you are enqueuing the list onto another list. When you allocate list elements you pop from the garbage collection list or allocate new space. The garbage collection list can be perodicly emptied (nulling elements). A trigger for emptying the list might be a generic garbage collection that could be called when handles exceede a certain ID number.

Obviously forgoing the stupid method of allocation used by structs is probably a good idea here.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Ok, ok.

The thing is that, give me a real map where you would need to deallocate linked lists so many times, that the algorithm will matter.
My point is that it's way too tedious, and it will be never noticeable in game.
And yes i prefer a map which is only partially broken than "totally".
And with safe allocate/deallocate the map could just work well even if there was a mistake on the script.

Ofc you're supposed to debug your map, but it doesn't mean you've catched all the bugs, you could have missed some cases.

And anyway about your previous sentence, come on, you're not the best person to talk about compromise.
 
Level 6
Joined
Jan 17, 2010
Messages
149
I'd like to add my 2 cents + experience with different list implementation for wc3. These are personal opinions + problems I've encountered from experience with vjass and honestly idc if someone has an objection.

Point #1
Generally if an O(n) deallocation becomes a problem for link lists, that means you are in danger of approaching the instance limit. I.E the lists are long or there are many tiny lists with few nodes each. Circumventing the instance limit defeats the point of having list's marginal speed gain. Using instance extension converts some of the array lookups into functions, which further makes it slower. Typically if you need 1000 lists containing 20 links each, you would want to use a hashtable implementation instead as there are no limits on the nodes that hashtable have (actually there is but it's much higher).

Point #2
Destroying lists in such frequency O(n) deallocation becomes a problem means you are doing it wrong. Generally you should avoid excessive memory allocation/deallocation in high frequency unless its absolutely necessary.

Point #3
Most of the lists I've encountered in wc3 (including libraries such as SoundUtils). have around 10 elements on average. O(n) where n = 10 is a non issue, unless you are spamming allocate/deallocate (see point #2)

Point #4
Don't use List { Node this, Node next } architecture. Instead of dedicated node structs, use the structs you are are listing.

This essentially means the list should be a module. Also, won't need to deallocate the nodes because there are no nodes to begin with. The drawback is that a struct can only belong to one llst, which is fine in most cases.


Once again, these are opinions backed by experience and practicality, not formal knowledge.
 
If you look at my Std Collections thing, the lists I have in there do not have deallocation. They leave deallocation up to the user =). The reason is that deallocation can be a little different depending on the circumstances for the list.

Here is my main argument for O(1). You say that O(n) is good enough. Why would you stick with good enough when you can have even better?

Also, I do happen to have at least one library that can have lists with between 200 and 4000 elements and I allocated/deallocate maybe 10 lists at a time in an instant... without O(1) deallocation, I'd hit the op limit in a major way. Don't tell me I'm doing the lib wrong either. It is one of the most efficient libs on THW. I also use trigger evals to avoid the op limit. If I were to follow your philosophy of O(n), it'd likely double the number of required trigger evals, which would cause a severe freeze in the game. I had to rewrite that entire lib to heavily optimize it as much as I could as people were complaining that it was too slow (and the slower version was still using optimal approaches that Troll-Brain would likely freak out at, 0 safety, max speed).

I speak of BigInt : D.


Also, when I work on a map, I thoroughly debug it. When I release it and a bug occurs that I didn't catch, I just go back to debug mode and squash the bug >.>. In gameplay, w/o debug mode, bugs do result in the game freezing tho : |.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Then we don't have the same meaning for the word "better".
I gave my reasons, efficiency is not an issue in most of cases, while safety and avoid memory leak really does matter.
Ofc it's better when it's faster AND doesn't have cons, it's not the case here.

And you lie to yourself, honestly how many maps you've released, hell even your code resources have bugs, and i expect there are more, since i supposed that they are not really used, excepted few ones probably.
But to be fair, they are legion though.

Now about BigInt, is it intended to be used several times in the game or only one ?
Anyway, if the difference is noticeable then ofc this deallocation in O(1) makes sense, but you have to agree that they are only rare concrete cases, not theoric ones.
Also, if you need that much of efficiency wouldn't be better to inline yourself this stuff, so this resource would be pointless, right ?
Or maybe as a textmacro, "module textmacro freaky", or whatever, i'm not the guy who use this kind of stuff ...
 
Level 6
Joined
Jan 17, 2010
Messages
149
Better is subjective, and therefore an opinion. Up to the user to decide, really.

I already explained why linked list spam is not very practical for wc3 and using hashtable based lists is more practical for some cases.

In other words, I'm against LinkedList Nodes as a structs (A node module would be better). This is because Nodes as structs do not cover use cases i'm getting hit with, just like someone might not like that for O(n) deallocation. It's all based on use case. O(n) deallocation is not enough as an argument against this resource, no matter how its put. Don't like it? delete the method yourself. problem solved.


Don't tell me I'm doing the lib wrong either

No offence, You're doing it wrong.

BigInt? for a save system?
much faster: http://en.wikipedia.org/wiki/Block_cipher_modes
2 array substitutions and a permutation per character that can store 6 bits of data.
if you hit OP limit with that you deserve a commadore64.
Yes, you'll have to rewrite your whole save system. Yes, it will be much shorter. Yes, it will be much faster. No, I won't give you my source code.

Anything else you need BigInt for wc3? A "lets have fun with math" map? meh. You're probably doing that wrong too. Think outside the box.

Once again, wrong is my opinion based and biased by my experience, it's up to you to judge the validity of it. I don't intend to shove my opinions it down to anyone's throat. Like it or leave it, idc, really.

So in other words, yes, you're doing it right, I'm doing it wrong. BigInt4life. Boom, blew your mind, dust settles, life moves on. Random lib is off topic, btw.
 
Well, it's not only BigInt that requires absolute efficiency. Block detection also requires insane efficiency. Even A* (what is considered to be the fastest) is not efficient enough. I had to do my own homebrewed method to increase the efficiency by perhaps 5000%.

As for systems, some have bugs, a lot don't ; \. The more complex the system it is and the lower version it is, the more likely it is to have bugs. BigInt is extremely complex, but it has 0 bugs. Timer Tools is also extremely complicated, and it does have bugs : \. AuraStruct, excluding Timer Tools, is very complicated, and its bugs were fixed, but it's still bugged as it uses the bugged Timer Tools, which I have yet to fix. My block detection has bugs in the preprocessing, but it's actual block detection algorithm is bugless. Believe me, at this point, I know what systems have bugs and what don't and I even know the causes of those bugs :\. All of my save/load stuff is flawless though ^)^. I'm just not into wc3 anymore, so I don't really do coding. Also, some of the bug fixes would require a lot of time to fix. I also may know the causes, but I may still have to figure out the solution to fixing them (correct logic, proper design, etc).


Anyways, I am still a firm believer that safety should only ever be in debug mode ^_^.
 
Level 6
Joined
Jan 17, 2010
Messages
149
Even if A* spam was viable, spamming it using dynamic allocation/deallocation of nodes is not, even if it's O(1). Instance limit.

Point is, this is useful but not because of its efficiency. Not being able to use this for BigInt or A* is poor argument.

P.S on the other hand, O(n) for size/contains/add/remove is unacceptable
 
Level 11
Joined
Mar 6, 2008
Messages
898
in the end I don't think that we should care TOO much about extreme performance in wc3 scripting as JASS and especially vJass are not really very performant themselves and besides that a good programmer knows which parts of his map/system/code should require high performance because of the amount of executions of the code snippet/function or whatever.

I will update this LinkedList object library and if you want you can add it to your pool for people like me who actually like it more than module lists. And if you don't I don't care and use it by myself. :p

Robbepop
 
Level 6
Joined
Jan 17, 2010
Messages
149
I completely agree with you. I disagree with O(n) deallocation = this is invalid. If for any reason this is invalid, its because you can only have 8191 nodes without problems. Heck, its even in the vjass documentation.
 
We're talking about the "protect the users from themselves" mentality vs the "perform as efficiently as possible" mentality. Protecting users from themselves helps them find bugs, yea. In gameplay, do the players want to see all of that debug crap? No. Do they want the map to limp on? No :\.

What I usually do in debug is completely destroy the map if a bug occurs. I will crash the thread, I will disable the system, I will stop the map from moving forward. Do players want that either? No. Do map makers want that? Yes, it helps them find bugs without getting spammed with error messages. Don't believe me? Try debugging a 5000 line system that has 20 errors in it running 1 test case. You will be spammed to hell and you will not even be able to read the crap or know where the errors occurred.

What I'm really saying is that I believe that the sort of "protection" demonstrated in this system is outdated compared to "newer" and what I consider to be "much better" methods. I'm not trying to be biased, I know I came up with most of these methods (I mean all of them, cough), but there are reasons for these new things.

#1: helps map makers spot bugs more quickly as the system disables itself and crashes the thread. That's good.

#2: keeps the map performing as quickly as possible. This may not really matter, but in a very high quality map, this can mean the difference between a slideshow and actual gameplay.

#3: performance makes room for other code to do its stuff. Code that doesn't perform as well takes longer, meaning that you can't run as much code per instant without turning the game into a slideshow. Take projectiles as an example. There are some projectile systems that can only handle 75 projectiles. There are others that can handle 125-150. The ones I do can typically handle between 400-700 depending on what features you are using. Not all of these tests were scaled on the same comp, but when they were, one projectile system (a popular one that i won't mention) could do about 100 projectiles. The one I did could do 650. This was the exact same computer. More efficient code = more room to run more stuff. Should it not be our goal then to keep code as absolutely efficient as possible so that later on we can add cool new features without having to go back and recode everything so that the map is optimized enough to handle said new features. It's better to just get it right the first time around. Not only will your map run better, but you'll save time in the long run as well (you won't have to go back and redo it all).

Yea, O(n) when it's the only thing running in the map is fine. Don't be a hog and take everything for yourself. It's like some systems that use an entire hashtable when they could just as easily run off of a table. There are only a limited number of resources that can be utilized in a map, so a resource developer that puts something out to the public should make it their goal to consume as little of those limited resources as possible. Make the dent in the person's map as small as possible. This means as little code as possible and as efficient code as possible. Debug statements should also be used to make the code as easy to use as possible (easy to debug usages of the system later on).


Now if you are all for, "let's consume whatever the hell we want and not give a damn about the mapper. Let's not even give them a choice as to whether they want protection or not, let's shove it down their throat," I'm afraid I can never ever agree with you : \. This is the reason why I hate most resources on wc3c, because that's exactly what they do.

If you want to make a resource for yourself, it's your own business. If you want to make a resource for the public, you better give them whatever options they want, even if you don't agree with them. This doesn't mean turn your resource into a chainsaw. On the contrary, keep your resource as simple as possible (which is why count shouldn't be included in this, you are forcing the user to have the count even if they don't need it just because you think it's cool).

Public resources are made for other users. You need to keep that in mind.

Write documentation that's easily understandable. It doesn't matter if you understand it, other people have to understand it too.
Write code that can either be safe or as speedy as possible. Some people always want safe and others are like me. Satisfy both of them, don't go FU to the other party. If the first party wants safety on at all times, they can just keep debug mode checked -.-. I know that's what TKoK does. This is not up for you to decide as it's a public resource.


You may think I'm being unreasonable, but I don't even write safety nets in my own private code. I have 0 safety in code that's not public. I follow the above things just like everybody else does. The above leads to quality code that everyone can be happy about. Sure, there will be some people that will always be FU just because the stuff is optional (they don't seem to understand that debug mode can just stay checked and they can have all of their safety on at all times), but those people are highly unreasonable and uncompromising. Don't code for just them >.>. Try to code for everybody.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Nestharus said:
but those people are highly unreasonable and uncompromising

And what about you, really ?
And yeah maybe i'm just the same.

No matter how many lines or even pages you will write about it, as said there are just opinions, the safety approach is still valid, ofc i'm not saying that it should display debug messages on a map, messages are for the debug mode only, and a released map should be saved on not debug mode.
Something like how struct allocations/deallocations are handled by vJass, even if yeah they could be improved.
 
Level 6
Joined
Jan 17, 2010
Messages
149
To robbepop

Please change to O(1) get/has/remove. This can be achieved with tables or some pointers in the Node struct.

for "has", node can have "owningList" field

"remove" just needs to set prev/next to prev.next = next and next .prev = .prev

"get" is tricky..Its also powers the above 2. This is because you may have different comparables (i.e criteria you get by- for units you may get by unit name, id, or type id). Not going in to this too deep, but a hashtable is pretty nice and simple solution.

These are just simple solutions.

I don't recommend removing size, as many people consider it a standard array/list operation.

O(n) deallocate is fine.
 
Level 11
Joined
Mar 6, 2008
Messages
898
Hiho,

yeah, as I've already said I will update it as I also found some mistakes within the code itself and I will try to do what you've recommended with hashtables in order to reduce has/get/remove from O(n) to O(1). ;-)

Then a moderator can decide if this resource is good or not - but I will use it anyway as I like list objects really much. =)

Robbepop
 
Top