On Sat, 23 Jul 2005, Stephane Glondu wrote:

> On Saturday 23 July 2005 11:27, Berke Durak wrote:
> > That was my point.  You could cleanly initialize your heap with that
> > "any" value.
> 
> I was thinking about sth you could adjust to your purpose:
> 
> module type HEAP = sig
>   type 'a t
>   val create : int -> 'a t
>   val set : 'a t -> int -> 'a -> unit
>   val get : 'a t -> int -> 'a
> end
> 
> module Heap : HEAP = struct
>   type 'a cell = Fill of 'a array | Empty of int
>   type 'a t = 'a cell ref
> 
>   let create n = ref (Empty n)
> 
>   let set h i e = match !h with
>       Empty n -> h := Fill (Array.create n e)
>     | Fill a -> a.(i) <- e
> 
>   let get h n = match !h with
>       Empty _ -> raise Not_found
>     | Fill a -> a.(n)
> end
> 
> No Obj.magic here. Does this suit you?

This seems to be equivalent to the idea of using an array option, which I 
mentioned earlier.

Problems:

What if I have operations that add and remove elements on the heap in 
random order (so that the heap sometimes has to shrink), and I want 
(1) that every element which was removed from the heap and is otherwise 
inaccessible can be reclaimed by GC, and (2) that removing a single 
element from the heap does not require copying the underlying Array?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)