radixtree

README

radixtree

Package radixtree implements multiple forms of an Adaptive Radix Tree, aka compressed trie or compact prefix tree. This data structure is useful to quickly lookup data, using only the portion of the key that prefixes existing data. It is also useful for finding items whose keys are a prefix of a search key (i.e. are found along the way when retrieving an item identified by a key), or when finding items whose keys are prefixed by the serach key (i.e. are found at or after a key). When different values are stored using keys that have a common prefix, the common part of the key is only stored once. Consider this when keys are similar to an OID, filepath, geohash, network address, etc.

This radix tree is adaptive in the sense that nodes are not constant size, having as few or many children as needed, up to the number of different key segments to traverse to the next branch or value.

An iterator for each type of radix tree allows a tree to be traversed one key segment at a time. This is useful for incremental lookups of partial keys. Iterators can be copied in order to branched a search, and copies iterated concurrently.

The implementations are optimized for Get performance and allocates 0 bytes of heap memory per Get; therefore no garbage to collect. Once the radix tree is built, it can be repeatedly searched quickly. Concurrent searches are safe since these do not modify the radixtree. Access is not synchronized (not concurrent safe with writes), allowing the caller to synchronize, if needed, in whatever manner works best for the application.

Install

$ go get github.com/gammazero/radixtree

Example

package main

import (
    "fmt"
    "github.com/gammazero/radixtree"
)

func main() {
    rt := new(radixtree.Runes)
    rt.Put("tomato", "TOMATO")
    rt.Put("tom", "TOM")
    rt.Put("tommy", "TOMMY")
    rt.Put("tornado", "TORNADO")

    val := rt.Get("tom")
    fmt.Println("Found", val)
    // Output: Found TOM

    // Find all items whose keys start with "tom"
    rt.Walk("tom", func(key fmt.Stringer, value interface{}) error {
        fmt.Println(value)
        return nil
    })
    // Output:
    // TOM
    // TOMATO
    // TOMMY

    // Find all items whose keys are a prefix of "tomato"
    rt.WalkPath("tomato", func(key string, value interface{}) error {
        fmt.Println(value)
        return nil
    })
    // Output:
    // TOM
    // TOMATO

    // Find each item whose key is a prefix of "tomato", using iterator
    iter := rt.NewIterator()
    for _, r := range "tomato" {
        if !iter.Next(r) {
            break
        }
        if val := iter.Value(); val != nil {
            fmt.Println(val)
        }
    }
    // Output:
    // TOM
    // TOMATO

    if rt.Delete("tom") {
        fmt.Println("Deleted tom")
    }
    // Output: Deleted tom

    val = rt.Get("tom")
    fmt.Println("Found", val)
    // Output: Found <nil>
}

License

MIT License

Documentation

Overview

Package radixtree implements multiple forms of an Adaptive Radix Tree, aka compressed trie or prefix tree. It is adaptive in the sense that nodes are not constant size, having as few or many children as needed, up to the number of different key segments to traverse to the next branch or value.

In a compressed radix tree, typically an edge is looked up by radix (single key symbol) and the edge label contains the key symbols to get to the next prefix branch or terminal (having a value) node, as well as a pointer the next node. This implementation puts the edge label in the next node so that there is not a separate structure for edge and node. Also, the first character of the edge label is omitted, since that is already known when descending the tree.

The implementations are optimized for Get performance and allocate 0 bytes of heap memory per Get; therefore no garbage to collect. Once the radix tree is built, it can be repeatedly searched very quickly.

The implementations are optimized for Get performance and allocates 0 bytes of heap memory per Get; therefore no garbage to collect. Once the radix tree is built, it can be repeatedly searched quickly. Concurrent searches are safe since these do not modify the radixtree. Access is not synchronized (not concurrent safe with writes), allowing the caller to synchronize, if needed, in whatever manner works best for the application.

Index

• Variables
• type InspectFunc
• type Paths
  • func NewPaths(pathSeparator string) *Paths
  • func (tree *Paths) Delete(key string) bool
  • func (tree *Paths) Get(key string) interface{}
  • func (tree *Paths) Inspect(inspectFn InspectFunc) error
  • func (tree *Paths) NewIterator() *PathsIterator
  • func (tree *Paths) PathSeparator() string
  • func (tree *Paths) Put(key string, value interface{}) bool
  • func (tree *Paths) Walk(key string, walkFn WalkFunc) error
  • func (tree *Paths) WalkPath(key string, walkFn WalkPathFunc) error
