trie

README

Trie

Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Usage

Create a Trie with:

t := trie.New()

Add Keys with:

// Add can take in meta information which can be stored with the key.
// i.e. you could store any information you would like to associate with
// this particular key.
t.Add("foobar", 1)

Find a key with:

node, ok := t.Find("foobar")
meta := node.Meta()
// use meta with meta.(type)

Remove Keys with:

t.Remove("foobar")

Prefix search with:

t.PrefixSearch("foo")

Fast test for valid prefix:

t.HasKeysWithPrefix("foo")

Fuzzy search with:

t.FuzzySearch("fb")

Contributing

Fork this repo and run tests with:

go test

Create a feature branch, write your tests and code and submit a pull request.

License

MIT

Documentation

Overview

Implementation of an R-Way Trie data structure.

A Trie has a root Node which is the base of the tree. Each subsequent Node has a letter and children, which are nodes that have letter values associated with them.

Index

• type ByKeys
  • func (a ByKeys) Len() int
  • func (a ByKeys) Less(i, j int) bool
  • func (a ByKeys) Swap(i, j int)
• type Node
  • func (n Node) Children() map[rune]*Node
  • func (n Node) Depth() int
  • func (n Node) Mask() uint64
  • func (n Node) Meta() interface{}
  • func (parent *Node) NewChild(val rune, path string, bitmask uint64, meta interface{}, term bool) *Node
  • func (n Node) Parent() *Node
  • func (n *Node) RemoveChild(r rune)
  • func (n Node) Terminating() bool
  • func (n Node) Val() rune
• type Trie
  • func New() *Trie
  • func (t *Trie) Add(key string, meta interface{}) *Node
  • func (t *Trie) Find(key string) (*Node, bool)
  • func (t Trie) FuzzySearch(pre string) []string
  • func (t *Trie) HasKeysWithPrefix(key string) bool
  • func (t *Trie) Keys() []string
  • func (t Trie) PrefixSearch(pre string) []string
  • func (t *Trie) Remove(key string)
  • func (t *Trie) Root() *Node

Types

type ByKeys

type ByKeys []string

func (ByKeys) Len

func (a ByKeys) Len() int

func (ByKeys) Less

func (a ByKeys) Less(i, j int) bool

func (ByKeys) Swap

func (a ByKeys) Swap(i, j int)

type Node

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

func (Node) Children

func (n Node) Children() map[rune]*Node

Returns the children of this node.

func (Node) Depth

func (n Node) Depth() int

func (Node) Mask

func (n Node) Mask() uint64

Returns a uint64 representing the current mask of this node.

func (Node) Meta

func (n Node) Meta() interface{}

Returns the meta information of this node.

func (*Node) NewChild

func (parent *Node) NewChild(val rune, path string, bitmask uint64, meta interface{}, term bool) *Node

Creates and returns a pointer to a new child for the node.

func (Node) Parent

func (n Node) Parent() *Node

Returns the parent of this node.

func (*Node) RemoveChild

func (n *Node) RemoveChild(r rune)

func (Node) Terminating

func (n Node) Terminating() bool

func (Node) Val

func (n Node) Val() rune

type Trie

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

func New

func New() *Trie

Creates a new Trie with an initialized root Node.

func (*Trie) Add

func (t *Trie) Add(key string, meta interface{}) *Node

Adds the key to the Trie, including meta data. Meta data is stored as `interface{}` and must be type cast by the caller.

func (*Trie) Find

func (t *Trie) Find(key string) (*Node, bool)

Finds and returns meta data associated with `key`.

func (Trie) FuzzySearch

func (t Trie) FuzzySearch(pre string) []string

Performs a fuzzy search against the keys in the trie.

func (*Trie) HasKeysWithPrefix

func (t *Trie) HasKeysWithPrefix(key string) bool

func (*Trie) Keys

func (t *Trie) Keys() []string

Returns all the keys currently stored in the trie.

func (Trie) PrefixSearch

func (t Trie) PrefixSearch(pre string) []string

Performs a prefix search against the keys in the trie.

func (*Trie) Remove

func (t *Trie) Remove(key string)

Removes a key from the trie, ensuring that all bitmasks up to root are appropriately recalculated.

func (*Trie) Root

func (t *Trie) Root() *Node

Returns the root node for the Trie.