OrderedMap

OrderedMap module: AVL tree-based sorted map.

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 is a ready-made comparator for Int, String and other ordered values. Lookup, put and delete are O(log n); keys, values, to_list and fold visit entries in ascending key order.

The map itself is a record holding the comparator and the tree root. Type: {cmp: (k,k)->Int, tree: Tree(k,v)}

Types

typeTreeTree(k, v) = Leaf | Node(Tree(k, v), k, v, Tree(k, v), Int)#

Internal AVL tree: Leaf | Node(left, key, value, right, height)

Functions

fndeletedelete(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, k : k) : {cmp: k -> k -> Int, tree: Tree(k, v)}#

Deletes key k from map m. No-op if key not present. O(log n).

Examples

march> let m = OrderedMap.from_list([(3, "c"), (1, "a"), (2, "b")], compare)
march> OrderedMap.keys(OrderedMap.delete(m, 2))
[1, 3]
march> let m = OrderedMap.from_list([(3, "c"), (1, "a"), (2, "b")], compare)
march> OrderedMap.size(OrderedMap.delete(m, 9))
3

fnfilterfilter(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, f : k -> v -> Bool) : {cmp: k -> k -> Int, tree: Tree(k, v)}#

Returns a new map containing only entries where f(k, v) is true.

Examples

march> OrderedMap.to_list(OrderedMap.filter(OrderedMap.from_list([(1, "a"), (2, "b"), (3, "c")], compare), fn (k, v) -> k != 2))
[(1, "a"), (3, "c")]

fnfoldfold(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, acc : b, f : b -> k -> v -> b) : b#

Folds over the map in ascending key order: f(acc, key, value) -> acc.

Examples

march> OrderedMap.fold(OrderedMap.from_list([(2, "b"), (1, "a")], compare), "", fn (acc, k, v) -> acc ++ v)
"ab"

fnfrom_listfrom_list(pairs : List((k, v)), cmp : k -> k -> Int) : {cmp: k -> k -> Int, tree: Tree(k, v)}#

Builds a map from a list of (key, value) pairs. Later pairs overwrite earlier ones with an equal key. O(n log n).

Examples

march> OrderedMap.to_list(OrderedMap.from_list([(2, "b"), (1, "a"), (2, "z")], compare))
[(1, "a"), (2, "z")]

fngetget(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, k : k) : Option(v)#

Looks up key k in map m. Returns Some(v) or None. O(log n).

Examples

march> let m = OrderedMap.from_list([(3, "c"), (1, "a"), (2, "b")], compare)
march> OrderedMap.get(m, 2)
Some("b")
march> let m = OrderedMap.from_list([(3, "c"), (1, "a"), (2, "b")], compare)
march> OrderedMap.get(m, 9)
None

fnget_orget_or(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, k : k, default : v) : v#

Returns the value for key k, or default if not present.

Examples

march> OrderedMap.get_or(OrderedMap.from_list([(1, "a")], compare), 1, "?")
"a"
march> OrderedMap.get_or(OrderedMap.from_list([(1, "a")], compare), 5, "?")
"?"

fnis_emptyis_empty(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Bool#

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

Examples

march> OrderedMap.is_empty(OrderedMap.delete(OrderedMap.from_list([(1, "a")], compare), 1))
true
march> OrderedMap.is_empty(OrderedMap.from_list([(1, "a")], compare))
false

fnkeyskeys(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : List(k)#

Returns all keys in ascending order.

Examples

march> OrderedMap.keys(OrderedMap.from_list([("b", 2), ("a", 1)], compare))
["a", "b"]

fnmapmap(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, f : k -> v -> w) : {cmp: k -> k -> Int, tree: Tree(k, w)}#

Maps f over all values, preserving keys and order. f receives both the key and the value: f(key, value) -> new_value.

Examples

march> OrderedMap.to_list(OrderedMap.map(OrderedMap.from_list([(1, 10), (2, 20)], compare), fn (k, v) -> k + v))
[(1, 11), (2, 22)]

fnmax_keymax_key(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Option(k)#

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

Examples

march> OrderedMap.max_key(OrderedMap.from_list([(3, "c"), (1, "a")], compare))
Some(3)
march> OrderedMap.max_key(OrderedMap.new(compare))
None

fnmembermember(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, k : k) : Bool#

Returns true if key k is present in map m.

Examples

march> OrderedMap.member(OrderedMap.from_list([("a", 1)], compare), "a")
true
march> OrderedMap.member(OrderedMap.new(compare), "a")
false

fnmin_keymin_key(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Option(k)#

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

Examples

march> OrderedMap.min_key(OrderedMap.from_list([(3, "c"), (1, "a")], compare))
Some(1)
march> OrderedMap.min_key(OrderedMap.new(compare))
None

fnnewnew(cmp : k -> k -> Int) : {cmp: k -> k -> Int, tree: Tree(k, v)}#

Creates a new empty ordered map with the given comparator (cmp(a, b) negative, zero or positive as a is less than, equal to or greater than b).

Examples

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

fnputput(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, k : k, v : v) : {cmp: k -> k -> Int, tree: Tree(k, v)}#

Inserts or updates key k with value v in map m. A key that compares equal to an existing one replaces both its key and its value. O(log n).

Examples

march> OrderedMap.to_list(OrderedMap.put(OrderedMap.put(OrderedMap.new(compare), 2, "b"), 1, "a"))
[(1, "a"), (2, "b")]
march> OrderedMap.get(OrderedMap.put(OrderedMap.from_list([(1, "a")], compare), 1, "z"), 1)
Some("z")

fnsizesize(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Int#

Returns the number of entries in the map. O(n): the count is not cached.

Examples

march> OrderedMap.size(OrderedMap.from_list([(1, "a"), (2, "b"), (1, "c")], compare))
2

fnto_listto_list(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : List((k, v))#

Returns all (key, value) pairs in ascending key order.

Examples

march> OrderedMap.to_list(OrderedMap.from_list([(3, "c"), (1, "a")], compare))
[(1, "a"), (3, "c")]
march> OrderedMap.to_list(OrderedMap.new(compare))
[]

fnvaluesvalues(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : List(v)#

Returns all values, in ascending order of their keys.

Examples

march> OrderedMap.values(OrderedMap.from_list([("b", 2), ("a", 1)], compare))
[1, 2]