1package avl
2
3type ITree interface {
4 // read operations
5
6 Size() int
7 Has(key string) bool
8 Get(key string) (value interface{}, exists bool)
9 GetByIndex(index int) (key string, value interface{})
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 interface{}) (updated bool)
18 Remove(key string) (value interface{}, removed bool)
19}
20
21type IterCbFn func(key string, value interface{}) 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 and a boolean indicating whether the key exists.
51func (tree *Tree) Get(key string) (value interface{}, exists bool) {
52 _, value, exists = tree.node.Get(key)
53 return
54}
55
56// GetByIndex retrieves the key-value pair at the specified index in the tree.
57// It returns the key and value at the given index.
58func (tree *Tree) GetByIndex(index int) (key string, value interface{}) {
59 return tree.node.GetByIndex(index)
60}
61
62// Set inserts a key-value pair into the tree.
63// If the key already exists, the value will be updated.
64// It returns a boolean indicating whether the key was newly inserted or updated.
65func (tree *Tree) Set(key string, value interface{}) (updated bool) {
66 newnode, updated := tree.node.Set(key, value)
67 tree.node = newnode
68 return updated
69}
70
71// Remove removes a key-value pair from the tree.
72// It returns the removed value and a boolean indicating whether the key was found and removed.
73func (tree *Tree) Remove(key string) (value interface{}, removed bool) {
74 newnode, _, value, removed := tree.node.Remove(key)
75 tree.node = newnode
76 return value, removed
77}
78
79// Iterate performs an in-order traversal of the tree within the specified key range.
80// It calls the provided callback function for each key-value pair encountered.
81// If the callback returns true, the iteration is stopped.
82func (tree *Tree) Iterate(start, end string, cb IterCbFn) bool {
83 return tree.node.TraverseInRange(start, end, true, true,
84 func(node *Node) bool {
85 return cb(node.Key(), node.Value())
86 },
87 )
88}
89
90// ReverseIterate performs a reverse in-order traversal of the tree within the specified key range.
91// It calls the provided callback function for each key-value pair encountered.
92// If the callback returns true, the iteration is stopped.
93func (tree *Tree) ReverseIterate(start, end string, cb IterCbFn) bool {
94 return tree.node.TraverseInRange(start, end, false, true,
95 func(node *Node) bool {
96 return cb(node.Key(), node.Value())
97 },
98 )
99}
100
101// IterateByOffset performs an in-order traversal of the tree starting from the specified offset.
102// It calls the provided callback function for each key-value pair encountered, up to the specified count.
103// If the callback returns true, the iteration is stopped.
104func (tree *Tree) IterateByOffset(offset int, count int, cb IterCbFn) bool {
105 return tree.node.TraverseByOffset(offset, count, true, true,
106 func(node *Node) bool {
107 return cb(node.Key(), node.Value())
108 },
109 )
110}
111
112// ReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset.
113// It calls the provided callback function for each key-value pair encountered, up to the specified count.
114// If the callback returns true, the iteration is stopped.
115func (tree *Tree) ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool {
116 return tree.node.TraverseByOffset(offset, count, false, true,
117 func(node *Node) bool {
118 return cb(node.Key(), node.Value())
119 },
120 )
121}
122
123// Verify that Tree implements TreeInterface
124var _ ITree = (*Tree)(nil)
tree.gno
4.11 Kb ยท 124 lines
