gno.land/p/moul/x/daily/orderedmap/v0⧉

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 is5// unspecified, so a realm that ranges over a built-in map to build its Render6// can emit a different page on every call — which is a consensus bug, not a7// cosmetic one. This type gives back a deterministic order without needing the8// keys to be sortable.9//10// Backed by a built-in map for O(1) lookup plus a slice holding insertion11// order. Delete is O(n) in the number of keys, because it has to close the gap12// 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 at17// [r/moul/x/daily/orderedmapdemo](/r/moul/x/daily/orderedmapdemo/v0).18package orderedmap1920// MaxKeys bounds the map so gas stays predictable.21const MaxKeys = 40962223// OrderedMap is a string-keyed map with deterministic iteration.24type OrderedMap struct {25	m    map[string]string26	keys []string27}2829// New returns an empty OrderedMap.30func New() *OrderedMap {31	return &OrderedMap{m: map[string]string{}}32}3334// Len returns the number of entries.35func (o *OrderedMap) Len() int { return len(o.keys) }3637// Set inserts or updates k. Updating an existing key keeps its original38// position — insertion order means FIRST insertion. Returns false when the map39// 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] = v43		return true44	}45	if len(o.keys) >= MaxKeys {46		return false47	}48	o.m[k] = v49	o.keys = append(o.keys, k)50	return true51}5253// Get returns the value for k.54func (o *OrderedMap) Get(k string) (string, bool) {55	v, ok := o.m[k]56	return v, ok57}5859// Has reports whether k is present.60func (o *OrderedMap) Has(k string) bool {61	_, ok := o.m[k]62	return ok63}6465// Delete removes k and reports whether it was present. O(n): the key's slot in66// the order slice has to be closed up, and the remaining keys shifted, so that67// order is preserved.68func (o *OrderedMap) Delete(k string) bool {69	if _, ok := o.m[k]; !ok {70		return false71	}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			break77		}78	}79	return true80}8182// 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 out87}8889// 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 out96}9798// Iterate calls fn for each entry in insertion order, stopping early if fn99// returns true. The map must not be mutated from inside fn — the walk is over100// 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			return105		}106	}107}108109// 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 "", "", false113	}114	k = o.keys[i]115	return k, o.m[k], true116}117118// 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 c125}126