README
¶
Trie
This is a fork of https://github.com/cespare/go-trie that adds the PrefixIndex method.
It's required for https://github.com/toqueteos/substring.
Documentation
¶
Overview ¶
Package trie is an implementation of a trie (prefix tree) data structure over byte slices. It provides a small and simple API for usage as a set as well as a 'Node' API for walking the trie.
Index ¶
Examples ¶
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
}
A Node represents a logical vertex in the trie structure.
Example ¶
This example demonstrates walking through the nodes of a Trie.
package main
import (
"fmt"
"github.com/toqueteos/trie"
)
func main() {
t := trie.New()
for _, s := range []string{"folk", "foxes", "fox"} {
t.Insert([]byte(s))
}
n := t.Root()
fmt.Println(n.Terminal()) // false
next, ok := n.Walk('a')
fmt.Println(ok) // false
for _, c := range []byte("fox") {
next, ok = n.Walk(c)
if !ok {
panic("unexpected")
}
fmt.Println(ok) // true
n = next
}
fmt.Println(n.Terminal()) // true
fmt.Println(n.Leaf()) // false
for _, c := range []byte("es") {
next, ok = n.Walk(c)
if !ok {
panic("unexpected")
}
n = next
}
fmt.Println(n.Terminal()) // true
fmt.Println(n.Leaf()) // true
}
Output: false false true true true true false true true
func (*Node) Leaf ¶
Leaf indicates whether n is a leaf node in the trie (that is, whether it has children). A leaf node must be terminal (else it would not exist). Logically, if n is a leaf node then the []byte represented by the path from the root to n is not a proper prefix of any element of the trie.
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
A Trie is a a prefix tree.
Example ¶
This example shows simple usage of a Trie as a []byte set.
package main
import (
"fmt"
"github.com/toqueteos/trie"
)
func main() {
t := trie.New()
t.Insert([]byte("hello"))
t.Insert([]byte("world"))
for _, s := range []string{"hello", "world", "he", "h", "worlds", ""} {
fmt.Println(t.Contains([]byte(s)))
}
}
Output: true true false false false false
func (*Trie) Insert ¶
Insert puts b into the Trie. It returns true if the element was not previously in t.
func (*Trie) PrefixIndex ¶
PrefixIndex walks through `b` until a prefix is found (terminal node) or it is exhausted.
Source Files