[vJASS] Efficient way to loop over struct instances

[moyackx]

Hello fellow vJASSers:

I've been reading some tutorials about optimized structs using the struct data extends array.

Now I'm using http://www.hiveworkshop.com/forums/jass-resources-412/snippet-alloc-192348/ to implement these kind of structs.

This is a sample struct:

struct test extends array
    // here we put more struct components
    implement Alloc // this module adds the allocate() and deallocate() methods...
    // my custom methods go here...
endstruct

Everything is fine but I'd like to know if there's an efficient way to loop through all the active instances with the less code possible. I've been looking in this site and I haven't found anything proper. Like this:

private method Loop takes nothing returns boolean
    local thistype this = ????
    loop
         exitwhen 0==this
    // do your stuff
    set this = next???
    endloop
endmethod

Any help would be really appreciated

 

[Dr Super Good]

I think it was discovered that the most efficient way to itterate was via a linked list. Thus you get a struct member to point at another struct instance and form a chain. You then itterate through the chain until the end is reached (signified by a constant).

Even if there is a lot of bloat code that is not used due to the way structs work, it is still the fastest way if what people say is true.

 

[PurgeandFire]

Well, to loop through all active instances you would need to have a list created for your struct. (or a stack)

Something like this:

struct Example extends array
    implement Alloc

    thistype next

    static method iterate takes nothing returns nothing
        local thistype this = thistype(0).next
        loop
            exitwhen this == 0
            // do actions...
            set this = this.next
        endloop
    endmethod

    static method create takes nothing returns thistype
        local thistype this = thistype.allocate()
        set this.next = thistype(0).next // our node's next is becomes head's next
        set thistype(0).next = this // next of the head becomes our node
        return this
    endmethod
endstruct

That is a basic linked list that will allow iteration. However, when you are removing a node, it becomes a bit complex in trying to keep the chain connected properly. Therefore, you can make them doubly if you need removal:

struct Example extends array
    implement Alloc

    thistype next
    thistype prev

    method remove takes nothing returns nothing
        set this.next.prev = this.prev // set the "prev" of the "next" node to our "prev"
        set this.prev.next = this.next // set the "next" of the "prev" node to our "next"
        call this.deallocate()
    endmethod

    static method iterate takes nothing returns nothing
        local thistype this = thistype(0).next
        loop
            exitwhen this == 0 // loop until this == 0, aka end of list
            // do actions...
            set this = this.next
        endloop
    endmethod

    static method create takes nothing returns thistype
        local thistype this = thistype.allocate()
        set thistype(0).next.prev = this // "next" of head has our new instance as "previous"
        set this.next = thistype(0).next // "next" of our node is the "next" of head
        set thistype(0).next = this // "next" of head is now our node
        set this.prev = 0 // "previous" of our node is the head [this case, thistype(0)]
        return this
    endmethod
endstruct

 

[Nestharus]

Not only doubly, but circularly as well ; P. Non circular is something of a pain to deal with ^)^.

 

[Berb]

You don't need a doubly linked-list if you traverse the nodes from head to tail and keep track of the previous node as you are traversing. This would allow you to maintain the pointers from the previous node without requiring you to have unnecessary members.

local node curr = head
local node prev = null
loop
    exitwhen (curr == null)
    // if you need to destroy "curr" then you can update pointers from "prev"
    // prev.next = curr.next 
    set prev = curr
    set curr = curr.next
endloop

 

[Nestharus]

Berb, he asked this

Everything is fine but I'd like to know if there's an efficient way to loop through all the active instances with the less code possible. I've been looking in this site and I haven't found anything proper. Like this:

So why are you giving him a less efficient method?

private method Loop takes nothing returns boolean
    local thistype this = ????
    loop
         exitwhen 0==this
    // do your stuff
    set this = next???
    endloop
endmethod

It really looks like he wants a doubly non circular linked list though ; ). But really, we don't know if he can get away with a stack/queue yet ; P.

 

[Berb]

You don't need a doubly linked-list if you traverse the nodes from head to tail and keep track of the previous node as you are traversing.

Why the hell are you suggesting a doubly linked-list that would only require more pointer maintenance. Stop throwing data-structure terms around I already know you have no idea what you're talking about.

I introduced one variable for all instances while you're telling me that's inefficient, and that in fact you should introduce a new variable per instance as if that's any better.

 

[Nestharus]

Why the hell are you suggesting a doubly linked-list that would only require more pointer maintenance. Stop throwing data-structure terms around I already know you have no idea what you're talking about.

I introduced one variable for all instances while you're telling me that's inefficient, and that in fact you should introduce a new variable per instance as if that's any better.

He said efficient for loops. Yours is not efficient for looping >.>.

