[Solved] Question with Indexing (Structs)

[MyPad]

I wonder how this will behave (indexing). Am I doing something wrong with indexing this?

private struct lolStruct extends array
        private static integer count = 0
        private static thistype recycle = 0
        private thistype recNext
       
        private static thistype first    =    0
        private static thistype last    =    0
        private thistype next
        private thistype prev
       
        method destroy takes nothing returns nothing
            set recNext = recycle
            set recycle = this
            if this.prev == 0 then
                set first = this.next
            else
                set this.prev.next = this.next
            endif
            if this.next == 0 then
                set last = this.prev
            else
                set this.next.prev = this.prev
            endif
        endmethod
       
        static method create takes nothing returns thistype
            local thistype this
            if recycle == 0 then
                set count = count + 1
                set this = count
            else
                set this = recycle
                set recycle = recycle.recNext
            endif
            return this
        endmethod
       
        method push takes nothing returns nothing
            if recycle == 0 then
                set first = this
                set last = this
                set this.next = 0
                set this.prev = 0
            else
                set this.next = first
                set this.prev = 0
                set first.prev = this
                set first = this
            endif
        endmethod
       
        method queue takes nothing returns nothing
            if recycle == 0 then
                set first = this
                set last = this
                set this.next = 0
                set this.prev = 0
            else
                set this.prev = last
                set this.next = 0
                set last.next = this
                set last = this
            endif
        endmethod
       
    endstruct

 

[KILLCIDE]

thistype.allocate() and thistype.deallocate() recycles indexes for you. All you have to do is "organize" the list.

 

[Flux]

@MyPad What exactly are you asking here, the allocation method you used or the function of "struct LearnData"?

Am I doing something wrong with indexing this?

Why extends array if you're gonna override it with your own allocation method anyways? You could argue for less generated script but it would be much more efficient (in terms of coding speed) to put your allocation method in a module and just implement it every time instead of rewriting the attributes and function for each struct.

 

[MyPad]

@Flux I wanted to ask about how the allocation method will behave. I wanted to know that what I wrote is the correct way.

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

I would like to add its' previous and next, but I don't know exactly how to do it.

EDIT:

Never mind the next portion. I think I figured it out.

 

[Flux]

Why are you even writing your own allocation in the first place? One of the advantage of a struct is letting JassHelper do it for you.

 

[KILLCIDE]

One of the advantage of a struct is letting JassHelper do it for you.

As I mentioned earlier: thistype.allocate() and thistype.deallocate()

 

[MyPad]

As I mentioned earlier: thistype.allocate() and thistype.deallocate()

I tried it with the generated constructors and destructors,

Now that the post is resolved, I have updated the code.

Thanks, @KILLCIDE and @Flux

 

[KILLCIDE]

Everything looks fine to me except this line: set thistype(0).prev.next = this. Correct me if I'm wrong, but that's basically equivalent to this.next = this, right? If I'm right, then the list would never go back to index 0.

Alternatively, you could also change set this.next = thistype(0) to this.next = 0.

 

[MyPad]

@KILLCIDE

I'll try to understand the logic first. I'll reply later.

EDIT:

I removed set this.next = 0 because I found it redundant to define.

These are my observations...

set thistype(0).prev.next = this    //next[prev[0]] == next[0] = 1, next[prev[0]] == next[1] = 2
set this.prev = thistype(0).prev    //prev[1] = prev[0] = 0, prev[2] = prev[0] = 1
set thistype(0).prev = this            //prev[0] = 1, prev[0] = 2

 

[Flux]

This is how I do my queued circular doubly linked list

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

You can pick all using

local thistype this = thistype(0).next
loop
    exitwhen this == 0
    //Do stuffs on this
    set this = this.next
endloop

^That will pick instances by order they are added (sometimes it matters sometimes it does not). That list also happens to be circular so when you removed the "exitwhen", it will go back to thistype(0) after the last node. It's simple, only need 4 lines for "push", 2 for "pop", only utilizes 2 arrays (some list algorithms I see here on hive uses an extra non-array variable usually called head or first) and at the same time queued and circular.

The "pop" from the list is exactly the same as yours.

 

[MyPad]

This is how I do my queued circular doubly linked list

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

You can pick all using

local thistype this = thistype(0).next
loop
    exitwhen this == 0
    //Do stuffs on this
    set this = this.next
endloop

^That will pick instances by order they are added (sometimes it matters sometimes it does not). That list also happens to be circular so when you removed the "exitwhen", it will go back to thistype(0) after the last node. It's simple, only need 4 lines for "push", 2 for "pop", only utilizes 2 arrays (some list algorithms I see here on hive uses an extra non-array variable usually called head or first) and at the same time queued and circular.

