FIFO and timers

04-18-2008, 04:13 PM

So, let's say you got a system that in multiple situations requires to wait 0.5 seconds and then do something on a certain, let's say for now, unit.

The precondition for this to work is that the timer period is constant, by adding the unit back to the queue the timer can be periodic

JASS:


function timerexpires takes nothing returns nothing
    call process( queue_front() )
    call queue_pop()

    call Recycle(GetExpiredTimer())
endfunction


function add takes unit u returns nothing
    call queue_push(u)
    call TimerStart(RecycledTimer(), 0.5 , false, function timerexpires)
endfunction

Anyways, queue stuff can be inlined and is simple tocode, if you don't want to use a new timer on every time (for example timer recycling functions are heavy since they at least need a function call) You can alter it a little by using two timers and skipping the next expiration time in another queue. You would then need a new TimerStart on every expire event.

The only problem relies in coding the queue, if you used a linked list it is very easy, but it is not fast if you need a function to recycle every node's id, you can just code the linked list yourself instead of using structs but then it gets a little messy.

You can just use an array for the queue and make it circular, this will require a modulo operation on every timer expire. (No function call/etc)

People interested in speed that don't bother about pretty code shall try using a manual linked list + textmacros to handle the timer start, the front, push and pop, etc.

Anyways, it works (as long as the delay is the same for every instance) it is multi instanceable and a good readable implementation requires at most one function call per timer expire.

04-18-2008, 07:04 PM

TheDamien

I was working on a queue struct prior to this, based on a singly-linked list. Works pretty well as far as I can tell.

JASS:

library Queue
    globals
        private integer array S
        private integer N = 0
        private integer M = 0
        private integer array val
        private integer array next
    endglobals
    
    struct Queue
        private integer front = 0
        private integer back = 0
        public integer size = 0

        public method push takes integer i returns nothing
            local integer d
            if (N == 0) then
                set M=M+1
                set d = M
            else
                set N=N-1
                set d = S[N]
            endif
            if (this.front == 0) then
                set this.front = d
                set this.back = d
            else
                set next[this.back] = d
                set this.back = d
            endif
            set val[d] = i
            set next[d] = 0
            set this.size = this.size+1
        endmethod
        
        public method shift takes nothing returns integer
            local integer d = this.front
            if (d > 0) then
                set this.size = this.size-1
                set this.front = next[d]
                set S[N] = d
                set N=N+1
                return val[d]
            endif
            return 0
        endmethod
        
        private method onDestroy takes nothing returns nothing
            local integer d = this.front
            loop
                exitwhen d == 0
                set S[N] = d
                set N=N+1
                set d = next[d]
            endloop
        endmethod
    endstruct
endlibrary

Usage:

JASS:

local Queue Q = Queue.create()
call Q.push(42)
call BJDebugMsg(I2S(Q.shift())) // Displays "42"
call BJDebugMsg(I2S(Q.size)) // Displays "0" because the shift method removes the element.
call Q.destroy() // Cleans up.

04-18-2008, 11:37 PM	#3
Strilanc	I'm exactly clear what your question is, Vexorian. I think you should go the circular array route. You don't need to use a modulo operation if you're only incrementing by 1. Just use an 'if ++x > 8190 then x = 0' line.

04-19-2008, 01:08 AM	#4
Vexorian	Darn, dunno what's happening to me lately, how could I have forgotten such trick I used that much in programming contests?