On Mon, 7 Apr 2003, Wheeler Ruml wrote:

> I saw Brian's recommendation of a priority queue, but wanted to
> mention that a resizable array would do here as well.  Eg, something
> like

It actually sounds like a simple tree is what he needs.  The problem with 
a resizeable array is that removing anything except the last element is 
O(n)- remember that you have to copy all the higher elements down.  He 
specified fast deletion of arbitrary elements.

> Brian's
> queue may well do this underneath, 

Actually, my PSQueue is built ontop of a red-black tree.  And it's mainly 
usefull when you need both the behaviors of a priority queue and a search 
tree.  Otherwise it is a little heavy/

> but there's no reason to suffer
> O(log n) insertion and removal time if you don't really care about the
> order.  Just add to the end and swap with a random element in constant
> time.  Or remove from a random place and copy in the last element.
> The only tricky thing is to be careful to fill any "empty" cells in
> the array with the same dummy value (which needs to be supplied at
> creation time) so you don't prevent objects from being GC'ed.

This was the problem I ran into trying to do an arbitrary resizeable
array- I ended up doing a Some of/None trick to handle empty array
elements.  Which, of course, added a whole second layer of references.  
Although requiring the user to supply a null item isn't as bad as I first
thought- it's the same thing that Array.make does...

Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners