🥮 mooncakes.io

    #Immutable Map

    An immutable tree map based on size balanced tree.

    #Usage

    #Create

    You can create an empty map using new() or construct it with a single key-value pair using singleton().

    ///|
    test {
      let map1 : @sorted_map.SortedMap[String, Int] = @sorted_map.new()
      let map2 = @sorted_map.singleton("a", 1)
      @test.assert_eq(map1.length(), 0)
      @test.assert_eq(map2.length(), 1)
    }

    Also, you can construct it from an array using SortedMap([...]).

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      @test.assert_eq(map.values().collect(), [1, 2, 3])
      @test.assert_eq(map.keys_as_iter().collect(), ["a", "b", "c"])
    }

    #Insert & Lookup

    You can use add() to add a key-value pair to the map and create a new map. Or use get() to get the value associated with a key.

    ///|
    test {
      let map : @sorted_map.SortedMap[String, Int] = @sorted_map.new()
      let map = map.add("a", 1)
      @test.assert_eq(map.get("a"), Some(1))
    }

    #Remove

    You can use remove() to remove a key-value pair from the map.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let map = map.remove("a")
      @test.assert_eq(map.get("a"), None)
    }

    #Contains

    You can use contains() to check whether a key exists.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      @test.assert_eq(map.contains("a"), true)
      @test.assert_eq(map.contains("d"), false)
    }

    #Size

    You can use length() to get the number of key-value pairs in the map.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      @test.assert_eq(map.length(), 3)
    }

    Similarly, you can use is_empty() to check whether the map is empty.

    ///|
    test {
      let map : @sorted_map.SortedMap[String, Int] = @sorted_map.new()
      @test.assert_eq(map.is_empty(), true)
    }

    #Traversal

    Use each() or eachi() to iterate through all key-value pairs.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let arr = []
      map.each((k, v) => arr.push("key:\{k}, value:\{v}"))
      @test.assert_eq(arr, ["key:a, value:1", "key:b, value:2", "key:c, value:3"])
      let arr = []
      map.eachi((i, k, v) => arr.push("index:\{i}, key:\{k}, value:\{v}"))
      @test.assert_eq(arr, [
        "index:0, key:a, value:1", "index:1, key:b, value:2", "index:2, key:c, value:3",
      ])
    }

    Use map() to map a function over all key-value pairs.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let map = map.map((_, v) => v + 1)
      @test.assert_eq(map.values().collect(), [2, 3, 4])
      let map = map.map((_k, v) => v + 1)
      @test.assert_eq(map.values().collect(), [3, 4, 5])
    }

    Use fold() to fold over the key-value pairs of the map. The default order is ascending by key; use rev_fold() to fold in descending key order.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      @test.assert_eq(map.fold((acc, _, v) => acc + v, init=0), 6) // 6
      @test.assert_eq(
        map.fold((acc, k, v) => acc + k + v.to_string(), init=""),
        "a1b2c3",
      ) // "a1b2c3"
      @test.assert_eq(
        map.rev_fold((acc, k, v) => acc + k + v.to_string(), init=""),
        "c3b2a1",
      ) // "c3b2a1"
    }

    Use filter() to filter all key-value pairs that satisfy the predicate.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let map = map.filter((_, v) => v > 1)
      @test.assert_eq(map.values().collect(), [2, 3])
      @test.assert_eq(map.keys_as_iter().collect(), ["b", "c"])
      let map = map.filter((k, v) => k > "a" && v > 1)
      @test.assert_eq(map.values().collect(), [2, 3])
      @test.assert_eq(map.keys_as_iter().collect(), ["b", "c"])
    }

    #Conversion

    Use values() to get all values in ascending order of their keys.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let values = map.values()
      @test.assert_eq(values.collect(), [1, 2, 3])
    }

    Use keys_as_iter() to get all keys of the map in ascending order.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let keys = map.keys_as_iter() // ["a", "b", "c"]
      @test.assert_eq(keys.collect(), ["a", "b", "c"])
    }

    #Reverse Iteration

    Use rev_keys() to get all keys in descending order.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let keys = map.rev_keys().collect()
      @test.assert_eq(keys, ["c", "b", "a"])
    }

    Use rev_values() to get all values in descending order of their keys.

    ///|
    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let values = map.rev_values().collect()
      @test.assert_eq(values, [3, 2, 1])
    }

    SortedMap

    source
    type SortedMap[K, V]

    Immutable map, consists of key-value pairs.

    Example

    test {
      let map1 = @sorted_map.SortedMap([(3, "three"), (8, "eight"), (1, "one")])
      let map2 = map1.add(2, "two").remove(3)
      @test.assert_eq(map2.get(2), Some("two"))
      let map3 = map2.add(2, "updated")
      @test.assert_eq(map2.get(3), None)
      @test.assert_eq(map3.get(3), None)
      @test.assert_eq(map3.get(2), Some("updated"))
    }
    impl Compare for SortedMap[K, V]
    impl Default for SortedMap[K, V]
    impl Eq for SortedMap[K, V]
    impl Hash for SortedMap[K, V]
    impl Show for SortedMap[K, V]
    impl ToJson for SortedMap[K, V]
    impl Debug for SortedMap[K, V]

    SortedMap::SortedMap

    source
    fn[K : Compare + Eq, V] SortedMap::SortedMap(array : ArrayView[(K, V)]) -> SortedMap[K, V]

    Build a map from an array of key-value pairs. O(n) when the input is already monotonic by key, otherwise O(n*log n).

    Example

    test {
      let m = @sorted_map.SortedMap([(3, "c"), (1, "a"), (2, "b")])
      @test.assert_eq(m.get(1), Some("a"))
      @test.assert_eq(m.get(3), Some("c"))
    }

    SortedMap::add

    source
    #alias(insert, deprecated="`insert` is deprecated, use `add` instead")
    fn[K : Compare + Eq, V] SortedMap::add(self : SortedMap[K, V], key : K, value : V) -> SortedMap[K, V]

    Returns a new map with the key-value pair added or updated. O(log n).

    SortedMap::at

    source
    #alias("_[_]")
    fn[K : Compare + Eq, V] SortedMap::at(self : SortedMap[K, V], key : K) -> V

    Get the value associated with a key. Aborts if the key is not present; use get for the Option-returning version. O(log n).

    SortedMap::compare

    source
    fn[K : Compare + Eq, V : Compare + Eq] SortedMap::compare(self : SortedMap[K, V], other : SortedMap[K, V]) -> Int

    SortedMap::contains

    source
    fn[K : Compare + Eq, V] SortedMap::contains(self : SortedMap[K, V], key : K) -> Bool

    Check if the map contains a key. O(log n).

    SortedMap::each

    source
    fn[K, V] SortedMap::each(self : SortedMap[K, V], f : (K, V) -> Unit) -> Unit

    Iterate over the key-value pairs in the map.

    SortedMap::eachi

    source
    fn[K, V] SortedMap::eachi(self : SortedMap[K, V], f : (Int, K, V) -> Unit) -> Unit

    Iterate over the key-value pairs with index.

    SortedMap::elems

    source
    #deprecated("Use `values` instead")
    fn[K, V] SortedMap::elems(self : SortedMap[K, V]) -> Array[V]

    Function elems.

    SortedMap::equal

    source
    fn[K : Eq, V : Eq] SortedMap::equal(self : SortedMap[K, V], other : SortedMap[K, V]) -> Bool

    SortedMap::filter

    source
    #alias(filter_with_key, deprecated="`filter_with_key` is deprecated, use `filter` instead")
    fn[K, V] SortedMap::filter(self : SortedMap[K, V], pred : (K, V) -> Bool raise?) -> SortedMap[K, V] raise?

    Filter key-value pairs that satisfy the predicate

    SortedMap::fold

    source
    #alias(foldl_with_key, deprecated="`foldl_with_key` is deprecated, use `fold` instead")
    fn[K, V, A] SortedMap::fold(self : SortedMap[K, V], f : (A, K, V) -> A, init~ : A) -> A

    Fold over the key-value pairs in ascending key order. O(n).

    SortedMap::from_array

    source
    #deprecated("Use @immut/sorted_map.SortedMap([...]) instead")
    #as_free_fn(of, deprecated="Use @immut/sorted_map.SortedMap([...]) instead")
    #alias(of, deprecated="Use @immut/sorted_map.SortedMap([...]) instead")
    #as_free_fn(deprecated="Use @immut/sorted_map.SortedMap([...]) instead")
    fn[K : Compare + Eq, V] SortedMap::from_array(array : ArrayView[(K, V)]) -> SortedMap[K, V]

    Build a map from an array of key-value pairs. O(n) when the input is already monotonic by key, otherwise O(n*log n).

    SortedMap::from_iter

    source
    #as_free_fn(from_iterator, deprecated="Use SortedMap::from_iter instead.")
    #alias(from_iterator, deprecated="`from_iterator` is deprecated, use `from_iter` instead")
    #as_free_fn
    fn[K : Compare + Eq, V] SortedMap::from_iter(iter : Iter[(K, V)]) -> SortedMap[K, V]

    Creates a sorted map from an iterator of key-value pairs.

    SortedMap::from_json

    source

    Create from json.

    SortedMap::get

    source
    #alias(lookup, deprecated="`lookup` is deprecated, use `get` instead")
    fn[K : Compare + Eq, V] SortedMap::get(self : SortedMap[K, V], key : K) -> V?

    Get the value associated with a key. O(log n).

    SortedMap::hash

    source
    fn[K : Hash, V : Hash] SortedMap::hash(self : SortedMap[K, V]) -> Int

    SortedMap::is_empty

    source
    fn[K, V] SortedMap::is_empty(self : SortedMap[K, V]) -> Bool

    Return whether the value empty.

    SortedMap::iter

    source
    #alias(iterator, deprecated="`iterator` is deprecated, use `iter` instead")
    fn[K, V] SortedMap::iter(self : SortedMap[K, V]) -> Iter[(K, V)]

    Returns an iterator over key-value pairs in ascending key order.

    SortedMap::iter2

    source
    #alias(iterator2, deprecated="`iterator2` is deprecated, use `iter2` instead")
    fn[K, V] SortedMap::iter2(self : SortedMap[K, V]) -> Iter2[K, V]

    Returns a two-element iterator over key-value pairs in ascending key order.

    SortedMap::keys

    source
    #deprecated("Use `keys_as_iter` instead. `keys` will return `Iter[K]` instead of `Array[K]` in the future.")
    fn[K, V] SortedMap::keys(self : SortedMap[K, V]) -> Array[K]

    Return all keys of the map in ascending order.

    SortedMap::keys_as_iter

    source
    fn[K, V] SortedMap::keys_as_iter(self : SortedMap[K, V]) -> Iter[K]

    Return all keys of the map in ascending order.

    SortedMap::length

    source
    #alias(size, deprecated="`size` is deprecated, use `length` instead")
    fn[K, V] SortedMap::length(self : SortedMap[K, V]) -> Int

    Get the number of key-value pairs in the map.

    SortedMap::map

    source
    #alias(map_with_key, deprecated="`map_with_key` is deprecated, use `map` instead")
    fn[K, X, Y] SortedMap::map(self : SortedMap[K, X], f : (K, X) -> Y) -> SortedMap[K, Y]

    Maps over the key-value pairs in the map.

    SortedMap::merge

    source
    fn[K : Compare + Eq, V] SortedMap::merge(self : SortedMap[K, V], other : SortedMap[K, V]) -> SortedMap[K, V]

    Merges two immutable sorted maps into a new map. Returns a new map containing all key-value pairs from both maps. When both maps contain the same key, the value from other takes precedence.

    This is a pure operation - it returns a new sorted map without modifying either input.

    Parameters:

    • self : The first sorted map.
    • other : The second sorted map whose values take precedence in case of key conflicts.

    Returns a new immutable sorted map containing all entries from both maps.

    Example:

    test {
      let map1 = @sorted_map.SortedMap([(1, "a"), (2, "b")])
      let map2 = @sorted_map.SortedMap([(2, "c"), (3, "d")])
      let merged = map1.merge(map2)
      debug_inspect(merged.get(1), content="Some(\"a\")")
      debug_inspect(merged.get(2), content="Some(\"c\")")
      debug_inspect(merged.get(3), content="Some(\"d\")")
    }

    SortedMap::new

    source
    #alias(empty, deprecated="`empty` is deprecated, use `new` instead")
    #as_free_fn
    fn[K, V] SortedMap::new() -> SortedMap[K, V]

    Create an empty map.

    SortedMap::range

    source
    fn[K : Compare + Eq, V] SortedMap::range(self : SortedMap[K, V], low~ : K, high~ : K) -> Iter2[K, V]

    Returns an iterator over all key-value pairs in the map where keys fall within the inclusive range [low, high].

    The iterator yields key-value pairs in ascending key order. Keys equal to low or high are included if present.

    Arguments

    • low - The lower bound of the range (inclusive).
    • high - The upper bound of the range (inclusive).

    Returns

    An Iter2[K, V] that yields key-value pairs (key, value) where low <= key <= high.

    Performance

    Time complexity is O(log n + k) where n is the size of the map and k is the number of elements in the range. The algorithm efficiently prunes subtrees that fall entirely outside the range.

    Behavior

    • If low > high, the iterator yields no elements.
    • If the range contains no keys from the map, the iterator yields no elements.
    • The iterator is single-use; create a new one for multiple traversals.

    Example

    test {
      let map = @sorted_map.SortedMap([
        (1, "a"),
        (2, "b"),
        (3, "c"),
        (4, "d"),
        (5, "e"),
      ])
      let result = []
      for k, v in map.range(low=2, high=4) {
        result.push((k, v))
      }
      @test.assert_eq(result, [(2, "b"), (3, "c"), (4, "d")])
    }

    SortedMap::remove

    source
    fn[K : Compare + Eq, V] SortedMap::remove(self : SortedMap[K, V], key : K) -> SortedMap[K, V]

    Returns a new map with the given key removed. O(log n). If the key is not present, the original map is returned.

    SortedMap::rev_fold

    source
    #alias(foldr_with_key)
    fn[K, V, A] SortedMap::rev_fold(self : SortedMap[K, V], f : (A, K, V) -> A, init~ : A) -> A

    Fold over the key-value pairs in descending key order. O(n).

    SortedMap::rev_keys

    source
    fn[K, V] SortedMap::rev_keys(self : SortedMap[K, V]) -> Iter[K]

    Return all keys of the map in descending order.

    Example

    test {
      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let keys = map.rev_keys().collect()
      @test.assert_eq(keys, ["c", "b", "a"])
    }

    SortedMap::rev_values

    source
    fn[K, V] SortedMap::rev_values(self : SortedMap[K, V]) -> Iter[V]

    Return all values of the map in descending order of their keys.

    Example

      let map = @sorted_map.SortedMap([("a", 1), ("b", 2), ("c", 3)])
      let values = map.rev_values().collect()
      @test.assert_eq(values, [3, 2, 1])

    SortedMap::singleton

    source
    #as_free_fn
    fn[K, V] SortedMap::singleton(key : K, value : V) -> SortedMap[K, V]

    Create a map with a single key-value pair.

    SortedMap::to_array

    source
    fn[K, V] SortedMap::to_array(self : SortedMap[K, V]) -> Array[(K, V)]

    Returns an array of all key-value pairs in ascending key order.

    SortedMap::to_json

    source
    fn[K : Show, V : ToJson] SortedMap::to_json(self : SortedMap[K, V]) -> Json

    Convert to json.

    SortedMap::values

    source
    fn[K, V] SortedMap::values(self : SortedMap[K, V]) -> Iter[V]

    Return all elements of the map in the ascending order of their keys.

    Source Files

    Powered by MoonBit

    Site sourceReport issuePackagesBuild queueSkillsStatistics

    © 2026 mooncakes.io