Double linked lists?

[Pinzu]

Can someone for the low of god teach me (show me) how to make a double linked list?

I just don't understand how to index and deindex them. :<

Here is one example of a unit group i'd like replaced:

    private function OnIndex takes nothing returns boolean
        if GetUnitAbilityLevel(udg_UDexLastUnit, HUNGERS) > 0 then
            call GroupAddUnit(playerHungryUnits[GetPlayerId(GetOwningPlayer(udg_UDexLastUnit))], udg_UDexLastUnit)
        endif
        return false 
    endfunction

Here is another:

// This loop can be optimized to only loop through those that actually have income if you index them
        
    private function GiveIncome takes nothing returns boolean 
    
        local integer i = 1
        loop
            if city[i].incFood > 0 then 
                call SetUnitState(city[i].u, UNIT_STATE_MANA, GetUnitState(city[i].u, UNIT_STATE_MANA) + city[i].incFood) 
            endif
            set i = i + 1
            exitwhen i > City.count
        endloop
        return false 
    endfunction

 

[PurgeandFire]

Doubly linked lists are just a list of data where each member knows its previous member and its next member. Imagine a bunch of people are holding hands in line. Each person only needs to hold the hand of the person in front of them and the person behind them. We can visualize that concept like so:

head <-> A <-> C <-> B <-> X <-> Z

"head" is the first person in the list. A, C, B, X, Z just represent random data organized in the list. The arrows < - > represent pointers to the previous and last member (e.g. C has "A" as its previous member, and "B" as its next). Similarly, in a struct we'll just have:

struct UnitList
    thistype next
    thistype prev
    unit u
endstruct

That is the basic outline. In this case, we'll be keeping track of units. Assuming we only need one list with this struct, we can just use thistype(0) as the "head". Don't worry about what it means, just know that thistype(0) is never used as a struct index. When we add a member, it is natural to just add it after the "head". So this is how we start out:

static method add takes unit u returns nothing
    /* Create the node we want to insert */
    local thistype new = thistype.allocate()
    set new.u = u

    /* Insert after the head */
    set new.prev = thistype(0)
    set new.next = thistype(0).next
    set new.next.prev = new
    set thistype(0).next = new
endmethod

This is complicated at first, so let's break it up. Imagine we have a list:

head <-> A <-> B

And that we are inserting some node C.

• set new.prev = thistype(0) - this sets C's previous to the head. So our diagram looks like:
  head <-> A <-> B .... head <- C
  They're drawn disjoint because we haven't changed any of the original relationships yet.
• set new.next = thistype(0).next - this sets C's next to the head's next. So our diagram looks like:
  head <-> A <-> B .... head <- C -> A
• set new.next.prev = new - this sets A's previous to be C (remember, A is C's next node). So now our diagram looks like:
  head -> A <-> B .... head <- C <-> A
• set thistype(0).next = new - finally, we set the next of the head to point to C (thus finishing the insertion after the head). Now our diagram looks like:
  head <-> C <-> A <-> B

Removing is simple. If you removed C, you would naturally just make A point back to head and head point forward to A. Nothing else needs to be done. So let's write that:

method destroy takes nothing returns nothing
    set this.next.prev = this.prev
    set this.prev.next = this.next
    call this.deallocate()
endmethod

I like to imagine the dots "." representative of ownership. So "set this.next.prev = this.prev" in English would be "set this instance's next member's previous to point to this instance's previous". But it may help to try it out yourself and mess around with it. It is tough to understand at first--but it is worthwhile to learn. It is better to understand the concept as a whole--that way you'll be able to easily implement circular lists, lists with arbitrary heads, etc.

 

[Dr Super Good]

The main advantage of a doubly linked list is it allows efficient node removal. This feature is not very useful when operating as a abstract data container since there are tricks to keep track of the previous node during list operations. However when you extend the node as part of a complex object it allows you to delete the object while keeping list integrity with a time complexity of O(1) as opposed to O(n).

Additionally double linked lists allow for a "backwards iterator". Such an iterator can be useful if the list contains ordered data since it allows free traversal in inverse order. With a single linked list such a traversal would have a complexity of O(n^2) as opposed to O(n) in the double linked list case.

 

[Nestharus]

Also google linked list animation. There's a website I love called CS Animated.

 

[Pinzu]

What still confuses me is:

method destroy takes nothing returns nothing
    set this.next.prev = this.prev
    set this.prev.next = this.next
    call this.deallocate()
endmethod

you still seem to have to recycle the array element, or how else would you know what to destroy?

Here is the trigger I'm trying to implement it in.

private function OnYieldChange takes nothing returns boolean
        local integer uid = GetUnitUserData(lastChangedFarm)
        local integer i = owningCity[uid]
        local integer pid = GetPlayerId(GetOwningPlayer(lastChangedFarm))
        if city[i].incFood == 0 then
            call FoodIncList.add(i)
        else 
            set city[i].incFood = city[i].incFood - incomeFood[uid]
            set incTotFood[pid] = incTotFood[pid] - incomeFood[uid]
        endif
        set incomeFood[uid] = R2I(FARM_INCOME*yield[uid])
        if incomeFood[uid] == 0 and city[i].incFood == 0 then 
            call FoodIncList.remove(i)
        else 
            set city[i].incFood = city[i].incFood + incomeFood[uid]
            set incTotFood[pid] = incTotFood[pid] + incomeFood[uid]
        endif
        if UnitAlive(lastChangedFarm) then  
            call DisplayUnitYield(lastChangedFarm)
        endif
        return false
    endfunction

