README.md
1go-immutable-radix [![CircleCI](https://circleci.com/gh/hashicorp/go-immutable-radix/tree/master.svg?style=svg)](https://circleci.com/gh/hashicorp/go-immutable-radix/tree/master)
2=========
3
4Provides the `iradix` package that implements an immutable [radix tree](http://en.wikipedia.org/wiki/Radix_tree).
5The package only provides a single `Tree` implementation, optimized for sparse nodes.
6
7As a radix tree, it provides the following:
8 * O(k) operations. In many cases, this can be faster than a hash table since
9 the hash function is an O(k) operation, and hash tables have very poor cache locality.
10 * Minimum / Maximum value lookups
11 * Ordered iteration
12
13A tree supports using a transaction to batch multiple updates (insert, delete)
14in a more efficient manner than performing each operation one at a time.
15
16For a mutable variant, see [go-radix](https://github.com/armon/go-radix).
17
18Documentation
19=============
20
21The full documentation is available on [Godoc](http://godoc.org/github.com/hashicorp/go-immutable-radix).
22
23Example
24=======
25
26Below is a simple example of usage
27
28```go
29// Create a tree
30r := iradix.New()
31r, _, _ = r.Insert([]byte("foo"), 1)
32r, _, _ = r.Insert([]byte("bar"), 2)
33r, _, _ = r.Insert([]byte("foobar"), 2)
34
35// Find the longest prefix match
36m, _, _ := r.Root().LongestPrefix([]byte("foozip"))
37if string(m) != "foo" {
38 panic("should be foo")
39}
40```
41
42Here is an example of performing a range scan of the keys.
43
44```go
45// Create a tree
46r := iradix.New()
47r, _, _ = r.Insert([]byte("001"), 1)
48r, _, _ = r.Insert([]byte("002"), 2)
49r, _, _ = r.Insert([]byte("005"), 5)
50r, _, _ = r.Insert([]byte("010"), 10)
51r, _, _ = r.Insert([]byte("100"), 10)
52
53// Range scan over the keys that sort lexicographically between [003, 050)
54it := r.Root().Iterator()
55it.SeekLowerBound([]byte("003"))
56for key, _, ok := it.Next(); ok; key, _, ok = it.Next() {
57 if key >= "050" {
58 break
59 }
60 fmt.Println(key)
61}
62// Output:
63// 005
64// 010
65```
66
67