1(* Intset -- applicative sets of integers                        *)
2(* From SML/NJ lib 0.2, copyright 1993 by AT&T Bell Laboratories *)
3(* Original implementation due to Stephen Adams, Southampton, UK *)
4
5signature Intset =
6sig
7
8type intset
9
10exception NotFound
11
12val empty        : intset
13val singleton    : int -> intset
14val add          : intset * int -> intset
15val addList      : intset * int list -> intset
16val isEmpty      : intset -> bool
17val equal        : intset * intset -> bool
18val isSubset     : intset * intset -> bool
19val member       : intset * int -> bool
20val delete       : intset * int -> intset
21val numItems     : intset ->  int
22val union        : intset * intset -> intset
23val intersection : intset * intset -> intset
24val difference   : intset * intset -> intset
25val listItems    : intset -> int list
26val app          : (int -> unit) -> intset -> unit
27val revapp       : (int -> unit) -> intset -> unit
28val foldr        : (int * 'b -> 'b) -> 'b -> intset -> 'b
29val foldl        : (int * 'b -> 'b) -> 'b -> intset -> 'b
30val find         : (int -> bool) -> intset -> int option
31
32end
33
34(*
35   [intset] is the type of sets of integers.
36
37   [empty] is the empty set of integers.
38
39   [singleton i] is the singleton set containing i.
40
41   [add(s, i)] adds item i to set s.
42
43   [addList(s, xs)] adds all items from the list xs to the set s.
44
45   [isEmpty s] returns true if and only if the set is empty.
46
47   [equal(s1, s2)] returns true if and only if the two sets have the
48   same elements.
49
50   [isSubset(s1, s2)] returns true if and only if s1 is a subset of s2.
51
52   [member(s, i)] returns true if and only if i is in s.
53
54   [delete(s, i)] removes item i from s.  Raises NotFound if i is not in s.
55
56   [numItems s] returns the number of items in set s.
57
58   [union(s1, s2)] returns the union of s1 and s2.
59
60   [intersection(s1, s2)] returns the intersectionof s1 and s2.
61
62   [difference(s1, s2)] returns the difference between s1 and s2 (that
63   is, the set of elements in s1 but not in s2).
64
65   [listItems s] returns a list of the items in set s, in increasing
66   order.
67
68   [app f s] applies function f to the elements of s, in increasing
69   order.
70
71   [revapp f s] applies function f to the elements of s, in decreasing
72   order.
73
74   [foldl f e s] applies the folding function f to the entries of the
75   set in increasing order.
76
77   [foldr f e s] applies the folding function f to the entries of the
78   set in decreasing order.
79
80   [find p s] returns SOME i, where i is an item in s which satisfies
81   p, if one exists; otherwise returns NONE.
82*)
83