store: github.com/biogo/store/llrb Index | Examples | Files

package llrb

import "github.com/biogo/store/llrb"

Package llrb implements Left-Leaning Red Black trees as described by Robert Sedgewick.

More details relating to the implementation are available at the following locations:

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java
http://www.teachsolaisgames.com/articles/balanced_left_leaning.html

Code:

package main

import (
    "fmt"

    "github.com/biogo/store/llrb"
)

type (
    Int           int
    IntUpperBound int
)

func (c Int) Compare(b llrb.Comparable) int {
    switch i := b.(type) {
    case Int:
        return int(c - i)
    case IntUpperBound:
        return int(c) - int(i)
    }
    panic("unknown type")
}

func (c IntUpperBound) Compare(b llrb.Comparable) int {
    var d int
    switch i := b.(type) {
    case Int:
        d = int(c) - int(i)
    case IntUpperBound:
        d = int(c - i)
    }
    if d == 0 {
        return 1
    }
    return d
}

func main() {
    values := []int{0, 1, 2, 3, 4, 2, 3, 5, 5, 65, 32, 3, 23}

    // Insert using a type that reports equality:
    {
        t := &llrb.Tree{}
        for _, v := range values {
            t.Insert(Int(v)) // Insert with replacement.
        }

        results := []int(nil)
        // More efficiently retrieved using Get(Int(3))...
        t.DoMatching(func(c llrb.Comparable) (done bool) {
            results = append(results, int(c.(Int)))
            return
        }, Int(3))

        fmt.Println("With replacement:   ", results)
    }

    // Insert using a type that does not report equality:
    {
        t := &llrb.Tree{}
        for _, v := range values {
            t.Insert(IntUpperBound(v)) // Insert without replacement.
        }

        results := []int(nil)
        t.DoMatching(func(c llrb.Comparable) (done bool) {
            results = append(results, int(c.(IntUpperBound)))
            return
        }, Int(3))

        fmt.Println("Without replacement:", results)
    }

}

Index

Examples

Package Files

llrb.go

Constants

const (
    TD234 = iota
    BU23
)
const Mode = BU23

Operation mode of the LLRB tree.

type Color Uses

type Color bool

A Color represents the color of a Node.

const (
    // Red as false give us the defined behaviour that new nodes are red. Although this
    // is incorrect for the root node, that is resolved on the first insertion.
    Red   Color = false
    Black Color = true
)

func (Color) String Uses

func (c Color) String() string

String returns a string representation of a Color.

type Comparable Uses

type Comparable interface {
    // Compare returns a value indicating the sort order relationship between the
    // receiver and the parameter.
    //
    // Given c = a.Compare(b):
    //  c < 0 if a < b;
    //  c == 0 if a == b; and
    //  c > 0 if a > b.
    //
    Compare(Comparable) int
}

A Comparable is a type that can be inserted into a Tree or used as a range or equality query on the tree,

type Node Uses

type Node struct {
    Elem        Comparable
    Left, Right *Node
    Color       Color
}

A Node represents a node in the LLRB tree.

type Operation Uses

type Operation func(Comparable) (done bool)

An Operation is a function that operates on a Comparable. If done is returned true, the Operation is indicating that no further work needs to be done and so the Do function should traverse no further.

type Tree Uses

type Tree struct {
    Root  *Node // Root node of the tree.
    Count int   // Number of elements stored.
}

A Tree manages the root node of an LLRB tree. Public methods are exposed through this type.

func (*Tree) Ceil Uses

func (t *Tree) Ceil(q Comparable) Comparable

Ceil returns the smallest value equal to or greater than the query q according to q.Compare().

func (*Tree) Delete Uses

func (t *Tree) Delete(e Comparable)

Delete deletes the node that matches e according to Compare(). Note that Compare must identify the target node uniquely and in cases where non-unique keys are used, attributes used to break ties must be used to determine tree ordering during insertion.

func (*Tree) DeleteMax Uses

func (t *Tree) DeleteMax()

DeleteMax deletes the node with the maximum value in the tree. If insertion without replacement has been used, the right-most maximum will be deleted.

func (*Tree) DeleteMin Uses

func (t *Tree) DeleteMin()

DeleteMin deletes the node with the minimum value in the tree. If insertion without replacement has been used, the left-most minimum will be deleted.

func (*Tree) Do Uses

func (t *Tree) Do(fn Operation) bool

Do performs fn on all values stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoMatching Uses

func (t *Tree) DoMatching(fn Operation, q Comparable) bool

DoMatch performs fn on all values stored in the tree that match q according to Compare, with q.Compare() used to guide tree traversal, so DoMatching() will out perform Do() with a called conditional function if the condition is based on sort order, but can not be reliably used if the condition is independent of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

func (*Tree) DoRange Uses

func (t *Tree) DoRange(fn Operation, from, to Comparable) bool

DoRange performs fn on all values stored in the tree over the interval [from, to) from left to right. If to is less than from DoRange will panic. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.

func (*Tree) DoRangeReverse Uses

func (t *Tree) DoRangeReverse(fn Operation, from, to Comparable) bool

DoRangeReverse performs fn on all values stored in the tree over the interval (to, from] from right to left. If from is less than to DoRange will panic. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships future tree operation behaviors are undefined.

func (*Tree) DoReverse Uses

func (t *Tree) DoReverse(fn Operation) bool

DoReverse performs fn on all values stored in the tree, but in reverse of sort order. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

func (*Tree) Floor Uses

func (t *Tree) Floor(q Comparable) Comparable

Floor returns the greatest value equal to or less than the query q according to q.Compare().

func (*Tree) Get Uses

func (t *Tree) Get(q Comparable) Comparable

Get returns the first match of q in the Tree. If insertion without replacement is used, this is probably not what you want.

func (*Tree) Insert Uses

func (t *Tree) Insert(e Comparable)

Insert inserts the Comparable e into the Tree at the first match found with e or when a nil node is reached. Insertion without replacement can specified by ensuring that e.Compare() never returns 0. If insert without replacement is performed, a distinct query Comparable must be used that can return 0 with a Compare() call.

func (*Tree) Len Uses

func (t *Tree) Len() int

Len returns the number of elements stored in the Tree.

func (*Tree) Max Uses

func (t *Tree) Max() Comparable

Return the maximum value stored in the tree. This will be the right-most maximum value if insertion without replacement has been used.

func (*Tree) Min Uses

func (t *Tree) Min() Comparable

Return the minimum value stored in the tree. This will be the left-most minimum value if insertion without replacement has been used.

Package llrb is imported by 212 packages. Updated 2016-07-17. Refresh now. Tools for package owners.