🥮 mooncakes.io
README

#Sorted Map

A mutable map backed by an AVL tree that maintains keys in sorted order.

#Overview

SortedMap is an ordered map implementation that keeps entries sorted by keys. It provides efficient lookup, insertion, and deletion operations, with stable traversal order based on key comparison.

#Performance

  • add/set: O(log n)
  • remove: O(log n)
  • get/contains: O(log n)
  • iterate: O(n)
  • range: O(log n + k) where k is number of elements in range
  • space complexity: O(n)

#Usage

#Create

You can create an empty SortedMap or a SortedMap from other containers.

///|
test {
  let _map1 : @sorted_map.SortedMap[Int, String] = SortedMap([])
  let _map2 = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
}

#Container Operations

Add a key-value pair to the SortedMap in place.

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two")])
  map.set(3, "three")
  @test.assert_eq(map.length(), 3)
}

You can also use the convenient subscript syntax to add or update values:

///|
test {
  let map = @sorted_map.SortedMap([])
  map[1] = "one"
  map[2] = "two"
  @test.assert_eq(map.length(), 2)
}

Remove a key-value pair from the SortedMap in place.

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
  map.remove(2)
  @test.assert_eq(map.length(), 2)
  @test.assert_eq(map.contains(2), false)
}

Get a value by its key. The return type is Option[V].

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
  assert_true(map.get(2) == Some("two"))
  assert_true(map.get(4) == None)
}

Safe access with error handling:

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two")])
  let key = 3
  debug_inspect(map.get(key), content="None")
}

Check if a key exists in the map.

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
  @test.assert_eq(map.contains(2), true)
  @test.assert_eq(map.contains(4), false)
}

Iterate over all key-value pairs in the map in sorted key order.

///|
test {
  let map = @sorted_map.from_array([(3, "three"), (1, "one"), (2, "two")])
  let keys = []
  let values = []
  map.each((k, v) => {
    keys.push(k)
    values.push(v)
  })
  @debug.assert_eq(keys, [1, 2, 3])
  @debug.assert_eq(values, ["one", "two", "three"])
}

Iterate with index:

///|
test {
  let map = @sorted_map.from_array([(3, "three"), (1, "one"), (2, "two")])
  let result = []
  map.eachi((i, k, v) => result.push((i, k, v)))
  @debug.assert_eq(result, [(0, 1, "one"), (1, 2, "two"), (2, 3, "three")])
}

Get the size of the map.

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
  @test.assert_eq(map.length(), 3)
}

Check if the map is empty.

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

Clear the map.

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
  map.clear()
  @test.assert_eq(map.is_empty(), true)
}

#Data Extraction

Get all keys or values from the map.

///|
test {
  let map = @sorted_map.from_array([(3, "three"), (1, "one"), (2, "two")])
  @debug.assert_eq(map.keys().collect(), [1, 2, 3])
  @debug.assert_eq(map.values().collect(), ["one", "two", "three"])
}

Convert the map to an array of key-value pairs.

///|
test {
  let map = @sorted_map.from_array([(3, "three"), (1, "one"), (2, "two")])
  @debug.assert_eq(map.to_array(), [(1, "one"), (2, "two"), (3, "three")])
}

#Range Operations

Get a subset of the map within a specified range of keys. The range is inclusive for both bounds [low, high].

///|
test {
  let map = @sorted_map.from_array([
    (1, "one"),
    (2, "two"),
    (3, "three"),
    (4, "four"),
    (5, "five"),
  ])
  let range_items = []
  map.range(2, 4).each((k, v) => range_items.push((k, v)))
  @debug.assert_eq(range_items, [(2, "two"), (3, "three"), (4, "four")])
}

Edge cases for range operations:
  • If low > high, returns an empty result
  • If low or high are outside the map bounds, returns only pairs within valid bounds
  • The returned iterator preserves the sorted order of keys

///|
///  Example with out-of-bounds range
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two"), (3, "three")])
  let range_items = []
  map.range(0, 10).each((k, v) => range_items.push((k, v)))
  @debug.assert_eq(range_items, [(1, "one"), (2, "two"), (3, "three")])

  // Example with invalid range
  let empty_range : Array[(Int, String)] = []
  map.range(10, 5).each((k, v) => empty_range.push((k, v)))
  @debug.assert_eq(empty_range, [])
}

#Iterators

The SortedMap supports several iterator patterns. Create a map from an iterator:

///|
test {
  let pairs = [(1, "one"), (2, "two"), (3, "three")].iter()
  let map = @sorted_map.from_iter(pairs)
  @test.assert_eq(map.length(), 3)
}

Use the iter method to get an iterator over key-value pairs:

