🥮 mooncakes.io
README

#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 of() or from_array().

///|
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 lookup() 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 size() 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 Pre-order; use rev_fold() for a Post-order fold.

///|
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() 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*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. 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

Pre-order fold. 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*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

Post-order fold. 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