• type PathsIterator
  • func (it *PathsIterator) Copy() *PathsIterator
  • func (it *PathsIterator) Next(part string) bool
  • func (it *PathsIterator) Value() interface{}
• type Runes
  • func (tree *Runes) Delete(key string) bool
  • func (tree *Runes) Get(key string) interface{}
  • func (tree *Runes) Inspect(inspectFn InspectFunc) error
  • func (tree *Runes) NewIterator() *RunesIterator
  • func (tree *Runes) Put(key string, value interface{}) bool
  • func (tree *Runes) Walk(key string, walkFn WalkFunc) error
  • func (tree *Runes) WalkPath(key string, walkFn WalkPathFunc) error
• type RunesIterator
  • func (it *RunesIterator) Copy() *RunesIterator
  • func (it *RunesIterator) Next(r rune) bool
  • func (it *RunesIterator) Value() interface{}
• type WalkFunc
• type WalkPathFunc

Examples

• Paths.NewIterator
• Paths.Walk
• Paths.WalkPath
• Runes.NewIterator
• Runes.Walk
• Runes.WalkPath

Variables

var Skip = errors.New("skip")

Skip is a special error return from WalkFunc and WalkPathFunc

Types

type InspectFunc

type InspectFunc func(link, prefix, key string, depth, children int, value interface{}) error

InspectFunc is the type of the function called for each node visited by Inspect. The key argument contains the key at which the node is located, the depth is the distance from the root of the tree, and children is the number of children the node has.

If an error is returned, processing of Inspect stops. The sole exception is when the function returns the special value Skip. When the function returns Skip, Inspect will not descend into any children of the current node.

type Paths

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

Paths is a radix tree of paths with string keys and interface{} values. Paths splits keys by separator, for example, "/a/b/c" splits to "/a", "/b", "/c". A different path separator string may be specified by setting by calling NewPaths with a the string to use as a separator.

Non-terminal nodes have nil values, so a stored nil value is not distinguishable and is not be included in Walk or WalkPath.

func NewPaths

func NewPaths(pathSeparator string) *Paths

NewPaths creates a new Paths instance allowin the path separator to be set.

The pathSeparator splits a path key into separate segments. The default path separator is forward slash. This variable may be set to any string to allow a different path separator, multi-character strings are OK.

func (*Paths) Delete

func (tree *Paths) Delete(key string) bool

Delete removes the value associated with the given key. Returns true if a node was found for the given key. If the node or any of its ancestors becomes childless as a result, it is removed from the tree.

func (*Paths) Get

func (tree *Paths) Get(key string) interface{}

Get returns the value stored at the given key. Returns nil for internal nodes or for nodes with a value of nil.

func (*Paths) Inspect

func (tree *Paths) Inspect(inspectFn InspectFunc) error

Inspect walks every node of the tree, whether or not it holds a value, calling inspectFn with information about each node. This allows the structure of the tree to be examined and detailed statistics to be collected.

If inspectFn returns an error, the traversal is aborted. If inspectFn returns Skip, Inspect will not descend into the node's children.

The tree is traversed depth-first, in no guaranteed order.

func (*Paths) NewIterator

func (tree *Paths) NewIterator() *PathsIterator

NewIterator returns a new PathsIterator instance that begins iterating from the root of the tree.

Example

package main

import (
	"fmt"
	"strings"

	"github.com/gammazero/radixtree"
)

func main() {
	pt := new(radixtree.Paths)
	pt.Put("home/abc", "my home directory")
	pt.Put("home/abc/a1.txt", "some text")
	pt.Put("home/abc/Documents", "my documents")
	pt.Put("home/abc/Documents/pic.png", "cat pic")
	pt.Put("home/abc/Documents/stuff.pdf", "story")

	// Find item in each path segment
	parts := strings.Split("home/abc/Documents/pic.png", "/")
	iter := pt.NewIterator()
	for i, p := range parts {
		if !iter.Next(p) {
			break
		}
		value := iter.Value()
		if value != nil {
			key := strings.Join(parts[:i+1], "/")
			fmt.Println(key, "=>", value)
		}
	}
}

Output:
home/abc => my home directory
home/abc/Documents => my documents
home/abc/Documents/pic.png => cat pic

func (*Paths) PathSeparator

func (tree *Paths) PathSeparator() string

PathSeparator returns this Paths instance's path separator

func (*Paths) Put

