#moonbit-indexmap

let map = @aurasuisui/indexmap.new()
map.insert("b", 2) |> ignore
map.insert("a", 1) |> ignore
map.insert("c", 3) |> ignore

// Iteration follows insertion order: b, a, c
let iter = map.iter()
while true {
  match iter.next() {
    Some((k, v)) => println("\{k}: \{v}")
    None => break
  }
}

#Features

• Insertion-order iteration — entries yield in the order they were first inserted
• O(1) average lookups — Robin Hood open-addressing hash table
• Index-based access — get_index(i), first(), last(), pop()
• Entry API — OccupiedEntry / VacantEntry for in-place manipulation
• IndexSet — ordered hash set with is_disjoint, is_subset, is_superset
• JSON support — ToJson preserves key order; from_json / from_json_with deserialize back (order-preserving, so from_json(m.to_json()) == m is a lossless round-trip for String-keyed maps)
• Standard traits — Debug, Default, Show, Hash, Eq, ToJson for both IndexMap and IndexSet
• QuickCheck support — Arbitrary trait for property-based testing

#Installation

{ "dependencies": { "aurasuisui/indexmap": "0.4.0" } }

git clone https://github.com/aurasuisui/moonbit-indexmap

#API Overview

#IndexMap[K, V]

#IndexSet[K]

#Design

1. Robin Hood hash table (Array[Entry[K, V]?]) — O(1) average lookup, reduced probe variance
2. Order array (Array[K]) — tracks insertion order for deterministic iteration

#Compared to built-in Map

#Gotchas

1. get_mut semantics: the callback's return value is authoritative (reworked in v0.3.3). get_mut(key, f) passes the current value to f (or None if the key is absent) and then re-applies the result through insert/remove: Some(v) stores v under key (inserting it if the callback removed it), and None removes key. Returning None therefore removes the key even if the callback re-inserted it — return Some(v) to keep a value. Because the result is re-applied via a fresh probe, the callback may safely mutate the map (including triggering a resize). Earlier versions wrote back to a stale bucket index, which could corrupt the table and silently broke plain deletion.

2. Eq and Hash are insertion-order-sensitive. Two maps with identical key-value pairs but different insertion orders are not equal and produce different hashes. Avoid using an IndexMap or IndexSet as a key in another hash container unless you can guarantee consistent insertion order.

3. swap_remove_index is actually O(n) shift-remove. Despite the name (kept for Rust indexmap API compatibility), it calls the order-preserving remove path — elements after the target are shifted one slot left. It does not swap with the last element in O(1). If you need actual O(1) order-breaking removal, you would need a dedicated method that directly swaps with the last element before popping — swap_remove_index does not do this.

4. max_probe() is refreshed after sort_by / sort_by_key (fixed in v0.3.2). Sorting rebuilds order[] and positions[]; as of v0.3.2 the internal max_probe_distance is also recalculated after sorting, so max_probe() reports the current (post-sort) probe distribution. (Sorting does not move buckets, so previously the value happened to remain correct — it is now maintained explicitly.)

5. Don't mutate the map while an iterator is active. Each iterator snapshots the map's mutation version at creation; if the map is structurally modified (insert, remove, clear, retain, sort_by*, reserve, shrink_to_fit, or an Entry / get_mut mutation) before the iterator is exhausted, the next next() aborts with IndexMap: map mutated during iteration — true fail-fast, added in v0.3.3. Earlier versions silently skipped entries and could crash with an out-of-bounds access. Finish all mutations first, then create a fresh iterator.

#Independent Test Report

Released: the from_json API addition, the deletion-engine rewrite (backward-shift, tombstone-free) and the test-suite reorganization described here shipped in v0.4.0. See CHANGELOG.md [0.4.0].

#Examples

• cmd/lru_cache — LRU eviction demo
• cmd/config_parse — order-preserving config parser
• cmd/json_order — ToJson key ordering

Note: the cmd/* example packages are workspace members (listed in moon.work) and use pkgtype(kind: "executable") (migrated off the deprecated options("is-main")). Being in the workspace, they resolve aurasuisui/indexmap to the local source — so they're checked/formatted by the root moon check / moon fmt and run by the CI examples job without depending on the mooncakes registry (the historical reason they were excluded — the options("is-main") / version: latest conflict — is resolved by pkgtype). To run one locally: moon run cmd/<name> from the repo root.

#Development

moon check            # Type check (0 warnings, 0 errors; --deny-warn clean)
moon test             # Run all in-package tests (white-box + library-specific)
moon test --target <t># t = wasm-gc | wasm | js | native (CI tests all four)
moon fmt              # Format code

#License