Linked Lists

[emjlr3]

as I don't quite get what is going on here, I would appreciate it if someone could learn me sumpin'

extracted from T32x:

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

what exactly is [ljass]thistype(0)[/ljass] referring to?

same thing in the [ljass]PeriodicLoop[/ljass] method

local thistype this=thistype(0).next

I was trying to use a similar approach, with the addition of a stop check for the periodic timer

if thistype(0).prev==0 then
    call PauseTimer(TIMER)
endif

just doesn't quite cut it....

 

[Narks]

http://en.wikipedia.org/wiki/Linked_list

linked lists have a head (the first node in the linked list)

i'm guessing since that the 0 struct is never used or allocated, t32x uses thistype(0).next as the head

 

[Troll-Brain]

thistype(<integer>) == structName(<integer>), since the default vJass allocator use the index 1 to 8190, Jesus4Lyf just use the index 0 for the head of the linked list (he could use a static member instead).

VJass does implicit typecasting when you use a struct instance as an integer, though you can explicit it with integer(<structInstance>).
But if you want to use an integer as a struct instance you have to explicit it, using thistype() or structName().

 

[Sevion]

[ljass]thistype(0)[/ljass] refers to the head (top, front, first, what-have-you).

It's literally the starting point of the list.

That first snippet

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

Think of it like this image that I whipped up:

The second snippet

local thistype this=thistype(0).next

Is making a variable (named this) point to the first non-null instance in the list (the second instance if you count thistype(0)).

As for the third part, [ljass]thistype(0).prev[/ljass] should always be 0 as long as it's not a doubly linked list (meaning first and last are linked together to make a full circle).

If you need more help explaining linked lists you can add me on MSN ([email protected]). It'd be a lot easier.

 

[emjlr3]

if i get this right

when [ljass]thistype(0)==0[/ljass] the list should be empty?

 

[Narks]

no

structs are really made out of arrays in vjass

when you typecast a struct instance to an integer, you're getting the array index the struct uses

eg:

    MyStruct(41).stringVariable = "blah"
    // translates to
    MyStruct__stringVariable[41] = "blah"

    // therefore
    (thistype(0) == 0)
    // becomes
    (0 == 0)
    // and will always return true


    // to check if the list is empty, you want to check if the head node exists
    (thistype(0).next == 0)
    // will return true if list is empty

 

[Sevion]

When [ljass]thistype(0).next == 0[/ljass] the list should be empty.

And Narks, I hate to nit pick, but [ljass]MyStruct(41).stringVariable = "blah"[/ljass] translates to [ljass]si__MyStruct_stringVariable[41] = "blah"[/ljass] and [ljass](thistype(0) == 0)[/ljass] translates to [ljass](si_MyStruct[0] == 0)[/ljass]

 

[emjlr3]

so the head basically does not count in this case? you never actually use it to run a spell from?

 

[Sevion]

Never. It just serves as a starting point. The first node that actually is used is [ljass]thistype(0).next[/ljass] (which is typically [ljass]thistype(1)[/ljass]).

 

[Narks]

(si_MyStruct[0] == 0)

wat
what's si_MyStruct? an integer array containing the index of the struct on each index? if so... wat

thistype(0) isn't used as a node - it's not part of the list, jesus was just using thistype(0).next as a head variable

think of it like:

private static thistype head;
private thistype next;

function iterateThroughList()
{
    thistype node = head;
    while (node != 0)
    {
        node.doStuff();
        node = node.next;
    }
}

// and the version jesus4lyf used:
private thistype next;

function iterateThroughList()
{
    // instead of using a static head variable:
    thistype node = thistype(0).next;
    while (node != 0)
    {
        node.doStuff();
        node = node.next;
    }
}

 

[tooltiperror]

so the head basically does not count in this case? you never actually use it to run a spell from?

Pretty much. Normally you would have to keep saving the head as a static variable in the struct. Instead, you just reserve 0 ([ljass]thistype(0)[/ljass]) to be the head always.

 

[Sevion]

I never said [ljass]thistype(0)[/ljass] was used as a node... If you read my posts I never once said that. I've been saying that [ljass]thistype(0)[/ljass] was the head.

 

[Nestharus]

I wrote this tutorial a while back if it helps -> http://www.hiveworkshop.com/forums/...array-linked-list-stack-queue-dequeue-188528/

check out linked list section. It explains them by pointers =).

 

[emjlr3]

I never said [ljass]thistype(0)[/ljass] was used as a node... If you read my posts I never once said that. I've been saying that [ljass]thistype(0)[/ljass] was the head.

i didnt know you meant the head was just a marker, and contained no data, I assumed it was also sued to store data, but was referred to as the head because it was the first node too

 

[Sevion]

Never. It just serves as a starting point. The first node that actually is used is [ljass]thistype(0).next[/ljass] (which is typically [ljass]thistype(1)[/ljass]).

 

[emjlr3]

well yea that is where I finally got it, prior to the aforementioned comment

 

[Sevion]

Post 12 was more directed at Narks than you

To explain why [ljass]thistype(0)[/ljass] translates to [ljass]si_MyStruct[0][/ljass]: thistype(0) is still a node. It's just the "first" node. It's simply the first instance of the array (at index 0).

If [ljass]thistype(0)[/ljass] translated to 0, then the entirety of structs wouldn't work in vJASS.