orderedmap.gno

  1// Package orderedmap is a map that remembers the order its keys were inserted,
  2// as a pure, reusable package.
  3//
  4// This matters more on chain than off it. gno map iteration order is
  5// unspecified, so a realm that ranges over a built-in map to build its Render
  6// can emit a different page on every call — which is a consensus bug, not a
  7// cosmetic one. This type gives back a deterministic order without needing the
  8// keys to be sortable.
  9//
 10// Backed by a built-in map for O(1) lookup plus a slice holding insertion
 11// order. Delete is O(n) in the number of keys, because it has to close the gap
 12// in that slice — an honest trade for O(1) Get and an allocation-free walk.
 13// Re-Setting an existing key updates the value and KEEPS its original position:
 14// insertion order means first insertion, not last write.
 15//
 16// A live demo of this package is at
 17// [r/moul/x/daily/orderedmapdemo](/r/moul/x/daily/orderedmapdemo/v0).
 18package orderedmap
 19
 20// MaxKeys bounds the map so gas stays predictable.
 21const MaxKeys = 4096
 22
 23// OrderedMap is a string-keyed map with deterministic iteration.
 24type OrderedMap struct {
 25	m    map[string]string
 26	keys []string
 27}
 28
 29// New returns an empty OrderedMap.
 30func New() *OrderedMap {
 31	return &OrderedMap{m: map[string]string{}}
 32}
 33
 34// Len returns the number of entries.
 35func (o *OrderedMap) Len() int { return len(o.keys) }
 36
 37// Set inserts or updates k. Updating an existing key keeps its original
 38// position — insertion order means FIRST insertion. Returns false when the map
 39// is full and k is new.
 40func (o *OrderedMap) Set(k, v string) bool {
 41	if _, ok := o.m[k]; ok {
 42		o.m[k] = v
 43		return true
 44	}
 45	if len(o.keys) >= MaxKeys {
 46		return false
 47	}
 48	o.m[k] = v
 49	o.keys = append(o.keys, k)
 50	return true
 51}
 52
 53// Get returns the value for k.
 54func (o *OrderedMap) Get(k string) (string, bool) {
 55	v, ok := o.m[k]
 56	return v, ok
 57}
 58
 59// Has reports whether k is present.
 60func (o *OrderedMap) Has(k string) bool {
 61	_, ok := o.m[k]
 62	return ok
 63}
 64
 65// Delete removes k and reports whether it was present. O(n): the key's slot in
 66// the order slice has to be closed up, and the remaining keys shifted, so that
 67// order is preserved.
 68func (o *OrderedMap) Delete(k string) bool {
 69	if _, ok := o.m[k]; !ok {
 70		return false
 71	}
 72	delete(o.m, k)
 73	for i, kk := range o.keys {
 74		if kk == k {
 75			o.keys = append(o.keys[:i], o.keys[i+1:]...)
 76			break
 77		}
 78	}
 79	return true
 80}
 81
 82// Keys returns the keys in insertion order, as an independent copy.
 83func (o *OrderedMap) Keys() []string {
 84	out := make([]string, len(o.keys))
 85	copy(out, o.keys)
 86	return out
 87}
 88
 89// Values returns the values in key-insertion order.
 90func (o *OrderedMap) Values() []string {
 91	out := make([]string, 0, len(o.keys))
 92	for _, k := range o.keys {
 93		out = append(out, o.m[k])
 94	}
 95	return out
 96}
 97
 98// Iterate calls fn for each entry in insertion order, stopping early if fn
 99// returns true. The map must not be mutated from inside fn — the walk is over
100// a live slice.
101func (o *OrderedMap) Iterate(fn func(k, v string) bool) {
102	for _, k := range o.keys {
103		if fn(k, o.m[k]) {
104			return
105		}
106	}
107}
108
109// At returns the i-th entry in insertion order.
110func (o *OrderedMap) At(i int) (k, v string, ok bool) {
111	if i < 0 || i >= len(o.keys) {
112		return "", "", false
113	}
114	k = o.keys[i]
115	return k, o.m[k], true
116}
117
118// Clone returns an independent copy preserving order.
119func (o *OrderedMap) Clone() *OrderedMap {
120	c := New()
121	for _, k := range o.keys {
122		c.Set(k, o.m[k])
123	}
124	return c
125}