moonbit-bimap

A bidirectional map (bijection) for MoonBit — a port of Rust’s bimap crate / Guava BiMap, extended with insertion-order preservation and index-based access (which neither Rust nor Guava provides).

A BiMap[L, R] keeps keys and values in one-to-one correspondence: you can look up left→right and right→left, and every insertion maintains the bijection invariant.

let m = @aurasuisui/bimap.new()
m.insert("alice", "admin") |> ignore
m.insert("bob", "user") |> ignore

// Forward and reverse lookup:
println(m.get_by_left("alice"))     // Some("admin")
println(m.get_by_right("user"))     // Some("bob")

// Index access (insertion order preserved):
println(m.get_index(0))             // Some(("alice", "admin"))

Why a BiMap? (vs the built-in Map and vs indexmap)

Feature	built-in Map	BiMap	indexmap
key → value	✅	✅	✅
value → key (reverse)	❌	✅	❌
index access get_index(i)	❌	✅	✅
keys unique	✅	✅	✅
values also unique (bijection)	❌	✅	❌
preserves insertion order	impl-defined	✅	✅
Eq/Hash semantics	order-independent	order-independent	order-sensitive

BiMap and indexmap solve orthogonal problems — Bi = bidirectional (one-to-one, reverse lookup); Index = positional access. They share only the underlying hash table (as any two maps share arrays). This package is a fresh, dependency-free library, not a fork or rename of indexmap.

Features

• Bidirectional lookup — get_by_left / get_by_right, contains_left / contains_right
• Bijection-enforcing insertion — insert returns an Overwritten enum describing what was displaced (including the classic C4 collapse, see below)
• Non-overwriting insertion — insert_no_overwrite returns Result[Unit, (L, R)]
• Insertion-order iteration — iter() yields pairs in the order left keys were inserted
• Index-based access — get_index(i), get_index_of_left, get_index_of_right, first(), last()
• Inverse copy — to_inverse() -> BiMap[R, L] (a copy, not a live view)
• Predicate filtering — retain(pred) keeps only the matching pairs in O(n), preserving their relative insertion order (a port of Rust bimap’s retain)
• Sorted bijection — BiBTreeMap: the same contract on a sorted engine (ascending by left key, range queries, first/last = min/max key), keys need only Compare; differential-tested against Rust bimap’s BiBTreeMap
• Set views + entry helpers — contains_pair(l, r), snapshot arrays left_keys() / right_values() (insertion order), and the stateless get_or_insert_left / get_or_insert_right — original extensions (Rust bimap v0.6.3 has none of them; its same-named right_values() is a lazy unordered iterator, ours is an ordered snapshot)
• Standard traits — Debug, Default, Show, Eq/Hash (order-independent), ToJson, plus QuickCheck Arbitrary
• JSON round-trip — from_json / from_json_with (both map types, v0.3.0) decode {"<left>": <right>, ...} objects with strict bijection validation: two left keys mapping to the same right raise DuplicateRightValue (the whole parse fails — no silent eviction); the JSON text key order becomes BiMap insertion order; decode errors pass through as Decode

Installation

Add the dependency to your project’s moon.mod:

import {
  "aurasuisui/bimap@0.3.0",
}

Then import it in the relevant moon.pkg:

import {
  "aurasuisui/bimap",
}

The five insertion cases (C0–C4)

Inserting (l, r) into a bijection has five sub-cases — the crux of a correct BiMap:

Case	Condition	insert returns	len change
C0	neither l nor r present	Neither	+1
C1	the exact pair (l, r) already present	Pair(l, r)	0
C2	l was bound to r'≠r; r free	Left(l, r')	0
C3	r was bound to l'≠l; l free	Right(l', r)	0
C4	l→r' and l'→r both exist	Both((l,r'), (l',r))	−1

C4 collapses two pairs into one — insert can reduce the map’s size! This mirrors Rust bimap‘s Overwritten::Both exactly.

