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
- 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 (n Node) Name() string
- func (parent *Node) NewChild(val rune, path string, bitmask uint64, meta interface{}, term bool) *Node
- func (n Node) Parent() *Node
- func (n Node) Path() string
- func (n *Node) RemoveChild(r rune)
- func (n Node) Terminating() bool
- func (n Node) Val() rune
- type Trie
- func (t *Trie) Add(key string, meta interface{}) *Node
- func (t *Trie) AddAtNode(key string, node *Node, meta interface{}) *Node
- func (t Trie) ExactSearchAtNode(s string, n *Node) ([]string, []*Node, error)
- func (t *Trie) Find(key string) (*Node, bool)
- func (t *Trie) FindAtNode(key string, n *Node) (*Node, bool)
- func (t Trie) FirstRegexMatchAtNode(s string, n *Node) (string, *Node, error)
- func (t Trie) FuzzySearch(pre string) []string
- func (t *Trie) HasKeysWithPrefix(key string) bool
- func (t *Trie) Keys() []string
- func (t Trie) ListAtNode(n *Node) ([]string, []*Node, error)
- func (t Trie) PrefixSearch(pre string) []string
- func (t *Trie) Remove(key string)
- func (t *Trie) RemoveAtNode(key string, node *Node)
- func (t *Trie) Root() *Node
- func (t Trie) WalkAtNode(n *Node, walker WalkFunc, nested bool) error
- type WalkFunc
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
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) RemoveChild ¶
func (Node) Terminating ¶
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
func (*Trie) Add ¶
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) ExactSearchAtNode ¶
func (*Trie) FindAtNode ¶
Finds and returns meta data associated with `key` relative to n.
func (Trie) FirstRegexMatchAtNode ¶
func (Trie) FuzzySearch ¶
Performs a fuzzy search against the keys in the trie.
func (*Trie) HasKeysWithPrefix ¶
func (Trie) PrefixSearch ¶
Performs a prefix search against the keys in the trie.
func (*Trie) Remove ¶
Removes a key from the trie, ensuring that all bitmasks up to root are appropriately recalculated.
func (*Trie) RemoveAtNode ¶
Removes a key from the trie relative to node. Node must be terminating Hence we use 'parent' so it can search for key relative to it.
Source Files