Efficient way to loop over struct instances

If you want to be able to easily free up any node in the list, then a doubly linked list is a must, otherwise you kill your looping. This is why I stated that we should know whether he could get away with a stack or a queue to see if he could go singly or not.

 

[Berb]

He said efficient for loops. Yours is not efficient for looping >.>.

If you're going to be maintaining two pointers when you destroy a link in the list you're going to have to do that within the loop. Rather than having to store a previous pointer for every link you've got, you only have to store it once and change the value as you loop.

If you want to be able to easily free up any node in the list, then a doubly linked list is a must, otherwise you kill your looping.

Well no you really won't. If you want to be deleting the "current" node in the traversal (which is most common because here is where you would check whether or not it should be in the list) then as I said just have a "prev" variable that keeps track of the previous pointer (rather than having one for every single node).

If you want to be able to destroy a node farther ahead in the list (which would be a special case, because this type of thing normally isn't done from within the list) then you can keep track of that (this is where you can debate whether you need a doubly linked list or just some value that represents whether or not the node needs to be removed). In the more typical case though, where you are traversing in one direction and determining whether the traversed node needs to be removed you do not need a doubly linked list, or a circular linked list, or a queue, or a dequeue, or a tree, or anything other than a standard linked list.

In this particular case, he asked what the most efficient way to loop through an entire collection of instances of a certain type. Each node only has a pointer to their next node, so I have a hard time imagining how he would be destroying nodes from arbitrary places without traversing the list again, which would be even less efficient.

Whether or not it is a queue or what have you is just the order in which he adds/removes items from the list. If you add to the beginning and take from the beginning, it is a stack. If you add from the beginning and take from the end, it is a queue.

 

[Nestharus]

If you want to be able to destroy a node farther ahead in the list (which would be a special case, because this type of thing normally isn't done from within the list) then you can keep track of that. In the more typical case though, where you are traversing in one direction and determining whether the traversed node needs to be removed you do not need a doubly linked list, or a circular linked list, or a queue, or a dequeue, or a tree, or anything other than a standard linked list.

It only makes sense to use a doubly linked list if you need to remove any given node in the list at any point, including during traversal >.>.


Using a singly when wanting to have that feature complicates everything, including traversal. A doubly simplifies it + makes it go faster >.>. It's a win win.


Now, if you are pushing/popping enqueuing/dequeuing, that's a whole other matter.



Now, this person asked for efficient traversal with the least code possible. You are not helping answer his question by giving him exactly what he didn't ask for, so just stop with this nonsense.



Purge's solutions were the best. If he only needs to add/remove from the front or back, then he can get away with solution #1, the singly. If anywhere, then solution #2, the doubly. Your solution does not make sense given what the author asked for.

 

[Berb]

It only makes sense to use a doubly linked list if you need to remove any given node in the list at any point, including during traversal >.>.

During traversals you do not need to have a doubly linked list to remove a node. If you want to remove an arbitrary node from the list (not necessarily the one you are currently traversing) then you will need to have a doubly linked list so you don't have to traverse the list to find the node being removed.

Using a singly when wanting to have that feature complicates everything, including traversal. A doubly simplifies it + makes it go faster >.>. It's a win win.

Adding a member to the struct doesn't make a loop iterate faster. I mean, okay. Let's say you want to traverse through the list. Having a variable that remembers what the node's previous link is would require you to set that link on each traversal. The doubly linked list would eliminate the need for this, but it would add the requirement that in order to destroy a node, you need to do a handful of extra array look-ups, though with a singly-linked-list you're only performing one.

Now, this person asked for efficient traversal with the least code possible. You are not helping answer his question by giving him exactly what he didn't ask for, so just stop with this nonsense.

Actually, my version would add two lines of code to the script. Your version would add several. Sorry, mine is 3 lines. Not 2.

    method traverseBerb takes nothing returns nothing
        local Node curr = head
        local Node prev = null
        loop
            exitwhen (curr == null)
            
            // if you need to remove "curr" from the list do the following:
            //      set prev.next = curr.next when "curr" is not the head of the list
            
            set prev = curr
            set curr = curr.next
        endloop
    endmethod

    method traverseNesth takes nothing returns nothing
        local Node curr = head
        loop
            exitwhen (curr == null)
            
            // now this requires "curr" to have a "prev" member
            // to maintain these pointers we have to do:
            
            //      if (curr.prev != null) then
            //          set curr.prev.next = curr.next
            //      endif
            //      if (curr.next != null) then
            //          set curr.next.prev = curr.prev
            //      endif
            
            set curr = curr.next
        endloop
    endmethod

Basically I am saying that you have less to keep track of with a singly-linked-list so the solution is more simple. You don't have to worry about pointers to each, nor do you have to have the extra member in your node.

Insertion is as simple as:

    method insert takes integer data returns nothing
        set head = Node.create(data, head)
    endmethod

It gets slightly more complicated with a doubly-linked-list.

 

[Nestharus]

The doubly linked list would eliminate the need for this, but it would add the requirement that in order to destroy a node, you need to do a handful of extra array look-ups, though with a singly-linked-list you're only performing one.

If it's a circular, you don't need to do the extra checks. Furthermore, for non circular, extra checks are 2 if statements and only on removal.


It was my understanding from the question asked that they wanted maximum traversal speed w/ minimum code. Given that, maximum traversal speed would be a doubly non circular if they need to remove from anywhere. If only front/back, then singly. If they care about removal speed and not as much traversal, then doubly circularly. If they don't care about traversal speed (opposite of what they said), then your method.


These statements go straight back to purge's provided solutions.


Please read the question before you put up a response
->Efficient way to loop over struct instances


Although, I guess it could be argued what he meant by efficient. Did he mean efficient in terms of code size or efficient in terms of memory use or efficient in terms of speed ;o. I guess perhaps the author should have made themselves more clear : ).


Perhaps it was both our bads to jump the gun by just assuming what he meant : ).

 

