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