- Kind
- Pure package
- Name
- v0
- Namespace
- nt / avl
- Exported functions
- n/a — not supported for pure packages by the node (vm/qfuncs)
- Module
- gno.land/p/nt/avl/v0
- gno
- 0.9
tree.gnogno
1package avl23type ITree interface {4 // read operations56 Size() int7 Has(key string) bool
not supported for pure packages by the node (vm/qfuncs)
Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.
8
Get(key string) any
9 GetByIndex(index int) (key string, value any)
10 Iterate(start, end string, cb IterCbFn) bool
11 ReverseIterate(start, end string, cb IterCbFn) bool
12 IterateByOffset(offset int, count int, cb IterCbFn) bool
13 ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool
14
15 // write operations
16
17 Set(key string, value any) (updated bool)
18 Remove(key string) (value any, removed bool)
19}
20
21type IterCbFn func(key string, value any) bool
22
23//----------------------------------------
24// Tree
25
26// The zero struct can be used as an empty tree.
27type Tree struct {
28 node *Node
29}
30
31// NewTree creates a new empty AVL tree.
32func NewTree() *Tree {
33 return &Tree{
34 node: nil,
35 }
36}
37
38// Size returns the number of key-value pair in the tree.
39func (tree *Tree) Size() int {
40 return tree.node.Size()
41}
42
43// Has checks whether a key exists in the tree.
44// It returns true if the key exists, otherwise false.
45func (tree *Tree) Has(key string) (has bool) {
46 return tree.node.Has(key)
47}
48
49// Get retrieves the value associated with the given key.
50// It returns the value if the key exists, or nil if it doesn't.
51// Note that a key stored with a nil value is indistinguishable
52// from an absent key; use Has to check for existence.
53// This allows for a simpler usage pattern with type assertions:
54//
55// if value, ok := tree.Get("key").(MyType); ok {
56// // use value
57// }
58func (tree *Tree) Get(key string) any {
59 _, value, _ := tree.node.Get(key)
60 return value
61}
62
63// GetByIndex retrieves the key-value pair at the specified index in the tree.
64// It returns the key and value at the given index.
65func (tree *Tree) GetByIndex(index int) (key string, value any) {
66 return tree.node.GetByIndex(index)
67}
68
69// Set inserts a key-value pair into the tree.
70// If the key already exists, the value will be updated.
71// It returns a boolean indicating whether the key was newly inserted or updated.
72func (tree *Tree) Set(key string, value any) (updated bool) {
73 newnode, updated := tree.node.Set(key, value)
74 tree.node = newnode
75 return updated
76}
77
78// Remove removes a key-value pair from the tree.
79// It returns the removed value and a boolean indicating whether the key was found and removed.
80func (tree *Tree) Remove(key string) (value any, removed bool) {
81 newnode, _, value, removed := tree.node.Remove(key)
82 tree.node = newnode
83 return value, removed
84}
85
86// Iterate performs an in-order traversal of the tree within the specified key range.
87// It calls the provided callback function for each key-value pair encountered.
88// If the callback returns true, the iteration is stopped.
89func (tree *Tree) Iterate(start, end string, cb IterCbFn) bool {
90 return tree.node.TraverseInRange(start, end, true, true,
91 func(node *Node) bool {
92 return cb(node.Key(), node.Value())
93 },
94 )
95}
96
97// ReverseIterate performs a reverse in-order traversal of the tree within the specified key range.
98// It calls the provided callback function for each key-value pair encountered.
99// If the callback returns true, the iteration is stopped.
100func (tree *Tree) ReverseIterate(start, end string, cb IterCbFn) bool {
101 return tree.node.TraverseInRange(start, end, false, true,
102 func(node *Node) bool {
103 return cb(node.Key(), node.Value())
104 },
105 )
106}
107
108// IterateByOffset performs an in-order traversal of the tree starting from the specified offset.
109// It calls the provided callback function for each key-value pair encountered, up to the specified count.
110// If the callback returns true, the iteration is stopped.
111func (tree *Tree) IterateByOffset(offset int, count int, cb IterCbFn) bool {
112 return tree.node.TraverseByOffset(offset, count, true, true,
113 func(node *Node) bool {
114 return cb(node.Key(), node.Value())
115 },
116 )
117}
118
119// ReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset.
120// It calls the provided callback function for each key-value pair encountered, up to the specified count.
121// If the callback returns true, the iteration is stopped.
122func (tree *Tree) ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool {
123 return tree.node.TraverseByOffset(offset, count, false, true,
124 func(node *Node) bool {
125 return cb(node.Key(), node.Value())
126 },
127 )
128}
129
130// Verify that Tree implements TreeInterface
131var _ ITree = (*Tree)(nil)
132