///|
test {
  let map = @sorted_map.from_array([(3, "three"), (1, "one"), (2, "two")])
  let pairs = map.iter().to_array()
  @debug.assert_eq(pairs, [(1, "one"), (2, "two"), (3, "three")])
}

Use the iter2 method for a more convenient key-value iteration:

///|
test {
  let map = @sorted_map.from_array([(3, "three"), (1, "one"), (2, "two")])
  let transformed = []
  map.iter2().each((k, v) => transformed.push(k.to_string() + ": " + v))
  @debug.assert_eq(transformed, ["1: one", "2: two", "3: three"])
}

#Equality

Maps with the same key-value pairs are considered equal, regardless of the order in which elements were added.

///|
test {
  let map1 = @sorted_map.from_array([(1, "one"), (2, "two")])
  let map2 = @sorted_map.from_array([(2, "two"), (1, "one")])
  @test.assert_eq(map1 == map2, true)
}

#Index Access

Use subscript syntax map[key] (the at operator) for direct access. Panics if the key is not found.

///|
test {
  let map = @sorted_map.from_array([(1, "one"), (2, "two")])
  @test.assert_eq(map[1], "one")
  @test.assert_eq(map[2], "two")
}

#Get with Default

get_or_default() returns a fallback value when the key is missing. get_or_init() lazily initializes and inserts the value if absent.

///|
test {
  let map = @sorted_map.from_array([(1, "one")])
  @test.assert_eq(map.get_or_default(1, "???"), "one")
  @test.assert_eq(map.get_or_default(2, "???"), "???")
  // get_or_init inserts the value if missing
  let val = map.get_or_init(3, fn() { "three" })
  @test.assert_eq(val, "three")
  @test.assert_eq(map.contains(3), true) // now in the map
}

#Copy

copy() creates a shallow clone of the map.

///|
test {
  let map = @sorted_map.from_array([(1, "a"), (2, "b")])
  let cloned = map.copy()
  cloned.set(3, "c")
  @test.assert_eq(map.contains(3), false) // original unchanged
  @test.assert_eq(cloned.contains(3), true)
}

#Merging

merge() returns a new map combining both. merge_in_place() mutates the receiver. On key conflicts, the right map wins.

///|
test {
  let m1 = @sorted_map.from_array([(1, "a"), (2, "b")])
  let m2 = @sorted_map.from_array([(2, "B"), (3, "c")])
  let merged = m1.merge(m2)
  assert_true(merged.get(2) == Some("B")) // right wins
  assert_true(merged.get(3) == Some("c"))
  // merge_in_place
  let m3 = @sorted_map.from_array([(1, "x")])
  let m4 = @sorted_map.from_array([(2, "y")])
  m3.merge_in_place(m4)
  @test.assert_eq(m3.contains(2), true)
}

#Error Handling Best Practices

When working with keys that might not exist, prefer using pattern matching for safety:

///|
fn get_score(scores : @sorted_map.SortedMap[Int, Int], student_id : Int) -> Int {
  match scores.get(student_id) {
    Some(score) => score
    None =>
      // println(
      //   "Student ID " +
      //   student_id.to_string() +
      //   " does not exist, returning default score",
      // )
      0 // Default score
  }
}

///|
test "safe_key_access" {
  // Create a mapping storing student IDs and their scores
  let scores = @sorted_map.from_array([(1001, 85), (1002, 92), (1003, 78)])

  // Access an existing key
  @test.assert_eq(get_score(scores, 1001), 85)

  // Access a non-existent key, returning the default value
  @test.assert_eq(get_score(scores, 9999), 0)
}

#Implementation Notes

The SortedMap is implemented as an AVL tree, a self-balancing binary search tree. After insertions and deletions, the tree automatically rebalances to maintain O(log n) search, insertion, and deletion times.

Key properties of the AVL tree implementation:
  • Each node stores a height field indicating the height of that subtree
  • The balance factor (height difference between left and right subtrees) is maintained between -1 and 1 for all nodes
  • Rebalancing is done through tree rotations (single and double rotations)

#Comparison with Other Collections

  • @hashmap.HashMap: Provides O(1) average case lookups but doesn't maintain order; use when order doesn't matter
  • @indexmap.T: Maintains insertion order but not sorted order; use when insertion order matters
  • @sorted_map.SortedMap: Maintains keys in sorted order; use when you need keys to be sorted

Choose SortedMap when you need:
  • Key-value pairs sorted by key
  • Efficient range queries
  • Ordered traversal guarantees

#
SortedMap

source
type SortedMap[K, V]

