From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA00186 for caml-redistribution; Tue, 23 Feb 1999 15:52:45 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA11503 for ; Mon, 22 Feb 1999 19:20:17 +0100 (MET) Received: from p-voyageur.issy.cnet.fr (p-voyageur.issy.cnet.fr [139.100.0.39]) by nez-perce.inria.fr (8.8.7/8.8.7) with SMTP id TAA14579 for ; Mon, 22 Feb 1999 19:20:16 +0100 (MET) Received: from l-mhs1.lannion.cnet.fr ([161.104.1.59]) by p-voyageur.issy.cnet.fr with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2232.9) id FB3V2WTY; Mon, 22 Feb 1999 19:17:13 +0100 Received: from lsun565.lannion.cnet.fr ([161.104.10.182]) by l-mhs1.lannion.cnet.fr with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2232.9) id ZNBGSPAC; Mon, 22 Feb 1999 19:23:46 +0100 Received: from lsun565.cnet by lsun565.lannion.cnet.fr (SMI-8.6/SMI-SVR4) id TAA03582; Mon, 22 Feb 1999 19:20:13 +0100 Date: Mon, 22 Feb 1999 19:20:13 +0100 Message-Id: <199902221820.TAA03582@lsun565.lannion.cnet.fr> From: Jean-Francois Monin MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: ohl@hep.tu-darmstadt.de Cc: caml-list@inria.fr Subject: Re: polymorphically comparable Maps? In-Reply-To: <14033.38333.652607.941379@heplix4.ikp.physik.tu-darmstadt.de> References: <14033.38333.652607.941379@heplix4.ikp.physik.tu-darmstadt.de> X-Mailer: VM 6.37 under Emacs 20.2.1 Sender: weis > 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. *)