Re: polymorphically comparable Maps?

[Jean-Francois Monin <JeanFrancois.Monin@cnet.francetelecom.fr>]

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