src/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
  30   type 'a node
  31   module rec Node : sig
  32     include  Hcons.S with type data = Data.t
  33   end
  34   and Data : sig
  35     include
  36       Hashtbl.HashedType with type t = Node.t node
  37   end
  38   type data = Data.t
  39   type t = Node.t
  40
  41   val empty : t
  42   val is_empty : t -> bool
  43   val mem : elt -> t -> bool
  44   val add : elt -> t -> t
  45   val singleton : elt -> t
  46   val remove : elt -> t -> t
  47   val union : t -> t -> t
  48   val inter : t -> t -> t
  49   val diff : t -> t -> t
  50   val compare : t -> t -> int
  51   val equal : t -> t -> bool
  52   val subset : t -> t -> bool
  53   val iter : (elt -> unit) -> t -> unit
  54   val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
  55   val for_all : (elt -> bool) -> t -> bool
  56   val exists : (elt -> bool) -> t -> bool
  57   val filter : (elt -> bool) -> t -> t
  58   val partition : (elt -> bool) -> t -> t * t
  59   val cardinal : t -> int
  60   val elements : t -> elt list
  61   val min_elt : t -> elt
  62   val max_elt : t -> elt
  63   val choose : t -> elt
  64   val split : elt -> t -> t * bool * t
  65     (*s Additional functions not appearing in the signature [Set.S] from ocaml
  66       standard library. *)
  67
  68   (* [intersect u v] determines if sets [u] and [v] have a non-empty
  69      intersection. *)
  70
  71 val intersect : t -> t -> bool
  72
  73 val is_singleton : t -> bool
  74 val mem_union : t -> t -> t
  75 val hash : t -> int
  76 val uid : t -> Uid.t
  77 val uncons : t -> elt * t
  78 val from_list : elt list -> t
  79 val make : data -> t
  80 val node : t -> data
  81 val stats : unit -> unit
  82 end
  83
  84
  85 module Int : sig
  86   include S with type elt = int
  87   val print : Format.formatter -> t -> unit
  88 end
  89
  90 module Make ( H : Hcons.SA ) : S with type elt = H.t