bidimap.gno

  1// Package bidimap is a bidirectional map — unique in both directions — as a
  2// pure, reusable package.
  3//
  4// A normal map answers "what is the value for this key". A bidirectional one
  5// also answers the reverse in O(1), by keeping a second index. The cost is an
  6// invariant a plain pair of maps does not give you: BOTH sides are unique, so
  7// inserting a pair whose value already belongs to another key must do something
  8// deliberate rather than silently corrupt the reverse index.
  9//
 10// This implementation makes that choice explicit. Put REPLACES: it evicts any
 11// 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 iteration
 16// 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 at
 20// [r/moul/x/daily/bidimapdemo](/r/moul/x/daily/bidimapdemo/v0).
 21package bidimap
 22
 23import "sort"
 24
 25// MaxPairs bounds the map so gas stays predictable.
 26const MaxPairs = 4096
 27
 28// BiMap is a string<->string map, unique in both directions.
 29type BiMap struct {
 30	fwd map[string]string
 31	rev map[string]string
 32}
 33
 34// New returns an empty BiMap.
 35func New() *BiMap {
 36	return &BiMap{fwd: map[string]string{}, rev: map[string]string{}}
 37}
 38
 39// Len returns the number of pairs.
 40func (m *BiMap) Len() int { return len(m.fwd) }
 41
 42// Get returns the value bound to key.
 43func (m *BiMap) Get(key string) (string, bool) {
 44	v, ok := m.fwd[key]
 45	return v, ok
 46}
 47
 48// 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, ok
 52}
 53
 54// Has reports whether key is present.
 55func (m *BiMap) Has(key string) bool { _, ok := m.fwd[key]; return ok }
 56
 57// HasValue reports whether value is present.
 58func (m *BiMap) HasValue(value string) bool { _, ok := m.rev[value]; return ok }
 59
 60// Put binds key<->value, REPLACING any existing pairing on either side. It
 61// returns the pairs that were evicted to make room, so the caller can see what
 62// 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]
 67
 68	// Already exactly this pair: nothing to do.
 69	if keyTaken && oldValue == value {
 70		return nil, true
 71	}
 72
 73	oldKey, valueTaken := m.rev[value]
 74
 75	// Only a pair that is new on BOTH sides grows the map. Rebinding either
 76	// 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, false
 81	}
 82
 83	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	}
 93
 94	m.fwd[key] = value
 95	m.rev[value] = key
 96	return evicted, true
 97}
 98
 99// PutUnique binds key<->value only when NEITHER side is already taken by a
100// 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 pair
104	}
105	if _, exists := m.rev[value]; exists {
106		return false
107	}
108	if len(m.fwd) >= MaxPairs {
109		return false
110	}
111	m.fwd[key] = value
112	m.rev[value] = key
113	return true
114}
115
116// 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 false
121	}
122	delete(m.fwd, key)
123	delete(m.rev, v)
124	return true
125}
126
127// 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 false
132	}
133	delete(m.fwd, k)
134	delete(m.rev, value)
135	return true
136}
137
138// Keys returns every key, sorted. Sorted, not map order: a Render built from an
139// unspecified order can differ between nodes.
140func (m *BiMap) Keys() []string { return sortedKeys(m.fwd) }
141
142// Values returns every value, sorted.
143func (m *BiMap) Values() []string { return sortedKeys(m.rev) }
144
145// 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			return
150		}
151	}
152}
153
154// 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] = k
159		out.rev[k] = v
160	}
161	return out
162}
163
164// Clone returns an independent copy.
165func (m *BiMap) Clone() *BiMap {
166	out := New()
167	for k, v := range m.fwd {
168		out.fwd[k] = v
169		out.rev[v] = k
170	}
171	return out
172}
173
174// Consistent reports whether the two indexes agree. Always true through the
175// 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 false
179	}
180	for k, v := range m.fwd {
181		if back, ok := m.rev[v]; !ok || back != k {
182			return false
183		}
184	}
185	return true
186}
187
188func 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 out
195}