Re: Priority Queues?

["Jérôme Vuarand" <jerome.vuarand@...>]

2007/7/24, Geoff Leyland <geoff_leyland@fastmail.fm>:
> 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.
>
> One way I can imagine doing this at the moment is to create a table
> in the registry and store the lua functions at indexes in that table,
> and then store those indexes in the priority_queue.  That way, Lua is
> aware that I'm interested in those objects, and I have a way of
> keeping hold of them.  Popping to top off the priority queue will
> also mean removing an element from the table, which I imagine will be
> a little inefficient.  Possibly more than I'd like, but I'll have to
> see.

I think this is the right solution.

> The other approach I can think of (which I don't really like) is to
> look at the Lua internals to see if I can hold on to a "lua object"
> other than in a stack or the registry, and if I can make sure the GC
> knows what I'm up to.  Like I said, probably not a good idea.

I second your feeling that it's probably not a good idea, unless you
really want to know the Lua internals and you want to consider this as
a good occasion.

> Does anyone have any advice on how to approach this?  Have any
> experience with storing a largish number of lua variables in a C data
> structure?  Am I missing anything obvious?  Is there anywhere this
> kind of question has already been covered?

If your Lua objects are userdata instead of functions or tables, you
can store them directly in the registry, with the userdata itself as
value, and a lightuserdata pointing to the full userdata as the key.
You can then store that lightuserdata in your priority_queue. This
removes the need for an intermediate table, and it may be easier to
manage than integers.

This means that you will use the hashmap part of the table instead of
the array part, but since your data structure is a queue it may end up
being a sparse array and anyway use the hashmap of the table.

That's just ideas to widen your perspectives, do not take it as an
expert's advice ;-)