I tried to use btree by using the example code from the example code:
package main
import (
"flag"
"fmt"
"math/rand"
"reflect"
"sort"
"sync"
"testing"
"time"
"github.com/google/btree"
// "github.com/petar/GoLLRB/llrb"
)
// Item represents a single object in the tree.
type Item interface {
// Less tests whether the current item is less than the given argument.
//
// This must provide a strict weak ordering.
// If !a.Less(b) && !b.Less(a), we treat this to mean a == b (i.e. we can only
// hold one of either a or b in the tree).
Less(than Item) bool
}
// Int implements the Item interface for integers.
type Int int
type byInts []Item
func (a byInts) Len() int {
return len(a)
}
func (a byInts) Less(i, j int) bool {
return a[i].(Int) < a[j].(Int)
}
func (a byInts) Swap(i, j int) {
a[i], a[j] = a[j], a[i]
}
func init() {
seed := time.Now().Unix()
fmt.Println(seed)
rand.Seed(seed)
}
// perm returns a random permutation of n Int items in the range [0, n).
func perm(n int) (out []Item) {
for _, v := range rand.Perm(n) {
out = append(out, Int(v))
}
return
}
// // rang returns an ordered list of Int items in the range [0, n).
// func rang(n int) (out []Item) {
// for i := 0; i < n; i++ {
// out = append(out, Int(i))
// }
// return
// }
// // all extracts all items from a tree in order as a slice.
// func all(t *BTree) (out []Item) {
// t.Ascend(func(a Item) bool {
// out = append(out, a)
// return true
// })
// return
// }
// // rangerev returns a reversed ordered list of Int items in the range [0, n).
// func rangrev(n int) (out []Item) {
// for i := n - 1; i >= 0; i-- {
// out = append(out, Int(i))
// }
// return
// }
// // allrev extracts all items from a tree in reverse order as a slice.
// func allrev(t *BTree) (out []Item) {
// t.Descend(func(a Item) bool {
// out = append(out, a)
// return true
// })
// return
// }
var btreeDegree = flag.Int("degree", 32, "B-Tree degree")
func TestBTree(t *testing.T) {
tr := btree.New(*btreeDegree)
const treeSize = 10000
for i := 0; i < 10; i++ {
if min := tr.Min(); min != nil {
t.Fatalf("empty min, got %+v", min)
}
if max := tr.Max(); max != nil {
t.Fatalf("empty max, got %+v", max)
}
for _, item := range perm(treeSize) {
if x := tr.ReplaceOrInsert(item); x != nil {
t.Fatal("insert found item", item)
}
}
for _, item := range perm(treeSize) {
if x := tr.ReplaceOrInsert(item); x == nil {
t.Fatal("insert didn't find item", item)
}
}
if min, want := tr.Min(), Item(Int(0)); min != want {
t.Fatalf("min: want %+v, got %+v", want, min)
}
if max, want := tr.Max(), Item(Int(treeSize-1)); max != want {
t.Fatalf("max: want %+v, got %+v", want, max)
}
got := all(tr)
want := rang(treeSize)
if !reflect.DeepEqual(got, want) {
t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
}
gotrev := allrev(tr)
wantrev := rangrev(treeSize)
if !reflect.DeepEqual(gotrev, wantrev) {
t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
}
for _, item := range perm(treeSize) {
if x := tr.Delete(item); x == nil {
t.Fatalf("didn't find %v", item)
}
}
if got = all(tr); len(got) > 0 {
t.Fatalf("some left!: %v", got)
}
}
}
func ExampleBTree() {
tr := New(*btreeDegree)
for i := Int(0); i < 10; i++ {
tr.ReplaceOrInsert(i)
}
fmt.Println("len: ", tr.Len())
fmt.Println("get3: ", tr.Get(Int(3)))
fmt.Println("get100: ", tr.Get(Int(100)))
fmt.Println("del4: ", tr.Delete(Int(4)))
fmt.Println("del100: ", tr.Delete(Int(100)))
fmt.Println("replace5: ", tr.ReplaceOrInsert(Int(5)))
fmt.Println("replace100:", tr.ReplaceOrInsert(Int(100)))
fmt.Println("min: ", tr.Min())
fmt.Println("delmin: ", tr.DeleteMin())
fmt.Println("max: ", tr.Max())
fmt.Println("delmax: ", tr.DeleteMax())
fmt.Println("len: ", tr.Len())
// Output:
// len: 10
// get3: 3
// get100: <nil>
// del4: 4
// del100: <nil>
// replace5: 5
// replace100: <nil>
// min: 0
// delmin: 0
// max: 100
// delmax: 100
// len: 8
}
func main() {
ExampleBTree()
}
But it is not working:
cpchung:main$ **sh -x try.sh**
+ export GOPATH=/home/cpchung/Dropbox/go/october
+ go get github.com/google/btree
+ go get github.com/petar/GoLLRB/llrb
+ go run example.go
# command-line-arguments
./example.go:8: imported and not used: "sort"
./example.go:9: imported and not used: "sync"
**./example.go:37: impossible type assertion:**
** Int does not implement Item (missing Less method)**
./example.go:54: cannot use Int(v) (type Int) as type Item in append:
Int does not implement Item (missing Less method)
./example.go:106: cannot use item (type Item) as type btree.Item in argument to tr.ReplaceOrInsert:
Item does not implement btree.Item (wrong type for Less method)
have Less(Item) bool
want Less(btree.Item) bool
./example.go:111: cannot use item (type Item) as type btree.Item in argument to tr.ReplaceOrInsert:
Item does not implement btree.Item (wrong type for Less method)
have Less(Item) bool
want Less(btree.Item) bool
./example.go:115: cannot convert Int(0) (type Int) to type Item:
Int does not implement Item (missing Less method)
./example.go:115: invalid operation: min != want (mismatched types btree.Item and Item)
./example.go:118: cannot convert Int(treeSize - 1) (type Int) to type Item:
Int does not implement Item (missing Less method)
./example.go:118: too many errors
The following is already in btree.go. Why I still need them in my example.go(the file contains main()) even after I imported “github.com/google/btree”?
// Int implements the Item interface for integers.
type Int int
func (a Int) Less(b Item) bool {
return a < b.(Int)
}