🥮 mooncakes.io
    Sign in

    #Sorted Map

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

    Floating elements and keys used by ordinary comparison-based operations must not be NaN, including floating components of derived/composite keys. Signed zeros, infinities, and subnormals are supported. This is an input precondition, not an automatic NaN check; see the Eq and Compare trait contracts.

    #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[Int32, 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[Int32, 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)
    }

    #Smallest, Largest and Nearest Keys

    first and last return the entries with the smallest and largest keys; pop_first and pop_last also remove them. first_ge, first_gt, last_le and last_lt find the nearest entry on either side of a key. All of these run in O(log n).

    “First”, “last”, and the nearest-key comparisons follow the keys' Compare ordering. For keys wrapped in @cmp.Reverse, the first entry has the largest underlying key and the last entry has the smallest.

    ///|
    test {
      let map = @sorted_map.from_array([(10, "a"), (20, "b"), (30, "c")])
      @debug.assert_eq(map.first(), Some((10, "a")))
      @debug.assert_eq(map.last(), Some((30, "c")))
      @debug.assert_eq(map.first_ge(15), Some((20, "b")))
      @debug.assert_eq(map.first_gt(20), Some((30, "c")))
      @debug.assert_eq(map.last_le(25), Some((20, "b")))
      @debug.assert_eq(map.last_lt(10), None)
      @debug.assert_eq(map.pop_first(), Some((10, "a")))
      @debug.assert_eq(map.pop_last(), Some((30, "c")))
      @debug.assert_eq(map.to_array(), [(20, "b")])
    }

    #Reverse Iteration

    rev_iter, rev_iter2, rev_keys and rev_values mirror iter, iter2, keys and values in descending key order, according to the keys' Compare ordering. rev_iter2 supports for key, value in map.rev_iter2().

    ///|
    test {
      let map = @sorted_map.from_array([(1, "a"), (2, "b"), (3, "c")])
      @debug.assert_eq(map.rev_keys().to_array(), [3, 2, 1])
      @debug.assert_eq(map.rev_iter().take(1).to_array(), [(3, "c")])
    }

    #Custom Ordering

    A SortedMap orders keys by their Compare implementation. To use a different order, wrap the key in a type whose Compare implements it. @cmp.Reverse gives descending order. When the order is only known at runtime, such as a per-column ascending or descending flag, let each key carry a reference to that configuration; all keys of one map share the same configuration array, so the extra cost is one field per key.

    In this example, every key must have the same number of columns, matching the configuration length. Stored keys and lookup keys must use the same ordering configuration. Do not mutate a stored key's columns or the shared ordering configuration while keys remain in the map; doing so invalidates the tree's ordering. To change the ordering, rebuild the map with new keys.

    ///|
    priv struct IndexKey {
      cols : Array[Int32]
      descending : Array[Bool] // shared by every key in the map
    }

    ///|
    impl Eq for IndexKey with fn equal(a, b) {
      a.cols == b.cols
    }

    ///|
    impl Compare for IndexKey with fn compare(a, b) {
      for i in 0..<a.cols.length() {
        let c = a.cols[i].compare(b.cols[i])
        if c != 0 {
          return if a.descending[i] { -c } else { c }
        }
      }
      0
    }

    ///|
    test {
      // Descending order with @cmp.Reverse
      let desc = @sorted_map.from_array([(@cmp.Reverse(1), "a"), (Reverse(3), "c")])
      @debug.assert_eq(desc.keys().map(k => k.0).to_array(), [3, 1])
      // Order chosen at runtime: first column ascending, second descending
      let descending = [false, true]
      let index : @sorted_map.SortedMap[IndexKey, String] = @sorted_map.from_array([])
      index.set({ cols: [1, 5], descending, }, "x")
      index.set({ cols: [1, 9], descending, }, "y")
      index.set({ cols: [0, 7], descending, }, "z")
      @debug.assert_eq(index.values().to_array(), ["z", "y", "x"])
    }

    #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[(Int32, String)] = []
      map.range(10, 5).each((k, v) => empty_range.push((k, v)))
      @debug.assert_eq(empty_range, [])
    }

    #Bounded Ranges

    range_bounds(lower, upper) takes a @cmp.Bound for each end: Included(k), Excluded(k) or Unbounded. Bounds are values, so the kind of each end can be chosen at runtime. rev_range_bounds returns the same entries in descending order. Both iterators are lazy, so taking the first few entries is cheap.

    ///|
    test {
      let map = @sorted_map.from_array([(1, "a"), (2, "b"), (3, "c"), (4, "d")])
      // 1 < key <= 3
      let mid = map.range_bounds(Excluded(1), Included(3)).iter().map(p => p.0)
      @debug.assert_eq(mid.to_array(), [2, 3])
      // key < 4, largest first
      let below = map.rev_range_bounds(Unbounded, Excluded(4)).iter().map(p => p.0)
      @debug.assert_eq(below.to_array(), [3, 2, 1])
      // choose the bound kind at runtime, e.g. for `x > 2` versus `x >= 2`
      let strict = true
      let lower : @cmp.Bound[Int32] = if strict { Excluded(2) } else { Included(2) }
      let tail = map.range_bounds(lower, Unbounded).iter().map(p => p.0)
      @debug.assert_eq(tail.to_array(), [3, 4])
    }

    rev_range(low, high) is the inclusive reverse of range(low, high).

    #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[Int32, Int32],
      student_id : Int32,
    ) -> Int32 {
      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. Takes O(n) for strictly ascending or descending keys, otherwise O(n log n). A strictly ordered prefix is built in O(k), then the remaining entries are inserted normally. Keys must satisfy the Compare laws: floating keys and floating components of derived/composite keys must not be NaN.

    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::first

    source
    fn[K, V] SortedMap::first(self : SortedMap[K, V]) -> (K, V)?

    Returns the entry with the smallest key, or None if the map is empty.

    test {
      let map = @sorted_map.from_array([(3, "c"), (1, "a"), (2, "b")])
      @debug.debug_inspect(map.first(), content="Some((1, \"a\"))")
    }

    SortedMap::first_ge

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

    Returns the entry with the smallest key that is greater than or equal to key, or None if there is no such entry.

    test {
      let map = @sorted_map.from_array([(10, "a"), (20, "b"), (30, "c")])
      @debug.debug_inspect(map.first_ge(20), content="Some((20, \"b\"))")
      @debug.debug_inspect(map.first_ge(21), content="Some((30, \"c\"))")
      @debug.debug_inspect(map.first_ge(31), content="None")
    }

    SortedMap::first_gt

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

    Returns the entry with the smallest key that is strictly greater than key, or None if there is no such entry.

    test {
      let map = @sorted_map.from_array([(10, "a"), (20, "b"), (30, "c")])
      @debug.debug_inspect(map.first_gt(20), content="Some((30, \"c\"))")
      @debug.debug_inspect(map.first_gt(30), content="None")
    }

    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::last

    source
    fn[K, V] SortedMap::last(self : SortedMap[K, V]) -> (K, V)?

    Returns the entry with the largest key, or None if the map is empty.

    test {
      let map = @sorted_map.from_array([(3, "c"), (1, "a"), (2, "b")])
      @debug.debug_inspect(map.last(), content="Some((3, \"c\"))")
    }

    SortedMap::last_le

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

    Returns the entry with the largest key that is less than or equal to key, or None if there is no such entry.

    test {
      let map = @sorted_map.from_array([(10, "a"), (20, "b"), (30, "c")])
      @debug.debug_inspect(map.last_le(20), content="Some((20, \"b\"))")
      @debug.debug_inspect(map.last_le(19), content="Some((10, \"a\"))")
      @debug.debug_inspect(map.last_le(9), content="None")
    }

    SortedMap::last_lt

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

    Returns the entry with the largest key that is strictly less than key, or None if there is no such entry.

    test {
      let map = @sorted_map.from_array([(10, "a"), (20, "b"), (30, "c")])
      @debug.debug_inspect(map.last_lt(20), content="Some((10, \"a\"))")
      @debug.debug_inspect(map.last_lt(10), content="None")
    }

    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::pop_first

    source
    fn[K, V] SortedMap::pop_first(self : SortedMap[K, V]) -> (K, V)?

    Removes and returns the entry with the smallest key, or returns None if the map is empty.

    test {
      let map = @sorted_map.from_array([(3, "c"), (1, "a"), (2, "b")])
      @debug.debug_inspect(map.pop_first(), content="Some((1, \"a\"))")
      @debug.debug_inspect(map.to_array(), content="[(2, \"b\"), (3, \"c\")]")
    }

    SortedMap::pop_last

    source
    fn[K, V] SortedMap::pop_last(self : SortedMap[K, V]) -> (K, V)?

    Removes and returns the entry with the largest key, or returns None if the map is empty.

    test {
      let map = @sorted_map.from_array([(3, "c"), (1, "a"), (2, "b")])
      @debug.debug_inspect(map.pop_last(), content="Some((3, \"c\"))")
      @debug.debug_inspect(map.to_array(), content="[(1, \"a\"), (2, \"b\")]")
    }

    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::range_bounds

    source
    fn[K : Compare + Eq, V] SortedMap::range_bounds(self : SortedMap[K, V], lower : 
    Bound    [K], upper : 
    Bound    [K]) -> Iter2[K, V]

    Returns an iterator over the entries whose keys lie between lower and upper, in ascending key order.

    Each end is a @cmp.Bound: Included(k), Excluded(k) or Unbounded. Because bounds are values, the kind of each end can be chosen at runtime. Inclusion and exclusion follow Compare::compare, as do range and the nearest-key queries. Lower and upper refer to that ordering, including when keys use @cmp.Reverse. The iterator is lazy: it visits O(log n) nodes to find the first entry, then O(1) amortized per entry, so stopping early is cheap.

    An empty iterator is returned when the bounds select no keys, including when lower is above upper. When the endpoints compare equal, excluding either endpoint selects no keys.

    test {
      let map = @sorted_map.from_array([(1, "a"), (2, "b"), (3, "c"), (4, "d")])
      let keys = map.range_bounds(Excluded(1), Included(3)).iter().map(p => p.0)
      @debug.debug_inspect(keys.to_array(), content="[2, 3]")
      let tail = map.range_bounds(Included(3), Unbounded).iter().map(p => p.0)
      @debug.debug_inspect(tail.to_array(), content="[3, 4]")
      let empty = map.range_bounds(Included(2), Excluded(2))
      @debug.debug_inspect(empty.iter().to_array(), content="[]")
    }

    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::rev_iter

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

    Returns an iterator over all entries in descending key order.

    test {
      let map = @sorted_map.from_array([(1, "a"), (3, "c"), (2, "b")])
      @debug.debug_inspect(
        map.rev_iter().to_array(),
        content="[(3, \"c\"), (2, \"b\"), (1, \"a\")]",
      )
    }

    SortedMap::rev_iter2

    source
    fn[K, V] SortedMap::rev_iter2(self : SortedMap[K, V]) -> Iter2[K, V]

    Returns a two-value iterator over entries in descending key order, according to the keys' Compare ordering.

    test {
      let map = @sorted_map.from_array([(1, "a"), (3, "c"), (2, "b")])
      let entries = []
      for key, value in map.rev_iter2() {
        entries.push((key, value))
      }
      @debug.debug_inspect(entries, content="[(3, \"c\"), (2, \"b\"), (1, \"a\")]")
    }

    SortedMap::rev_keys

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

    Returns an iterator over the keys in descending order.

    SortedMap::rev_range

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

    Returns an iterator over the entries whose keys are within [low, high] (both inclusive), in descending key order. This is the reverse of range.

    test {
      let map = @sorted_map.from_array([(1, "a"), (2, "b"), (3, "c"), (4, "d")])
      let keys = map.rev_range(2, 3).iter().map(p => p.0)
      @debug.debug_inspect(keys.to_array(), content="[3, 2]")
    }

    SortedMap::rev_range_bounds

    source
    fn[K : Compare + Eq, V] SortedMap::rev_range_bounds(self : SortedMap[K, V], lower : 
    Bound    [K], upper : 
    Bound    [K]) -> Iter2[K, V]

    Returns an iterator over the entries whose keys lie between lower and upper, in descending key order. See range_bounds for how bounds work. The arguments remain in lower–upper order; only traversal is reversed.

    test {
      let map = @sorted_map.from_array([(1, "a"), (2, "b"), (3, "c"), (4, "d")])
      let keys = map.rev_range_bounds(Unbounded, Excluded(4)).iter().map(p => p.0)
      @debug.debug_inspect(keys.to_array(), content="[3, 2, 1]")
    }

    SortedMap::rev_values

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

    Returns an iterator over the values in descending key order.

    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, Int32] = 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