// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ssa
import (
"fmt"
"testing"
)
type sstring string
func (s sstring) String() string {
return string(s)
}
// wellFormed ensures that a red-black tree meets
// all of its invariants and returns a string identifying
// the first problem encountered. If there is no problem
// then the returned string is empty. The size is also
// returned to allow comparison of calculated tree size
// with expected.
func (t *RBTint32) wellFormed() (s string, i int) {
if t.root == nil {
s = ""
i = 0
return
}
return t.root.wellFormedSubtree(nil, -0x80000000, 0x7fffffff)
}
// wellFormedSubtree ensures that a red-black subtree meets
// all of its invariants and returns a string identifying
// the first problem encountered. If there is no problem
// then the returned string is empty. The size is also
// returned to allow comparison of calculated tree size
// with expected.
func (t *node32) wellFormedSubtree(parent *node32, min, max int32) (s string, i int) {
i = -1 // initialize to a failing value
s = "" // s is the reason for failure; empty means okay.
if t.parent != parent {
s = "t.parent != parent"
return
}
if min >= t.key {
s = "min >= t.key"
return
}
if max <= t.key {
s = "max <= t.key"
return
}
l := t.left
r := t.right
if l == nil && r == nil {
if t.rank != rankLeaf {
s = "leaf rank wrong"
return
}
}
if l != nil {
if t.rank < l.rank {
s = "t.rank < l.rank"
} else if t.rank > 1+l.rank {
s = "t.rank > 1+l.rank"
} else if t.rank <= l.maxChildRank() {
s = "t.rank <= l.maxChildRank()"
} else if t.key <= l.key {
s = "t.key <= l.key"
}
if s != "" {
return
}
} else {
if t.rank != 1 {
s = "t w/ left nil has rank != 1"
return
}
}
if r != nil {
if t.rank < r.rank {
s = "t.rank < r.rank"
} else if t.rank > 1+r.rank {
s = "t.rank > 1+r.rank"
} else if t.rank <= r.maxChildRank() {
s = "t.rank <= r.maxChildRank()"
} else if t.key >= r.key {
s = "t.key >= r.key"
}
if s != "" {
return
}
} else {
if t.rank != 1 {
s = "t w/ right nil has rank != 1"
return
}
}
ii := 1
if l != nil {
res, il := l.wellFormedSubtree(t, min, t.key)
if res != "" {
s = "L." + res
return
}
ii += il
}
if r != nil {
res, ir := r.wellFormedSubtree(t, t.key, max)
if res != "" {
s = "R." + res
return
}
ii += ir
}
i = ii
return
}
func (t *RBTint32) DebugString() string {
if t.root == nil {
return ""
}
return t.root.DebugString()
}
// DebugString prints the tree with nested information
// to allow an eyeball check on the tree balance.
func (t *node32) DebugString() string {
s := ""
if t.left != nil {
s = s + "["
s = s + t.left.DebugString()
s = s + "]"
}
s = s + fmt.Sprintf("%v=%v:%d", t.key, t.data, t.rank)
if t.right != nil {
s = s + "["
s = s + t.right.DebugString()
s = s + "]"
}
return s
}
func allRBT32Ops(te *testing.T, x []int32) {
t := &RBTint32{}
for i, d := range x {
x[i] = d + d // Double everything for glb/lub testing
}
// fmt.Printf("Inserting double of %v", x)
k := 0
min := int32(0x7fffffff)
max := int32(-0x80000000)
for _, d := range x {
if d < min {
min = d
}
if d > max {
max = d
}
t.Insert(d, sstring(fmt.Sprintf("%v", d)))
k++
s, i := t.wellFormed()
if i != k {
te.Errorf("Wrong tree size %v, expected %v for %v", i, k, t.DebugString())
}
if s != "" {
te.Errorf("Tree consistency problem at %v", s)
return
} else {
// fmt.Printf("%s", t.DebugString())
}
}
oops := false
for _, d := range x {
s := fmt.Sprintf("%v", d)
f := t.Find(d)
// data
if s != fmt.Sprintf("%v", f) {
te.Errorf("s(%v) != f(%v)", s, f)
oops = true
}
}
if !oops {
for _, d := range x {
s := fmt.Sprintf("%v", d)
kg, g := t.Glb(d + 1)
kge, ge := t.GlbEq(d)
kl, l := t.Lub(d - 1)
kle, le := t.LubEq(d)
// keys
if d != kg {
te.Errorf("d(%v) != kg(%v)", d, kg)
}
if d != kl {
te.Errorf("d(%v) != kl(%v)", d, kl)
}
if d != kge {
te.Errorf("d(%v) != kge(%v)", d, kge)
}
if d != kle {
te.Errorf("d(%v) != kle(%v)", d, kle)
}
// data
if s != fmt.Sprintf("%v", g) {
te.Errorf("s(%v) != g(%v)", s, g)
}
if s != fmt.Sprintf("%v", l) {
te.Errorf("s(%v) != l(%v)", s, l)
}
if s != fmt.Sprintf("%v", ge) {
te.Errorf("s(%v) != ge(%v)", s, ge)
}
if s != fmt.Sprintf("%v", le) {
te.Errorf("s(%v) != le(%v)", s, le)
}
}
for _, d := range x {
s := fmt.Sprintf("%v", d)
kge, ge := t.GlbEq(d + 1)
kle, le := t.LubEq(d - 1)
if d != kge {
te.Errorf("d(%v) != kge(%v)", d, kge)
}
if d != kle {
te.Errorf("d(%v) != kle(%v)", d, kle)
}
if s != fmt.Sprintf("%v", ge) {
te.Errorf("s(%v) != ge(%v)", s, ge)
}
if s != fmt.Sprintf("%v", le) {
te.Errorf("s(%v) != le(%v)", s, le)
}
}
kg, g := t.Glb(min)
kge, ge := t.GlbEq(min - 1)
kl, l := t.Lub(max)
kle, le := t.LubEq(max + 1)
fmin := t.Find(min - 1)
fmax := t.Find(min + 11)
if kg != 0 || kge != 0 || kl != 0 || kle != 0 {
te.Errorf("Got non-zero-key for missing query")
}
if g != nil || ge != nil || l != nil || le != nil || fmin != nil || fmax != nil {
te.Errorf("Got non-error-data for missing query")
}
}
}
func TestAllRBTreeOps(t *testing.T) {
allRBT32Ops(t, []int32{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})
allRBT32Ops(t, []int32{22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 3, 2, 1, 25, 24, 23, 12, 11, 10, 9, 8, 7, 6, 5, 4})
allRBT32Ops(t, []int32{25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1})
allRBT32Ops(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24})
allRBT32Ops(t, []int32{1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2})
allRBT32Ops(t, []int32{24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25})
}