#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)
• Standard traits — Debug, Default, Show, Eq/Hash (order-independent), ToJson, plus QuickCheck Arbitrary

#Installation

import {
  "aurasuisui/bimap@0.1.1",
}

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. Because Hash combines pair hashes commutatively, it is weaker against collision attacks — fine for a collection, but be mindful if using a BiMap as a key in another hash container.
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.

#API Overview

#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

Note: the cmd/* example packages are standalone modules excluded from the root workspace (they import the published aurasuisui/bimap). To run one, make the package resolvable (e.g. after moon publish) and run moon run cmd/<name>.

#Development

moon check   # type check
moon test    # run all 229 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