radixtree

README

radixtree

A data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.

This implementation will store strings with values, the trie allow nil values to be stored but not nil.

API

Create new

Create a new RadixTree

trie = trie.NewRadixTree()

Put key value

Put key value into the trie

trie = trie.NewRadixTree()
trie.Put("abc", 1)

Get value

Retrieve the value stored in the trie for the key else else nil.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
result, _ = trie.Get("abc")

Delete value

Delete the value stored in the trie for the key, returns true if a key was found and the value was deleted else returns false.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
deleted, _ = trie.Delete("abc")

Check if key stored with value

Return true if key was found in the trie.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
deleted, _ = trie.Contains("abc")

Longest Prefix

Find the key with longest prefix in the trie for the query string.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
key, _ = trie.LongestPrefixOf("abcdef")

Keys For Prefix

Return all the keys in the trie that starts with this prefix.

trie = trie.NewRadixTree()
trie.Put("www.test.com", 1)
trie.Put("www.example.com", 1)
key_channel = trie.KeyWithPrefix("www.")

All Keys

Return all the keys in the trie.

trie = trie.NewRadixTree()
trie.Put("www.test.com", 1)
trie.Put("www.example.com", 1)
key_channel = trie.Keys()

All Key Value Pairs

Return all the key value pairs.

trie = trie.NewRadixTree()
trie.Put("www.test.com", 1)
trie.Put("www.example.com", 1)
key_channel = trie.Items()

Tests

The tests can be invoked with go test

License

MIT © Oliver Daff

Documentation

Overview

Package radixtree a data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.

Index

• type KeyValue
• type RadixTree
  • func NewRadixTree() *RadixTree
  • func (rt *RadixTree) Contains(key string) (bool, error)
  • func (rt *RadixTree) Delete(key string) (bool, error)
  • func (rt *RadixTree) Get(key string) (interface{}, error)
  • func (rt *RadixTree) IsEmpty() bool
  • func (rt *RadixTree) Items() <-chan KeyValue
  • func (rt *RadixTree) Keys() <-chan string
  • func (rt *RadixTree) KeysWithPrefix(s string) <-chan string
  • func (rt *RadixTree) LongestPrefixOf(key string) (string, error)
  • func (rt *RadixTree) Put(key string, value interface{}) error

Types

type KeyValue

type KeyValue struct {
	Key   string
	Value interface{}
}

KeyValue is a key value pair from the RadixTree.

type RadixTree

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

RadixTree is a external API for the trie.

func NewRadixTree

func NewRadixTree() *RadixTree

NewRadixTree creates a new RadixTree

func (*RadixTree) Contains

func (rt *RadixTree) Contains(key string) (bool, error)

Contains returns true if the trie contains the key else returns false. A error is returned if the key has zero length.

func (*RadixTree) Delete

func (rt *RadixTree) Delete(key string) (bool, error)

Delete removes the key and value from the tree returns true if the key was found else returns false. A error is returned if the key has zero length.

func (*RadixTree) Get

func (rt *RadixTree) Get(key string) (interface{}, error)

Get returns the value associated with the key else returns nil. Get returns an error if the key passed has zero length.

func (*RadixTree) IsEmpty

func (rt *RadixTree) IsEmpty() bool

IsEmpty returns true if the trie is empty.

func (*RadixTree) Items

func (rt *RadixTree) Items() <-chan KeyValue

Items returns a channel that receives all key value pairs in the trie.

func (*RadixTree) Keys

func (rt *RadixTree) Keys() <-chan string

Keys returns a channel that receives all keys in the trie.

func (*RadixTree) KeysWithPrefix

func (rt *RadixTree) KeysWithPrefix(s string) <-chan string

KeysWithPrefix searches the tree for all the keys for which s is a valid prefix. Returns a channel that returns all the keys

func (*RadixTree) LongestPrefixOf

func (rt *RadixTree) LongestPrefixOf(key string) (string, error)

LongestPrefixOf returns the longest prefix of the key found in the trie. A empty string is returned no common prefix is found. A error is returned if the passed key has zero length.

func (*RadixTree) Put

func (rt *RadixTree) Put(key string, value interface{}) error

Put stores a key value in the trie. Returns a error if the key has zero length.