lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

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 <> 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

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
		if min == pos then break end
		self[pos], self[min] = self[min], self[pos]
		pos = min

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 )
	self[last]  = nil
	return node

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

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 )

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

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

-- 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