The "pop" from the list is exactly the same as yours.

Woah, thanks for that. Now, I can have a nice alternative to hashtables.

 

[Nestharus]

The only problem is that this is not instanced.

Push

if (isEmpty()) then
    set p__first = element
    set p__last = element
    set element.p__next = 0
    set element.p__prev = 0
else
    set element.p__next = p__first
    set element.p__prev = 0
    set p__first.p__prev = element
    set p__first = element
endif

Enqueue

if (isEmpty()) then
    set p__first = element
    set p__last = element
    set element.p__next = 0
    set element.p__prev = 0
else
    set element.p__prev = p__last
    set element.p__next = 0
    set p__last.p__next = element
    set p__last = element
endif

Remove

if (element.p__prev == 0) then
    set p__first = element.p__next
else
    set element.p__prev.p__next = element.p__next
endif
if (element.p__next == 0) then
    set p__last = element.p__prev
else
    set element.p__next.p__prev = element.p__prev
endif

 

[Flux]

The only problem is that this is not instanced.

Push

if (isEmpty()) then
    set p__first = element
    set p__last = element
    set element.p__next = 0
    set element.p__prev = 0
else
    set element.p__next = p__first
    set element.p__prev = 0
    set p__first.p__prev = element
    set p__first = element
endif

Enqueue

if (isEmpty()) then
    set p__first = element
    set p__last = element
    set element.p__next = 0
    set element.p__prev = 0
else
    set element.p__prev = p__last
    set element.p__next = 0
    set p__last.p__next = element
    set p__last = element
endif

Remove

if (element.p__prev == 0) then
    set p__first = element.p__next
else
    set element.p__prev.p__next = element.p__next
endif
if (element.p__next == 0) then
    set p__last = element.p__prev
else
    set element.p__next.p__prev = element.p__prev
endif

Yeah but if you will only have 1 list just for the purpose of picking all instances (like most Spells), then thistype(0) can serve as the "universal" head.

 

[MyPad]

The only problem is that this is not instanced.

Push

if (isEmpty()) then
    set p__first = element
    set p__last = element
    set element.p__next = 0
    set element.p__prev = 0
else
    set element.p__next = p__first
    set element.p__prev = 0
    set p__first.p__prev = element
    set p__first = element
endif

Enqueue

if (isEmpty()) then
    set p__first = element
    set p__last = element
    set element.p__next = 0
    set element.p__prev = 0
else
    set element.p__prev = p__last
    set element.p__next = 0
    set p__last.p__next = element
    set p__last = element
endif

Remove

if (element.p__prev == 0) then
    set p__first = element.p__next
else
    set element.p__prev.p__next = element.p__next
endif
if (element.p__next == 0) then
    set p__last = element.p__prev
else
    set element.p__next.p__prev = element.p__prev
endif

At this point, I'm just learning unique ways with indexing certain elements. Thanks for you help:

By the way, I have updated the code above. I just need a bit of clarification with this:

(isEmpty())

Is it recycle == 0, or is it something else entirely?

EDIT:

I think that the create method should be combined with either the push or the queue. Maybe I might be wrong on this...

 

[Nestharus]

public method isEmpty takes nothing returns boolean
    return p__first.isNull
endmethod

public method operator isNull takes nothing returns boolean
    return this == 0
endmethod

Create is not combined with push or enqueue. Create creates the collection. Push/enqueue create nodes.

public static method create takes nothing returns thistype
    return createCollection()
endmethod

public method destroy takes nothing returns nothing
    static if DEBUG_MODE and LIBRARY_ErrorMessage then
        call AssertCollection("destroy", this, p__collection)
    endif

    call destroyCollection()
endmethod

public method enqueueCollection takes nothing returns thistype
    local thistype element = createElement(this)

    if (isEmpty()) then
        set p__first = element
        set p__last = element
        set element.p__next = 0
        set element.p__prev = 0
    else
        set element.p__prev = p__last
        set element.p__next = 0
        set p__last.p__next = element
        set p__last = element
    endif

    return element
endmethod

method enqueue takes nothing returns thistype
   static if DEBUG_MODE and LIBRARY_ErrorMessage then
      call AssertCollection("enqueue", this, p__collection)
   endif

   return enqueueCollection()
endmethod

On top of this, the allocation for nodes is a little bit unique to save on variables. Note that p__next is used as the recycler. Also, note that in this example nodes use a different allocator from the collection itself. This means that this module has 2 allocators. They can also share the same allocator. I still like to use p__next for nodes and p__first for collections for my allocators : ). This means that I use extends array on my structs.

            local thistype this = thistype(0).p__next

            if (p__next == 0) then
                set thistype(0).p__next = this + 1
            else
                set thistype(0).p__next = p__next
            endif

            set p__next = 0

 

