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
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.
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.
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.
fnmembermember(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}, k : k) : Bool# Returns true if key k is present in map m.
fnkeyskeys(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : List(k)# Returns an in-order list of all keys.
fnvaluesvalues(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : List(v)# Returns an in-order list of all values.
fnto_listto_list(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : List((k, v))# Returns an in-order list of (key, value) pairs.
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.
fnsizesize(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : Int# Returns the number of entries in the map.
fnmin_keymin_key(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : Option(k)# Returns the smallest key, or None if empty.
fnmax_keymax_key(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : Option(k)# Returns the largest key, or None if empty.
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.
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.
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.
fnis_emptyis_empty(m : %{cmp: (k, k) -> Int, tree: Tree(k, v)}) : Bool# Returns true if the map is empty.
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.