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. *)
31 val is_empty : t -> bool
33 val mem : int -> t -> bool
35 val add : int -> t -> t
37 val singleton : int -> t
39 val remove : int -> t -> t
41 val union : t -> t -> t
43 val subset : t -> t -> bool
45 val inter : t -> t -> t
47 val diff : t -> t -> t
49 val equal : t -> t -> bool
51 val compare : t -> t -> int
53 val elements : t -> int list
57 val cardinal : t -> int
59 val iter : (int -> unit) -> t -> unit
61 val fold : (int -> 'a -> 'a) -> t -> 'a -> 'a
63 val for_all : (int -> bool) -> t -> bool
65 val exists : (int -> bool) -> t -> bool
67 val filter : (int -> bool) -> t -> t
69 val partition : (int -> bool) -> t -> t * t
71 val split : int -> t -> t * bool * t
73 (*s Warning: [min_elt] and [max_elt] are linear w.r.t. the size of the
74 set. In other words, [min_elt t] is barely more efficient than [fold
77 val min_elt : t -> int
78 val max_elt : t -> int
80 (*s Additional functions not appearing in the signature [Set.S] from ocaml
83 (* [intersect u v] determines if sets [u] and [v] have a non-empty
86 val intersect : t -> t -> bool
87 val is_singleton : t -> bool
91 val from_list : int list -> t
94 val to_int_vector : t -> int_vector