1// Package flatmap is a sorted-vector map — the STL flat_map / Abseil2// btree_map trade — as a pure, reusable package.3//4// Keys and values live in two parallel sorted slices instead of a hash table or5// a tree of nodes. Lookup is a binary search, O(log n) rather than O(1), but it6// touches contiguous memory instead of chasing pointers, iteration is already7// in key order with nothing to sort, and there is no per-entry node overhead.8// Insertion in the middle is O(n) because it shifts the tail. That is the whole9// bargain: cheap reads and cheap ordered iteration, paid for at write time.10//11// On chain the ordering is the real draw. A built-in gno map iterates in an12// unspecified order, so a Render built from one can differ between nodes — a13// consensus bug rather than a cosmetic one. A flat map is sorted by14// construction, so iteration is deterministic without a sort on every read.15//16// Appending in ascending key order is the fast path: it hits the end of the17// slice and shifts nothing.18//19// A live demo of this package is at20// [r/moul/x/daily/flatmapdemo](/r/moul/x/daily/flatmapdemo/v0).21package flatmap2223import "sort"2425// MaxEntries bounds the map so gas stays predictable.26const MaxEntries = 40962728// FlatMap is a string->string map backed by parallel sorted slices.29type FlatMap struct {30 keys []string31 vals []string32}3334// New returns an empty FlatMap.35func New() *FlatMap { return &FlatMap{} }3637// Len returns the number of entries.38func (f *FlatMap) Len() int { return len(f.keys) }3940// IsEmpty reports whether the map holds nothing.41func (f *FlatMap) IsEmpty() bool { return len(f.keys) == 0 }4243// search returns the index where key is, or would be inserted, plus whether it44// is actually present.45func (f *FlatMap) search(key string) (int, bool) {46 i := sort.SearchStrings(f.keys, key)47 return i, i < len(f.keys) && f.keys[i] == key48}4950// Get returns the value for key.51func (f *FlatMap) Get(key string) (string, bool) {52 i, found := f.search(key)53 if !found {54 return "", false55 }56 return f.vals[i], true57}5859// Has reports whether key is present.60func (f *FlatMap) Has(key string) bool { _, found := f.search(key); return found }6162// Set inserts or updates key. Returns false only when the map is full and key63// is new — updating an existing key always succeeds.64func (f *FlatMap) Set(key, value string) bool {65 i, found := f.search(key)66 if found {67 f.vals[i] = value68 return true69 }70 if len(f.keys) >= MaxEntries {71 return false72 }73 // Grow by one, then shift the tail right to open a slot at i.74 f.keys = append(f.keys, "")75 f.vals = append(f.vals, "")76 copy(f.keys[i+1:], f.keys[i:])77 copy(f.vals[i+1:], f.vals[i:])78 f.keys[i] = key79 f.vals[i] = value80 return true81}8283// Delete removes key. Returns false when absent.84func (f *FlatMap) Delete(key string) bool {85 i, found := f.search(key)86 if !found {87 return false88 }89 copy(f.keys[i:], f.keys[i+1:])90 copy(f.vals[i:], f.vals[i+1:])91 f.keys = f.keys[:len(f.keys)-1]92 f.vals = f.vals[:len(f.vals)-1]93 return true94}9596// Keys returns the keys in sorted order, as a copy.97func (f *FlatMap) Keys() []string {98 out := make([]string, len(f.keys))99 copy(out, f.keys)100 return out101}102103// Values returns the values ordered by their keys, as a copy.104func (f *FlatMap) Values() []string {105 out := make([]string, len(f.vals))106 copy(out, f.vals)107 return out108}109110// At returns the i-th entry in key order — the indexed access a hash map cannot111// offer, and one reason to pay for sorted storage.112func (f *FlatMap) At(i int) (key, value string, ok bool) {113 if i < 0 || i >= len(f.keys) {114 return "", "", false115 }116 return f.keys[i], f.vals[i], true117}118119// Iterate calls fn for each entry in key order. Returning true stops.120func (f *FlatMap) Iterate(fn func(key, value string) bool) {121 for i := range f.keys {122 if fn(f.keys[i], f.vals[i]) {123 return124 }125 }126}127128// Range calls fn for entries with lo <= key < hi, in key order. An empty hi129// means "to the end". This is the other thing sorted storage buys: a range130// query is two binary searches and a walk.131func (f *FlatMap) Range(lo, hi string, fn func(key, value string) bool) {132 start := sort.SearchStrings(f.keys, lo)133 for i := start; i < len(f.keys); i++ {134 if hi != "" && f.keys[i] >= hi {135 return136 }137 if fn(f.keys[i], f.vals[i]) {138 return139 }140 }141}142143// Clone returns an independent copy.144func (f *FlatMap) Clone() *FlatMap {145 return &FlatMap{keys: f.Keys(), vals: f.Values()}146}147148// Sorted reports whether the backing slice is in strictly ascending order.149// Always true through the public API; exported so callers can assert it.150func (f *FlatMap) Sorted() bool {151 for i := 1; i < len(f.keys); i++ {152 if f.keys[i-1] >= f.keys[i] {153 return false154 }155 }156 return len(f.keys) == len(f.vals)157}158Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.