64 lines
1018 B
Go
64 lines
1018 B
Go
package redblack
|
|
|
|
import (
|
|
"math/rand"
|
|
"testing"
|
|
"time"
|
|
)
|
|
|
|
type testKey int
|
|
|
|
func (k testKey) Compare(c Comparable) int {
|
|
if ck, ok := c.(testKey); ok {
|
|
return int(k - ck)
|
|
}
|
|
|
|
panic("unexpected type")
|
|
}
|
|
|
|
func TestMulti(t *testing.T) {
|
|
for i := 0; i < 20; i++ {
|
|
TestInsert(t)
|
|
}
|
|
}
|
|
|
|
func TestInsert(t *testing.T) {
|
|
var (
|
|
tree *Tree
|
|
out []Comparable
|
|
keys []testKey
|
|
input []testKey
|
|
)
|
|
|
|
keys = make([]testKey, 1000000)
|
|
for i := range keys {
|
|
keys[i] = testKey(i + 1)
|
|
}
|
|
//t.Log("base:", keys)
|
|
input = make([]testKey, len(keys))
|
|
copy(input, keys)
|
|
|
|
r := rand.New(rand.NewSource(time.Now().UnixNano()))
|
|
r.Shuffle(len(input), func(i, j int) {
|
|
input[i], input[j] = input[j], input[i]
|
|
})
|
|
//t.Log("shuffled:", input)
|
|
|
|
tree = new(Tree)
|
|
for _, k := range input {
|
|
tree.Insert(k)
|
|
}
|
|
|
|
out = tree.Slice()
|
|
//t.Log("output:", out)
|
|
for i, d := range out {
|
|
if ck, ok := d.(testKey); ok {
|
|
if ck != keys[i] {
|
|
t.Fatal("mismatch data")
|
|
}
|
|
} else {
|
|
t.Fatal("invalid data type")
|
|
}
|
|
}
|
|
}
|