avl

package
v1.0.22 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 6, 2016 License: Apache-2.0 Imports: 1 Imported by: 0

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL