trie

Documentation

Index

• func PathSegmenter(path string, start int) (segment string, next int)
• func PathSegmenter2(path string, start int) (segment string, next int)
• type PathTrie
  • func NewPathTrie[T any]() *PathTrie[T]
  • func NewPathTrieWithConfig[T any](config *PathTrieConfig) *PathTrie[T]
  • func (trie *PathTrie[T]) Delete(key string) bool
  • func (trie *PathTrie[T]) Get(key string) (T, string)
  • func (trie *PathTrie[T]) Put(key string, value T) bool
  • func (trie *PathTrie[T]) Walk(walker WalkFunc[T]) error
  • func (trie *PathTrie[T]) WalkPath(key string, walker WalkFunc[T]) error
• type PathTrieConfig
• type StringSegmenter
• type WalkFunc

Functions

func PathSegmenter

func PathSegmenter(path string, start int) (segment string, next int)

PathSegmenter segments string key paths by slash separators. For example, "/a/b/c" -> ("/a", 2), ("/b", 4), ("/c", -1) in successive calls. It does not allocate any heap memory.

func PathSegmenter2

func PathSegmenter2(path string, start int) (segment string, next int)

PathSegmenter2 segments string key paths by slash separators. For example, "/a/b/c" -> ("/", 0), ("/a", 2), ("/b", 4), ("/c", -1) in successive calls. It does not allocate any heap memory.

Types

type PathTrie

type PathTrie[T any] struct {
	// contains filtered or unexported fields
}

PathTrie is a trie of string keys and T 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 NewPathTrie

func NewPathTrie[T any]() *PathTrie[T]

NewPathTrie allocates and returns a new *PathTrie.

func NewPathTrieWithConfig

func NewPathTrieWithConfig[T any](config *PathTrieConfig) *PathTrie[T]

NewPathTrieWithConfig allocates and returns a new *PathTrie with the given *PathTrieConfig

func (*PathTrie[T]) Delete

func (trie *PathTrie[T]) Delete(key string) bool

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[T]) Get

func (trie *PathTrie[T]) Get(key string) (T, string)

Get returns the value matched by path. Returns default value for internal nodes or for nodes with a default value.

func (*PathTrie[T]) Put

func (trie *PathTrie[T]) Put(key string, value T) bool

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[T]) Walk

func (trie *PathTrie[T]) Walk(walker WalkFunc[T]) error

Walk iterates over each key/value stored in the trie and calls the given walker function with the key and value. If the walker function returns an error, the walk is aborted. The traversal is depth first with no guaranteed order.

func (*PathTrie[T]) WalkPath

func (trie *PathTrie[T]) WalkPath(key string, walker WalkFunc[T]) error

WalkPath iterates over each key/value in the path in trie from the root to the node at the given key, calling the given walker function for each key/value. If the walker function returns an error, the walk is aborted.

type PathTrieConfig

type PathTrieConfig struct {
	Segmenter StringSegmenter
}

PathTrieConfig for building a path trie with different segmenter

type StringSegmenter

type StringSegmenter func(key string, start int) (segment string, nextIndex int)

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 WalkFunc

type WalkFunc[T any] func(key string, value T) error

WalkFunc defines some action to take on the given key and value during a Trie Walk. Returning a non-nil error will terminate the Walk.