SortedSet

SortedSet module: AVL tree-based sorted set.

Wraps OrderedMap with unit values for a pure set interface. Keys are ordered by a user-supplied comparator function: cmp(a, b) < 0 means a < b cmp(a, b) = 0 means a = b cmp(a, b) > 0 means a > b

Types

typeTreeTree(a) = Leaf | Node(Tree(a), a, Tree(a), Int)#

Functions

fnnewnew(cmp : (a, a) -> Int) : %{cmp: (a, a) -> Int, tree: Tree(a)}#

Creates a new empty sorted set with the given comparator.

fnaddadd(s : %{cmp: (a, a) -> Int, tree: Tree(a)}, v : a) : %{cmp: (a, a) -> Int, tree: Tree(a)}#

Adds element v to the set. No-op if already present.

fnremoveremove(s : %{cmp: (a, a) -> Int, tree: Tree(a)}, v : a) : %{cmp: (a, a) -> Int, tree: Tree(a)}#

Removes element v from the set. No-op if not present.

fnmembermember(s : %{cmp: (a, a) -> Int, tree: Tree(a)}, v : a) : Bool#

Returns true if v is in the set.

fnto_listto_list(s : %{cmp: (a, a) -> Int, tree: Tree(a)}) : List(a)#

Returns all elements in sorted order.

fnfrom_listfrom_list(items : List(a), cmp : (a, a) -> Int) : %{cmp: (a, a) -> Int, tree: Tree(a)}#

Builds a set from a list of elements.

fnsizesize(s : %{cmp: (a, a) -> Int, tree: Tree(a)}) : Int#

Returns the number of elements in the set.

fnminmin(s : %{cmp: (a, a) -> Int, tree: Tree(a)}) : Option(a)#

Returns the smallest element, or None if empty.

fnmaxmax(s : %{cmp: (a, a) -> Int, tree: Tree(a)}) : Option(a)#

Returns the largest element, or None if empty.

fnunionunion(a : %{cmp: (k, k) -> Int, tree: Tree(k)}, b : %{cmp: (k, k) -> Int, tree: Tree(k)}) : %{cmp: (k, k) -> Int, tree: Tree(k)}#

Returns a set containing all elements in either a or b.

fnintersectintersect(a : %{cmp: (k, k) -> Int, tree: Tree(k)}, b : %{cmp: (k, k) -> Int, tree: Tree(k)}) : %{cmp: (k, k) -> Int, tree: Tree(k)}#

Returns a set containing only elements in both a and b.

fndifferencedifference(a : %{cmp: (k, k) -> Int, tree: Tree(k)}, b : %{cmp: (k, k) -> Int, tree: Tree(k)}) : %{cmp: (k, k) -> Int, tree: Tree(k)}#

Returns a set of elements in a that are not in b.

fnfoldfold(s : %{cmp: (a, a) -> Int, tree: Tree(a)}, acc : b, f : (b, a) -> b) : b#

Folds over the set in sorted order: f(acc, element) -> acc.

fnis_emptyis_empty(s : %{cmp: (a, a) -> Int, tree: Tree(a)}) : Bool#

Returns true if the set is empty.

fnsubsetsubset(a : %{cmp: (k, k) -> Int, tree: Tree(k)}, b : %{cmp: (k, k) -> Int, tree: Tree(k)}) : Bool#

Returns true if a is a subset of b (every element of a is in b).