  lua-l archive

• Subject: Re: Priority Queues?
• From: Luis Carvalho <carvalho@...>
• Date: Wed, 25 Jul 2007 11:49:50 -0400

```> The simulation is mostly written in C++, and I started using Lua for
> its configuration files which turned out to be very effective and
> easy, so the next step has been to make the simulation a Lua module,
> which has made the whole thing far more useful and easy to test.
>
> What I'm thinking of next is writing some of the simulation logic in
> Lua.  This seems to mean storing "pointers to Lua objects" (functions
> or callable tables) on the C++ side which should be ok. I think where
> I'd like to get to, or at least try as an exercise, is having
> something like a std::priority_queue containing "pointers to Lua
> functions".
>
> I'm not quite sure how to go about this.  The queue might get longish
> - 100,000's of elements, and I'd like the solution to be moderately
> efficient.

<snip>

You should try a pure Lua solution first, and see if that's efficient enough
for you since it'd be easier to write and maintain. Here's a simple
implementation:

-- Heap.lua
-- A simple priority queue implementation
local assert, setmetatable = assert, setmetatable

module(...)

local function push (h, k, v)
assert(v ~= nil, "cannot push nil")
local t = h.nodes
local h = h.heap
local n = #h + 1 -- node position in heap array (leaf)
local p = (n - n % 2) / 2 -- parent position in heap array
h[n] = k -- insert at a leaf
t[k] = v
while n > 1 and t[h[p]] < v do -- climb heap?
h[p], h[n] = h[n], h[p]
n = p
p = (n - n % 2) / 2
end
end

local function pop (h)
local t = h.nodes
local h = h.heap
local s = #h
assert(s > 0, "cannot pop from empty heap")
local e = h -- min (heap root)
local r = t[e]
local v = t[h[s]]
h = h[s] -- move leaf to root
h[s] = nil -- remove leaf
t[e] = nil
s = s - 1
local n = 1 -- node position in heap array
local p = 2 * n -- left sibling position
if s > p and t[h[p]] < t[h[p + 1]] then
p = 2 * n + 1 -- right sibling position
end
while s >= p and t[h[p]] > v do -- descend heap?
h[p], h[n] = h[n], h[p]
n = p
p = 2 * n
if s > p and t[h[p]] < t[h[p + 1]] then
p = 2 * n + 1
end
end
return e, r
end

local function isempty (h) return h.heap == nil end

function new ()
return setmetatable({heap = {}, nodes = {}},
{__index = {push=push, pop=pop, isempty=isempty}})
end

Quick test:

\$ lua -lHeap
Lua 5.1.2  Copyright (C) 1994-2007 Lua.org, PUC-Rio
> h = Heap.new()
> for i=1,10 do h:push(i, math.random()) end
> while not h:isempty() do print(h:pop()) end
3       0.83096534611237
7       0.67114938407724
6       0.52970019333516
2       0.51941637206795
1       0.38350207748986
9       0.38341565075489
10      0.066842237518561
5       0.053461635044525
4       0.034572110527461
8       0.0076981862111474

Note that keys can be arbitrary:

> for i=1,10 do h:push(math.random()>0.5 and newproxy() or {}, math.random()) end
> while not h:isempty() do print(h:pop()) end
table: 0x30b130 0.98255028621412
table: 0x30b4c0 0.89765628655332
userdata: 0x30b264      0.8847071285754
userdata: 0x30b044      0.75335583498392
userdata: 0x30b474      0.47773176500468
table: 0x30b270 0.43641140565109
table: 0x30b480 0.2749068403034
table: 0x30b4a0 0.16650720041548
userdata: 0x30b064      0.072685882948658
userdata: 0x30b4f4      0.060564327547589

This is a bit off-topic, but what kind of transport simulation you're doing?
Is it traffic network simulation? I used to be a transport engineer and these
things still entice my curiosity. :) Are you planning on making your work
available? Please keep us informed of your progress.

Cheers,
Luis.

--
A mathematician is a device for turning coffee into theorems.
-- P. Erdos

--
Luis Carvalho
Applied Math PhD Student - Brown University
PGP Key: E820854A <carvalho@dam.brown.edu>

```