(**************************************************************************) (* *) (* Copyright (C) Jean-Christophe Filliatre *) (* *) (* This software is free software; you can redistribute it and/or *) (* modify it under the terms of the GNU Library General Public *) (* License version 2.1, with the special exception on linking *) (* described in file LICENSE. *) (* *) (* This software is distributed in the hope that it will be useful, *) (* but WITHOUT ANY WARRANTY; without even the implied warranty of *) (* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *) (* *) (**************************************************************************) (* This module implements imperative sets as hash tables. Operations like union, intersection or difference are not provided, since there is no way to implement them easily (i.e. more easily than iterating over sets). *) (*s Generic interface *) type 'a t (* The type of sets. Elements have type ['a]. *) val create : int -> 'a t (* [Hashset.create n] creates a new, empty set. For best results, [n] should be on the order of the expected number of elements that will be in the set. The internal structure grows as needed, so [n] is just an initial guess. *) val clear : 'a t -> unit (* Empty a set. *) val add : 'a t -> 'a -> unit (* [Hashset.add s x] adds [x] into the set [s]. *) val copy : 'a t -> 'a t (* Return a copy of the given set. *) val mem : 'a t -> 'a -> bool (* [Hashset.mem s x] checks if [x] belongs to [s]. *) val remove : 'a t -> 'a -> unit (* [Hashset.remove s x] removes [x] from [s]. It does nothing if [x] does not belong to [s]. *) val cardinal : 'a t -> int (* [Hashset.cardinal s] returns the cardinal of [s]. *) val iter : ('a -> unit) -> 'a t -> unit (* [Hashset.iter f s] applies [f] to all elements in [s]. *) val fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b (* [Hashset.fold f s init] computes [(f eN ... (f e1 init)...)], where [e1 ... eN] are the elements in [s]. The order in which the elements are passed to [f] is unspecified. *) (*s Functorial interface *) module type HashedType = sig type t (* The type of the elements. *) val equal : t -> t -> bool (* The equality predicate used to compare elements. *) val hash : t -> int (* A hashing function on elements. It must be such that if two elements are equal according to [equal], then they have identical hash values as computed by [hash]. Examples: suitable ([equal], [hash]) pairs for arbitrary element types include ([(=)], {!Hashset.hash}) for comparing objects by structure, and ([(==)], {!Hashset.hash}) for comparing objects by addresses (e.g. for mutable or cyclic keys). *) end (* The input signature of the functor {!Hashset.Make}. *) module type S = sig type elt type t val create : int -> t val clear : t -> unit val copy : t -> t val add : t -> elt -> unit val remove : t -> elt -> unit val mem : t -> elt -> bool val cardinal : t -> int val iter : (elt -> unit) -> t -> unit val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a end (* The output signature of the functor {!Hashset.Make}. *) module Make (H : HashedType) : S with type elt = H.t (* Functor building an implementation of the hashtable structure. The functor [Hashset.Make] returns a structure containing a type [elt] of elements and a type [t] of hash sets. The operations perform similarly to those of the generic interface, but use the hashing and equality functions specified in the functor argument [H] instead of generic equality and hashing. *)

*This document was generated using
caml2html*