trie

package
Version: v0.1.17 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Nov 18, 2021 License: MIT Imports: 1 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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 added in v0.1.10

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 added in v0.1.16

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.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL