Documentation ¶
Overview ¶
Package trie implements several types of performant Tries (e.g. rune-wise, path-wise).
The implementations are optimized for Get performance and to allocate 0 bytes of heap memory (i.e. garbage) per Get.
The Tries do not synchronize access (not thread-safe). A typical use case is to perform Puts and Deletes upfront to populate the Trie, then perform Gets very quickly.
Index ¶
- func PathSegmenter(path string, start int) (segment string, next int)
- type PathTrie
- func (trie *PathTrie) Children() []Trier
- func (trie *PathTrie) Delete(key string) bool
- func (trie *PathTrie) Get(key string) interface{}
- func (trie *PathTrie) GetPath(key string) []interface{}
- func (trie *PathTrie) Node(key string) Trier
- func (trie *PathTrie) Put(key string, value interface{}) bool
- func (trie *PathTrie) Value() interface{}
- func (trie *PathTrie) Walk(walker WalkFunc) error
- type RuneTrie
- func (trie *RuneTrie) Children() []Trier
- func (trie *RuneTrie) Delete(key string) bool
- func (trie *RuneTrie) Get(key string) interface{}
- func (trie *RuneTrie) GetPath(key string) []interface{}
- func (trie *RuneTrie) Node(key string) Trier
- func (trie *RuneTrie) Put(key string, value interface{}) bool
- func (trie *RuneTrie) Value() interface{}
- func (trie *RuneTrie) Walk(walker WalkFunc) error
- type StringSegmenter
- type Trier
- type WalkFunc
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type PathTrie ¶
type PathTrie struct {
// contains filtered or unexported fields
}
PathTrie is a trie of string keys and interface{} values. Internal nodes have nil values so stored nil values cannot be distinguished and are excluded from walks. By default, PathTrie will segment keys by forward slashes with PathSegmenter (e.g. "/a/b/c" -> "/a", "/b", "/c"). A custom StringSegmenter may be used to customize how strings are segmented into nodes. A classic trie might segment keys by rune (i.e. unicode points).
func (*PathTrie) Delete ¶
Delete removes the value associated with the given key. Returns true if a node was found for the given key. If the node or any of its ancestors becomes childless as a result, it is removed from the trie.
func (*PathTrie) Get ¶
Get returns the value stored at the given key. Returns nil for internal nodes or for nodes with a value of nil.
func (*PathTrie) GetPath ¶
GetPath returns all values stored at each node in the path from the root to the given key. Does not return values for internal nodes or for nodes with a nil value.
func (*PathTrie) Node ¶
Node returns the trie node with the given key. Returns nil if the node with the given key is not found
func (*PathTrie) Put ¶
Put inserts the value into the trie at the given key, replacing any existing items. It returns true if the put adds a new value, false if it replaces an existing value. Note that internal nodes have nil values so a stored nil value will not be distinguishable and will not be included in Walks.
func (*PathTrie) Value ¶
func (trie *PathTrie) Value() interface{}
Value returns the value at the current trie node
type RuneTrie ¶
type RuneTrie struct {
// contains filtered or unexported fields
}
RuneTrie is a trie of runes with string keys and interface{} values. Note that internal nodes have nil values so a stored nil value will not be distinguishable and will not be included in Walks.
func (*RuneTrie) Delete ¶
Delete removes the value associated with the given key. Returns true if a node was found for the given key. If the node or any of its ancestors becomes childless as a result, it is removed from the trie.
func (*RuneTrie) Get ¶
Get returns the value stored at the given key. Returns nil for internal nodes or for nodes with a value of nil.
func (*RuneTrie) GetPath ¶
GetPath returns all values stored at each node in the path from the root to the given key. Does not return values for internal nodes or for nodes with a nil value.
func (*RuneTrie) Node ¶
Node returns the trie node with the given key. Returns nil if the node with the given key is not found
func (*RuneTrie) Put ¶
Put inserts the value into the trie at the given key, replacing any existing items. It returns true if the put adds a new value, false if it replaces an existing value. Note that internal nodes have nil values so a stored nil value will not be distinguishable and will not be included in Walks.
func (*RuneTrie) Value ¶
func (trie *RuneTrie) Value() interface{}
Value returns the value at the current trie node
type StringSegmenter ¶
StringSegmenter takes a string key with a starting index and returns the first segment after the start and the ending index. When the end is reached, the returned nextIndex should be -1. Implementations should NOT allocate heap memory as Trie Segmenters are called upon Gets. See PathSegmenter.
type Trier ¶
type Trier interface { Get(key string) interface{} GetPath(key string) []interface{} Put(key string, value interface{}) bool Delete(key string) bool Walk(walker WalkFunc) error Value() interface{} Node(key string) Trier Children() []Trier }
Trier exposes the Trie structure capabilities.