Re: Priority Queues?

[Luis Carvalho <carvalho@...>]

> 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[1] -- min (heap root)
  local r = t[e]
  local v = t[h[s]]
  h[1] = 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[1] == 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>