tree.gno

  1// Package avl is a vendored copy of gno.land/p/nt/avl/v0, pinned under
  2// this project's own namespace instead of imported from the shared
  3// stdlib. Necessary because that shared package is NOT the same across
  4// gno.land networks: testnet's Tree.Get returns a single value (any),
  5// while Beta Mainnet's already returns two (value any, exists bool) —
  6// confirmed directly from each chain's own deployed source, not
  7// documentation. Code built against one signature fails to compile on
  8// the other, so this project can't depend on the shared import staying
  9// consistent across every network it deploys to. Vendoring under our
 10// own address means every deploy — local, testnet, Beta Mainnet, or
 11// wherever gno.land goes next — gets the exact same, single-return
 12// Get() this project's code (grc721 + nftminter) is written against,
 13// regardless of whatever the shared package looks like on that chain.
 14//
 15// Copied verbatim from gno.land/p/nt/avl/v0 (testnet's version, single-
 16// return Get) as of 2026-08 — not reimplemented, to avoid introducing
 17// any behavioral drift from the tested original.
 18package avl
 19
 20type ITree interface {
 21	// read operations
 22
 23	Size() int
 24	Has(key string) bool
 25	Get(key string) any
 26	GetByIndex(index int) (key string, value any)
 27	Iterate(start, end string, cb IterCbFn) bool
 28	ReverseIterate(start, end string, cb IterCbFn) bool
 29	IterateByOffset(offset int, count int, cb IterCbFn) bool
 30	ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool
 31
 32	// write operations
 33
 34	Set(key string, value any) (updated bool)
 35	Remove(key string) (value any, removed bool)
 36}
 37
 38type IterCbFn func(key string, value any) bool
 39
 40//----------------------------------------
 41// Tree
 42
 43// The zero struct can be used as an empty tree.
 44type Tree struct {
 45	node *Node
 46}
 47
 48// NewTree creates a new empty AVL tree.
 49func NewTree() *Tree {
 50	return &Tree{
 51		node: nil,
 52	}
 53}
 54
 55// Size returns the number of key-value pair in the tree.
 56func (tree *Tree) Size() int {
 57	return tree.node.Size()
 58}
 59
 60// Has checks whether a key exists in the tree.
 61// It returns true if the key exists, otherwise false.
 62func (tree *Tree) Has(key string) (has bool) {
 63	return tree.node.Has(key)
 64}
 65
 66// Get retrieves the value associated with the given key.
 67// It returns the value if the key exists, or nil if it doesn't.
 68// Note that a key stored with a nil value is indistinguishable
 69// from an absent key; use Has to check for existence.
 70// This allows for a simpler usage pattern with type assertions:
 71//
 72//	if value, ok := tree.Get("key").(MyType); ok {
 73//	    // use value
 74//	}
 75func (tree *Tree) Get(key string) any {
 76	_, value, _ := tree.node.Get(key)
 77	return value
 78}
 79
 80// GetByIndex retrieves the key-value pair at the specified index in the tree.
 81// It returns the key and value at the given index.
 82func (tree *Tree) GetByIndex(index int) (key string, value any) {
 83	return tree.node.GetByIndex(index)
 84}
 85
 86// Set inserts a key-value pair into the tree.
 87// If the key already exists, the value will be updated.
 88// It returns a boolean indicating whether the key was newly inserted or updated.
 89func (tree *Tree) Set(key string, value any) (updated bool) {
 90	newnode, updated := tree.node.Set(key, value)
 91	tree.node = newnode
 92	return updated
 93}
 94
 95// Remove removes a key-value pair from the tree.
 96// It returns the removed value and a boolean indicating whether the key was found and removed.
 97func (tree *Tree) Remove(key string) (value any, removed bool) {
 98	newnode, _, value, removed := tree.node.Remove(key)
 99	tree.node = newnode
100	return value, removed
101}
102
103// Iterate performs an in-order traversal of the tree within the specified key range.
104// It calls the provided callback function for each key-value pair encountered.
105// If the callback returns true, the iteration is stopped.
106func (tree *Tree) Iterate(start, end string, cb IterCbFn) bool {
107	return tree.node.TraverseInRange(start, end, true, true,
108		func(node *Node) bool {
109			return cb(node.Key(), node.Value())
110		},
111	)
112}
113
114// ReverseIterate performs a reverse in-order traversal of the tree within the specified key range.
115// It calls the provided callback function for each key-value pair encountered.
116// If the callback returns true, the iteration is stopped.
117func (tree *Tree) ReverseIterate(start, end string, cb IterCbFn) bool {
118	return tree.node.TraverseInRange(start, end, false, true,
119		func(node *Node) bool {
120			return cb(node.Key(), node.Value())
121		},
122	)
123}
124
125// IterateByOffset performs an in-order traversal of the tree starting from the specified offset.
126// It calls the provided callback function for each key-value pair encountered, up to the specified count.
127// If the callback returns true, the iteration is stopped.
128func (tree *Tree) IterateByOffset(offset int, count int, cb IterCbFn) bool {
129	return tree.node.TraverseByOffset(offset, count, true, true,
130		func(node *Node) bool {
131			return cb(node.Key(), node.Value())
132		},
133	)
134}
135
136// ReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset.
137// It calls the provided callback function for each key-value pair encountered, up to the specified count.
138// If the callback returns true, the iteration is stopped.
139func (tree *Tree) ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool {
140	return tree.node.TraverseByOffset(offset, count, false, true,
141		func(node *Node) bool {
142			return cb(node.Key(), node.Value())
143		},
144	)
145}
146
147// Verify that Tree implements TreeInterface
148var _ ITree = (*Tree)(nil)