[Berb]

If it's a circular, you don't need to do the extra checks. Furthermore, for non circular, extra checks are 2 if statements and only on removal.

Then you'll have to remember how large your list is, and do extra checks to make sure you aren't traversing already traversed nodes.

Given that, maximum traversal speed would be a doubly non circular if they need to remove from anywhere. If only front/back, then singly. If they care about removal speed and not as much traversal, then doubly circularly..

If the user needs to only be removing a predictable node from the list then a doubly linked-list is not required. If you can show me that your extra array with array look-up and occasional assignment is faster than local declaration with local assignment (on more frequent occasion) then I'll believe you.

It doesn't matter if they're only removing the front or the back, the key here is the predictability of the nodes that are being removed. Also you say that if you want to remove from the back of the list, you'll want a singly linked list. Good luck removing the last node in a list without a "prev" member (given all you know is that one node).

If they don't care about traversal speed (opposite of what they said), then your method.

You haven't shown anything.

 

[Nestharus]

Then you'll have to remember how large your list is, and do extra checks to make sure you aren't traversing already traversed nodes.

wth? Ever hear of a sentinel node?

It doesn't matter if they're only removing the front or the back, the key here is the predictability of the nodes that are being removed. Also you say that if you want to remove from the back of the list, you'll want a singly linked list. Good luck removing the last node in a list without a "prev" member (given all you know is that one node).

a non array last pointer?

You haven't shown anything.

my method is the same as purge's

If the user needs to only be removing a predictable node from the list then a doubly linked-list is not required. If you can show me that your extra array with array look-up and occasional assignment is faster than local declaration with local assignment (on more frequent occasion) then I'll believe you.

but the traversal is slower, hence why I said we should wait for them to tell us what they meant by efficiency. If they wanted optimal speed, then obviously your approach isn't going to work.

 

[Berb]

wth? Ever hear of a sentinel node?

Ever heard of .next == null?

a non array last pointer?

What is an "array last pointer" for there to be a "non array last pointer"? More than 4 words please.

but the traversal is slower, hence why I said we should wait for them to tell us what they meant by efficiency. If they wanted optimal speed, then obviously your approach isn't going to work.

That depends if traversals or insertions/deletions are more common. I admit, in the traversal portion (specifically) Purge's method does not have the overhead of allocating a variable and constantly assigning it, but the trade-off is the array look-ups and the physically longer code (plus its slightly more complicated with two pointers).

 

[Nestharus]

Ahem...

struct CircularDoublyLinkedList extends array
    private static integer instanceCount = 0
    readonly thistype next
    readonly thistype prev
    readonly boolean head //for faster iteration

    static method create takes nothing returns thistype
        local thistype this = thistype(0).next
        if (0 == this) then
            set this = instanceCount + 1
            set instanceCount = this
        else
            set thistype(0).next = next
        endif

        set next = this
        set prev = this
        set head = true
    endmethod

    method destroy takes nothing returns nothing
        set next = thistype(0).next
        set thistype(0).next = this
    endmethod

    method add takes thistype node returns nothing
        set node.prev = prev
        set node.next = this
        set prev.next = node
        set prev = node
        set node.head = false
    endmethod
    method remove takes nothing returns nothing
        set prev.next = next
        set next.prev = prev
        set head = true
    endmethod
    method loop takes nothing returns nothing
        loop
            set this = next
            exitwhen head
        endloop
    endmethod
