Re: efficient timers

[Oliver Kroth <oliver.kroth@...>]

Hi Nagaev,

here you are. In this implementation, the events are closures being 
called when due.

--
Oliver Kroth


Am 13.04.2015 um 10:38 schrieb Nagaev Boris:
> On Mon, Apr 13, 2015 at 8:17 AM, Oliver Kroth <oliver.kroth@nec-i.de> wrote:
> > Hi Thijs,
> >
> > not sure if someone else referred to a solution like mine:
> > I used in one of my projects a so called binary heap as "queue". New events
> > are inserted at the end and bubbled up. Deleted timers leave a hole that is
> > filled by inserting the last element and resort the heap. Checking whether
> > the first (earliest) event is due can be done in O(1) by looking on the
> > heap's root. Inserting and deleting events can be done in O(log n). The
> > funny thing is that the heap does not use pointers but is stored in a
> > contiguous array using the event's index to calculate the parent's and
> > children's indexes.
> >
> > May not be the most efficient solution but had the smallest overhead on
> > checking the due events, and has reasonable effort on queue management.
> > The Lua implementations is about 100 LOC.
> >
> > If someone is interested, I may post it.
> >
> > --
> > Oliver Kroth
> I am interested. Could you post it, please?
>
> Best regards,
> Boris Nagaev

#license =_MANIFEST.license
---
--- module for a binary heap with { time, f(params) }
--- f is a function that shall be triggered at time 'time'
---   actually its a closure with all params

--
-- we define an event queue
-- that is a binary heap implemented as array
-- each element is a tupel of when it happens and what happens
-- usually, what is a so called closure, i.e. a function with
-- upvalues uses
-- e.g. schedule( 100, decrement( timers, 1))
-- will first create a function that will, when called, decrement timers[1]
-- and then insert this into the heap

local schedule = {}
local now = os.time
local floor = math.floor

function schedule:bubbleUp( pos )
	while pos>1 do
		local parent = floor(pos/2)
		if self[parent].when <= self[pos].when then break end
		self[parent], self[pos]= self[pos], self[parent]
		pos = parent
	end
end

function schedule:sinkDown( pos )
	local last = #self
	while true do
		local min = pos
		local child =2*pos

		for c=child, child+1 do
			if c <= last and self[c].when < self[min].when then min = c end
		end
		
		if min == pos then break end
	
		self[pos], self[min] = self[min], self[pos]
		pos = min
	end
end

function schedule:remove( pos )
	local last = #self
	if pos<1 or pos>last then return end
	
	local node  = self[ pos ]
	
	if pos<last then
		self[pos] = self[last]
		self:bubbleUp( pos )
		self:sinkDown( pos )
	end
	
	self[last]  = nil
	return node
end

function schedule:get( when )
	if #self>0 and self[1].when < (when or now()) then 
		return self:remove( 1 ).what
	end
end

function schedule:put( when, what  )
	local pos = #self+1
	if when < 1000000 then when = when + now() end -- relative time -> absolute
	
	self[pos] =  {when=when, what=what}
	self:bubbleUp( pos )
end

function schedule:run( when )
	when = when or now()
	while true do 
		local what = self:get( when )
		if not what then break end
		what( when )
	end
end

function schedule:schedule( when, what )
	if what then
		return self:put( when, what )
	else
		return self:run( when )
	end
end

--
-- schedule()			will do schedule:run()
-- schedule(when)		will do schedule:run(when)
-- schedule(when,what)	will do schedule:put(when,what)

setmetatable( schedule, {__call = schedule.schedule })

return schedule