let m = @aurasuisui/bimap.new()
m.insert("a", 1) |> ignore   // Neither      {a↔1}
m.insert("b", 2) |> ignore   // Neither      {a↔1, b↔2}
m.insert("a", 4) |> ignore   // Left(a, 1)   {a↔4, b↔2}
m.insert("c", 2) |> ignore   // Right(b, 2)  {a↔4, c↔2}
let r = m.insert("a", 2)     // Both((a,4),(c,2))  {a↔2}  — len 2→1!

Gotchas

1. insert can shrink the map (C4 collapse). Check the returned Overwritten if you need to know what was displaced.
2. Eq and Hash are order-independent. A BiMap is a set of pairs; two maps with the same pairs in different insertion order are equal and hash the same. This is the opposite of the author’s indexmap, whose Eq/Hash are order-sensitive. The hash is hardened (2026-08): it folds the sorted per-pair fingerprint sequence (the pair set’s canonical form), so map-level collisions reduce to equal fingerprint multisets — engineering one now requires hash-level control over the keys (e.g. shifting h(l) up by t while shifting h(r) down by K·t). Remaining boundaries: fingerprint-level collisions are still possible in principle, and hashing a whole map costs O(n log n) (the sort). Fine for collections; if you hash very large BiMaps hot, cache the result.
3. to_inverse() returns a copy, not a live view. Mutating the inverse does not affect the original (MoonBit’s ownership model favors copies over shared live views; this matches Rust bimap‘s method-based access rather than Guava’s live inverse()).
4. ToJson keys use l.to_string() (L : Show), so String keys serialize verbatim.
5. Don’t mutate the map while an iterator is active — iterators are fail-fast (they snapshot a mutation counter and abort if the map changes mid-iteration).
6. from_array resolves duplicate pairs by “last wins” (via insert), matching Rust’s FromIterator.
7. A rebind (C2) keeps the left key’s insertion position — rebinding l to a new right value does not move l to the end of the order. This is an intentional, order-preserving extension over Rust’s remove-then-reinsert behavior (see CHANGELOG).
8. BiMap is not thread-safe. It is mutable and its iterators are fail-fast; concurrent reads/writes from multiple threads are undefined behavior. Use one BiMap per thread, or guard shared access with external synchronization.
9. Removal shifts the insertion order — O(n) worst case. remove_by_left / remove_by_right keep the order array dense by shifting later entries, so a single removal costs O(len) in the worst case, and removing n pairs in insertion (head-first) order is O(n²) overall (bench-measured, see Performance). For bulk clear-outs, drain in reverse insertion order (each shift degenerates to O(1)) or rebuild (from_array / copy).
10. from_json validates strictly; parse_key must be total. A JSON object with two left keys decoding to the same right raises DuplicateRightValue instead of silently evicting a pair (the opposite of Rust bimap’s serde, which overwrites). The parse_key you pass to from_json_with has no raise channel — absorb parse failures inside it (e.g. catch @string.parse_int and fall back to a default). And R = Json is type-level impossible: Json has no Hash/Compare, which the right side of both map types requires.

API Overview

Category	Methods
Construct	new(), with_capacity(n), from_array(pairs), default()（Default trait 实现）, copy(), from_json(json), from_json_with(json, parse_key)
Query	len(), is_empty(), capacity()
Insert	insert(l, r) -> Overwritten, insert_no_overwrite(l, r) -> Result[Unit,(L,R)]
Forward	get_by_left(l), contains_left(l), remove_by_left(l) -> R?
Reverse	get_by_right(r), contains_right(r), remove_by_right(r) -> L?
Index	get_index(i), get_index_of_left(l), get_index_of_right(r), first(), last()
Iterate	iter(), lefts(), rights(), into_array()
Views	contains_pair(l, r), left_keys(), right_values()
Entry	get_or_insert_left(l, r) -> R, get_or_insert_right(r, l) -> L
Bulk	retain(pred)
Convert	to_inverse() -> BiMap[R, L]
Traits	Debug, Default, Show, Hash, Eq, ToJson, Arbitrary

