1(* Binaryset -- sets implemented by ordered balanced binary trees *)
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 Binaryset =
6sig
7
8type 'item set
9
10exception NotFound
11
12val empty        : ('item * 'item -> order) -> 'item set
13val singleton    : ('item * 'item -> order) -> 'item -> 'item set
14val add          : 'item set * 'item -> 'item set
15val addList      : 'item set * 'item list -> 'item set
16val retrieve     : 'item set * 'item -> 'item
17val peek         : 'item set * 'item -> 'item option
18val isEmpty      : 'item set -> bool
19val equal        : 'item set * 'item set -> bool
20val isSubset     : 'item set * 'item set -> bool
21val member       : 'item set * 'item -> bool
22val delete       : 'item set * 'item -> 'item set
23val numItems     : 'item set ->  int
24val union        : 'item set * 'item set -> 'item set
25val intersection : 'item set * 'item set -> 'item set
26val difference   : 'item set * 'item set -> 'item set
27val listItems    : 'item set -> 'item list
28val app          : ('item -> unit) -> 'item set -> unit
29val revapp       : ('item -> unit) -> 'item set -> unit
30val foldr        : ('item * 'b -> 'b) -> 'b -> 'item set -> 'b
31val foldl        : ('item * 'b -> 'b) -> 'b -> 'item set -> 'b
32val find         : ('item -> bool) -> 'item set -> 'item option
33
34end
35
36(*
37   ['item set] is the type of sets of ordered elements of type 'item.
38   The ordering relation on the elements is used in the representation
39   of the set.  The result of combining two sets with different
40   underlying ordering relations is undefined.  The implementation
41   uses ordered balanced binary trees.
42
43   [empty ordr] creates a new empty set with the given ordering
44   relation.
45
46   [singleton ordr i] creates the singleton set containing i, with the
47   given ordering relation.
48
49   [add(s, i)] adds item i to set s.
50
51   [addList(s, xs)] adds all items from the list xs to the set s.
52
53   [retrieve(s, i)] returns i if it is in s; raises NotFound otherwise.
54
55   [peek(s, i)] returns SOME i if i is in s; returns NONE otherwise.
56
57   [isEmpty s] returns true if and only if the set is empty.
58
59   [equal(s1, s2)] returns true if and only if the two sets have the
60   same elements.
61
62   [isSubset(s1, s2)] returns true if and only if s1 is a subset of s2.
63
64   [member(s, i)] returns true if and only if i is in s.
65
66   [delete(s, i)] removes item i from s.  Raises NotFound if i is not in s.
67
68   [numItems s] returns the number of items in set s.
69
70   [union(s1, s2)] returns the union of s1 and s2.
71
72   [intersection(s1, s2)] returns the intersectionof s1 and s2.
73
74   [difference(s1, s2)] returns the difference between s1 and s2 (that
75   is, the set of elements in s1 but not in s2).
76
77   [listItems s] returns a list of the items in set s, in increasing
78   order.
79
80   [app f s] applies function f to the elements of s, in increasing
81   order.
82
83   [revapp f s] applies function f to the elements of s, in decreasing
84   order.
85
86   [foldl f e s] applies the folding function f to the entries of the
87   set in increasing order.
88
89   [foldr f e s] applies the folding function f to the entries of the
90   set in decreasing order.
91
92   [find p s] returns SOME i, where i is an item in s which satisfies
93   p, if one exists; otherwise returns NONE.
94*)
95