742110D73E4848…FC47CDE24D1B

Arguments · 9

1. #1flatmap
2. #2README.md
3. #3# `gno.land/p/moul/x/daily/flatmap/v0` **Sorted-vector map** — `New`, `Set`, `Get`, `Has`, `Delete`, `Keys`, `Values`, `At`, `Iterate`, `Range`, `Clone`, `Sorted`, `MaxEntries`. ```go import "gno.land/p/moul/x/daily/flatmap/v0" f := flatmap.New() f.Set("delta", "4"); f.Set("alpha", "1") f.Keys() // ["alpha" "delta"] — sorted by construction f.At(0) // "alpha", "1", true — indexed access f.Range("a", "c", fn) // lo inclusive, hi exclusive ``` The STL `flat_map` trade. Keys and values live in two parallel sorted slices instead of a hash table or a tree of nodes: | operation | cost | |---|---| | `Get` | O(log n) binary search over contiguous memory | | iteration | O(n), already ordered, nothing to sort | | `Set` in the middle | **O(n)** — the tail shifts | | `Set` at the end | O(1) amortised — the fast path | Cheap reads and cheap ordered iteration, paid for at write time. That trade is stated rather than hidden. On chain the ordering is the real draw: a built-in gno map iterates in an unspecified order, so a `Render` built from one can differ between nodes. A flat map is sorted by construction, so iteration is deterministic **without a sort on every read**. Sorted storage also buys two things a hash map cannot offer: `At(i)` positional access, and `Range(lo, hi)` as two binary searches and a walk — including when the bounds are not themselves keys. `Sorted()` is exported so callers can assert the invariant; it holds through the whole public API, including 200 worst-case head insertions. **Live demo:** [`r/moul/x/daily/flatmapdemo`](https://github.com/moul/gno-contracts/tree/main/r/moul/x/daily/flatmapdemo/v0) · render it at [`/r/moul/x/daily/flatmapdemo/v0`](https://gno.land/r/moul/x/daily/flatmapdemo/v0). <!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) --> --- Part of **[moul/gno-contracts](https://github.com/moul/gno-contracts)** — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage. > 🧪 **Highly experimental — potentially vibe-coded.** Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: [DISCLAIMER](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md). <!-- END GNOCONTRACTS FOOTER -->
4. #4flatmap.gno
5. #5// Package flatmap is a sorted-vector map — the STL flat_map / Abseil // btree_map trade — as a pure, reusable package. // // Keys and values live in two parallel sorted slices instead of a hash table or // a tree of nodes. Lookup is a binary search, O(log n) rather than O(1), but it // touches contiguous memory instead of chasing pointers, iteration is already // in key order with nothing to sort, and there is no per-entry node overhead. // Insertion in the middle is O(n) because it shifts the tail. That is the whole // bargain: cheap reads and cheap ordered iteration, paid for at write time. // // On chain the ordering is the real draw. A built-in gno map iterates in an // unspecified order, so a Render built from one can differ between nodes — a // consensus bug rather than a cosmetic one. A flat map is sorted by // construction, so iteration is deterministic without a sort on every read. // // Appending in ascending key order is the fast path: it hits the end of the // slice and shifts nothing. // // A live demo of this package is at // [r/moul/x/daily/flatmapdemo](/r/moul/x/daily/flatmapdemo/v0). package flatmap import "sort" // MaxEntries bounds the map so gas stays predictable. const MaxEntries = 4096 // FlatMap is a string->string map backed by parallel sorted slices. type FlatMap struct { keys []string vals []string } // New returns an empty FlatMap. func New() *FlatMap { return &FlatMap{} } // Len returns the number of entries. func (f *FlatMap) Len() int { return len(f.keys) } // IsEmpty reports whether the map holds nothing. func (f *FlatMap) IsEmpty() bool { return len(f.keys) == 0 } // search returns the index where key is, or would be inserted, plus whether it // is actually present. func (f *FlatMap) search(key string) (int, bool) { i := sort.SearchStrings(f.keys, key) return i, i < len(f.keys) && f.keys[i] == key } // Get returns the value for key. func (f *FlatMap) Get(key string) (string, bool) { i, found := f.search(key) if !found { return "", false } return f.vals[i], true } // Has reports whether key is present. func (f *FlatMap) Has(key string) bool { _, found := f.search(key); return found } // Set inserts or updates key. Returns false only when the map is full and key // is new — updating an existing key always succeeds. func (f *FlatMap) Set(key, value string) bool { i, found := f.search(key) if found { f.vals[i] = value return true } if len(f.keys) >= MaxEntries { return false } // Grow by one, then shift the tail right to open a slot at i. f.keys = append(f.keys, "") f.vals = append(f.vals, "") copy(f.keys[i+1:], f.keys[i:]) copy(f.vals[i+1:], f.vals[i:]) f.keys[i] = key f.vals[i] = value return true } // Delete removes key. Returns false when absent. func (f *FlatMap) Delete(key string) bool { i, found := f.search(key) if !found { return false } copy(f.keys[i:], f.keys[i+1:]) copy(f.vals[i:], f.vals[i+1:]) f.keys = f.keys[:len(f.keys)-1] f.vals = f.vals[:len(f.vals)-1] return true } // Keys returns the keys in sorted order, as a copy. func (f *FlatMap) Keys() []string { out := make([]string, len(f.keys)) copy(out, f.keys) return out } // Values returns the values ordered by their keys, as a copy. func (f *FlatMap) Values() []string { out := make([]string, len(f.vals)) copy(out, f.vals) return out } // At returns the i-th entry in key order — the indexed access a hash map cannot // offer, and one reason to pay for sorted storage. func (f *FlatMap) At(i int) (key, value string, ok bool) { if i < 0 || i >= len(f.keys) { return "", "", false } return f.keys[i], f.vals[i], true } // Iterate calls fn for each entry in key order. Returning true stops. func (f *FlatMap) Iterate(fn func(key, value string) bool) { for i := range f.keys { if fn(f.keys[i], f.vals[i]) { return } } } // Range calls fn for entries with lo <= key < hi, in key order. An empty hi // means "to the end". This is the other thing sorted storage buys: a range // query is two binary searches and a walk. func (f *FlatMap) Range(lo, hi string, fn func(key, value string) bool) { start := sort.SearchStrings(f.keys, lo) for i := start; i < len(f.keys); i++ { if hi != "" && f.keys[i] >= hi { return } if fn(f.keys[i], f.vals[i]) { return } } } // Clone returns an independent copy. func (f *FlatMap) Clone() *FlatMap { return &FlatMap{keys: f.Keys(), vals: f.Values()} } // Sorted reports whether the backing slice is in strictly ascending order. // Always true through the public API; exported so callers can assert it. func (f *FlatMap) Sorted() bool { for i := 1; i < len(f.keys); i++ { if f.keys[i-1] >= f.keys[i] { return false } } return len(f.keys) == len(f.vals) }
6. #6gnomod.toml
7. #7module = "gno.land/p/moul/x/daily/flatmap/v0" gno = "0.9"
8. #8/gno.MemPackageType
9. #9 MPUserProd