README
¶
Immutable AA Trees
A persistent implementation of AA Trees (paper), including the join-based tree algorithms, and augmented with order statistics.
Documentation
¶
Overview ¶
Package aa implements immutable AA trees.
Index ¶
- func Equal[K cmp.Ordered, V comparable](t1, t2 *Tree[K, V]) bool
- func Overlap[K cmp.Ordered, V any](t1, t2 *Tree[K, V]) bool
- func Subset[K cmp.Ordered, V comparable](t1, t2 *Tree[K, V]) bool
- type Tree
- func Difference[K cmp.Ordered, V any](t1, t2 *Tree[K, V]) *Tree[K, V]
- func Intersection[K cmp.Ordered, V any](t1, t2 *Tree[K, V]) *Tree[K, V]
- func MakeMap[K cmp.Ordered, V any](m map[K]V) *Tree[K, V]
- func MakeSet[K cmp.Ordered](keys ...K) *Tree[K, struct{}]
- func SymmetricDifference[K cmp.Ordered, V any](t1, t2 *Tree[K, V]) *Tree[K, V]
- func Union[K cmp.Ordered, V any](t1, t2 *Tree[K, V]) *Tree[K, V]
- func (tree *Tree[K, V]) Add(key K) *Tree[K, V]
- func (tree *Tree[K, V]) Ascend() iter.Seq2[K, V]
- func (tree *Tree[K, V]) AscendCeil(pivot K) iter.Seq2[K, V]
- func (tree *Tree[K, V]) AscendFloor(pivot K) iter.Seq2[K, V]
- func (tree *Tree[K, V]) Ceil(key K) *Tree[K, V]
- func (tree *Tree[K, V]) Collect() map[K]V
- func (tree *Tree[K, V]) Delete(key K, pred ...func(node *Tree[K, V]) bool) *Tree[K, V]
- func (tree *Tree[K, V]) DeleteMax() (_, node *Tree[K, V])
- func (tree *Tree[K, V]) DeleteMin() (_, node *Tree[K, V])
- func (tree *Tree[K, V]) Descend() iter.Seq2[K, V]
- func (tree *Tree[K, V]) DescendCeil(pivot K) iter.Seq2[K, V]
- func (tree *Tree[K, V]) DescendFloor(pivot K) iter.Seq2[K, V]
- func (tree *Tree[K, V]) Filter(pred func(node *Tree[K, V]) bool) *Tree[K, V]
- func (tree *Tree[K, V]) Floor(key K) *Tree[K, V]
- func (tree *Tree[K, V]) Get(key K) (value V, found bool)
- func (tree *Tree[K, V]) Has(key K) bool
- func (tree *Tree[K, V]) Key() K
- func (tree *Tree[K, V]) Left() *Tree[K, V]
- func (tree *Tree[K, V]) Len() int
- func (tree *Tree[K, V]) Level() int
- func (tree *Tree[K, V]) Max() *Tree[K, V]
- func (tree *Tree[K, V]) Min() *Tree[K, V]
- func (tree *Tree[K, V]) Partition(pred func(node *Tree[K, V]) bool) (t, f *Tree[K, V])
- 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]) Rank(key K) int
- func (tree *Tree[K, V]) Right() *Tree[K, V]
- func (tree *Tree[K, V]) Select(i int) *Tree[K, V]
- func (tree *Tree[K, V]) Split(key K) (left, node, right *Tree[K, V])
- func (tree *Tree[K, V]) Value() V
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Equal ¶ added in v0.3.7
func Equal[K cmp.Ordered, V comparable](t1, t2 *Tree[K, V]) bool
Equal reports whether two trees contain the same key/value pairs.
Types ¶
type Tree ¶
Tree is an immutable AA tree, a form of self-balancing binary search tree.
Use *Tree as a reference type; the zero value for *Tree (nil) is the empty tree:
var empty *aa.Tree[int, string] one := empty.Put(1, "one") one.Has(1) ⟹ true
Note: the zero value for Tree{} is a valid — but non-empty — tree.
func Difference ¶ added in v0.3.2
Difference returns the set difference of two trees.
func Intersection ¶ added in v0.3.2
Intersection returns the set intersection of two trees, first value wins.
func SymmetricDifference ¶ added in v0.3.3
SymmetricDifference returns the set symmetric difference of two trees.
func (*Tree[K, V]) Add ¶
Add returns a (possibly) modified tree that contains key.
tree.Add(key).Has(key) ⟹ true
func (*Tree[K, V]) AscendCeil ¶ added in v0.3.0
AscendCeil returns an ascending iterator for this tree, starting at the least key in this tree greater-than or equal-to pivot.
func (*Tree[K, V]) AscendFloor ¶ added in v0.3.0
AscendFloor returns an ascending iterator for this tree, starting at the greatest key in this tree less-than or equal-to pivot.
func (*Tree[K, V]) Ceil ¶ added in v0.2.0
Ceil finds the least key in this tree greater-than or equal-to key, and returns the node for that key, or nil if no such key exists in this tree.
func (*Tree[K, V]) Collect ¶ added in v0.3.4
func (tree *Tree[K, V]) Collect() map[K]V
Collect collects key-value pairs from this tree into a new map and returns it.
func (*Tree[K, V]) Delete ¶
Delete returns a (possibly) modified tree with key removed from it. The optional pred is called to confirm deletion.
tree.Delete(key).Has(key) ⟹ false
func (*Tree[K, V]) DeleteMax ¶ added in v0.3.0
DeleteMax returns a modified tree with its greatest key removed from it, and the removed node.
func (*Tree[K, V]) DeleteMin ¶ added in v0.3.0
DeleteMin returns a modified tree with its least key removed from it, and the removed node.
func (*Tree[K, V]) DescendCeil ¶ added in v0.3.0
DescendCeil returns a descending iterator for this tree, starting at the least key in this tree greater-than or equal-to pivot.
func (*Tree[K, V]) DescendFloor ¶ added in v0.3.0
DescendFloor returns a descending iterator for this tree, starting at the greatest key in this tree less-than or equal-to pivot.
func (*Tree[K, V]) Filter ¶ added in v0.3.3
Filter returns a tree of nodes for which pred returns true.
func (*Tree[K, V]) Floor ¶ added in v0.2.0
Floor finds the greatest key in this tree less-than or equal-to key, and returns the node for that key, or nil if no such key exists in this tree.
func (*Tree[K, V]) Get ¶
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 ¶
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 ¶
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]) Max ¶ added in v0.3.0
Max finds the greatest key in this tree, and returns the node for that key, or nil if this tree is empty.
func (*Tree[K, V]) Min ¶ added in v0.3.0
Min finds the least key in this tree, and returns the node for that key, or nil if this tree is empty.
func (*Tree[K, V]) Partition ¶ added in v0.3.3
Partition returns a tree of nodes for which pred returns true, and a tree of nodes for which it returns false.
func (*Tree[K, V]) Patch ¶
Patch finds 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 ¶
Put returns a modified tree with key set to value.
tree.Put(key, value).Get(key) ⟹ (value, true)
func (*Tree[K, V]) Rank ¶ added in v0.3.6
Rank finds the rank of key, the number of nodes in this tree less than key.
tree.Rank(tree.Select(i).Key()) ⟹ i, iff 0 ≤ i < tree.Len()
func (*Tree[K, V]) Right ¶
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]) Select ¶ added in v0.3.6
Select finds the node at index i of this tree and returns it (or nil if i is out of range).
Source Files