trie

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) Mask() uint64
  • func (n Node) Meta() interface{}
  • func (n *Node) NewChild(val rune, bitmask uint64, meta interface{}, term bool) *Node
  • func (n Node) Parent() *Node
  • func (n *Node) RemoveChild(r rune)
  • 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) 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 (n *Node) NewChild(val rune, 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) 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.