avl

Documentation

Overview

Package avl includes an immutable AVL tree.

AVL trees can be used as the foundation for many functional data types. Combined with a B+ tree, you can make an immutable index which serves as the backbone for many different kinds of key/value stores.

Time complexities: Space: O(n) Insert: O(log n) Delete: O(log n) Get: O(log n)

The immutable version of the AVL tree is obviously going to be slower than the mutable version but should offer higher read availability.

Index

• type Entries
• type Entry
• type Immutable
  • func NewImmutable() *Immutable
  • func (immutable *Immutable) Delete(entries ...Entry) (*Immutable, Entries)
  • func (immutable *Immutable) Get(entries ...Entry) Entries
  • func (immutable *Immutable) Insert(entries ...Entry) (*Immutable, Entries)
  • func (immutable *Immutable) Len() uint64

Types

type Entries

type Entries []Entry

Entries is a list of type Entry.

type Entry

type Entry interface {
	// Compare should return a value indicating the relationship
	// of this Entry to the provided Entry.  A -1 means this entry
	// is less than, 0 means equality, and 1 means greater than.
	Compare(Entry) int
}

Entry represents all items that can be placed into the AVL tree. They must implement a Compare method that can be used to determine the Entry's correct place in the tree. Any object can implement Compare.

type Immutable

type Immutable struct {
	// contains filtered or unexported fields
}

Immutable represents an immutable AVL tree. This is acheived by branch copying.

func NewImmutable

func NewImmutable() *Immutable

NewImmutable allocates, initializes, and returns a new immutable AVL tree.

func (*Immutable) Delete

func (immutable *Immutable) Delete(entries ...Entry) (*Immutable, Entries)

Delete will remove the provided entries from this AVL tree and return a new tree and any entries removed. If an entry could not be found, nil is returned in its place.

func (*Immutable) Get

func (immutable *Immutable) Get(entries ...Entry) Entries

Get will get the provided Entries from the tree. If no matching Entry is found, a nil is returned in its place.

func (*Immutable) Insert

func (immutable *Immutable) Insert(entries ...Entry) (*Immutable, Entries)

Insert will add the provided entries into the tree and return the new state. Also returned is a list of Entries that were overwritten. If nothing was overwritten for an Entry, a nil is returned in its place.

func (*Immutable) Len

func (immutable *Immutable) Len() uint64

Len returns the number of items in this immutable.