SET

template <typename T> pure Set<T> set(void);
template <typename T> pure Set<T> set(List<T> xs);
template <typename T> pure bool empty(Set<T> xs);
template <typename T> pure bool find(Set<T> s, const T &k);
template <typename T> pure Set<T> insert(Set<T> s, const T &k);
template <typename T> pure Set<T> erase(Set<T> s, const T &k);
template <typename T> pure Set<T> merge(Set<T> s, Set<T> t);
template <typename T> pure Set<T> intersect(Set<T> s, Set<T> t);
template <typename T> pure Set<T> diff(Set<T> s, Set<T> t);
template <typename T> pure size_t size(Set<T> s);
template <typename T, typename A, typename F> pure A foldl(Set<T> s, const A &arg, F func);
template <typename T, typename A, typename F> pure A foldr(Set<T> s, const A &arg, F func);
template <typename T> pure int compare(Set<T> s, Set<T> t);
template <typename T> pure String show(Set<T> s);
template <typename T> pure SetItr<T> begin(Set<T> s);
template <typename T> pure SetItr<T> end(Set<T> s);
template <typename T> SetItr<T> &operator++(SetItr<T> &i);
template <typename T> SetItr<T> &operator--(SetItr<T> &i);
template <typename T> SetItr<T> &operator+(SetItr<T> &i, ssize_t offset);
template <typename T> SetItr<T> &operator-(SetItr<T> &i, ssize_t offset);
template <typename T> SetItr<T> &operator+=(SetItr<T> &i, ssize_t offset);
template <typename T> SetItr<T> &operator-=(SetItr<T> &i, ssize_t offset);
template <typename T> pure const T &operator*(SetItr<T> &i);
template <typename T> pure bool verify(Set<T> s);
template <typename T> pure bool operator==(const SetItr<T> &i, const SetItr<T> &j);
template <typename T> pure bool operator!=(const SetItr<T> &i, const SetItr<T> &j);

template <typename T>
pure Set<T> set(void)

Construct the empty set. O(1).

template <typename T>
pure Set<T> set(List<T> xs)

Construct a set from a list. O(n * log(n)).

template <typename T>
pure bool empty(Set<T> xs)

Test if a set is empty. O(1).

template <typename T>
pure bool find(Set<T> s, const T &k)

Test if an element is a member of a set. O(log(n)).

template <typename T>
pure Set<T> insert(Set<T> s, const T &k)

Set insert. O(log(n)).

template <typename T>
pure Set<T> erase(Set<T> s, const T &k)

Set remove. O(log(n)).

template <typename T>
pure Set<T> merge(Set<T> s, Set<T> t)

Set union (merge). O(log(n) + log(m)).

template <typename T>
pure Set<T> intersect(Set<T> s, Set<T> t)

Set intersect. O(log(n) + log(m)).

template <typename T>
pure Set<T> diff(Set<T> s, Set<T> t)

Set difference. O(log(n) + log(m)).

template <typename T>
pure size_t size(Set<T> s)

Set size. O(n).

template <typename T, typename A, typename F>
pure A foldl(Set<T> s, const A &arg, F func)

Set fold left. ([](A a, T x) -> A). O(n).

template <typename T, typename A, typename F>
pure A foldr(Set<T> s, const A &arg, F func)

Set fold right. ([](A a, T x) -> A). O(n).

template <typename T>
pure int compare(Set<T> s, Set<T> t)

Set compare. O(n).

template <typename T>
pure String show(Set<T> s)

Set show. O(n).

template <typename T>
pure SetItr<T> begin(Set<T> s)

Construct an iterator pointing to the least element of a set. O(1).

template <typename T>
pure SetItr<T> end(Set<T> s)

Construct an iterator representing one past the greatest element of a set. O(1).

template <typename T>
SetItr<T> &operator++(SetItr<T> &i)

Set iterator increment. O(1).

template <typename T>
SetItr<T> &operator--(SetItr<T> &i)

Set iterator decrement. O(1).

template <typename T>
SetItr<T> &operator+(SetItr<T> &i, ssize_t offset)

Set iterator add offset. O(1).

template <typename T>
SetItr<T> &operator-(SetItr<T> &i, ssize_t offset)

Set iterator substract offset. O(1).

template <typename T>
SetItr<T> &operator+=(SetItr<T> &i, ssize_t offset)

Set iterator add offset. O(1).

template <typename T>
SetItr<T> &operator-=(SetItr<T> &i, ssize_t offset)

Set iterator substract offset. O(1).

template <typename T>
pure const T &operator*(SetItr<T> &i)

Set iterator dereference. O(log(delta)), where delta is distance to last dereference.

template <typename T>
pure bool verify(Set<T> s)

Set verify. O(n).

template <typename T>
pure bool operator==(const SetItr<T> &i, const SetItr<T> &j)

Set iterator same offset. O(1).

template <typename T>
pure bool operator!=(const SetItr<T> &i, const SetItr<T> &j)

Set iterator different offset. O(1).