radix

README

Radix

An implementation of a radix tree in Go. See

Donald R. Morrison. "PATRICIA -- practical algorithm to retrieve
information coded in alphanumeric". Journal of the ACM, 15(4):514-534,
October 1968

Or the wikipedia article.

Usage

Get the package:

$ go get github.com/miekg/radix

Import the package:

import (
	"github.com/miekg/radix"
)

You can use the tree as a key-value structure, where every node's can have its own value (as shown in the example below), or you can of course just use it to look up strings, like so:

r := radix.New()
r.Insert("foo", true)
    x, e := r.Find("foo")
    if e {
    fmt.Printf("foo is contained: %v\n", x.Value)
    }

Documentation

For full package documentation, visit http://go.pkgdoc.org/github.com/miekg/radix.

License

This code is licensed under a BSD License:

Copyright (c) 2012 Alexander Willing and Miek Gieben. All rights reserved.
Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file.

Documentation

Overview

Package radix implements a radix tree.

A radix tree is defined in:

Donald R. Morrison. "PATRICIA -- practical algorithm to retrieve
information coded in alphanumeric". Journal of the ACM, 15(4):514-534,
October 1968

Also see http://en.wikipedia.org/wiki/Radix_tree for more information.

Index

• type Radix
  • func New() *Radix
  • func (r *Radix) Do(f func(interface{}))
  • func (r *Radix) Find(key string) (node *Radix, exact bool)
  • func (r *Radix) FindFunc(key string, f func(interface{}) bool) (node *Radix, exact bool, funcfound bool)
  • func (r *Radix) Insert(key string, value interface{}) *Radix
  • func (r *Radix) Key() (s string)
  • func (r *Radix) Len() int
  • func (r *Radix) Next() *Radix
  • func (r *Radix) NextDo(f func(interface{}))
  • func (r *Radix) Prev() *Radix
  • func (r *Radix) PrevDo(f func(interface{}))
  • func (r *Radix) Remove(key string) *Radix
  • func (r *Radix) String() string
  • func (r *Radix) Up() *Radix

Types

type Radix

type Radix struct {

	// The contents of the radix node.
	Value interface{}
	// contains filtered or unexported fields
}

Radix represents a radix tree.

func New

func New() *Radix

New returns an initialized radix tree.

func (*Radix) Do

func (r *Radix) Do(f func(interface{}))

Do traverses the tree r in an unordered fashion and calls function f on each (non-nil) node, f's parameter is r.Value.

func (*Radix) Find

func (r *Radix) Find(key string) (node *Radix, exact bool)

Find returns the node associated with key, r must be the root of the Radix tree, although this is not enforced. If the node is located it is returned and exact is set to true. If the node found has a nil Value, Find will go up in the tree to look for a non-nil Value. If this happens exact is set to false. Also if the node is not found, the immediate predecessor is returned and exact is set to false. If this node also has a nil Value the same thing happens: the tree is search upwards, until the first non-nil Value node is found.

func (*Radix) FindFunc

func (r *Radix) FindFunc(key string, f func(interface{}) bool) (node *Radix, exact bool, funcfound bool)

FindFunc works just like Find, but each non-nil Value of each node traversed during the search is given to the function f. Is this function returns true, that node is returned and the search stops, exact is set to false and funcfound to true. If during the search f does not return true FindFunc behaves just as Find.

func (*Radix) Insert

func (r *Radix) Insert(key string, value interface{}) *Radix

Insert inserts the value into the tree with the specified key. It returns the radix node it just inserted, r must the root of the radix tree.

func (*Radix) Key

func (r *Radix) Key() (s string)

Key returns the full (from r down to this node) key under which r is stored.

func (*Radix) Len

func (r *Radix) Len() int

Len computes the number of nodes in the radix tree r.

func (*Radix) Next

func (r *Radix) Next() *Radix

Next returns the next node in the tree. For non-leaf nodes this is the left most child node. For leaf nodes this is the first neighbor to the right. If no such neighbor is found, it's the first existing neighbor of a parent. This finally terminates the root of the tree. Next can return nodes with Value is nil.

func (*Radix) NextDo

func (r *Radix) NextDo(f func(interface{}))

NextDo traverses the tree r in Next-order and calls function f on each node, f's parameter is be r.Value, f will never be called with a nil value.

func (*Radix) Prev

func (r *Radix) Prev() *Radix

Prev returns the previous node in the tree, it is the opposite of Next. The following holds true: r.Next().Prev().Key() = r.Key()

func (*Radix) PrevDo

func (r *Radix) PrevDo(f func(interface{}))

PrevDo traverses the tree r in Prev-order and calls function f on each node, f's parameter is be r.Value, f will never be called with a nil value.

func (*Radix) Remove

func (r *Radix) Remove(key string) *Radix

Remove removes any value set to key. It returns the removed node or nil if the node cannot be found.

func (*Radix) String

func (r *Radix) String() string

func (*Radix) Up

func (r *Radix) Up() *Radix

Up returns the first node above r which has a non-nil Value. It terminates at the root and returns nil if that happens.