module std.set

This module provides ordered persistent sets. Sets are isomorphic to maps with no values, but the implementations of maps and sets in Spiral use completely different data structures, so sets have some extra operations (notably indexing). A set also needs a comparator, as described in module std.map.

• (set-new cmp) creates an empty set with comparator cmp.

• (set-empty? s) decides in time O(1) whether the set s is empty.

• (set-len s) returns the number of elements in set s. This takes time O(1).

• (set-contains? s key) returns true if the set s contains key, with time complexity O(log n).

• (set-insert s key) returns a set that contains all keys from set s with the key key in time O(log n).

• (set-remove s key) returns a set that contains all keys from set s except key in time O(log n).

• (set-to-list s) returns an ordered list of all keys from set s. This operation takes O(n) time.

• (set-from-list cmp keys) creates a new set with comparator cmp containing all keys in O(n log n).

• (set-find-index s key) returns the index of key in the set s or false if the key is not contained in s.

• (set-get-index s idx) returns the key at index idx in set s or panics when the index is out of range.

• (set-remove-index s idx) returns set s without the key at index idx or panics if the index is out of range.