tree.gno

  1// Package cow provides a Copy-on-Write (CoW) AVL tree implementation.
  2// This is a fork of gno.land/p/demo/avl that adds CoW functionality
  3// 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 a
  8// 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 operation
 13//   - Minimal memory usage through structural sharing
 14//   - Full AVL tree functionality (self-balancing, ordered operations)
 15//   - Thread-safe for concurrent reads of shared structures
 16//
 17// While the CoW mechanism handles structural copying automatically, users need
 18// 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 automatically
 22//     - No additional handling needed
 23//
 24//  2. Complex Values (structs, pointers):
 25//     - Only the reference is copied by default
 26//     - Users must implement their own deep copy mechanism if needed
 27//
 28// Example:
 29//
 30//	// Create original tree
 31//	original := cow.NewTree()
 32//	original.Set("key1", "value1")
 33//
 34//	// Create a clone - O(1) operation
 35//	clone := original.Clone()
 36//
 37//	// Modify clone - only affected nodes are copied
 38//	clone.Set("key1", "modified")
 39//
 40//	// Original remains unchanged
 41//	val, _ := original.Get("key1") // Returns "value1"
 42package cow
 43
 44type IterCbFn func(key string, value any) bool
 45
 46//----------------------------------------
 47// Tree
 48
 49// The zero struct can be used as an empty tree.
 50type Tree struct {
 51	node *Node
 52}
 53
 54// NewTree creates a new empty AVL tree.
 55func NewTree() *Tree {
 56	return &Tree{
 57		node: nil,
 58	}
 59}
 60
 61// Size returns the number of key-value pair in the tree.
 62func (tree *Tree) Size() int {
 63	return tree.node.Size()
 64}
 65
 66// 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}
 71
 72// 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	return
 77}
 78
 79// 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}
 84
 85// 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 = newnode
 91	return updated
 92}
 93
 94// 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 = newnode
 99	return value, removed
100}
101
102// 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}
112
113// 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}
123
124// 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}
134
135// 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}
145
146// 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 == other
152	}
153	return tree.node.Equal(other.node)
154}
155
156// Clone creates a shallow copy of the tree
157func (tree *Tree) Clone() *Tree {
158	if tree == nil {
159		return nil
160	}
161	return &Tree{
162		node: tree.node,
163	}
164}