tree.gno

  1package avl
  2
  3type ITree interface {
  4	// read operations
  5
  6	Size() int
  7	Has(key string) bool
  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)