trie

README

go-trie (WORK IN PROGRESS)

A pure-Go implementation of a Trie data structure for strings.

Installation

$ go get github.com/cespare/go-trie

Usage

Very simple example usage.

import (
  "github.com/cespare/go-trie"
)

t = trie.New()
t.Add("Hello!")
t.Contains("Hello!")   // => true
t.Contains("Goodbye!") // => false

Please see the API documentation for more information and more advanced usage.

Author

Caleb Spare (cespare)

To Do

• Finish a working implementation!
• The trie.Retrieve method(s) don't need to do a node-by-node walk -- they can do a more efficient search by doing a direct byte-by-byte comparison as soon as we get to the tail.
• Reading/writing from disk

License

MIT Licensed.

Documentation

Overview

The trie package implements a trie (prefix tree) data structure over byte slices.

Index

• type Node
  • func (n *Node) Copy() *Node
  • func (n *Node) Leaf() bool
  • func (n *Node) Terminal() bool
  • func (n *Node) Walk(ch byte) bool
• type Trie
  • func New() *Trie
  • func (t *Trie) Add(s []byte) bool
  • func (t *Trie) ChildrenWithPrefix(prefix []byte) [][]byte
  • func (t *Trie) Contains(s []byte) bool
  • func (t *Trie) Delete(s []byte) bool
  • func (t *Trie) Keys() [][]byte
  • func (t *Trie) Print()
  • func (t *Trie) Root() *Node

Types

type Node

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

The Node abstraction is provided to allow for simple walking and inspection of the trie. It represents a single vertex of the logical trie structure.

func (*Node) Copy

func (n *Node) Copy() *Node

Copy a node's state to a new node.

func (*Node) Leaf

func (n *Node) Leaf() bool

Check whether this node is a leaf of the trie (i.e., there are no children).

func (*Node) Terminal

func (n *Node) Terminal() bool

Check whether this is a terminal node of some string in the trie.

func (*Node) Walk

func (n *Node) Walk(ch byte) bool

Walk down the trie along some edge ch. If there is no such child, the return value is false and the state of the Node is unchanged. Otherwise, the return value is true.

type Trie

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

The core trie data structure.

func New

func New() *Trie

Construct a new, empty trie.

func (*Trie) Add

func (t *Trie) Add(s []byte) bool

Add a []byte to a trie. The return value indicates whether s was added to the trie -- it is true if s was not already present; false otherwise.

func (*Trie) ChildrenWithPrefix

func (t *Trie) ChildrenWithPrefix(prefix []byte) [][]byte

Return all keys in the trie beginning with a certain prefix.

func (*Trie) Contains

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

Test whether a []byte is present in the trie.

func (*Trie) Delete

func (t *Trie) Delete(s []byte) bool

Remove a []byte from the trie. Returns true if the []byte was removed; returns false if the []byte is not in the trie.

func (*Trie) Keys

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

Get every key in the trie.

func (*Trie) Print

func (t *Trie) Print()

Print debugging info.

func (*Trie) Root

func (t *Trie) Root() *Node

Return the Node at the root of the trie.