gno.land/p/samcrew/avl⧉

1package avl23type ITree interface {4	// read operations56	Size() int7	Has(key string) bool8	Get(key string) (value any, exists bool)9	GetByIndex(index int) (key string, value any)10	Iterate(start, end string, cb IterCbFn) bool11	ReverseIterate(start, end string, cb IterCbFn) bool12	IterateByOffset(offset int, count int, cb IterCbFn) bool13	ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool1415	// write operations1617	Set(key string, value any) (updated bool)18	Remove(key string) (value any, removed bool)19}2021type IterCbFn func(key string, value any) bool2223//----------------------------------------24// Tree2526// The zero struct can be used as an empty tree.27type Tree struct {28	node *Node29}3031// NewTree creates a new empty AVL tree.32func NewTree() *Tree {33	return &Tree{34		node: nil,35	}36}3738// Size returns the number of key-value pair in the tree.39func (tree *Tree) Size() int {40	return tree.node.Size()41}4243// 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}4849// 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	return54}5556// 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}6162// 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 = newnode68	return updated69}7071// 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 = newnode76	return value, removed77}7879// 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}8990// 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}100101// 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}111112// 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}122123// Verify that Tree implements TreeInterface124var _ ITree = (*Tree)(nil)125