trie

package
v0.12.0 Latest Latest
Warning

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

 Go to latest Published: Dec 27, 2022 License: Apache-2.0 Imports: 5 Imported by: 0

Documentation

Overview

Package trie provides generic Trie implementations

Index

Constants

View Source 
const (
	NextPosTerminate = -1
	NextPosErrBadKey = -2
)

Variables

This section is empty.

Functions

func ForEachKey 

func ForEachKey[P, K any, KY KeyIter[P, K]](keyer KY, searchPath P, visit func(k K) bool) error

ForEachKey calls visit on each key in searchPath

it returns an bad search path error when keyer.Next returns -2

Types

type DeletionMode 

type DeletionMode uint8
const (
	// DeletionMode_TargetNode deletes the target node entirely, and all its children will be gone
	DeletionMode_TargetNode DeletionMode = iota

	// DeletionMode_TargetIfLeafNode deletes the target node only when it's a leaf node (no child).
	//
	// for non-leaf nodes, return that node and do nothing
	DeletionMode_TargetIfLeafNode
)

type ErrBadSearchPath 

type ErrBadSearchPath struct {
	SearchPath string
	Pos        int
}

func (*ErrBadSearchPath) Error 

func (e *ErrBadSearchPath) Error() string

type KeyIter 

type KeyIter[SearchType, KeyType any] interface {
	// FormatSearchPath formats a search path to string
	FormatSearchPath(s SearchType) string

	// Next generates next key in a trie from the full search path
	//
	// return value of nextPos has special meanings when it's less than zero:
	//
	//	-1: end of search path, no key will be generated
	//	-2: bad search path at pos
	Next(s SearchType, pos int) (k KeyType, nextPos int)
}

type Keyer 

type Keyer[SearchType, KeyType any] interface {
	// ZeroSearchPath returns the zero value of the search path for the key generator
	ZeroSearchPath() SearchType

	// JoinSearchPath appends k to s
	JoinSearchPath(s SearchType, k KeyType) SearchType

	// CompareKey returns true if k1 < k2
	CompareKey(k1, k2 KeyType) int

	KeyIter[SearchType, KeyType]
}

type MapNode 

type MapNode[P any, K comparable, V any, KY Keyer[P, K]] struct {
	Value V
	// contains filtered or unexported fields
}

func (*MapNode[P, K, V, KY]) Children 

func (n *MapNode[P, K, V, KY]) Children(keyer KY) (ret []*MapNode[P, K, V, KY])

Children implements Node[*MapNode, P, K, V, KY]

func (*MapNode[P, K, V, KY]) GetChild 

func (n *MapNode[P, K, V, KY]) GetChild(keyer KY, key K) (child *MapNode[P, K, V, KY])

GetChild implements Node[*MapNode, P, K, V, KY]

func (*MapNode[P, K, V, KY]) Key 

func (n *MapNode[P, K, V, KY]) Key() K

Key implements Node[*MapNode, P, K, V, KY]

func (*MapNode[P, K, V, KY]) New 

func (n *MapNode[P, K, V, KY]) New(parent *MapNode[P, K, V, KY], key K) *MapNode[P, K, V, KY]

New implements Node[*MapNode, P, K, V, KY]

func (*MapNode[P, K, V, KY]) SearchPath 

func (n *MapNode[P, K, V, KY]) SearchPath(gen KY) P

SearchPath rimplements Node[*MapNode, P, K, V, KY]

type MapTrie 

type MapTrie[P any, K comparable, V any, KY Keyer[P, K]] struct {
	Keyer KY
	// contains filtered or unexported fields
}

MapTrie is a trie with MapNode

type param P for searchPath, K for node key, V for node value, KY for keyer

func NewMapTrie 

func NewMapTrie[P any, K comparable, V any, KY Keyer[P, K]](keyer KY) *MapTrie[P, K, V, KY]

func (*MapTrie[P, K, V, KY]) Delete 

func (t *MapTrie[P, K, V, KY]) Delete(
	searchPath P, mode DeletionMode,
) (nodeDeleted *MapNode[P, K, V, KY], err error)

Delete the exact matching Node of the searchPath

nodeDeleted is nil if there is no exact match

func (*MapTrie[P, K, V, KY]) Get 

func (t *MapTrie[P, K, V, KY]) Get(searchPath P) (_ *MapNode[P, K, V, KY], exact bool, err error)

Get returns the exact or the nearest matching Node for searchPath

exact is set to ture when the returned Node is a exact match

func (*MapTrie[P, K, V, KY]) InOrder 

func (t *MapTrie[P, K, V, KY]) InOrder(visit func(*MapNode[P, K, V, KY]) bool)

func (*MapTrie[P, K, V, KY]) Init 

func (t *MapTrie[P, K, V, KY]) Init()

func (*MapTrie[P, K, V, KY]) LevelOrder 

func (t *MapTrie[P, K, V, KY]) LevelOrder(visit func(*MapNode[P, K, V, KY]) bool)

LevelOrder calls visit on every nodes of the trie in level order

func (*MapTrie[P, K, V, KY]) PostOrder 

