bidimap.gno
5.45 Kb · 195 lines
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/nym-moultest123/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}