[Anitarf]

With regards to the code currently posted in the first post, the create method lacks the following line: set this.next = thistype(0)

 

[MyPad]

public method isEmpty takes nothing returns boolean
    return p__first.isNull
endmethod

public method operator isNull takes nothing returns boolean
    return this == 0
endmethod

Create is not combined with push or enqueue. Create creates the collection. Push/enqueue create nodes.

public static method create takes nothing returns thistype
    return createCollection()
endmethod

public method destroy takes nothing returns nothing
    static if DEBUG_MODE and LIBRARY_ErrorMessage then
        call AssertCollection("destroy", this, p__collection)
    endif

    call destroyCollection()
endmethod

public method enqueueCollection takes nothing returns thistype
    local thistype element = createElement(this)

    if (isEmpty()) then
        set p__first = element
        set p__last = element
        set element.p__next = 0
        set element.p__prev = 0
    else
        set element.p__prev = p__last
        set element.p__next = 0
        set p__last.p__next = element
        set p__last = element
    endif

    return element
endmethod

method enqueue takes nothing returns thistype
   static if DEBUG_MODE and LIBRARY_ErrorMessage then
      call AssertCollection("enqueue", this, p__collection)
   endif

   return enqueueCollection()
endmethod

On top of this, the allocation for nodes is a little bit unique to save on variables. Note that p__next is used as the recycler. Also, note that in this example nodes use a different allocator from the collection itself. This means that this module has 2 allocators. They can also share the same allocator. I still like to use p__next for nodes and p__first for collections for my allocators : ). This means that I use extends array on my structs.

            local thistype this = thistype(0).p__next

            if (p__next == 0) then
                set thistype(0).p__next = this + 1
            else
                set thistype(0).p__next = p__next
            endif

            set p__next = 0

I updated parts of the code now. This is what it looks like:

private struct lolStruct extends array
        private static integer count = 0
        private static thistype recycle = 0
        private thistype recNext
       
        private static thistype first    =    0
        private static thistype last    =    0
        private thistype next
        private thistype prev
       
        method operator Null takes nothing returns boolean
            return this == 0
        endmethod
       
        method Empty takes nothing returns boolean
            return first.Null
        endmethod
       
        static method create takes nothing returns thistype
            local thistype this
            if recycle.Null then
                set count = count + 1
                set this = count
            else
                set this = recycle
                set recycle = recycle.recNext
            endif
            return this
        endmethod
        
        //push and queue code...
        //destroy below...

        method destroy takes nothing returns nothing
            set recNext = recycle
            set recycle = this
            if this.prev == 0 then
                set first = this.next
            else
                set this.prev.next = this.next
            endif
            if this.next == 0 then
                set last = this.prev
            else
                set this.next.prev = this.prev
            endif
        endmethod
       
    endstruct

Which one of these is more acceptable?

This?

method pushOne takes nothing returns thistype
        local thistype that = thistype(0).next
        if that.next.Null then
            set thistype(0).next = that + 1
        else
            set thistype(0).next = that.next
        endif
        set that.next = 0
        if Empty() then    //first == 0
            set first = that
            set last = that
            set that.next = 0
            set that.prev = 0
        else            //first != 0
            set that.next = first
            set that.prev = 0
            set first.prev = that
            set first = that
        endif
        return that
endmethod

or this?

method pushTwo takes nothing returns thistype
        local thistype that = thistype.create()
        set that.next = 0
        if Empty() then    //first == 0
            set first = that
            set last = that
            set that.next = 0
            set that.prev = 0
        else            //first != 0
            set that.next = first
            set that.prev = 0
            set first.prev = that
            set first = that
        endif
        return that
endmethod

 

[Nestharus]

I don't know what your aim is.

Are you aiming for a static linked list or an instantiable linked list?


Static means that you may only have one list. Instantiable means that one struct can have N lists on it.

The following is instanced

// two different lists from the same struct
local List listA = List.create()
local List listB = List.create()

// each has one node each
local List nodeA = listA.push() // retrieve the node pushed onto the first list
call listB.push()

call nodeA.remove() // now listA has no nodes on it. nodeA is destroyed.
call listB.clear() // now listB has no nodes on it

call listA.push()

call listA.destroy() // destroys listA. The node that was on listA is also destroyed.
call listB.destroy() // destroys listB.

The following is static

local List nodeA = List.push() // notice that now push is static!

call List.clear()

set nodeA = List.enqueue()

call nodeA.remove()

// notice there is no destroy method
// clearing the list is all that needs to be done because the list is static

Which style are you aiming for?