🥮 mooncakes.io

    #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")
      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
    • Map (builtin): 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 shallow 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 an iterator over the key-value pairs whose keys are within the specified range [low, high] (both bounds inclusive).

    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