JSON round-trip (from_json)

ToJson has a strict inverse (v0.3.0): from_json / from_json_with decode a JSON object { "<left>": <right-json>, ... } back into a bijection, with strict bijection validation — a right-value conflict raises BiMapDecodeError::DuplicateRightValue (payload: right value + both conflicting left keys), value decode errors pass through as Decode and take priority, and duplicate keys are last-wins. For BiMap use the free function; BiBTreeMap is reached by method call (MoonBit free functions cannot overload by return type). Both raise BiMapDecodeError — catch it, or let it propagate:

let json = @json.parse("{\"bob\":2,\"alice\":1}") // text -> Json

// BiMap: free function; insertion order = JSON text key order
let m : @aurasuisui/bimap.BiMap[String, Int] = @aurasuisui/bimap.from_json(json)

// BiBTreeMap: method call; sorted by left key (input key order irrelevant)
let s : @aurasuisui/bimap.BiBTreeMap[String, Int] =
  @aurasuisui/bimap.BiBTreeMap::from_json(json)

// Int-keyed text: from_json_with + a TOTAL parse_key (P1-2: no raise channel —
// absorb parse failures inside, e.g. fall back to a default):
let ints = @json.parse("{\"10\":10,\"20\":20}")
let n : @aurasuisui/bimap.BiMap[Int, Int] = @aurasuisui/bimap.from_json_with(
  ints,
  fn(k) { @string.parse_int(k) catch { _ => 0 } },
)

The round-trip is lossless: from_json(m.to_json()) == m (set equality), and for BiMap the iteration order survives as the text key order. parse_key must be total. R = Json is type-level impossible (Json lacks Hash/Compare). See docs/SPEC.md §12 and the runnable cmd/json_roundtrip example.

BiBTreeMap — the sorted variant

BiBTreeMap[L, R] is the same bijection on a sorted engine: two core SortedMap tables (ordered by left / by right). Sorted order replaces insertion order — no index access, first()/last() return the smallest/largest left key, and range(lo, hi) slices by left key (inclusive on both ends; the reverse-side range is deferred — see CHANGELOG). The whole C0–C4 insertion contract, retain, the M2 views/entry helpers, Eq/Hash set semantics, and fail-fast iterators carry over unchanged; keys only need Compare (no Hash required), and the snapshot/iteration/copy methods are all zero-bound. Differential-tested against the real Rust bimap BiBTreeMap v0.6.3 (golden + 6000-op stream + exact sorted terminal state).

let m = @aurasuisui/bimap.BiBTreeMap::from_array([("b", 2), ("a", 1), ("c", 3)])
println(m.into_array())       // [("a", 1), ("b", 2), ("c", 3)] — ascending by left
println(m.first())            // Some(("a", 1))   — smallest left key
println(m.range("a", "b").to_array())  // [("a", 1), ("b", 2)] — [lo, hi] inclusive

Category	Methods
Construct	new(), from_array(pairs), default()（Default trait 实现）, copy(), from_json(json), from_json_with(json, parse_key)
Query	len(), is_empty(), first(), last(), range(lo, hi) -> Iter
Insert	insert(l, r) -> Overwritten, insert_no_overwrite(l, r) -> Result[Unit,(L,R)]
Forward	get_by_left(l), contains_left(l), remove_by_left(l) -> R?
Reverse	get_by_right(r), contains_right(r), remove_by_right(r) -> L?
Views	contains_pair(l, r), left_keys(), right_values()
Entry	get_or_insert_left(l, r) -> R, get_or_insert_right(r, l) -> L
Bulk	retain(pred)
Iterate	iter(), into_array()
Convert	to_inverse() -> BiBTreeMap[R, L]
Traits	Debug, Default, Show, Hash, Eq, ToJson, Arbitrary

Design

