aa

README

Immutable AA Trees

https://en.wikipedia.org/wiki/AA_tree
https://user.it.uu.se/~arnea/ps/simp.pdf

Documentation

Overview

Package aa implements immutable AA trees.

Index

• type Tree
  • func (tree *Tree[K, V]) Add(key K) *Tree[K, V]
  • func (tree *Tree[K, V]) All() func(yield func(node *Tree[K, V]) bool)
  • func (tree *Tree[K, V]) Contains(key K) bool
  • func (tree *Tree[K, V]) Delete(key K) *Tree[K, V]
  • func (tree *Tree[K, V]) Get(key K) (value V, found bool)
  • func (tree *Tree[K, V]) Key() K
  • func (tree *Tree[K, V]) Left() *Tree[K, V]
  • func (tree *Tree[K, V]) Level() int
  • func (tree *Tree[K, V]) Patch(key K, update func(node *Tree[K, V]) (value V, ok bool)) *Tree[K, V]
  • func (tree *Tree[K, V]) Put(key K, value V) *Tree[K, V]
  • func (tree *Tree[K, V]) Right() *Tree[K, V]
  • func (tree *Tree[K, V]) Value() V

Types

type Tree

type Tree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Tree is an immutable AA tree, a form of self-balancing binary search tree.

Use *Tree as reference type; the zero value for *Tree (nil) is the empty tree:

var empty *aa.Tree[int, string]
one := empty.Put(1, "one")
one.Contains(1) ⟹ true

Note: the zero value for Tree{} is a valid, but non-empty, tree.

func (*Tree[K, V]) Add

func (tree *Tree[K, V]) Add(key K) *Tree[K, V]

Add returns a (possibly) modified tree that contains key.

tree.Add(key).Contains(key) ⟹ true

func (*Tree[K, V]) All

func (tree *Tree[K, V]) All() func(yield func(node *Tree[K, V]) bool)

All returns an in-order iterator for this tree.

tree.All()(func(node *aa.Tree[int, any]) bool {
	fmt.Println(node.Key(), node.Value())
	return true
})

func (*Tree[K, V]) Contains

func (tree *Tree[K, V]) Contains(key K) bool

Contains reports whether key exists in this tree.

func (*Tree[K, V]) Delete

func (tree *Tree[K, V]) Delete(key K) *Tree[K, V]

Delete returns a modified tree with key removed from it.

tree.Delete(key).Contains(key) ⟹ false

func (*Tree[K, V]) Get

func (tree *Tree[K, V]) Get(key K) (value V, found bool)

Get retrieves the value for a given key; found indicates whether key exists in this tree.

func (*Tree[K, V]) Key

func (tree *Tree[K, V]) Key() K

Key returns the key at the root of this tree.

Note: getting the root key of an empty tree (nil) causes a runtime panic.

func (*Tree[K, V]) Left

func (tree *Tree[K, V]) Left() *Tree[K, V]

Left returns the left subtree of this tree, containing all keys less than its root key.

Note: the left subtree of the empty tree is the empty tree (nil).

func (*Tree[K, V]) Level

func (tree *Tree[K, V]) Level() int

Level returns the level of this AA tree.

Notes:

• the level of the empty tree (nil) is 0.
• the height of a tree of level n is between n and 2·n.
• the number of nodes in a tree of level n is between 2ⁿ-1 and 3ⁿ-1.

func (*Tree[K, V]) Patch

func (tree *Tree[K, V]) Patch(key K, update func(node *Tree[K, V]) (value V, ok bool)) *Tree[K, V]

Patch looks for key in this tree, calls update with the node for that key (or nil, if key is not found), and returns a possibly modified tree.

The update callback can opt to set/update the value for the key, by returning (value, true), or not, by returning false.

func (*Tree[K, V]) Put

func (tree *Tree[K, V]) Put(key K, value V) *Tree[K, V]

Put returns a modified tree with key set to value.

tree.Put(key, value).Get(key) ⟹ (value, true)

func (*Tree[K, V]) Right

func (tree *Tree[K, V]) Right() *Tree[K, V]

Right returns the right subtree of this tree, containing all keys greater than its root key.

Note: the right subtree of the empty tree is the empty tree (nil).

func (*Tree[K, V]) Value

func (tree *Tree[K, V]) Value() V

Value returns the value at the root of this tree.

Note: getting the root value of an empty tree (nil) causes a runtime panic.