TrieSet
Sets are partial maps from element type to unit type, i.e., the partial map represents the set with its domain.
This data structure allows at most MAX_LEAF_SIZE = 8 hash collisions.
Attempts to insert more than 8 elements with the same hash value—either directly via put or indirectly via other operations—will trap.
This limitation is inherited from the underlying Trie data structure.
Type Hash
type Hash = Hash.Hash
Type Set
type Set<T> = Trie.Trie<T, ()>
Function empty
func empty<T>() : Set<T>
Empty set.
Function put
func put<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Set<T>
Put an element into the set.
Function delete
func delete<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Set<T>
Delete an element from the set.
Function equal
func equal<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Bool
Test if two sets are equal.
Function size
func size<T>(s : Set<T>) : Nat
The number of set elements, set's cardinality.
Function isEmpty
func isEmpty<T>(s : Set<T>) : Bool
Test if s is the empty set.
Function isSubset
func isSubset<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Bool
Test if s1 is a subset of s2.
Function mem
func mem<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Bool
Use TrieSet.contains() instead.
Test if a set contains a given element.
Function contains
func contains<T>(s : Set<T>, x : T, xh : Hash, eq : (T, T) -> Bool) : Bool
Test if a set contains a given element.
Function union
func union<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Set<T>
Function diff
func diff<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Set<T>
Function intersect
func intersect<T>(s1 : Set<T>, s2 : Set<T>, eq : (T, T) -> Bool) : Set<T>
Function fromArray
func fromArray<T>(arr : [T], elemHash : T -> Hash, eq : (T, T) -> Bool) : Set<T>
Construct a set from an array.
Function toArray
func toArray<T>(s : Set<T>) : [T]
Returns the set as an array.