radix

README

go-radix

Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

As a radix tree, it provides the following:

• O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
• Minimum / Maximum value lookups
• Ordered iteration

For an immutable variant, see go-immutable-radix.

Documentation

The full documentation is available on Godoc.

Example

Below is a simple example of usage

// Create a tree
r := radix.New()
r.Insert("foo", 1)
r.Insert("bar", 2)
r.Insert("foobar", 2)

// Find the longest prefix match
m, _, _ := r.LongestPrefix("foozip")
if m != "foo" {
    panic("should be foo")
}

Documentation

Index

• type Tree
  • func New() *Tree
  • func NewFromMap(m map[string]interface{}) *Tree
  • func (t *Tree) Delete(s string) (interface{}, bool)
  • func (t *Tree) DeletePrefix(s string) int
  • func (t *Tree) Get(s string) (interface{}, bool)
  • func (t *Tree) Insert(s string, v interface{}) (interface{}, bool)
  • func (t *Tree) Len() int
  • func (t *Tree) LongestPrefix(s string) (string, interface{}, bool)
  • func (t *Tree) Maximum() (string, interface{}, bool)
  • func (t *Tree) Minimum() (string, interface{}, bool)
  • func (t *Tree) ToMap() map[string]interface{}
  • func (t *Tree) Walk(fn WalkFn)
  • func (t *Tree) WalkPath(path string, fn WalkFn)
  • func (t *Tree) WalkPrefix(prefix string, fn WalkFn)
• type WalkFn

Types

type Tree

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

Tree implements a radix tree. This can be treated as a Dictionary abstract data type. The main advantage over a standard hash map is prefix-based lookups and ordered iteration,

func New

func New() *Tree

New returns an empty Tree

func NewFromMap

func NewFromMap(m map[string]interface{}) *Tree

NewFromMap returns a new tree containing the keys from an existing map

func (*Tree) Delete

func (t *Tree) Delete(s string) (interface{}, bool)

Delete is used to delete a key, returning the previous value and if it was deleted

func (*Tree) DeletePrefix

func (t *Tree) DeletePrefix(s string) int

DeletePrefix is used to delete the subtree under a prefix Returns how many nodes were deleted Use this to delete large subtrees efficiently

func (*Tree) Get

func (t *Tree) Get(s string) (interface{}, bool)

Get is used to lookup a specific key, returning the value and if it was found

func (*Tree) Insert

func (t *Tree) Insert(s string, v interface{}) (interface{}, bool)

Insert is used to add a newentry or update an existing entry. Returns if updated.

func (*Tree) Len

func (t *Tree) Len() int

Len is used to return the number of elements in the tree

func (*Tree) LongestPrefix

func (t *Tree) LongestPrefix(s string) (string, interface{}, bool)

LongestPrefix is like Get, but instead of an exact match, it will return the longest prefix match.

func (*Tree) Maximum

func (t *Tree) Maximum() (string, interface{}, bool)

Maximum is used to return the maximum value in the tree

func (*Tree) Minimum

func (t *Tree) Minimum() (string, interface{}, bool)

Minimum is used to return the minimum value in the tree

func (*Tree) ToMap

func (t *Tree) ToMap() map[string]interface{}

ToMap is used to walk the tree and convert it into a map

func (*Tree) Walk

func (t *Tree) Walk(fn WalkFn)

Walk is used to walk the tree

func (*Tree) WalkPath

func (t *Tree) WalkPath(path string, fn WalkFn)

WalkPath is used to walk the tree, but only visiting nodes from the root down to a given leaf. Where WalkPrefix walks all the entries *under* the given prefix, this walks the entries *above* the given prefix.

func (*Tree) WalkPrefix

func (t *Tree) WalkPrefix(prefix string, fn WalkFn)

WalkPrefix is used to walk the tree under a prefix

type WalkFn

type WalkFn func(s string, v interface{}) bool

WalkFn is used when walking the tree. Takes a key and value, returning if iteration should be terminated.