tree.gno
5.58 Kb · 164 lines
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 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}