endstruct

Yea, tons of extra code to remove

    method remove takes nothing returns nothing
        set prev.next = next
        set next.prev = prev
    endmethod

I mean look at how mad that is. That's a whole two lines.

And look at the looping for a circular linked list

    method loop takes nothing returns nothing
        loop
            set this = next
            exitwhen head
        endloop
    endmethod

Zamgz... that's just totally mad >.<. And heck, we coulda done it this way too

    method loop takes nothing returns nothing
        local integer head = this
        loop
            set this = next
            exitwhen this == head
        endloop
    endmethod

And if we went with non circular, we coulda done it this way

    method loop takes nothing returns nothing
        loop
            set this = next
            exitwhen 0 == this
        endloop
    endmethod

At the cost of more overhead in add/remove.

 

[Berb]

In your list, every single node has the head value as true. I also don't see anywhere where you maintain this value.

 

[Nestharus]

oh woops, my bad. Wrote it in kind of a hurry.


This style allows you to freely convert nodes to heads and heads to nodes ;\. It's a pretty whacked style, but ehh, w/e.


Also, you can clear a whole linked list in O(1).

 

[Berb]

That's an up-side of using an array.

By the way I think your instanceCounter needs to be dealt with too. I don't see anything that prevents it from hitting the limit on how many of this struct you can have, nor do I see anywhere where it recycles numbers when nodes are destroyed.

You really need to show me everything though, show me how you plan on maintaining the head member and how you plan on recycling your IDs.

I don't think either of those things will really affect traversal though, but it will impact the allocation/creation/insertion time. I suppose the answer to this thread is then that specific way, but it will be a little more complicated to set up.

        local thistype this = thistype(0).next
        if (0 == this) then
            set this = instanceCount + 1
            set instanceCount = this
        else
            set thistype(0).next = next
        endif

This part here is pretty wacko though. Are you sure this works properly? Still doesn't recycle IDs though. I don't know what the point of the else statement is. Honestly you might as well just do:

local thistype this = instanceCount + 1
set instanceCount = this
...

 

[Nestharus]

By the way I think your instanceCounter needs to be dealt with too. I don't see anything that prevents it from hitting the limit on how many of this struct you can have, nor do I see anywhere where it recycles numbers when nodes are destroyed.

It does recycle, but as for instance counter, chances of it even going above 1000 are pretty slim ;p. If it goes above limit, then it'll crash either way, so debug seems kinda silly ^)^.

 

[Berb]

Okay, yes it does recycle. I did not see your destroy method. I guess that was the point of the if-statement.

In your example, the loop executes assuming that this is the head of the list. Curious as to how one would implement this, or how they would determine which nodes are the heads of lists.

It seems like in your add method you make the head the "end" of the list. Where are you adding to in the list when you do that?

 

[Nestharus]

The head is whatever node you are adding to. For example, if you decided to declare a new list

List list = List.create()

then do something like
List.add(List.create())

list would still be the head, and the new list you made would be the node ; ). If you removed that list you added, it would then be converted into its own list.

Anything that is a list has head marked as true. Anything that isn't a list has head marked as false. The list is how you reference your linked list ; P. Obviously, you wouldn't reference it via one of its nodes ; ).


Add can actually add to any node in the list, not just the head. It adds after the target node

local List list = List.create()
local List node = List.create()

call list.add(node)

loop
    set list = list.next
    exitwhen list.head
endloop

That is how you would use. If you wanted to take the node out

call node.remove()

Now the node is marked as a head again.


Furthermore, clearing out the list is O(1). You can remove or destroy a range of nodes. Furthermore, you can sub a list with O(1) so long as you have the beginning/end nodes ^)^.

edit
That script I wrote is a rather standard approach to doing linked lists for wc3.

 

[moyackx]

WOW!!! thanks for this big amount of answers

Unfortunately I've been absorbed by work, but surely I'll test all your suggestions and give feedback properly.

Man love for all of you

 

[Berb]

Nestharus I am looking over your code and wondering how you figure the cleaning of a list to be O(1). I initially thought, oh well you can just clear the head of the list because its all pointers, but then you wouldn't be getting any of those IDs back. In order to get all the IDs that were used back, you would then have to iterate through nodes and make sure their IDs get put on the thistype(0) list again, which would be O(n).

 

[Nestharus]

//on head, O(1) insta clear + deallocation

if (not next.head) then

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

endif

You can destroy a list in the same fashion. Just include the head in the range and remove the if statement .

 

[Berb]

Okay I see what you mean, just add it to the list of recycling IDs.

 

[Troll-Brain]

It's a pretty good trick, as long you don't need to work with the members of the list on destroy.