1// Package cow provides a Copy-on-Write (CoW) AVL tree implementation.2// This is a fork of gno.land/p/nt/avl that adds CoW functionality3// while maintaining the original AVL tree interface and properties.4//5// Copy-on-Write creates a copy of a data structure only when it is modified,6// while still presenting the appearance of a full copy. When a tree is cloned,7// it initially shares all its nodes with the original tree. Only when a8// modification is made to either the original or the clone are new nodes created,9// and only along the path from the root to the modified node.10//11// Key features:12// - O(1) cloning operation13// - Minimal memory usage through structural sharing14// - Full AVL tree functionality (self-balancing, ordered operations)15// - Thread-safe for concurrent reads of shared structures16//17// While the CoW mechanism handles structural copying automatically, users need18// to consider how to handle the values stored in the tree:19//20// 1. Simple Values (int, string, etc.):21// - These are copied by value automatically22// - No additional handling needed23//24// 2. Complex Values (structs, pointers):25// - Only the reference is copied by default26// - Users must implement their own deep copy mechanism if needed27//28// Example:29//30// // Create original tree31// original := cow.NewTree()32// original.Set("key1", "value1")33//34// // Create a clone - O(1) operation35// clone := original.Clone()36//37// // Modify clone - only affected nodes are copied38// clone.Set("key1", "modified")39//40// // Original remains unchanged41// val, _ := original.Get("key1") // Returns "value1"42package cow4344type IterCbFn func(key string, value any) bool4546//----------------------------------------47// Tree4849// The zero struct can be used as an empty tree.50type Tree struct {51 node *Node52}5354// NewTree creates a new empty AVL tree.55func NewTree() *Tree {56 return &Tree{57 node: nil,58 }59}6061// Size returns the number of key-value pair in the tree.62func (tree *Tree) Size() int {63 return tree.node.Size()64}6566// Has checks whether a key exists in the tree.67// It returns true if the key exists, otherwise false.68func (tree *Tree) Has(key string) (has bool) {69 return tree.node.Has(key)70}7172// Get retrieves the value associated with the given key.73// It returns the value and a boolean indicating whether the key exists.74func (tree *Tree) Get(key string) (value any, exists bool) {75 _, value, exists = tree.node.Get(key)76 return77}7879// GetByIndex retrieves the key-value pair at the specified index in the tree.80// It returns the key and value at the given index.81func (tree *Tree) GetByIndex(index int) (key string, value any) {82 return tree.node.GetByIndex(index)83}8485// Set inserts a key-value pair into the tree.86// If the key already exists, the value will be updated.87// It returns a boolean indicating whether the key was newly inserted or updated.88func (tree *Tree) Set(key string, value any) (updated bool) {89 newnode, updated := tree.node.Set(key, value)90 tree.node = newnode91 return updated92}9394// Remove removes a key-value pair from the tree.95// It returns the removed value and a boolean indicating whether the key was found and removed.96func (tree *Tree) Remove(key string) (value any, removed bool) {97 newnode, _, value, removed := tree.node.Remove(key)98 tree.node = newnode99 return value, removed100}101102// Iterate performs an in-order traversal of the tree within the specified key range.103// It calls the provided callback function for each key-value pair encountered.104// If the callback returns true, the iteration is stopped.105func (tree *Tree) Iterate(start, end string, cb IterCbFn) bool {106 return tree.node.TraverseInRange(start, end, true, true,107 func(node *Node) bool {108 return cb(node.Key(), node.Value())109 },110 )111}112113// ReverseIterate performs a reverse in-order traversal of the tree within the specified key range.114// It calls the provided callback function for each key-value pair encountered.115// If the callback returns true, the iteration is stopped.116func (tree *Tree) ReverseIterate(start, end string, cb IterCbFn) bool {117 return tree.node.TraverseInRange(start, end, false, true,118 func(node *Node) bool {119 return cb(node.Key(), node.Value())120 },121 )122}123124// IterateByOffset performs an in-order traversal of the tree starting from the specified offset.125// It calls the provided callback function for each key-value pair encountered, up to the specified count.126// If the callback returns true, the iteration is stopped.127func (tree *Tree) IterateByOffset(offset int, count int, cb IterCbFn) bool {128 return tree.node.TraverseByOffset(offset, count, true, true,129 func(node *Node) bool {130 return cb(node.Key(), node.Value())131 },132 )133}134135// ReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset.136// It calls the provided callback function for each key-value pair encountered, up to the specified count.137// If the callback returns true, the iteration is stopped.138func (tree *Tree) ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool {139 return tree.node.TraverseByOffset(offset, count, false, true,140 func(node *Node) bool {141 return cb(node.Key(), node.Value())142 },143 )144}145146// Equal returns true if the two trees contain the same key-value pairs.147// WARNING: This is an expensive operation that recursively traverses the entire tree structure.148// It should only be used in tests or when absolutely necessary.149func (tree *Tree) Equal(other *Tree) bool {150 if tree == nil || other == nil {151 return tree == other152 }153 return tree.node.Equal(other.node)154}155156// Clone creates a shallow copy of the tree157func (tree *Tree) Clone() *Tree {158 if tree == nil {159 return nil160 }161 return &Tree{162 node: tree.node,163 }164}165Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.