**Next message:**Ching-Tsun Chou: "Re: Warnings in ocaml"**Previous message:**Pierre Weis: "Re: Warnings in ocaml"**Next in thread:**Stefan Monnier: "Re: polymorphically comparable Maps?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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. *)

**Next message:**Ching-Tsun Chou: "Re: Warnings in ocaml"**Previous message:**Pierre Weis: "Re: Warnings in ocaml"**Next in thread:**Stefan Monnier: "Re: polymorphically comparable Maps?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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