Initial Version

So I finally stopped screwing around with my datatypes and started getting coding done. When you don't know a language well it's tedious at first just doing basic things, like inserting elements into arrays. The implementation is not complete but it supports insertion and iteration over elements. The repo is here:

https://github.com/mike-matera/GoLibrary

Validation.

I've only done basic work on validating the data structure so far. Though I found that Go enables interesting mechanisms for testing. This is my test function:

func doTest(tree *btree.Btree, count int, 
        generate func(int, *btree.Btree), 
        check func(current, last uint64) bool) bool {

start := time.Now().UnixNano();
for i := 0; i<count; i++ {
generate(i, tree)
}
end := time.Now().UnixNano()
us := (end - start) / 1000
var rate float32 = float32 (((int64(count) * 1000000) / us) / 1000) 
fmt.Print("\tinsertions took ", us, " us (", rate, " K/sec)\n")

start = time.Now().UnixNano();
ch := tree.Iterate()
last := <- ch
for key := range ch {
if ! check(key,last) {
fmt.Print("\t[fail]\n")
return false
}
last = key
}
end = time.Now().UnixNano()
us = (end - start) / 1000
rate = float32 (((int64(count) * 1000000) / us) / 1000) 
fmt.Print("\titeration took ", us, " us (", rate, " K/sec)\n")
fmt.Print("\t[pass]\n")
return true
}

The function automates a bunch of not-so-fun work, like looping over insertions and deletions. It takes advantage of Go's easy ability to use function pointers. The caller looks like this:

tree := new (btree.Btree)

n := 500000

fmt.Print("[test] Linear insertion ", n, " elements\n")

doTest(tree, n, 

func(i int, t *btree.Btree) {

t.Insert(uint64(i), nil)

},

func(current, last uint64) bool {

return (current == last + 1)

})

The calling syntax uses closures. I probably could get away with not passing a pointer to the tree in the inserter function, but I was working fast. The above test is for linear insertion (or insertion of the integers in order. I have also tested using random numbers. That test looks like this:

tree = new (btree.Btree)

n = 500000

fmt.Print("[test] Random insertion ", n, " elements\n")

r := rand.New(rand.NewSource(time.Now().UnixNano()))

doTest(tree, n, 

func(i int, t *btree.Btree) {

t.Insert(uint64(r.Int63()), nil)

},

func(current, last uint64) bool {

return (current > last)

})

That test is working quite well also. Initially I was testing using random numbers gotten with the Int31() function. This produced the same number twice and threw off my testing. I'm not sure what's supposed to happen when you stuff a B-tree with the same key twice. Because I want to use my B-tree for search I need to make sure that when that happens the result is stable (i.e. that elements with the same key are extracted in insertion order).