Module imm/sorted_map

Persistent immutable sorted map using a left-leaning red-black tree.

SortedMap(K, V) stores key-value pairs in sorted order by key. All mutations return new maps, leaving the original unchanged. Backed by atomic object nodes for thread-safe structural sharing.

Keys must implement Eq, Ord, and Send. Values must implement Send.

Examples

{ SortedMap } :: import "std/imm/sorted_map";

m := SortedMap(i32, i32).new();
m = m.insert(i32(3), i32(30));
m = m.insert(i32(1), i32(10));
m = m.insert(i32(2), i32(20));
// keys are always sorted: 1, 2, 3

A left-leaning red-black tree keeps the depth in O(log n), so get, insert and remove are all O(log n) and a mutation copies only the nodes on its path — the rest is shared with the map it came from. This is the ordered counterpart of imm.Map's HAMT: reach for it when iteration must come out in key order. keys/values/entries, and the IntoIterator behind for(map, ...), MATERIALIZE an imm.List in key order first — O(n) time and allocation, not a lazy in-order cursor.

Stability

unstable — the same open shape as imm.Map (plans/STD_API_STABILIZATION.md §4): remove(key) -> Self cannot report whether the key was there, and deciding that changes this signature. The eager imm.List iteration above is the other known gap, and a stack-based in-order cursor is the intended fix; that one is additive.