Re: AW: [Caml-list] generic Hashtbl.to_array

[skaller <skaller@users.sourceforge.net>]

On Tue, 2006-07-25 at 12:19 +0200, Christoph Bauer wrote:
> Hi,
> 
> > 
> > You could also try inverting the Hashtbl fold into an 
> > iterator+closure and pass the closure into the Array.init 
> > function, but I'm not sure how complicated/efficient that would be.
> 
> Something like:
> 
> let to_array_2 t =
>   let init _ = fun () -> raise Not_found  in
>   let a = Array.init (Hashtbl.length t) init in
>     ignore
>       (Hashtbl.fold (fun k v i -> a.(i) <- (fun () -> (k, v)); i+1) t 0);
>     Array.map (fun f -> f ())  a

ugg .. really need a variable length array here. However the most
efficient solution is:

(1) Use Hashtbl.iter to capture just one value out of the 
Hashtble:

	let get1 h = 
		Hashtbl.iter (fun k v -> raise XSome (k,v)) h;
		raise XNone
	in

(2) Initialise the array with it:

	let a = try get1 h with
	| XSome x -> Array.init (Hashtbl.length h) x
	| XNone -> raise Not_found (* zero length array? *)
	in

(3) Now use Hashtbl.fold or iter to initialise the array.

This 'costs' a write barrier but there is no additional
data structure required, and the whole thing is quite safe.

This leaves open the problem of making a zero length array
of the correct type.. not a problem if you're writing
the code inside the Hashtbl module, but trickier if you're
doing it outside.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net