func (t *MapTrie[P, K, V, KY]) PostOrder(visit func(*MapNode[P, K, V, KY]) bool)

func (*MapTrie[P, K, V, KY]) PreOrder 

func (t *MapTrie[P, K, V, KY]) PreOrder(visit func(*MapNode[P, K, V, KY]) bool)

func (*MapTrie[P, K, V, KY]) Root 

func (t *MapTrie[P, K, V, KY]) Root() *MapNode[P, K, V, KY]

Root returns the root node of the trie

MUST NOT assign custom value to the returned node

func (*MapTrie[P, K, V, KY]) Set 

func (t *MapTrie[P, K, V, KY]) Set(searchPath P, value V) (*MapNode[P, K, V, KY], error)

Set value stored at searchPath

func (*MapTrie[P, K, V, KY]) Walk 

func (t *MapTrie[P, K, V, KY]) Walk(searchPath P, fn MapTrieWalkFunc[P, K, V, KY]) error

Walk visits all matched trie nodes in searchPath

type MapTrieWalkFunc 

type MapTrieWalkFunc[P any, K comparable, V any, KY Keyer[P, K]] func(key K, n *MapNode[P, K, V, KY]) bool

MapTrieWalkFunc is the function type called in SliceTrie.Walk

type Node 

type Node[Self, P, K, V any, KY Keyer[P, K]] interface {
	// New creates a new node of the same type
	New(parent Self, key K) Self

	// Key returns the key stored in the current node
	Key() K

	// SearchPath returns the search path leading to this node from the root node
	SearchPath(KY) P

	// Children returns all direct children of this node in ascending order
	Children(KY) []Self

	// GetChild returns the child Node with the expected key of n, when not found, return (nil, false)
	GetChild(keyer KY, key K) Self
}

type PathKeyer 

type PathKeyer struct{}

PathKeyer generates keys from a slash separated path

for absolute paths (paths prefixed with a slash): the first key is always the root path (`/`), otherwise the first path element in the path becomes the first key.

func (PathKeyer) CompareKey 

func (PathKeyer) CompareKey(k1, k2 string) int

CompareKey implements Keyer[string, string]

func (PathKeyer) FormatSearchPath 

func (PathKeyer) FormatSearchPath(s string) string

FormatSearchPath implements Keyer[string, string]

func (PathKeyer) JoinSearchPath 

func (PathKeyer) JoinSearchPath(s, k string) string

JoinSearchPath implements Keyer[string, string]

func (PathKeyer) Next 

func (PathKeyer) Next(s string, pos int) (k string, nextPos int)

Next implements Keyer[string, string]

pos is the byte index into key

func (PathKeyer) ZeroSearchPath 

func (PathKeyer) ZeroSearchPath() (zero string)

ZeroSearchPath implements Keyer[string, string]

type PathTrieMapStore 

type PathTrieMapStore[V any] struct {
	MapTrie[string, string, V, PathKeyer]
}

PathTrieMapStore

type PathTrieSliceStore 

type PathTrieSliceStore[V any] struct {
	SliceTrie[string, string, V, PathKeyer]
}

PathTrieSliceStore is a trie for slash (`/`) paths using sorted slice to store node childrens

zero value of PathTrieSliceStore is valid

NOTE: posix path elements `..` and `.` are treated as normal path elements

type RuneKeyer 

type RuneKeyer struct{}

func (RuneKeyer) CompareKey 

func (RuneKeyer) CompareKey(k1, k2 rune) int

CompareKey implements Keyer[string, rune]

func (RuneKeyer) FormatSearchPath 

func (RuneKeyer) FormatSearchPath(s string) string

FormatSearchPath implements Keyer[string, rune]

func (RuneKeyer) JoinSearchPath 

func (RuneKeyer) JoinSearchPath(s string, k rune) string

JoinSearchPath implements Keyer[string, rune]

func (RuneKeyer) Next 

func (RuneKeyer) Next(s string, pos int) (k rune, nextPos int)

Next implements Keyer[string, rune]

pos is the byte index into key

func (RuneKeyer) ZeroSearchPath 

func (RuneKeyer) ZeroSearchPath() (zero string)

ZeroSearchPath implements Keyer[string, rune]

type RuneTrieMapStore 

type RuneTrieMapStore[V any] struct {
	MapTrie[string, rune, V, RuneKeyer]
}

RuneTrieMapStore

type RuneTrieSliceStore 

type RuneTrieSliceStore[V any] struct {
	SliceTrie[string, rune, V, RuneKeyer]
}

RuneTrieSliceStore is a trie for utf-8 runes, each rune in string becomes a node key

zero value of RuneTrieSliceStore is valid

type SectionKeyer 

type SectionKeyer string

SectionKeyer generates keys from a multi-sectioned string

sections are defined using common separator, leading sep does produce a empty section, but tail sep doesn't. for example: 

let sep = "#", s = "#foo#bar#"
will produce a sequence of key: ["", "foo", "bar"]

func (SectionKeyer) CompareKey 

func (SectionKeyer) CompareKey(k1, k2 string) int

CompareKey implements Keyer[string, string]