• Two inverse Robin Hood hash tables (forward: L→R, backward: R→L) keep the bijection.
• One shared order array + positions map tracks left-key insertion order, enabling index access without a second order structure on the backward table.
• All mutations funnel through private put_pair / remove_by_left / remove_by_right helpers that maintain the invariants: ∀(l,r)∈forward ⟺ backward[r]==l, and five consistent counters.
• The Robin Hood engine is adapted from the author’s aurasuisui/indexmap (see below).

Examples

Runnable example packages live in cmd/:

• cmd/username_email — username ↔ email bidirectional lookup, iteration, and a rebind
• cmd/country_code — country name ↔ ISO code ("China" ↔ "CN"), reverse lookup, index access, and non-overwriting insert
• cmd/json_roundtrip — from_json/from_json_with on both map types, strict-conflict error handling, and the lossless text round-trip (runs against the published @0.3.0 after release)

Note: the cmd/* example packages are standalone modules (they import the published aurasuisui/bimap and are not part of the root package — the repo ships no workspace manifest). To run one, make the package resolvable (e.g. after moon publish) and run moon run cmd/<name>.

Performance

Measured with bench/ (official @bench framework, native backend, --release, benchmarking the published package) on an AMD Ryzen 7 7840H, Windows 11, moonc v0.10.8 (2026-08-19). Median of 5 samples, Int ↔ Int maps at n = 100 000, per-operation cost:

operation	BiMap	built-in Map
insert (fresh pair)	≈ 2 980 ns	≈ 410 ns
get_by_left (hit)	≈ 260 ns	≈ 130 ns (get)
get_by_right (hit)	≈ 330 ns	—
insert_no_overwrite (conflict)	≈ 300 ns	—
remove_by_left (tail-first drain)¹	≈ 1 510 ns	≈ 396 ns²
into_array (full traversal)	≈ 495 ns/pair	—

¹ Derived: insert+remove_all-reverse (≈ 4 490 ns/op) minus insert-fresh; draining in tail order makes each order shift O(1). ² Built-in Map figure is insert+remove combined, not directly split.

Read the numbers as the constant-factor price of bidirectionality + insertion order + index access: lookups run ≈2× the built-in map, inserts ≈7× (every write touches two hash tables, the order array, and the positions map). Reverse lookup stays within 25% of forward lookup. Worst case — bulk removal in insertion order: order_remove is an O(n) shift, so draining n pairs head-first is O(n²) overall (measured ≈ 133 µs/op at n = 10 000, ≈ 90× the tail-first drain). Drain in reverse insertion order, or rebuild — see Gotcha #9.

Reproduce with moon run --release bench/main.mbt (see bench/README.md; single-machine numbers, indicative of constant factors, not absolute speed).

Development

moon check   # type check
moon test    # run all 369 tests
moon fmt     # format
moon build   # build

The five-step CI pipeline runs: moon fmt --check → moon check → moon info && git diff --exit-code → moon test → moon build.

See CONTRIBUTING.md for the architecture deep-dive and test conventions.

Known Issues

• Fail-fast abort is not in-process testable. Mutating a map mid-iteration triggers abort, which the MoonBit test framework cannot catch as a passing assertion (a panicking test is reported as failed, not as “expected panic”). The version-snapshot + abort logic in src/bimap_iter.mbt is verified by inspection and by a manual reproduction (documented there); all other iterator behavior is fully tested.

Acknowledgements & Licensing

• The Robin Hood hash-table engine is adapted from the author’s aurasuisui/indexmap (Apache-2.0).
• The BiMap semantics (insert/insert_no_overwrite, Overwritten, bidirectional lookup) are ported from the Rust bimap crate (MIT / Apache-2.0), with conceptual reference to Guava BiMap (Apache-2.0). Order preservation and index access are original additions.

License

Apache 2.0 — see LICENSE.

Built for the 2026 MoonBit Open Source Ecosystem Hackathon (August).