avl: git.schwanenlied.me/yawning/avl.git Index | Examples | Files

package avl

import "git.schwanenlied.me/yawning/avl.git"

Package avl implements an AVL tree.

Code:

// example_test.go - AVL tree example.
//
// To the extent possible under law, Yawning Angel has waived all copyright
// and related or neighboring rights to avl, using the Creative
// Commons "CC0" public domain dedication. See LICENSE or
// <http://creativecommons.org/publicdomain/zero/1.0/> for full details.

package main

import "fmt"

func CompareIntegers(a, b interface{}) int {
    // Returns < 0, 0, > 1 if a < b, a == b, a > b respectively.
    return a.(int) - b.(int)
}

func main() {
    // Create a new tree that will store integers.
    tree := New(CompareIntegers)

    // Insert a handful of integers in random order.
    s := []int{5, 2, 6, 3, 1, 4}
    for _, i := range s {
        tree.Insert(i)
    }

    // Traverse the tree forward in-order.
    forwardInOrder := make([]int, 0, len(s))
    tree.ForEach(Forward, func(node *Node) bool {
        forwardInOrder = append(forwardInOrder, node.Value.(int))
        return true
    })

    fmt.Println(forwardInOrder)

    // Traverse the tree backward using an interator.
    backwardInOrder := make([]int, 0, len(s))
    iter := tree.Iterator(Backward)
    for node := iter.First(); node != nil; node = iter.Next() {
        backwardInOrder = append(backwardInOrder, node.Value.(int))

        // It is safe to remove the current node while iterating.
        tree.Remove(node)
    }

    fmt.Println(backwardInOrder)

    // The tree is empty after the Remove() calls.
    fmt.Println(tree.Len())

}

Index

Examples

Package Files

avl.go

type CompareFunc Uses

type CompareFunc func(a, b interface{}) int

CompareFunc is the function used to compare entries in the Tree to maintain ordering. It MUST return < 0, 0, or > 0 if a is less than, equal to, or greater than b respectively.

Note: All calls made to the comparison function will pass the user supplied value as a, and the in-Tree value as b.

type Direction Uses

type Direction int8

Direction is the direction associated with an iterator.

const (
    // Backward is backward in-order.
    Backward Direction = -1

    // Forward is forward in-order.
    Forward Direction = 1
)

type Iterator Uses

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

Iterator is a Tree iterator. Modifying the Tree while iterating is unsupported except for removing the current Node.

func (*Iterator) First Uses

func (it *Iterator) First() *Node

First moves the iterator to the first Node in the Tree and returns the first Node or nil iff the Tree is empty. Note that "first" in this context is dependent on the direction specified when constructing the iterator.

func (*Iterator) Get Uses

func (it *Iterator) Get() *Node

Get returns the Node currently pointed to by the iterator. It is safe to remove the Node returned from the Tree.

func (*Iterator) Next Uses

func (it *Iterator) Next() *Node

Next advances the iterator and returns the Node or nil iff the end of the Tree has been reached.

type Node Uses

type Node struct {
    // Value is the value stored by the Node.
    Value interface{}
    // contains filtered or unexported fields
}

Node is a node of a Tree.

type Tree Uses

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

Tree represents an AVL tree.

func New Uses

func New(cmpFn CompareFunc) *Tree

New returns an initialized Tree.

func (*Tree) Find Uses

func (t *Tree) Find(v interface{}) *Node

Find finds the value in the Tree, and returns the Node or nil iff the value is not present.

func (*Tree) First Uses

func (t *Tree) First() *Node

First returns the first node in the Tree (in-order) or nil iff the Tree is empty.

func (*Tree) ForEach Uses

func (t *Tree) ForEach(direction Direction, fn func(*Node) bool)

ForEach executes a function for each Node in the tree, visiting the nodes in-order in the direction specified. If the provided function returns false, the iteration is stopped. Modifying the Tree from within the function is unsupprted except for removing the current Node.

func (*Tree) Insert Uses

func (t *Tree) Insert(v interface{}) *Node

Insert inserts the value into the Tree, and returns the newly created Node or the existing Node iff the value is already present in the tree.

func (*Tree) Iterator Uses

func (t *Tree) Iterator(direction Direction) *Iterator

Iterator returns an iterator that traverses the tree (in-order) in the specified direction. Modifying the Tree while iterating is unsupported except for removing the current Node.

func (*Tree) Last Uses

func (t *Tree) Last() *Node

Last returns the last element in the Tree (in-order) or nil iff the Tree is empty.

func (*Tree) Len Uses

func (t *Tree) Len() int

Len returns the number of elements in the Tree.

func (*Tree) Remove Uses

func (t *Tree) Remove(node *Node)

Remove removes the Node from the Tree.

Package avl imports 1 packages (graph) and is imported by 1 packages. Updated 2018-03-31. Refresh now. Tools for package owners.