Trees, lists and pointers?

Questions
1

I’m working on an algorithm that needs a priority queue and a binary search tree.
I’ve got those parts working, but in an ugly way.
Both are implemented by adding items to a list and using the index of the array as a sort of pointer.
Problem is that when sorting stuff all “pointers” need to be reindexed.
I’ ve a gut feeling that it should be possible to use a more lua-way of doing it, but I’m stuck.
Could someone point me to a tutorial or example?

2

Maybe table.remove and table.insert can help you there, at least with the queue. They can remove and insert stuff on both ends of a table, thus making it easy to use tables as lists, queues, dequeues, stacks, stuff like that. As for the binary search tree, you can just implement that in a flat array, preferrably using a balanced tree algorithm. The two child nodes of th node at index an would be at indices 2n and 2n+1.

3

Very true. I think I need to refrase my question.
the queue and the binary tree contain pointers to eachother.
The issue is that if i insert an item in the queue, the pointers in the binary tree are no longer correct. I’m looking for a solution that doesn’t involve updating all pointers on the other list when an add/remove command is issued.

4

ok, I got that now. What kind of data are you storing?

5

I’m trying to build an implementation of Fortune’s algorithm to compute Voronoi diagrams. In it I have a priority queue that stores events sorted by their coordinate. It also stores intermediate data (the sweepline) in a binary search tree. Some events point to the sweepline data, some sweepline data points to events in the queue.
I see two directions forward:

  1. don’t use a search tree / queue, bruteforce search each lookup. I don’t expect to have many data points, so this might work
  2. keep the events in a static list, use a seperate array to store pointers to this list. By sorting these pointers the queue is implemented, external methods could point directly to the static list.

Still, because lua relies heavily on pointers, there may be a more “lua-way” of doing this.