patricia

Documentation

Index

• Variables
• func SetMaxPrefixPerNode(value int)
• type FuzzyVisitorFunc
• type Item
• type Prefix
• type Trie
  • func NewTrie() *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) VisitFuzzy(partial Prefix, caseInsensitive bool, visitor FuzzyVisitorFunc) error
  • func (trie *Trie) VisitPrefixes(key Prefix, caseInsensitive bool, visitor VisitorFunc) error
  • func (trie *Trie) VisitSubstring(substring Prefix, caseInsensitive bool, visitor VisitorFunc) error
  • func (trie *Trie) VisitSubtree(prefix Prefix, visitor VisitorFunc) error
• type VisitorFunc

Examples

• Trie

Variables

var (
	SkipSubtree  = errors.New("Skip this subtree")
	ErrNilPrefix = errors.New("Nil prefix passed into a method call")
)

Functions

func SetMaxPrefixPerNode

func SetMaxPrefixPerNode(value int)

SetMaxPrefixPerNode sets the maximum length of a prefix before it is split into two nodes

Types

type FuzzyVisitorFunc

type FuzzyVisitorFunc func(prefix Prefix, item Item, skipped int) error

FuzzyVisitorFunc additionaly returns how many characters were skipped which can be sorted on

type Item

type Item interface{}

Item is just interface{}

type Prefix

type Prefix []byte

Prefix is the type of node prefixes

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, false, 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
"Pepa Novak": 1
"Pepa Sindelar": 2
"Karel Macha": 3
"Karel Hynek Macha": 4
"Pepa Novak": 1
"Pepa Sindelar": 2
"Karel Hynek Macha": 10
"Karel Hynek Macha": 10
"Pepa Sindelar": 2
"Karel Hynek Macha": 10
"Karel Hynek Macha": 10

func NewTrie

func NewTrie() *Trie

NewTrie constructs a new trie.

func (*Trie) Clone

func (trie *Trie) Clone() *Trie

Clone makes a copy of an existing trie. Items stored in both tries become shared, obviously.

func (*Trie) Delete

func (trie *Trie) Delete(key Prefix) (deleted bool)

Delete deletes the item represented by the given prefix.

True is returned if the matching node was found and deleted.

func (*Trie) DeleteSubtree

func (trie *Trie) DeleteSubtree(prefix Prefix) (deleted bool)

DeleteSubtree finds the subtree exactly matching prefix and deletes it.

True is returned if the subtree was found and deleted.

func (*Trie) Get

func (trie *Trie) Get(key Prefix) (item Item)

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

func (trie *Trie) Insert(key Prefix, item Item) (inserted bool)

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) Item

func (trie *Trie) Item() Item

Item returns the item stored in the root of this trie.

func (*Trie) Match

func (trie *Trie) Match(prefix Prefix) (matchedExactly bool)

Match returns what Get(prefix) != nil would return. The same warning as for Get applies here as well.

func (*Trie) MatchSubtree

func (trie *Trie) MatchSubtree(key Prefix) (matched bool)

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

func (trie *Trie) Set(key Prefix, item Item)

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) VisitFuzzy

func (trie *Trie) VisitFuzzy(partial Prefix, caseInsensitive bool, visitor FuzzyVisitorFunc) error

VisitFuzzy visits every node that is succesfully matched via fuzzy matching

func (*Trie) VisitPrefixes

func (trie *Trie) VisitPrefixes(key Prefix, caseInsensitive bool, 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) VisitSubstring

func (trie *Trie) VisitSubstring(substring Prefix, caseInsensitive bool, visitor VisitorFunc) error

VisitSubstring takes a substring and visits all the nodes that whos prefix contains this substring

func (*Trie) VisitSubtree

func (trie *Trie) VisitSubtree(prefix Prefix, visitor VisitorFunc) error

VisitSubtree works much like Visit, but it only visits nodes matching prefix.

type VisitorFunc

type VisitorFunc func(prefix Prefix, item Item) error

VisitorFunc is the type of functions passed to visit function