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 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)# 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.
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.
fnfoldfold(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, acc : b, f : b -> k -> v -> b) : b# Folds over the map in key order: f(acc, key, value) -> acc.
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.
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.
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.
fnis_emptyis_empty(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Bool# Returns true if the map is empty.
fnkeyskeys(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : List(k)# Returns an in-order list of all keys.
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.
fnmax_keymax_key(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Option(k)# Returns the largest key, or None if empty.
fnmembermember(m : {cmp: k -> k -> Int, tree: Tree(k, v)}, k : k) : Bool# Returns true if key k is present in map m.
fnmin_keymin_key(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Option(k)# Returns the smallest key, or None if empty.
fnnewnew(cmp : k -> k -> Int) : {cmp: k -> k -> Int, tree: Tree(k, v)}# Creates a new empty ordered map with the given comparator.
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.
fnsizesize(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : Int# Returns the number of entries in the map.
fnto_listto_list(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : List((k, v))# Returns an in-order list of (key, value) pairs.
fnvaluesvalues(m : {cmp: k -> k -> Int, tree: Tree(k, v)}) : List(v)# Returns an in-order list of all values.