tree.gno

  1package avl
  2
  3type ITree interface {
  4	// read operations
  5
  6	Size() int
  7	Has(key string) bool
  8	Get(key string) (value any, exists bool)
  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 and a boolean indicating whether the key exists.
 51func (tree *Tree) Get(key string) (value any, 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 any) {
 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 any) (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 any, 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)