patricia

Documentation

Index

• Constants
• Variables
• type Item
• type Prefix
• type Trie
  • func NewTrie() *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

• Trie

Constants

const MaxChildrenPerSparseNode = 8

Max children to keep in a node in the sparse mode.

Variables

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

var MaxPrefixPerNode = 10

Max prefix length that is kept in a single trie node.

Types

type Item

type Item interface{}

type Prefix

type Prefix []byte

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

// 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)
// "Pepa Sindelar": 2
// "Karel Hynek Macha": 10

// 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

Trie constructor.

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.

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.

type VisitorFunc

type VisitorFunc func(prefix Prefix, item Item) error