1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
(**************************************************************************)
(* *)
(* Menhir *)
(* *)
(* Franois Pottier and Yann Rgis-Gianas, INRIA Rocquencourt *)
(* *)
(* Copyright 2005 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* under the terms of the Q Public License version 1.0, with the *)
(* change described in file LICENSE. *)
(* *)
(**************************************************************************)
(* This is a stripped down version of [GSet] that describes both [Patricia]
and [CompressedBitSet]. The full version of [GSet] is in [AlphaLib]. *)
module type S = sig
(* Elements are assumed to have a natural total order. *)
type element
(* Sets. *)
type t
(* The empty set. *)
val empty: t
(* [is_empty s] tells whether [s] is the empty set. *)
val is_empty: t -> bool
(* [singleton x] returns a singleton set containing [x] as its only
element. *)
val singleton: element -> t
(* [cardinal s] returns the cardinal of [s]. *)
val cardinal: t -> int
(* [choose s] returns an arbitrarily chosen element of [s], if [s]
is nonempty, and raises [Not_found] otherwise. *)
val choose: t -> element
(* [mem x s] returns [true] if and only if [x] appears in the set
[s]. *)
val mem: element -> t -> bool
(* [add x s] returns a set whose elements are all elements of [s],
plus [x]. *)
val add: element -> t -> t
(* [remove x s] returns a set whose elements are all elements of
[s], except [x]. *)
val remove: element -> t -> t
(* [union s1 s2] returns the union of the sets [s1] and [s2]. *)
val union: t -> t -> t
(* [inter s t] returns the set intersection of [s] and [t], that is,
$s\cap t$. *)
val inter: t -> t -> t
(* [disjoint s1 s2] returns [true] if and only if the sets [s1] and
[s2] are disjoint, i.e. iff their intersection is empty. *)
val disjoint: t -> t -> bool
(* [iter f s] invokes [f x], in turn, for each element [x] of the
set [s]. Elements are presented to [f] in increasing order. *)
val iter: (element -> unit) -> t -> unit
(* [fold f s seed] invokes [f x accu], in turn, for each element [x]
of the set [s]. Elements are presented to [f] in increasing
order. The initial value of [accu] is [seed]; then, at each new
call, its value is the value returned by the previous invocation
of [f]. The value returned by [fold] is the final value of
[accu]. In other words, if $s = \{ x_1, x_2, \ldots, x_n \}$,
where $x_1 < x_2 < \ldots < x_n$, then [fold f s seed] computes
$([f]\,x_n\,\ldots\,([f]\,x_2\,([f]\,x_1\,[seed]))\ldots)$. *)
val fold: (element -> 'b -> 'b) -> t -> 'b -> 'b
(* [elements s] is a list of all elements in the set [s]. *)
val elements: t -> element list
(* [compare] is an ordering over sets. *)
val compare: t -> t -> int
(* [equal] implements equality over sets. *)
val equal: t -> t -> bool
(* [subset] implements the subset predicate over sets. *)
val subset: (t -> t -> bool)
end
|
