Re: polymorphically comparable Maps?

From: Jean-Francois Monin (JeanFrancois.Monin@cnet.francetelecom.fr)
Date: Mon Feb 22 1999 - 19:20:13 MET


Date: Mon, 22 Feb 1999 19:20:13 +0100
Message-Id: <199902221820.TAA03582@lsun565.lannion.cnet.fr>
From: Jean-Francois Monin <JeanFrancois.Monin@cnet.francetelecom.fr>
To: ohl@hep.tu-darmstadt.de
Subject: Re: polymorphically comparable Maps?
In-Reply-To: <14033.38333.652607.941379@heplix4.ikp.physik.tu-darmstadt.de>

> Does anybody know of a fast data structure for (applicative)
> association tables over ordered types (like Map in the standard
> library) with the property that identical maps will have an identical
> representation? Sorted association lists work, but have linear access
> and insertion. Is there something logarithmical (even with an OCaml
> implementation)?
>
> Thanks,
> -Thorsten

I've just finished an in-place polymorphic version of splay trees,
with quite good perf. Splay trees (Tarjan & Sleator) are binary trees
where often accessed data tend to be near the root.

Here is the current mli. Only iter and fold are still not
implemented, because I am currently experimenting this structure on an
application where they are not used. I can send the whole thing if you
are interested.

-- 
Jean-Francois Monin, CNET DTL/MSV,          Tel +33 2 96 05 26 79
2 av. Pierre Marzin, 22307 Lannion, France  Fax +33 2 96 05 39 45
SANS TRAIT D'UNION :      JeanFrancois.Monin@cnet.francetelecom     

----------------------------------------------------------- (* splay.mli *) (* NOT THREAD SAFE : env needs a mutex *) (* WARNING : compare must not raise anu exception *)

module type OrderedType = sig type tt type tk val compare_int : tt -> tt -> int val compare_ext : tk -> tt -> int val print : tt -> unit end

module type S = sig type eltt (* The type of elements in the tree. *) type eltk (* The type of keys used for searching in the tree. *) type t (* The type of trees. *) exception Already_there exception Is_empty val print : t -> unit (* prints a tree *) val create: unit -> t (* The empty tree. *) val is_empty: t -> bool (* Test whether a tree is empty or not. *) val find: eltk -> t -> eltt (* [find x s] is an element y of [s] such that [compare_ext x y = 0]. *) val add: eltt -> t -> unit (* [add x s] adds the element [x] to the tree [s], If [x] was already in [s], [Already_there] is raised. *) val remove: eltk -> t -> unit (* [remove x s] returns a tree containing all elements of [s], except [y] such that compare_ext x y = 0. If [x] was not in [s], TO BE COMPLETED. *) (* val iter: (eltt -> unit) -> t -> unit val fold: (eltt -> 'a -> 'a) -> t -> 'a -> 'a *) val cardinal: t -> int (* Return the number of elements of a tree. *) val elements: t -> eltt list (* Return the list of all elements of the given tree. The returned list is sorted in increasing order with respect to the ordering [Ord.compare_int], where [Ord] is the argument given to [Set.Make]. *) val min_elt: t -> eltt (* Return the smallest element of the given tree (with respect to the [Ord.compare_int] ordering), or raise [Not_found] if the tree is empty. *) val max_elt: t -> eltt (* Same as [min_elt], but returns the largest element of the given tree. *) val choose: t -> eltt (* Return one element of the given tree, or raise [Not_found] if the tree is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal trees. *) end

module Make(Ord: OrderedType): (S with type eltt = Ord.tt and type eltk = Ord.tk) (* Functor building an implementation of the tree structure given a totally ordered type. *)



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET