(***********************************************************************)
(*                                                                     *)
(*                               TAToo                                 *)
(*                                                                     *)
(*                     Kim Nguyen, LRI UMR8623                         *)
(*                   Université Paris-Sud & CNRS                       *)
(*                                                                     *)
(*  Copyright 2010-2012 Université Paris-Sud and Centre National de la *)
(*  Recherche Scientifique. All rights reserved.  This file is         *)
(*  distributed under the terms of the GNU Lesser General Public       *)
(*  License, with the special exception on linking described in file   *)
(*  ../LICENSE.                                                        *)
(*                                                                     *)
(***********************************************************************)

(** Implementation of generic hashconsing. *)

module type Abstract =
  sig
    type data
      (** The type of the data to be hashconsed *)

    type t
      (** The type of hashconsed data *)

    val make : data -> t
      (** [make v] internalizes the value [v], making it an hashconsed
          value.
      *)

    val node : t -> data
      (** [node h] extract the original data from its hashconsed value
      *)

    val hash : t -> int
      (** [hash h] returns a hash of [h], such that for every [h1] and
          [h2], [equal h1 h2] implies [hash h1 = hash h2].
      *)

    val uid : t -> Uid.t
      (** [uid h] returns a unique identifier *)
    val equal : t -> t -> bool
      (** Equality between hashconsed values. Equivalent to [==] *)

    val init : unit -> unit
      (** Initializes the internal storage. Any previously hashconsed
          element is discarded. *)

  end
(** Abstract signature of a module implementing an hashconsed datatype *)

module type S =
sig
  type data
  type t = private { id   : Uid.t;
                     key  : int;
                     node : data }
  include Abstract with type data := data and type t := t
end

(** Output signature of the functor {!Hcons.Make} *)

module Make (H : Sigs.HashedType) : S with type data = H.t
(** Functor building an implementation of hashconsed values for a given
    implementation of {!Sigs.HashedType}. Hashconsed values are
    persistent: the are kept in memory even if no external reference
    remain. Calling [init()] explicitely will reclaim the space.
*)

module Weak (H : Sigs.HashedType) : S with type data = H.t
(** Functor building an implementation of hashconsed values for a given
    implementation of {!Sigs.HashedType}. Hashconsed values have a
    weak semantics: they may be reclaimed as soon as no external
    reference to them exists. The space may still be reclaimed
    explicitely by calling [init].
*)

module PosInt : Abstract with type data = int and type t = int
(** Compact implementation of hashconsed positive integer that
    avoids boxing. [PosInt.make v] raises [Invalid_argument] if
    [ v < 0 ]
*)