1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
# go-patricia #
**Documentation**: [GoDoc](http://godoc.org/github.com/tchap/go-patricia/patricia)<br />
**Build Status**: [](https://drone.io/github.com/tchap/go-patricia/latest)<br />
**Test Coverage**: [](https://coveralls.io/r/tchap/go-patricia)
## About ##
A generic patricia trie (also called radix tree) implemented in Go (Golang).
The patricia trie as implemented in this library enables fast visiting of items
in some particular ways:
1. visit all items saved in the tree,
2. visit all items matching particular prefix (visit subtree), or
3. given a string, visit all items matching some prefix of that string.
`[]byte` type is used for keys, `interface{}` for values.
`Trie` is not thread safe. Synchronize the access yourself.
### State of the Project ###
Apparently some people are using this, so the API should not change often.
Any ideas on how to make the library better are still welcome.
More (unit) testing would be cool as well...
## Usage ##
Import the package from GitHub first.
```go
import "github.com/tchap/go-patricia/patricia"
```
You can as well use gopkg.in thingie:
```go
import "gopkg.in/tchap/go-patricia.v1/patricia"
```
Then you can start having fun.
```go
printItem := func(prefix patricia.Prefix, item patricia.Item) error {
fmt.Printf("%q: %v\n", prefix, item)
return nil
}
// 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))
// "Pepa Novak" present? true
key = Prefix("Karel")
fmt.Printf("Anybody called %q here? %v\n", key, trie.MatchSubtree(key))
// Anybody called "Karel" here? true
// 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
```
## License ##
MIT, check the `LICENSE` file.
[](https://www.gittip.com/tchap/
"Gittip Badge")
[](https://bitdeli.com/free
"Bitdeli Badge")
|
