ptset.mli

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Copyright (C) Jean-Christophe Filliatre                               *)
   4 (*                                                                        *)
   5 (*  This software is free software; you can redistribute it and/or        *)
   6 (*  modify it under the terms of the GNU Library General Public           *)
   7 (*  License version 2.1, with the special exception on linking            *)
   8 (*  described in file LICENSE.                                            *)
   9 (*                                                                        *)
  10 (*  This software is distributed in the hope that it will be useful,      *)
  11 (*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
  12 (*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
  13 (*                                                                        *)
  14 (**************************************************************************)
  15
  16 (*i $Id: ptset.mli,v 1.10 2008-07-21 14:53:06 filliatr Exp $ i*)
  17
  18 (*s Sets of integers implemented as Patricia trees.  The following
  19     signature is exactly [Set.S with type elt = int], with the same
  20     specifications. This is a purely functional data-structure. The
  21     performances are similar to those of the standard library's module
  22     [Set]. The representation is unique and thus structural comparison
  23     can be performed on Patricia trees. *)
  24
  25 module type S =
  26 sig
  27
  28   type elt
  29   type data
  30   type t
  31   val empty : t
  32   val is_empty : t -> bool
  33   val mem : elt -> t -> bool
  34   val add : elt -> t -> t
  35   val singleton : elt -> t
  36   val remove : elt -> t -> t
  37   val union : t -> t -> t
  38   val inter : t -> t -> t
  39   val diff : t -> t -> t
  40   val compare : t -> t -> int
  41   val equal : t -> t -> bool
  42   val subset : t -> t -> bool
  43   val iter : (elt -> unit) -> t -> unit
  44   val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
  45   val for_all : (elt -> bool) -> t -> bool
  46   val exists : (elt -> bool) -> t -> bool
  47   val filter : (elt -> bool) -> t -> t
  48   val partition : (elt -> bool) -> t -> t * t
  49   val cardinal : t -> int
  50   val elements : t -> elt list
  51   val min_elt : t -> elt
  52   val max_elt : t -> elt
  53   val choose : t -> elt
  54   val split : elt -> t -> t * bool * t
  55     (*s Additional functions not appearing in the signature [Set.S] from ocaml
  56       standard library. *)
  57
  58   (* [intersect u v] determines if sets [u] and [v] have a non-empty
  59      intersection. *)
  60
  61 val intersect : t -> t -> bool
  62
  63 val is_singleton : t -> bool
  64 val mem_union : t -> t -> t
  65 val hash : t -> int
  66 val uid : t -> int
  67 val uncons : t -> elt * t
  68 val from_list : elt list -> t
  69 val make : data -> t
  70 val node : t -> data
  71 end
  72
  73
  74 module Int : sig
  75   include S with type elt = int
  76   val print : Format.formatter -> t -> unit
  77 end
  78 module Make ( H : Hcons.S ) : S with type elt = H.t