func (tree *Paths) Put(key string, value interface{}) bool

Put inserts the value into the tree at the given key, replacing any existing items. It returns true if the put adds a new value, false if it replaces an existing value.

Note that internal nodes have nil values so a stored nil value is not distinguishable and is not included in Walks.

func (*Paths) Walk

func (tree *Paths) Walk(key string, walkFn WalkFunc) error

Walk visits all nodes whose keys match or are are prefixed by the specified key, calling walkFn for each value found. If walkFn returns an error, the walk is aborted. If walkFn returns Skip, Walk will not descend into the node's children. Use empty key "" to visit all nodes.

The tree is traversed depth-first, in no guaranteed order.

Walk can be thought of as GetItemsWithPrefix(key)

Example

nolint errcheck // Walk only returns error is user function returns error

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	pt := new(radixtree.Paths)
	pt.Put("home/abc", "my home directory")
	pt.Put("home/abc/a1.txt", "some text")
	pt.Put("home/abc/Documents", "my documents")
	pt.Put("home/abc/Documents/pic.png", "cat pic")
	pt.Put("home/abc/Documents/stuff.pdf", "story")

	// Find all items with keys that start with "home/abc/Documents"
	pt.Walk("home/abc/Documents", func(key fmt.Stringer, value interface{}) error {
		fmt.Println(value)
		return nil
	})
}

func (*Paths) WalkPath

func (tree *Paths) WalkPath(key string, walkFn WalkPathFunc) error

WalkPath walks the path in tree from the root to the node at the given key, calling walkFn for each node that has a value. If walkFn returns an error, the walk is aborted and returns the error. If walkFn returns Skip, WalkPath is aborted but does not return an error.

The tree is traversed in the order of path segments in the key.

WalkPath can be thought of as GetItemsThatArePrefixOf((key)

Example

nolint errcheck // WalkPath only returns error is user function returns error

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	pt := new(radixtree.Paths)
	pt.Put("home/abc", "my home directory")
	pt.Put("home/abc/a1.txt", "some text")
	pt.Put("home/abc/Documents", "my documents")
	pt.Put("home/abc/Documents/pic.png", "cat pic")
	pt.Put("home/abc/Documents/stuff.pdf", "story")

	// Find item in each path segment
	pt.WalkPath("home/abc/Documents/pic.png", func(key string, value interface{}) error {
		fmt.Println(key, "=>", value)
		return nil
	})
}

Output:
home/abc => my home directory
home/abc/Documents => my documents
home/abc/Documents/pic.png => cat pic

type PathsIterator

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

PathsIterator traverses a Paths radix tree one path segment at a time.

Note: Any modification to the tree invalidates the iterator.

func (*PathsIterator) Copy

func (it *PathsIterator) Copy() *PathsIterator

Copy makes a copy of the current iterator. This allows branching an iterator into two iterators that can take separate paths. These iterators do not affect eachother and can be iterated concurrently.

func (*PathsIterator) Next

func (it *PathsIterator) Next(part string) bool

Next advances the iterator from its current position, to the position of given path segment in the tree, so long as the given segment is next in a path in the tree. If the segment allows the iterator to advance, then true is returned. Otherwise false is returned.

When false is returned the iterator is not modified. This allows different values to be used, in subsequent calls to Next, to advance the iterator from its current position.

Any part subsequent to the first, must begin with the PathSeparator.

func (*PathsIterator) Value

func (it *PathsIterator) Value() interface{}

Value returns the value at the current iterator position, or nil if there is no value at the position.

type Runes

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

Runes is a radix tree of runes with string keys and interface{} values. Non-terminal nodes have nil values, so a stored nil value is not distinguishable and is not included in Walk or WalkPath.

func (*Runes) Delete

func (tree *Runes) Delete(key string) bool

Delete removes the value associated with the given key. Returns true if a node was found for the given key, and that node had a non-nil value. If the node has no children (is a leaf node) it is removed from the tree. If any of of the node's ancestors becomes childless as a result, they are also removed from the tree.

func (*Runes) Get

func (tree *Runes) Get(key string) interface{}

Get returns the value stored at the given key. Returns nil for internal nodes or for nodes with a value of nil.

func (*Runes) Inspect

func (tree *Runes) Inspect(inspectFn InspectFunc) error

Inspect walks every node of the tree, whether or not it holds a value, calling inspectFn with information about each node. This allows the structure of the tree to be examined and detailed statistics to be collected.

