alice
library
manual.
signature IMP_SET
functor MkHashImpSet (Item : HASHABLE) :> IMP_SET where type item = Item.t
functor MkRedBlackImpSet (Item : ORDERED) :> IMP_SET where type item = Item.t
The SET signature provides an imperative interface to finite sets. The MkHashImpSet functor provides an implementation of this interface based on hash tables, while the MkRedBlackImpSet functor provides an implementation based on red-black trees.
Note that imperative sets are not thread-safe. Explicit locking has to be used if they need to be accessed concurrently. Also note that the behaviour of iterator functionals is unspecified if the passed argument function tries to modify the set.
See also: SET, IMP_MAP, HASHABLE, ORDERED
import signature IMP_SET from "x-alice:/lib/data/IMP_SET-sig"
import functor MkHashImpSet from "x-alice:/lib/data/MkHashImpSet"
import functor MkRedBlackImpSet from "x-alice:/lib/data/MkRedBlackImpSet"
signature IMP_SET =
sig
type item
eqtype set
type t = set
exception Unknown of item
exception Collision of item
val set : unit -> set
val clone : set -> set
val fromList : item list -> set
val fromVector : item vector -> set
val toList : set -> item list
val toVector : set -> item vector
val insert : set * item -> unit
val insertDisjoint : set * item -> unit
val insertWith : (item -> unit) -> set * item -> unit
val remove : set * item -> unit
val removeExistent : set * item -> unit
val removeWith : (item -> unit) -> set * item -> unit
val removeAll : set -> unit
val union : set * set -> unit
val unionDisjoint : set * set -> unit
val unionWith : (item -> unit) -> set * set -> unit
val intersect : set * set -> unit
val difference : set * set -> unit
val size : set -> int
val isEmpty : set -> bool
val member : set * item -> bool
val choose : set -> item option
val equal : set * set -> bool
val subset : set * set -> bool
val disjoint : set * set -> bool
val compare : set * set -> order
val app : (item -> unit) -> set -> unit
val fold : (item * 'a -> 'a) -> 'a -> set -> 'a
val all : (item -> bool) -> set -> bool
val exists : (item -> bool) -> set -> bool
val find : (item -> bool) -> set -> item option
val filter : (item -> bool) -> set -> unit
end
The type of elements in the set.
The type of sets over elements of type item. Only sets created by the same function application are equal.
Indicates that an item could not be found in the set.
Indicates an attempt to add an item that already is in the set when using functions that disallow replacement.
Creates an empty set.
Creates a copy of the set s.
Creates a set containing the elements from list l. Raises Collision x if x is an element in the list that is followed by at least one other element equal to x.
Creates a set containing the elements from list v. Raises Collision x if x is an element of the vector that is followed by at least one other element equal to x. Equivalent to fromList(Vector.toList v).
Returns the list of items in the set s. For red-black sets, the items are delivered in increasing order.
Returns the vector of items in the set s. For red-black sets, the items are delivered in increasing order. Equivalent to Vector.fromList(toList s).
Extends the set s with element x. In the first form, if s already contains an element y equal to x, then it gets replaced by x. In the second form, Collision y will be raised. In the third form, f is applied to y before the set is modified. The following equivalences hold:
insert = insertWith ignore
insertDisjoint = insertWith (fn y => raise Collision y)
Removes the element x from the set s. In the first form, if no element equal to x is contained in s, then the set is left unchanged. In the second form, Unknown x will be raised. In the third form, f is applied to x before the set is modified. The following equivalences hold:
remove = removeWith ignore
removeExistent = removeWith (fn y => raise Unknown y)
Removes all elements from the set s.
Inserts all elements from set s2 into s1. In the first form, if s2 contains an element x2 equal to an element x1 in set s1, then it will get replaced by x2. In the second form, Collision x2 will be raised. In the third form, f is applied to x2 before the set is modified as in the first form. The following equivalences hold:
union = unionWith ignore
unionDisjoint = unionWith (fn y => raise Collision y)
Removes all elements from set s1 that are not contained in s2.
Removes all elements from set s1 that are contained in s2.
Returns the cardinality of the set s, i.e. the number of elements it contains.
Returns true if s is an empty set, false otherwise. Equivalent to size s = 0.
Returns true if the set s contains an element equal to x, false otherwise.
Returns SOME x, where x is an element of the set s. Returns NONE if s is empty. For red-black sets, x will be the smallest element in the set.
Returns true if s1 and s2 are sets with equal elements, false otherwise.
Returns true if s1 is a subset of s2, false otherwise.
Returns true if s1 and s2 are disjoint sets, false otherwise.
Returns EQUAL if s1 and s2 are equal sets, LESS if s1 is a subset of s2, and GREATER if s2 is a subset of s1. Otherwise it raises Unordered.
Applies f to each element in set s. For red-black trees, this happens in increasing order. Equivalent to List.app f (toList s).
Sequentially applies f to the pair of a set item and the result of the previous application, starting with initial value a. For red-black trees, folding is performed in increasing order. Equivalent to List.foldl f a (toList s).
Applies f to each element x of set s until f x delivers false. Returns false if such an x exists, true otherwise. For red-black trees, f is applied in increasing order. Equivalent to List.all f (toList s).
Applies f to each element x of set s until f x delivers true. Returns true if such an x exists, false otherwise. For red-black trees, f is applied in increasing order. Equivalent to List.exists f (toList s).
Applies f to each element x of set s until f x delivers true. Returns SOME x if such an x exists, NONE otherwise. For red-black trees, f is applied in increasing order. Equivalent to List.find f (toList s).
Applies f to each element x of set s and removes all elements for which f x delivered false. For red-black trees, f is applied in increasing order.