trie

Documentation

Overview

Package trie provides a prefix tree implementation.

Add, Has and Delete operations are linear in query length, regardless of the size of the trie. All operations are non-recursive except for marshaling.

Index

• type Trie
  • func New() *Trie
  • func (t *Trie) Add(b []byte)
  • func (t *Trie) Delete(b []byte) bool
  • func (t *Trie) ForEach(f func([]byte) bool)
  • func (t *Trie) Has(b []byte) bool
  • func (t *Trie) MarshalJSON() ([]byte, error)
  • func (t *Trie) UnmarshalJSON(data []byte) error

Types

type Trie

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

A Trie is a prefix tree that supports lookups. A zero value trie is invalid; use New to create a new instance.

func New

func New() *Trie

New returns an empty trie.

func (*Trie) Add

func (t *Trie) Add(b []byte)

Add inserts b and its prefixes to the trie. If b was already added, the object is unchanged.

func (*Trie) Delete

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

Delete removes prefix b from the trie. All sequences that have b as their prefix are removed. All other sequences are unchanged. Returns the result of calling Has(b) before deleting.

func (*Trie) ForEach

func (t *Trie) ForEach(f func([]byte) bool)

ForEach calls f for each final sequence (leaf) in the trie. A final sequence is a sequence that is not a prefix of a longer sequence. f should return whether or not the iteration should continue. f's input slice may be overwritten by subsequent iterations.

func (*Trie) Has

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

Has checks whether b was added to the trie. b could have been added by being a prefix of a longer input.

func (*Trie) MarshalJSON

func (t *Trie) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaler interface.

func (*Trie) UnmarshalJSON

func (t *Trie) UnmarshalJSON(data []byte) error

UnmarshalJSON implements the json.Unmarshaler interface.