Documentation
¶
Index ¶
- Constants
- Variables
- type Item
- type Option
- type Prefix
- type Trie
- func (trie *Trie) Clone() *Trie
- func (trie *Trie) Delete(key Prefix) (deleted bool)
- func (trie *Trie) DeleteSubtree(prefix Prefix) (deleted bool)
- func (trie *Trie) Get(key Prefix) (item Item)
- func (trie *Trie) Insert(key Prefix, item Item) (inserted bool)
- func (trie *Trie) Item() Item
- func (trie *Trie) Match(prefix Prefix) (matchedExactly bool)
- func (trie *Trie) MatchSubtree(key Prefix) (matched bool)
- func (trie *Trie) Set(key Prefix, item Item)
- func (trie *Trie) Visit(visitor VisitorFunc) error
- func (trie *Trie) VisitPrefixes(key Prefix, visitor VisitorFunc) error
- func (trie *Trie) VisitSubtree(prefix Prefix, visitor VisitorFunc) error
- type VisitorFunc
Examples ¶
Constants ¶
const ( DefaultMaxPrefixPerNode = 10 DefaultMaxChildrenPerSparseNode = 8 )
Variables ¶
var ( SkipSubtree = errors.New("Skip this subtree") ErrNilPrefix = errors.New("Nil prefix passed into a method call") )
Functions ¶
This section is empty.
Types ¶
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Trie is a generic patricia trie that allows fast retrieval of items by prefix. and other funky stuff.
Trie is not thread-safe.
Example ¶
// Create a new tree.
trie := NewTrie()
// Insert some items.
trie.Insert(Prefix("Pepa Novak"), 1)
trie.Insert(Prefix("Pepa Sindelar"), 2)
trie.Insert(Prefix("Karel Macha"), 3)
trie.Insert(Prefix("Karel Hynek Macha"), 4)
// Just check if some things are present in the tree.
key := Prefix("Pepa Novak")
fmt.Printf("%q present? %v\n", key, trie.Match(key))
key = Prefix("Karel")
fmt.Printf("Anybody called %q here? %v\n", key, trie.MatchSubtree(key))
// Walk the tree.
trie.Visit(printItem)
// "Karel Hynek Macha": 4
// "Karel Macha": 3
// "Pepa Novak": 1
// "Pepa Sindelar": 2
// Walk a subtree.
trie.VisitSubtree(Prefix("Pepa"), printItem)
// "Pepa Novak": 1
// "Pepa Sindelar": 2
// Modify an item, then fetch it from the tree.
trie.Set(Prefix("Karel Hynek Macha"), 10)
key = Prefix("Karel Hynek Macha")
fmt.Printf("%q: %v\n", key, trie.Get(key))
// "Karel Hynek Macha": 10
// Walk prefixes.
prefix := Prefix("Karel Hynek Macha je kouzelnik")
trie.VisitPrefixes(prefix, printItem)
// "Karel Hynek Macha": 10
// Delete some items.
trie.Delete(Prefix("Pepa Novak"))
trie.Delete(Prefix("Karel Macha"))
// Walk again.
trie.Visit(printItem)
// "Karel Hynek Macha": 10
// "Pepa Sindelar": 2
// Delete a subtree.
trie.DeleteSubtree(Prefix("Pepa"))
// Print what is left.
trie.Visit(printItem)
// "Karel Hynek Macha": 10
Output: "Pepa Novak" present? true Anybody called "Karel" here? true "Karel Hynek Macha": 4 "Karel Macha": 3 "Pepa Novak": 1 "Pepa Sindelar": 2 "Pepa Novak": 1 "Pepa Sindelar": 2 "Karel Hynek Macha": 10 "Karel Hynek Macha": 10 "Karel Hynek Macha": 10 "Pepa Sindelar": 2 "Karel Hynek Macha": 10
func (*Trie) Clone ¶
Clone makes a copy of an existing trie. Items stored in both tries become shared, obviously.
func (*Trie) Delete ¶
Delete deletes the item represented by the given prefix.
True is returned if the matching node was found and deleted.
func (*Trie) DeleteSubtree ¶
DeleteSubtree finds the subtree exactly matching prefix and deletes it.
True is returned if the subtree was found and deleted.
func (*Trie) Get ¶
Get returns the item located at key.
This method is a bit dangerous, because Get can as well end up in an internal node that is not really representing any user-defined value. So when nil is a valid value being used, it is not possible to tell if the value was inserted into the tree by the user or not. A possible workaround for this is not to use nil interface as a valid value, even using zero value of any type is enough to prevent this bad behaviour.
func (*Trie) Insert ¶
Insert inserts a new item into the trie using the given prefix. Insert does not replace existing items. It returns false if an item was already in place.
func (*Trie) Match ¶
Match returns what Get(prefix) != nil would return. The same warning as for Get applies here as well.
func (*Trie) MatchSubtree ¶
MatchSubtree returns true when there is a subtree representing extensions to key, that is if there are any keys in the tree which have key as prefix.
func (*Trie) Set ¶
Set works much like Insert, but it always sets the item, possibly replacing the item previously inserted.
func (*Trie) Visit ¶
func (trie *Trie) Visit(visitor VisitorFunc) error
Visit calls visitor on every node containing a non-nil item in alphabetical order.
If an error is returned from visitor, the function stops visiting the tree and returns that error, unless it is a special error - SkipSubtree. In that case Visit skips the subtree represented by the current node and continues elsewhere.
func (*Trie) VisitPrefixes ¶
func (trie *Trie) VisitPrefixes(key Prefix, visitor VisitorFunc) error
VisitPrefixes visits only nodes that represent prefixes of key. To say the obvious, returning SkipSubtree from visitor makes no sense here.
func (*Trie) VisitSubtree ¶
func (trie *Trie) VisitSubtree(prefix Prefix, visitor VisitorFunc) error
VisitSubtree works much like Visit, but it only visits nodes matching prefix.
Source Files