Documentation
¶
Overview ¶
Package trie provides an implementation of a XOR Trie.
Package trie provides an implementation of a XOR Trie
Index ¶
- func Equal[K kad.Key[K], D any](a, b *Trie[K, D]) bool
- func Find[K kad.Key[K], D any](tr *Trie[K, D], kk K) (bool, D)
- func Locate[K kad.Key[K], D any](tr *Trie[K, D], target K) (bool, int)
- type Entry
- type Trie
- func (tr *Trie[K, D]) Add(kk K, data D) bool
- func (tr *Trie[K, D]) AddMany(entries ...Entry[K, D]) int
- func (tr *Trie[K, D]) Branch(dir int) *Trie[K, D]
- func (tr *Trie[K, D]) Copy() *Trie[K, D]
- func (tr *Trie[K, D]) Data() D
- func (tr *Trie[K, D]) HasKey() bool
- func (tr *Trie[K, D]) IsEmptyLeaf() bool
- func (tr *Trie[K, D]) IsLeaf() bool
- func (tr *Trie[K, D]) IsNonEmptyLeaf() bool
- func (tr *Trie[K, D]) Key() *K
- func (tr *Trie[K, D]) Remove(kk K) bool
- func (tr *Trie[K, D]) Size() int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Trie ¶
Trie is a trie for equal-length bit vectors, which stores values only in the leaves. A node may optionally hold data of type D Trie node invariants: (1) Either both branches are nil, or both are non-nil. (2) If branches are non-nil, key must be nil. (3) If both branches are leaves, then they are both non-empty (have keys).
func Add ¶
Add adds the key to trie, returning a new trie if the key was not already in the trie. Add is immutable/non-destructive: the original trie remains unchanged.
func Remove ¶
Remove removes the key from the trie. Remove is immutable/non-destructive: the original trie remains unchanged. If the key did not exist in the trie then the original trie is returned.
func (*Trie[K, D]) Add ¶
Add attempts to add a key to the trie, mutating the trie. Returns true if the key was added, false otherwise.
func (*Trie[K, D]) AddMany ¶
AddMany attempts to add multiple entries to the trie, mutating the trie. Returns the number of entries that were successfully added. Duplicate keys within entries or keys already in the trie are ignored.
Performance: This function sorts entries once (O(N log N)) and removes duplicates in a single pass (O(N)). The sorted entries enable zero-allocation partitioning during recursive insertion via subslicing.
func (*Trie[K, D]) IsEmptyLeaf ¶
IsEmptyLeaf reports whether the Trie is a leaf node without branches that also has no key.
func (*Trie[K, D]) IsLeaf ¶
IsLeaf reports whether the Trie is a leaf node. A leaf node has no child branches but may hold a key and data.
func (*Trie[K, D]) IsNonEmptyLeaf ¶
IsNonEmptyLeaf reports whether the Trie is a leaf node without branches but has a key.
Source Files