#moonbit-bimap

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)

#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

import {
  "aurasuisui/bimap@0.3.0",
}

import {
  "aurasuisui/bimap",
}

#The five insertion cases (C0–C4)

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

#JSON round-trip (from_json)

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 } },
)

#BiBTreeMap — the sorted variant

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

#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

• 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

#Development

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

#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