SortedSet

SortedSet module: AVL tree-based sorted set.

Same AVL design as OrderedMap, storing elements only (its own tree type, not an OrderedMap underneath). 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 The built-in compare works for Int, String and other ordered values. add / remove / member are O(log n); to_list and fold run in ascending order. Binary operations (union, intersect, difference, subset) use each argument's own comparator for its own tree; the result of union, intersect and difference keeps a's comparator.

Types

typeAvlTreeAvlTree(a) = AvlLeaf | AvlNode(AvlTree(a), a, AvlTree(a), Int)#

Internal AVL tree (same as OrderedMap, keyed by element, value: unit). Named apart from OrderedMap's Tree/Leaf/Node: the refinement checker does not qualify datatype or constructor names by module, and the proofs below need this tree's constructors to be its own.

Functions

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

Adds element v to the set. No-op if already present. O(log n).

Examples

march> SortedSet.to_list(SortedSet.add(SortedSet.from_list([3, 1], compare), 2))
[1, 2, 3]
march> SortedSet.size(SortedSet.add(SortedSet.from_list([1], compare), 1))
1

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

Returns a set of elements in a that are not in b (removes each element of b from a; the result keeps a's comparator).

Examples

march> SortedSet.to_list(SortedSet.difference(SortedSet.from_list([1, 2, 3], compare), SortedSet.from_list([2, 9], compare)))
[1, 3]

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

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

Examples

march> SortedSet.fold(SortedSet.from_list([3, 1, 2], compare), 0, fn (acc, x) -> acc * 10 + x)
123

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

Builds a set from a list of elements; duplicates are kept once. O(n log n).

Examples

march> SortedSet.to_list(SortedSet.from_list([3, 1, 2, 3, 1], compare))
[1, 2, 3]

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

Returns a set containing only elements in both a and b (the result keeps a's comparator).

Examples

march> SortedSet.to_list(SortedSet.intersect(SortedSet.from_list([1, 2, 3], compare), SortedSet.from_list([2, 3, 4], compare)))
[2, 3]
march> SortedSet.is_empty(SortedSet.intersect(SortedSet.from_list([1], compare), SortedSet.from_list([2], compare)))
true

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

Returns true if the set is empty. O(1).

Examples

march> SortedSet.is_empty(SortedSet.remove(SortedSet.from_list([1], compare), 1))
true
march> SortedSet.is_empty(SortedSet.from_list([1], compare))
false

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

Returns the largest element, or None if empty. O(log n).

Examples

march> SortedSet.max(SortedSet.from_list([3, 1, 2], compare))
Some(3)
march> SortedSet.max(SortedSet.new(compare))
None

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

Returns true if v is in the set. O(log n).

Examples

march> SortedSet.member(SortedSet.from_list(["a", "b"], compare), "b")
true
march> SortedSet.member(SortedSet.from_list(["a", "b"], compare), "c")
false

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

Returns the smallest element, or None if empty. O(log n).

Examples

march> SortedSet.min(SortedSet.from_list([3, 1, 2], compare))
Some(1)
march> SortedSet.min(SortedSet.new(compare))
None

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

Creates a new empty sorted set with the given comparator.

Examples

march> SortedSet.is_empty(SortedSet.new(compare))
true

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

Removes element v from the set. No-op if not present. O(log n).

Examples

march> SortedSet.to_list(SortedSet.remove(SortedSet.from_list([1, 2, 3], compare), 2))
[1, 3]
march> SortedSet.to_list(SortedSet.remove(SortedSet.from_list([1, 2, 3], compare), 9))
[1, 2, 3]

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

Returns the number of elements in the set. O(n): the count is not cached.

Examples

march> SortedSet.size(SortedSet.from_list([5, 5, 6], compare))
2

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

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

Examples

march> SortedSet.subset(SortedSet.from_list([1, 3], compare), SortedSet.from_list([1, 2, 3], compare))
true
march> SortedSet.subset(SortedSet.from_list([1, 4], compare), SortedSet.from_list([1, 2, 3], compare))
false
march> SortedSet.subset(SortedSet.new(compare), SortedSet.from_list([1], compare))
true

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

Returns all elements in ascending order.

Examples

march> SortedSet.to_list(SortedSet.from_list(["pear", "apple", "fig"], compare))
["apple", "fig", "pear"]
march> SortedSet.to_list(SortedSet.new(compare))
[]

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

Returns a set containing all elements in either a or b (adds each element of b to a; the result keeps a's comparator).

Examples

march> SortedSet.to_list(SortedSet.union(SortedSet.from_list([1, 3], compare), SortedSet.from_list([2, 3], compare)))
[1, 2, 3]