Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Brian Hurt <brian.hurt@q...>
Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures
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...


To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: