polymorphically comparable Maps?

Thorsten Ohl
 JeanFrancois Monin
 Stefan Monnier
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  19990223 (14:52) 
From:  JeanFrancois Monin <JeanFrancois.Monin@c...> 
Subject:  Re: polymorphically comparable Maps? 
> 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 inplace 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.  JeanFrancois 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. *)