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

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    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.