If inspectFn returns an error, the traversal is aborted. If inspectFn returns Skip, Inspect will not descend into the node's children.

The tree is traversed depth-first, in no guaranteed order.

func (*Runes) NewIterator

func (tree *Runes) NewIterator() *RunesIterator

NewIterator returns a new RunesIterator instance that begins iterating from the root of the tree.

Example

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := new(radixtree.Runes)
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	iter := rt.NewIterator()
	for _, r := range "tomato" {
		if !iter.Next(r) {
			break
		}
		val := iter.Value()
		if val != nil {
			fmt.Println(val)
		}
	}
}

Output:
TOM
TOMATO

func (*Runes) Put

func (tree *Runes) Put(key string, value interface{}) bool

Put inserts the value into the tree at the given key, replacing any existing items. It returns true if the put adds a new value, false if it replaces an existing value.

Note that internal nodes have nil values so a stored nil value is not distinguishable and is not included in Walks.

func (*Runes) Walk

func (tree *Runes) Walk(key string, walkFn WalkFunc) error

Walk visits all nodes whose keys match or are are prefixed by the specified key, calling walkFn for each value found. If walkFn returns an error, the walk is aborted and returns the error. If walkFn returns Skip, Walk will not descend into the node's children. Use empty key "" to visit all nodes.

The tree is traversed depth-first, in no guaranteed order.

Walk can be thought of as GetItemsWithPrefix(key)

Example

nolint errcheck // Walk only returns error is user function returns error

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := new(radixtree.Runes)
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	// Find all items whose keys start with "tom"
	rt.Walk("tom", func(key fmt.Stringer, value interface{}) error {
		fmt.Println(value)
		return nil
	})
}

func (*Runes) WalkPath

func (tree *Runes) WalkPath(key string, walkFn WalkPathFunc) error

WalkPath walks the path in tree from the root to the node at the given key, calling walkFn for each node that has a value. If walkFn returns an error, the walk is aborted and returns the error. If walkFn returns Skip, WalkPath is aborted but does not return an error.

The tree is traversed in the order of key symbols in the key.

WalkPath can be thought of as GetItemsThatArePrefixOf((key)

Example

nolint errcheck // WalkPath only returns error is user function returns error

package main

import (
	"fmt"

	"github.com/gammazero/radixtree"
)

func main() {
	rt := new(radixtree.Runes)
	rt.Put("tomato", "TOMATO")
	rt.Put("tom", "TOM")
	rt.Put("tommy", "TOMMY")
	rt.Put("tornado", "TORNADO")

	// Find all items that are a prefix of "tomato"
	rt.WalkPath("tomato", func(key string, value interface{}) error {
		fmt.Println(value)
		return nil
	})
}

Output:
TOM
TOMATO

type RunesIterator

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

RunesIterator is a stateful iterator that traverses a Runes radix tree one character at a time.

Note: Any modification to the tree invalidates the iterator.

func (*RunesIterator) Copy

func (it *RunesIterator) Copy() *RunesIterator

Copy makes a copy of the current iterator. This allows branching an iterator into two iterators that can take separate paths. These iterators do not affect eachother and can be iterated concurrently.

func (*RunesIterator) Next

func (it *RunesIterator) Next(r rune) bool

Next advances the iterator from its current position, to the position of given key symbol in the tree, so long as the given symbol is next in a path in the tree. If the symbol allows the iterator to advance, then true is returned. Otherwise false is returned.

When false is returned the iterator is not modified. This allows different values to be used, in subsequent calls to Next, to advance the iterator from its current position.

func (*RunesIterator) Value

func (it *RunesIterator) Value() interface{}

Value returns the value at the current iterator position, or nil if there is no value at the position.

type WalkFunc

type WalkFunc func(key fmt.Stringer, value interface{}) error

WalkFunc is the type of the function called for each value visited by Walk. The key argument contains the elements of the key at which the value is stored, available as a string by key.String().

If an error is returned, processing of Walk stops. The sole exception is when the function returns the special value Skip. When the function returns Skip, Walk will not descend into any children of the current node.

type WalkPathFunc

type WalkPathFunc func(key string, value interface{}) error

WalkPathFunc is the type of the function called for each value visited by WalkPath. The key argument is the key at which the value is stored.

If an error is returned, processing of WalkPath stops. The sole exception is when the function returns the special value Skip. When the function returns Skip, WalkPath stops processing and returns a nil error.