trie

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

• type Node
  • func (n *Node) Leaf() bool
  • func (n *Node) Terminal() bool
  • func (n *Node) Walk(c byte) (next *Node, ok bool)
• type Trie
  • func New() *Trie
  • func (t *Trie) Contains(b []byte) bool
  • func (t *Trie) Insert(b []byte) bool
  • func (t *Trie) PrefixIndex(b []byte) int
  • func (t *Trie) Root() *Node

Examples

• Node
• Trie

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

func (n *Node) Leaf() bool

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.

func (*Node) Terminal

func (n *Node) Terminal() bool

Terminal indicates whether n is terminal in the trie (that is, whether the path from the root to n represents an element in the set). For instance, if the root node is terminal, then []byte{} is in the trie.

func (*Node) Walk

func (n *Node) Walk(c byte) (next *Node, ok bool)

Walk returns the node reached along edge c, if one exists. The ok value indicates whether such a node exist.

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 New

func New() *Trie

New construct a new, empty Trie ready for use.

func (*Trie) Contains

func (t *Trie) Contains(b []byte) bool

Contains checks t for membership of b.

func (*Trie) Insert

func (t *Trie) Insert(b []byte) bool

Insert puts b into the Trie. It returns true if the element was not previously in t.

func (*Trie) PrefixIndex

func (t *Trie) PrefixIndex(b []byte) int

PrefixIndex walks through `b` until a prefix is found (terminal node) or it is exhausted.

func (*Trie) Root

func (t *Trie) Root() *Node

Root returns the root node of a Trie. A valid Trie (i.e., constructed with New), always has a non-nil root node.