138494Sobrien(* Redblackset -- sets implemented by Red-Black trees *) 2310490Scysignature Redblackset = 338494Sobriensig 438494Sobrientype 'item set 538494Sobrien 638494Sobrienexception NotFound 738494Sobrien 838494Sobrienval empty : ('item * 'item -> order) -> 'item set 938494Sobrienval singleton : ('item * 'item -> order) -> 'item -> 'item set 1038494Sobrienval fromList : ('item * 'item -> order) -> 'item list -> 'item set 1138494Sobrienval add : 'item set * 'item -> 'item set 1238494Sobrienval addList : 'item set * 'item list -> 'item set 1338494Sobrienval retrieve : 'item set * 'item -> 'item 1438494Sobrienval peek : 'item set * 'item -> 'item option 1538494Sobrienval isEmpty : 'item set -> bool 1638494Sobrienval equal : 'item set * 'item set -> bool 1738494Sobrienval isSubset : 'item set * 'item set -> bool 1838494Sobrienval member : 'item set * 'item -> bool 19310490Scyval delete : 'item set * 'item -> 'item set 2038494Sobrienval numItems : 'item set -> int 2138494Sobrienval union : 'item set * 'item set -> 'item set 2238494Sobrienval intersection : 'item set * 'item set -> 'item set 2338494Sobrienval difference : 'item set * 'item set -> 'item set 2438494Sobrienval listItems : 'item set -> 'item list 2538494Sobrienval app : ('item -> unit) -> 'item set -> unit 2638494Sobrienval revapp : ('item -> unit) -> 'item set -> unit 2738494Sobrienval foldr : ('item * 'b -> 'b) -> 'b -> 'item set -> 'b 2838494Sobrienval foldl : ('item * 'b -> 'b) -> 'b -> 'item set -> 'b 2938494Sobrienval find : ('item -> bool) -> 'item set -> 'item option 3038494Sobrienval filter : ('item -> bool) -> 'item set -> 'item set 3138494Sobrien 3238494Sobrienend 3338494Sobrien 3438494Sobrien(* 3538494Sobrien ['item set] is the type of sets of ordered elements of type 'item. 36310490Scy The ordering relation on the elements is used in the representation 3751300Sobrien of the set. The result of combining two sets with different 3838494Sobrien underlying ordering relations is undefined. The implementation 39174297Sobrien uses Okasaki-style Red-Black trees. 4039087Sobrien 4139087Sobrien [empty ordr] creates a new empty set with the given ordering 4239087Sobrien relation. 4339087Sobrien 4439087Sobrien [singleton ordr i] creates the singleton set containing i, with the 4539087Sobrien given ordering relation. 4639087Sobrien 4739087Sobrien [fromList ordr xs] creates the set containing all items from the 4839087Sobrien list xs, with the given ordering relation. It is equivalent to 49174415Sru addList (empty ordr, xs). 5039087Sobrien 51174415Sru [add(s, i)] adds item i to set s. 5239087Sobrien 53174415Sru [addList(s, xs)] adds all items from the list xs to the set s. 54147439Sru 5539087Sobrien [retrieve(s, i)] returns i if it is in s; raises NotFound otherwise. 5638494Sobrien 5739087Sobrien [peek(s, i)] returns SOME i if i is in s; returns NONE otherwise. 58147439Sru 59147439Sru [isEmpty s] returns true if and only if the set is empty. 60147439Sru 6138494Sobrien [equal(s1, s2)] returns true if and only if the two sets have the 6239087Sobrien same elements. 63174415Sru 64174415Sru [isSubset(s1, s2)] returns true if and only if s1 is a subset of s2. 6538494Sobrien 6639087Sobrien [member(s, i)] returns true if and only if i is in s. 6738494Sobrien 6839087Sobrien [delete(s, i)] removes item i from s. Raises NotFound if i is not in s. 6938494Sobrien 7039087Sobrien [numItems s] returns the number of items in set s. 7138494Sobrien 7238494Sobrien [union(s1, s2)] returns the union of s1 and s2. 7338494Sobrien 7439087Sobrien [intersection(s1, s2)] returns the intersection of s1 and s2. 7539087Sobrien 76147439Sru [difference(s1, s2)] returns the difference between s1 and s2 (that 77147439Sru is, the set of elements in s1 but not in s2). 7839087Sobrien 7938494Sobrien [listItems s] returns a list of the items in set s, in increasing 80147439Sru order. 81147439Sru 8239087Sobrien [app f s] applies function f to the elements of s, in increasing 8339087Sobrien order. 8439087Sobrien 85147439Sru [revapp f s] applies function f to the elements of s, in decreasing 86174415Sru order. 87174415Sru 88174415Sru [foldl f e s] applies the folding function f to the entries of the 89157828Sdelphij set in increasing order. 90147439Sru 91147439Sru [foldr f e s] applies the folding function f to the entries of the 92174415Sru set in decreasing order. 9339087Sobrien 94174415Sru [find p s] returns SOME i, where i is an item in s which satisfies 9539087Sobrien p, if one exists; otherwise returns NONE. Traverses the entries of 9638494Sobrien the set in increasing order. 9739087Sobrien*) 9838494Sobrien