impl Default for SortedMap[K, V]
impl Eq 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
#as_free_fn(of, deprecated="Use from_array instead")
#alias(of, deprecated="Use from_array instead")
#as_free_fn(from_array)
#alias(from_array)
fn[K : Compare + Eq, V] SortedMap::SortedMap(entries : ArrayView[(K, V)]) -> SortedMap[K, V]

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

Example

test {
  let map = @sorted_map.SortedMap([(1, "one"), (2, "two")])
  assert_true(map.get(1) == Some("one"))
}

#
SortedMap::at

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

Returns the value for the key. Panics if the key is not present.

#
SortedMap::clear

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

Removes all entries from the map.

#
SortedMap::contains

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

Returns true if the map contains the given key.

#
SortedMap::copy

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

Creates a deep copy of the sorted map.

This operation creates a new map with the same structure and contents as the original map. The copy is independent - modifications to the copy will not affect the original map and vice versa.

This is more efficient than creating a new map and inserting all elements, as it preserves the tree structure without needing to rebalance.

Parameters:

  • self : The sorted map to copy.

Returns a new sorted map with the same contents and structure.

Example:

test {
  let map1 = @sorted_map.from_array([(1, "a"), (2, "b"), (3, "c")])
  let map2 = map1.copy()
  map2.set(4, "d")
  inspect(map1.length(), content="3")
  inspect(map2.length(), content="4")
}

#
SortedMap::each

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

Calls f on each key-value pair in ascending key order.

#
SortedMap::eachi

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

Calls f on each key-value pair with its index (0-based), in ascending key order.

#
SortedMap::equal

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

#
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::get

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

Returns the value associated with the key, or None if not found.

#
SortedMap::get_or_default

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

Returns the value for the key if present, otherwise returns default.

#
SortedMap::get_or_init

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

Returns the value for the key if present, otherwise inserts the value produced by init and returns it.

#
SortedMap::is_empty

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

Returns true if the map contains no entries.

#
SortedMap::iter

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

Return an iterator via iter.

#
SortedMap::iter2

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

Return an iterator via iter2.

#
SortedMap::keys

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

Returns an iterator over the keys 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

Returns the count of 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 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 does not modify either of the input maps.

Parameters:

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

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

Example:

test {
  let map1 = @sorted_map.from_array([(1, "a"), (2, "b")])
  let map2 = @sorted_map.from_array([(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::merge_in_place

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

Merges another sorted map into this map in-place. Updates the current map by adding all key-value pairs from other. When both maps contain the same key, the value from other overwrites the value in this map.

This is a mutating operation - it modifies the receiver map.

Parameters:

  • self : The sorted map to be modified.
  • other : The sorted map whose entries will be added to self.

Example:

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

#
SortedMap::new

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

Creates an empty sorted map.

Deprecated: use SortedMap([]) instead.

#
SortedMap::range

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

Returns a new array of key-value pairs that are within the specified range [low, high].

#
SortedMap::remove

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

Removes the entry for the given key. Does nothing if the key is not present.

#
SortedMap::set

source
#alias(add, deprecated="Use set instead")
#alias("_[_]=_")
fn[K : Compare + Eq, V] SortedMap::set(self : SortedMap[K, V], key : K, value : V) -> Unit

FIXME: (remove this line will break formatter)
test {
  let map = @sorted_map.SortedMap([])
  map.set(1, "a")
  map.set(2, "b")
  map.set(2, "c") // updates value for key 2
  debug_inspect(map.get(1), content="Some(\"a\")")
  debug_inspect(map.get(2), content="Some(\"c\")")
}

#
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::update_or_default

source
fn[K : Compare + Eq, V] SortedMap::update_or_default(self : SortedMap[K, V], key : K, default : V, f : (V) -> V) -> Unit

Inserts default for key if it is absent, otherwise replaces the existing value with f(existing). The pairing of an eager default value with a modifier function lets the canonical counter pattern read literally:

Example

test {
  let counts : @sorted_map.SortedMap[String, Int] = SortedMap([])
  counts.update_or_default("a", 1, x => x + 1)
  counts.update_or_default("a", 1, x => x + 1)
  counts.update_or_default("b", 1, x => x + 1)
  debug_inspect(counts.get("a"), content="Some(2)")
  debug_inspect(counts.get("b"), content="Some(1)")
}

Note: f is not applied to default on first insertion — default is the value stored when the key is absent. This mirrors Java's Map.merge and Rust's Entry::and_modify(f).or_insert(default).

#
SortedMap::values

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

Returns an iterator over the values in ascending key order.

Source Files

Powered by MoonBit

Site sourceReport issuePackagesBuild queueSkillsStatistics

© 2026 mooncakes.io