Maybe if I store the struct index in a hashtable, if that works, in this case though a normal index might suffice. Would something like this work:

struct FoodIncList 
        integer city 
        thistype next
        thistype prev
        static hashtable hash = InitHashtable()
        
        static method add takes integer i returns nothing 
            local thistype new = thistype.allocate()
            call SaveInteger(hash, i, 0, new)
            set new.city = i
            set new.prev = thistype(0)
            set new.next = thistype(0).next
            set new.next.prev = new
            set thistype(0).next = new
        endmethod
        
        static method remove takes integer i returns nothing
            local thistype old = LoadInteger(hash, i, 0) 
            call FlushChildHashtable(hash, i) 
            set old.next.prev = old.prev
            set old.prev.next = old.next 
            call old.deallocate()
        endmethod
    endstruct

It seems to work now, brilliant!

private function GiveIncome takes nothing returns boolean 
        local FoodIncList index = FoodIncList(0).next
        loop
            exitwhen index.city == 0
            call SetUnitState(city[index.city].u, UNIT_STATE_MANA, GetUnitState(city[index.city].u, UNIT_STATE_MANA) + city[index.city].incFood) 
            set index = index.next
       endloop
        return false 
    endfunction

__________________________

How about something like this for 12 players:

struct HungryUnitList 
        unit u
        thistype prev
        thistype next
        static thistype array head[12]
        static hashtable hash = InitHashtable()
        
        static method add takes unit u returns nothing
            local thistype new = thistype.allocate()
            local integer i = GetPlayerId(GetOwningPlayer(u))
            set new.u = u
            call SaveInteger(hash, GetHandleId(u), 0, new)
            /* Insert after the head */
            set new.prev = new.head[i]
            set new.next = new.head[i].next
            set new.next.prev = new
            set new.head[i].next = new
        endmethod
        
        static method remove takes unit u returns nothing
            local integer id = GetHandleId(u)
            local thistype old = LoadInteger(hash, id, 0)
            local integer i = GetPlayerId(GetOwningPlayer(u))               
            call FlushChildHashtable(hash, id) 
            set old.next.prev = old.prev
            set old.prev.next = old.next 
            call old.deallocate()
        endmethod
    endstruct 
    
    // It finds the added units on every value of pnum, even though they are added to head[0]
    private function OnTimerEnd takes nothing returns nothing
        local HungryUnitList index = HungryUnitList.head[pnum].next
        call BJDebugMsg("num: " + I2S(pnum))
        loop
            exitwhen index.u == null 
            call BJDebugMsg("found 1")
            set index = index.next
        endloop
        set pnum = pnumNext[pnum]
    endfunction

 

[PurgeandFire]

The 12 player version will run into issues because the head values all default to 0. What you want is 12 heads with different next/prev's, but since all the heads just equal 0, it'll be overwriting the same values.

At that point, it is important to know that structs are really just integers in disguise, and that members are parallel arrays indexed by those "struct integers".

You can always just add an init method to initialize 12 heads:

private static method onInit takes nothing returns nothing
    local integer i = 0
    loop 
        exitwhen i == 12
        set head[i] = thistype.allocate()
        set i = i + 1
    endloop
endmethod

Then it should work (I assume).

 

[Dr Super Good]

you still seem to have to recycle the array element, or how else would you know what to destroy?

Double linked lists really shine if you know a node and what to remove it (eg it is part of a more complex object). The other useful property is the inverse iterator (iterate backwards) which is a lot more simple than with a single linked list. If you are simply using it as an abstract data structure then there is very little different between a single and double linked list (possibly other sorts of lists may be better).

 

[Pinzu]

...

Your code worked!

Is there any point in making a PlayerList and changing the timer-interval depending on the count of players in the list. and thus removing that oh so heavy if statement and few redundant function calls. Only problem I would have with that is that I don't know how the actual changing of the timer would look.

private static method OnTimer takes nothing returns nothing
            local HungryUnitList index 
            // if PlayerIsActive then 
                set index = HungryUnitList.head[thistype.p].next
                loop
                    exitwhen index.u == null 
                    if not UnitAlive(index.u) then
                        call BJDebugMsg("removed!")
                        call HungryUnitList.remove(index.u)
                    else
                        call BJDebugMsg("found 1")
                    endif
                    set index = index.next
                endloop
            //endif    
            set thistype.p = thistype.next_p[thistype.p]       
        endmethod
        
        private static method onInit takes nothing returns nothing 
            local timer t = CreateTimer()
            local integer i = 0
            loop 
                exitwhen i == 12
                set head[i] = thistype.allocate()
                set i = i + 1
            endloop
            set table = Table.create()
            set i = 0
            loop
                set thistype.next_p[i] = i + 1
                set i = i + 1
                exitwhen i == 11
            endloop
            set thistype.next_p[11] = 0
            call TimerStart(t, INTERVAL/12, true, function thistype.OnTimer)
            set t = null
        endmethod
    endstruct