Double Linked List - Submission

[MyPad]

Code

library TimerQueue

    struct TimeQueue
        thistype prev
        thistype next

        // these methods are for ease in typing later on...
        method pop takes nothing returns nothing
            set next.prev = prev
            set prev.next = next
        endmethod

        method push takes thistype nodeNext returns nothing
            set next = nodeNext
            set prev = next.prev
            set next.prev = this
            set prev.next = this
        endmethod

        //  the main member of the struct...
        private static constant timer oneTimer = CreateTimer()

        real timeStamp

        method destroy takes nothing returns nothing
            set timeStamp = 0
            call pop()
            call deallocate()
        endmethod

        private static method onExpire takes nothing returns nothing
            local thistype this = thistype(0).next
            call this.destroy()
            set this = this.next
            call TimerStart(oneTimer, this.timeStamp, false, function thistype.onExpire)
        endmethod

        method adjust takes nothing returns nothing
            local thistype that = thistype(0).next
            loop
                exitwhen that == 0 or that.timeStamp - GetTimerExpired() > this.timeStamp
                set that = that.next
            endloop
            if that == 0 then
                call this.push(0)
                set this.timeStamp = this.timeStamp - that.prev.timeStamp
            else
                set that.timeStamp = that.timeStamp - GetTimerExpired() - this.timeStamp
                call this.push(that)
                call PauseTimer(oneTimer)
            endif
            call TimerStart(oneTimer, this.timeStamp, false, function thistype.onExpire)
        endmethod

        static method create takes real dur returns thistype
            local thistype this = allocate()
            set this.timeStamp = dur
            call this.adjust()
            return this
        endmethod
    endstruct
endlibrary

Mission Performed: Double Linked List

 

[IcemanBo]

Could you explain what it does, and why it make sense to use a doubly linked list?

 

[Aniki]

where the traversal of a certain pointer will always return back to the head (which in this case, any node can be a head.)

// It seems that only node(0) can be the head/sentinel node:
method push takes nothing returns nothing
    static if DEBUG_MODE then
        if next != 0 or (next == 0 and prev != 0) or thistype(0).next == this then
            call BJDebugMsg("|cffffcc00Error:|r Attempted to push existent node.")
        elseif this == 0 and (prev == 0 and next == 0) then
            call BJDebugMsg("|cffffcc00Error:|r Attempted to push head without its' nodes.")
        endif
        return // in debug mode we always return?
    endif
    set next = 0
    set prev = next.prev
    set next.prev = this
    set prev.next = this
endmethod


// In order for any node to be used as a sentinel/head it needs to be created with
// something like this:
//
static method create_sentinel takes nothing returns thistype
    local thistype sentinel = allocate()

    // in order for a node to be a sentinel/head it needs to point to itself when created
    // like node(0), except we are explicit now
    //
    set sentinel.prev = sentinel
    set sentinel.next = sentinel

    return sentinel
endmethod
static method create_node takes nothing returns thistype
    local thistype node = allocate()
    set node.prev = 0
    set node.next = 0
    return node
endmethod

method push takes thistype node returns nothing
    // `this` is the head/sentinel node, `node` is the node we want to add to the list

static if DEBUG_MODE then
    if node.prev != 0 or node.next != 0 then
        call BJDebugMsg("|cffffcc00Error:|r attempt to push a node that's already in a list")
        return
    endif
endif

    set node.prev = this.prev
    set node.next = this
    set node.prev.next = node
    set node.next.prev = node
endmethod

method pop takes nothing returns nothing
    // `this` is the node we want to remove from the list it was added

static if DEBUG_MODE then
    if this.prev == 0 or this.next == 0 then
        call BJDebugMsg("|cffffcc00Error:|r attempt to pop a node that's not in any list")
        return
    endif
endif

    set this.prev.next = this.next
    set this.next.prev = this.prev
endmethod

 

[MyPad]

method push takes thistype node returns nothing
    // `this` is the head/sentinel node, `node` is the node we want to add to the list

static if DEBUG_MODE then
    if node.prev != 0 or node.next != 0 then
        call BJDebugMsg("|cffffcc00Error:|r attempt to push a node that's already in a list")
        return
    endif
endif

    set node.prev = this.prev
    set node.next = this
    set node.prev.next = node
    set node.next.prev = node
endmethod

I usually do it the other way around, when I really need to make a linked list within a linked list: (Though it is just personal preference.)

method push takes thistype head returns nothing
    set next = head
    set prev = next.prev
    set next.prev = this
    set prev.next = this
endmethod

 

[IcemanBo]

You make much and good theory and provide a doubly linked list system (which is maybe a bit more advanced, but not very my goal); but I would want a little example where it's just applied, where it makes sense. (it can be hold prretty minimalistic, but should work)

 

[MyPad]

An application of double-linked list, you say?

One application of it is popping or removal.. (while keeping it in order)

Original List:
       1 -> 2 -> 4 -> 3 -> 5 -> 0
0 <- 1 <- 2 <- 4 <- 3 <- 5

Remove: 4

       (<- 4) -> == (4 ->); 2 -> 3
       <- (4 ->) == (<- 4); 2 <- 3

       next of 4 is 3;
       previous of 4 is 2;
       next of previous of 4 becomes next of 4; (3)
       previous of next of 4 becomes previous of 4; (2)

Result:

       1 -> 2 -> 3 -> 5 -> 0
0 <- 1 <- 2 <- 3 <- 5

                4 -> 3
         2 <- 4

      4: T_T

Spoiler: 4 says

Hey, man. What happened? Why did you kick me out of the list? I belong in that list!
*At this point, a mix of cursing and sobbing can be heard in his mumbling fervor*

EDIT: 18th of May, 2017

Scenario 1

Scenario 2

Scenario 3

Think of bricks making up a line. These bricks are indistinguishable from each other, save for their number. All you know is that they are all ordered. However, due to an accident, you took a chink off of a certain brick. You would then try to remove the brick and move the adjacent bricks closer to bridge the gap.

1-5-7-2-4-0-3-8-6

0 got damaged, remove...

1-5-7-2-4-3-8-6

What if you have a passive spell that runs periodically and has priority stuff? You would sort it out, first with those of highest priority down to the lowest. Then, you build a linked list off of that. That way, you know that no instance is disordered, though if the effects are instantaneous, then it would essentially be useless.

Almost the same case as Scenario 2, you are a waiter who takes the orders, serves the food and hands over the bill. Now, we have 5 types of customers:

Extremely Rich - (10 times richer than Bill Gates) (very impatient)
Rich - (Multi-millionaires) (somewhat patient)
Middle - (Ordinary) (patient)
Poor - (Namesake) (very impatient as well)
Loyal - (May be Extremely Rich, Rich, Middle or Poor) (Patience outlasts Bogo Sort sorting a thousand elements)

All of them appear, and you can't just render your service on queue, you have to prioritize them.

(Prioritization: Highest to Lowest as of Time Zero):

Extremely Rich
Rich
Poor
Middle
Loyal

Looking at that above, even if a poor guy was your first customer, you would prioritize the next customer if it so happens that the customer is at least Rich.

With that being said, if your first was a Middle-class customer, and your second is a Loyal one, you would render your service first to the middle-class customer.

 

[IcemanBo]

No.

Again; what you do might be right but not the goal. What you do is theory; I want a useable demonstration in practice inwhich a doubly linked list makes sense; not a module system or so. : )

 

[IcemanBo]

Not sure you are trolling me.

 

[MyPad]

Sorry for the long wait. I'll try to revisit the mission section first and check if my submission fits the intended goal.