1// Package bidimap is a bidirectional map — unique in both directions — as a2// pure, reusable package.3//4// A normal map answers "what is the value for this key". A bidirectional one5// also answers the reverse in O(1), by keeping a second index. The cost is an6// invariant a plain pair of maps does not give you: BOTH sides are unique, so7// inserting a pair whose value already belongs to another key must do something8// deliberate rather than silently corrupt the reverse index.9//10// This implementation makes that choice explicit. Put REPLACES: it evicts any11// existing pairing on either side first, so the two indexes can never disagree.12// PutUnique refuses instead, returning false. Pick whichever the caller wants;13// what is not on offer is a half-updated map.14//15// Iteration is over sorted keys, never a built-in map range: gno map iteration16// order is unspecified, and a Render built from one can differ between nodes,17// which is a consensus bug rather than a cosmetic one.18//19// A live demo of this package is at20// [r/moul/x/daily/bidimapdemo](/r/moul/x/daily/bidimapdemo/v0).21package bidimap2223import "sort"2425// MaxPairs bounds the map so gas stays predictable.26const MaxPairs = 40962728// BiMap is a string<->string map, unique in both directions.29type BiMap struct {30 fwd map[string]string31 rev map[string]string32}3334// New returns an empty BiMap.35func New() *BiMap {36 return &BiMap{fwd: map[string]string{}, rev: map[string]string{}}37}3839// Len returns the number of pairs.40func (m *BiMap) Len() int { return len(m.fwd) }4142// Get returns the value bound to key.43func (m *BiMap) Get(key string) (string, bool) {44 v, ok := m.fwd[key]45 return v, ok46}4748// GetKey returns the key bound to value — the reverse lookup, also O(1).49func (m *BiMap) GetKey(value string) (string, bool) {50 k, ok := m.rev[value]51 return k, ok52}5354// Has reports whether key is present.55func (m *BiMap) Has(key string) bool { _, ok := m.fwd[key]; return ok }5657// HasValue reports whether value is present.58func (m *BiMap) HasValue(value string) bool { _, ok := m.rev[value]; return ok }5960// Put binds key<->value, REPLACING any existing pairing on either side. It61// returns the pairs that were evicted to make room, so the caller can see what62// it displaced rather than discovering it later.63//64// Returns ok=false only when the map is full and the pair is entirely new.65func (m *BiMap) Put(key, value string) (evicted [][2]string, ok bool) {66 oldValue, keyTaken := m.fwd[key]6768 // Already exactly this pair: nothing to do.69 if keyTaken && oldValue == value {70 return nil, true71 }7273 oldKey, valueTaken := m.rev[value]7475 // Only a pair that is new on BOTH sides grows the map. Rebinding either76 // side reuses a slot, so it stays allowed at capacity. Checked up front:77 // evicting first and rolling back on failure would be unreachable code,78 // since any eviction frees the very slot the check is about.79 if !keyTaken && !valueTaken && len(m.fwd) >= MaxPairs {80 return nil, false81 }8283 if keyTaken {84 evicted = append(evicted, [2]string{key, oldValue})85 delete(m.rev, oldValue)86 delete(m.fwd, key)87 }88 if valueTaken {89 evicted = append(evicted, [2]string{oldKey, value})90 delete(m.fwd, oldKey)91 delete(m.rev, value)92 }9394 m.fwd[key] = value95 m.rev[value] = key96 return evicted, true97}9899// PutUnique binds key<->value only when NEITHER side is already taken by a100// different pairing. Returns false without changing anything otherwise.101func (m *BiMap) PutUnique(key, value string) bool {102 if v, exists := m.fwd[key]; exists {103 return v == value // idempotent for the identical pair104 }105 if _, exists := m.rev[value]; exists {106 return false107 }108 if len(m.fwd) >= MaxPairs {109 return false110 }111 m.fwd[key] = value112 m.rev[value] = key113 return true114}115116// Delete removes the pair for key. Returns false when key is absent.117func (m *BiMap) Delete(key string) bool {118 v, ok := m.fwd[key]119 if !ok {120 return false121 }122 delete(m.fwd, key)123 delete(m.rev, v)124 return true125}126127// DeleteValue removes the pair for value. Returns false when value is absent.128func (m *BiMap) DeleteValue(value string) bool {129 k, ok := m.rev[value]130 if !ok {131 return false132 }133 delete(m.fwd, k)134 delete(m.rev, value)135 return true136}137138// Keys returns every key, sorted. Sorted, not map order: a Render built from an139// unspecified order can differ between nodes.140func (m *BiMap) Keys() []string { return sortedKeys(m.fwd) }141142// Values returns every value, sorted.143func (m *BiMap) Values() []string { return sortedKeys(m.rev) }144145// Iterate calls fn for each pair in sorted key order. Returning true stops.146func (m *BiMap) Iterate(fn func(key, value string) bool) {147 for _, k := range m.Keys() {148 if fn(k, m.fwd[k]) {149 return150 }151 }152}153154// Invert returns a new BiMap with keys and values swapped.155func (m *BiMap) Invert() *BiMap {156 out := New()157 for k, v := range m.fwd {158 out.fwd[v] = k159 out.rev[k] = v160 }161 return out162}163164// Clone returns an independent copy.165func (m *BiMap) Clone() *BiMap {166 out := New()167 for k, v := range m.fwd {168 out.fwd[k] = v169 out.rev[v] = k170 }171 return out172}173174// Consistent reports whether the two indexes agree. Always true through the175// public API; exported so tests and callers can assert the invariant directly.176func (m *BiMap) Consistent() bool {177 if len(m.fwd) != len(m.rev) {178 return false179 }180 for k, v := range m.fwd {181 if back, ok := m.rev[v]; !ok || back != k {182 return false183 }184 }185 return true186}187188func sortedKeys(m map[string]string) []string {189 out := make([]string, 0, len(m))190 for k := range m {191 out = append(out, k)192 }193 sort.Strings(out)194 return out195}196Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.