func (SectionKeyer) FormatSearchPath 

func (SectionKeyer) FormatSearchPath(s string) string

FormatSearchPath implements Keyer[string, rune]

func (SectionKeyer) JoinSearchPath 

func (SectionKeyer) JoinSearchPath(s, k string) string

JoinSearchPath implements Keyer[string, string]

func (SectionKeyer) Next 

func (sep SectionKeyer) Next(s string, pos int) (k string, nextPos int)

Next implements Keyer[string, string]

pos is the byte index into key

func (SectionKeyer) ZeroSearchPath 

func (SectionKeyer) ZeroSearchPath() (zero string)

ZeroSearchPath implements Keyer[string, string]

type SliceNode 

type SliceNode[P, K, V any, KY Keyer[P, K]] struct {
	Value V
	// contains filtered or unexported fields
}

func (*SliceNode[P, K, V, KY]) Children 

func (n *SliceNode[P, K, V, KY]) Children(KY) []*SliceNode[P, K, V, KY]

Children implements Node[*SliceNode, P, K, V, KY]

func (*SliceNode[P, K, V, KY]) GetChild 

func (n *SliceNode[P, K, V, KY]) GetChild(keyer KY, key K) (child *SliceNode[P, K, V, KY])

GetChild implements Node[*SliceNode, P, K, V, KY]

func (*SliceNode[P, K, V, KY]) Key 

func (n *SliceNode[P, K, V, KY]) Key() K

Key implements Node[*SliceNode, P, K, V, KY]

func (*SliceNode[P, K, V, KY]) New 

func (n *SliceNode[P, K, V, KY]) New(parent *SliceNode[P, K, V, KY], key K) *SliceNode[P, K, V, KY]

New implements Node[*SliceNode, P, K, V, KY]

func (*SliceNode[P, K, V, KY]) SearchPath 

func (n *SliceNode[P, K, V, KY]) SearchPath(gen KY) P

SearchPath rimplements Node[*SliceNode, P, K, V, KY]

type SliceTrie 

type SliceTrie[P, K, V any, KY Keyer[P, K]] struct {
	Keyer KY
	// contains filtered or unexported fields
}

SliceTrie is a trie with SliceNode

type param P for searchPath, K for node key, V for node value, KY for keyer

func NewSliceTrie 

func NewSliceTrie[P, K, V any, KY Keyer[P, K]](keyer KY) *SliceTrie[P, K, V, KY]

NewSliceTrie creates a new trie tree with custom keyer

func (*SliceTrie[P, K, V, KY]) Delete 

func (t *SliceTrie[P, K, V, KY]) Delete(
	searchPath P, mode DeletionMode,
) (nodeDeleted *SliceNode[P, K, V, KY], err error)

Delete the exact matching Node of the searchPath

deleted will be false if there is no exact match, in that case, nodeDeleted is nil

func (*SliceTrie[P, K, V, KY]) Get 

func (t *SliceTrie[P, K, V, KY]) Get(searchPath P) (_ *SliceNode[P, K, V, KY], exact bool, err error)

Get returns the exact or the nearest matching Node for searchPath

exact is set to ture when the returned Node is a exact match

func (*SliceTrie[P, K, V, KY]) InOrder 

func (t *SliceTrie[P, K, V, KY]) InOrder(visit func(*SliceNode[P, K, V, KY]) bool)

func (*SliceTrie[P, K, V, KY]) Init 

func (t *SliceTrie[P, K, V, KY]) Init()

func (*SliceTrie[P, K, V, KY]) LevelOrder 

func (t *SliceTrie[P, K, V, KY]) LevelOrder(visit func(*SliceNode[P, K, V, KY]) bool)

LevelOrder calls visit on every nodes of the trie in level order

func (*SliceTrie[P, K, V, KY]) PostOrder 

func (t *SliceTrie[P, K, V, KY]) PostOrder(visit func(*SliceNode[P, K, V, KY]) bool)

func (*SliceTrie[P, K, V, KY]) PreOrder 

func (t *SliceTrie[P, K, V, KY]) PreOrder(visit func(*SliceNode[P, K, V, KY]) bool)

func (*SliceTrie[P, K, V, KY]) Root 

func (t *SliceTrie[P, K, V, KY]) Root() *SliceNode[P, K, V, KY]

Root returns the root node of the trie

MUST NOT assign custom value to the returned node

func (*SliceTrie[P, K, V, KY]) Set 

func (t *SliceTrie[P, K, V, KY]) Set(searchPath P, value V) (*SliceNode[P, K, V, KY], error)

Set value stored at searchPath

func (*SliceTrie[P, K, V, KY]) Walk 

func (t *SliceTrie[P, K, V, KY]) Walk(searchPath P, fn SliceTrieWalkFunc[P, K, V, KY]) error

Walk visits all matched trie nodes in searchPath

type SliceTrieWalkFunc 

type SliceTrieWalkFunc[P, K, V any, KY Keyer[P, K]] func(key K, n *SliceNode[P, K, V, KY]) bool

SliceTrieWalkFunc is the function type called in SliceTrie.Walk

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.