1 (**************************************************************************)
3 (* Copyright (C) Jean-Christophe Filliatre *)
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. *)
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. *)
14 (**************************************************************************)
16 (*i $Id: ptset.mli,v 1.10 2008-07-21 14:53:06 filliatr Exp $ i*)
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. *)
32 include Hcons.S with type data = Data.t
36 Hashtbl.HashedType with type t = Node.t node
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
64 val split : elt -> t -> t * bool * t
65 (*s Additional functions not appearing in the signature [Set.S] from ocaml
68 (* [intersect u v] determines if sets [u] and [v] have a non-empty
71 val intersect : t -> t -> bool
73 val is_singleton : t -> bool
74 val mem_union : t -> t -> t
77 val uncons : t -> elt * t
78 val from_list : elt list -> t
81 val stats : unit -> unit
82 val init : unit -> unit
87 include S with type elt = int
88 val print : Format.formatter -> t -> unit
91 module Make ( H : Hcons.SA ) : S with type elt = H.t