1 // Copyright 2016 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package ssa 6 7 import ( 8 "fmt" 9 "testing" 10 ) 11 12 type sstring string 13 14 func (s sstring) String() string { 15 return string(s) 16 } 17 18 // wellFormed ensures that a red-black tree meets 19 // all of its invariants and returns a string identifying 20 // the first problem encountered. If there is no problem 21 // then the returned string is empty. The size is also 22 // returned to allow comparison of calculated tree size 23 // with expected. 24 func (t *RBTint32) wellFormed() (s string, i int) { 25 if t.root == nil { 26 s = "" 27 i = 0 28 return 29 } 30 return t.root.wellFormedSubtree(nil, -0x80000000, 0x7fffffff) 31 } 32 33 // wellFormedSubtree ensures that a red-black subtree meets 34 // all of its invariants and returns a string identifying 35 // the first problem encountered. If there is no problem 36 // then the returned string is empty. The size is also 37 // returned to allow comparison of calculated tree size 38 // with expected. 39 func (t *node32) wellFormedSubtree(parent *node32, min, max int32) (s string, i int) { 40 i = -1 // initialize to a failing value 41 s = "" // s is the reason for failure; empty means okay. 42 43 if t.parent != parent { 44 s = "t.parent != parent" 45 return 46 } 47 48 if min >= t.key { 49 s = "min >= t.key" 50 return 51 } 52 53 if max <= t.key { 54 s = "max <= t.key" 55 return 56 } 57 58 l := t.left 59 r := t.right 60 if l == nil && r == nil { 61 if t.rank != rankLeaf { 62 s = "leaf rank wrong" 63 return 64 } 65 } 66 if l != nil { 67 if t.rank < l.rank { 68 s = "t.rank < l.rank" 69 } else if t.rank > 1+l.rank { 70 s = "t.rank > 1+l.rank" 71 } else if t.rank <= l.maxChildRank() { 72 s = "t.rank <= l.maxChildRank()" 73 } else if t.key <= l.key { 74 s = "t.key <= l.key" 75 } 76 if s != "" { 77 return 78 } 79 } else { 80 if t.rank != 1 { 81 s = "t w/ left nil has rank != 1" 82 return 83 } 84 } 85 if r != nil { 86 if t.rank < r.rank { 87 s = "t.rank < r.rank" 88 } else if t.rank > 1+r.rank { 89 s = "t.rank > 1+r.rank" 90 } else if t.rank <= r.maxChildRank() { 91 s = "t.rank <= r.maxChildRank()" 92 } else if t.key >= r.key { 93 s = "t.key >= r.key" 94 } 95 if s != "" { 96 return 97 } 98 } else { 99 if t.rank != 1 { 100 s = "t w/ right nil has rank != 1" 101 return 102 } 103 } 104 ii := 1 105 if l != nil { 106 res, il := l.wellFormedSubtree(t, min, t.key) 107 if res != "" { 108 s = "L." + res 109 return 110 } 111 ii += il 112 } 113 if r != nil { 114 res, ir := r.wellFormedSubtree(t, t.key, max) 115 if res != "" { 116 s = "R." + res 117 return 118 } 119 ii += ir 120 } 121 i = ii 122 return 123 } 124 125 func (t *RBTint32) DebugString() string { 126 if t.root == nil { 127 return "" 128 } 129 return t.root.DebugString() 130 } 131 132 // DebugString prints the tree with nested information 133 // to allow an eyeball check on the tree balance. 134 func (t *node32) DebugString() string { 135 s := "" 136 if t.left != nil { 137 s = s + "[" 138 s = s + t.left.DebugString() 139 s = s + "]" 140 } 141 s = s + fmt.Sprintf("%v=%v:%d", t.key, t.data, t.rank) 142 if t.right != nil { 143 s = s + "[" 144 s = s + t.right.DebugString() 145 s = s + "]" 146 } 147 return s 148 } 149 150 func allRBT32Ops(te *testing.T, x []int32) { 151 t := &RBTint32{} 152 for i, d := range x { 153 x[i] = d + d // Double everything for glb/lub testing 154 } 155 156 // fmt.Printf("Inserting double of %v", x) 157 k := 0 158 min := int32(0x7fffffff) 159 max := int32(-0x80000000) 160 for _, d := range x { 161 if d < min { 162 min = d 163 } 164 165 if d > max { 166 max = d 167 } 168 169 t.Insert(d, sstring(fmt.Sprintf("%v", d))) 170 k++ 171 s, i := t.wellFormed() 172 if i != k { 173 te.Errorf("Wrong tree size %v, expected %v for %v", i, k, t.DebugString()) 174 } 175 if s != "" { 176 te.Errorf("Tree consistency problem at %v", s) 177 return 178 } else { 179 // fmt.Printf("%s", t.DebugString()) 180 } 181 } 182 183 oops := false 184 185 for _, d := range x { 186 s := fmt.Sprintf("%v", d) 187 f := t.Find(d) 188 189 // data 190 if s != fmt.Sprintf("%v", f) { 191 te.Errorf("s(%v) != f(%v)", s, f) 192 oops = true 193 } 194 } 195 196 if !oops { 197 for _, d := range x { 198 s := fmt.Sprintf("%v", d) 199 200 kg, g := t.Glb(d + 1) 201 kge, ge := t.GlbEq(d) 202 kl, l := t.Lub(d - 1) 203 kle, le := t.LubEq(d) 204 205 // keys 206 if d != kg { 207 te.Errorf("d(%v) != kg(%v)", d, kg) 208 } 209 if d != kl { 210 te.Errorf("d(%v) != kl(%v)", d, kl) 211 } 212 if d != kge { 213 te.Errorf("d(%v) != kge(%v)", d, kge) 214 } 215 if d != kle { 216 te.Errorf("d(%v) != kle(%v)", d, kle) 217 } 218 // data 219 if s != fmt.Sprintf("%v", g) { 220 te.Errorf("s(%v) != g(%v)", s, g) 221 } 222 if s != fmt.Sprintf("%v", l) { 223 te.Errorf("s(%v) != l(%v)", s, l) 224 } 225 if s != fmt.Sprintf("%v", ge) { 226 te.Errorf("s(%v) != ge(%v)", s, ge) 227 } 228 if s != fmt.Sprintf("%v", le) { 229 te.Errorf("s(%v) != le(%v)", s, le) 230 } 231 } 232 233 for _, d := range x { 234 s := fmt.Sprintf("%v", d) 235 kge, ge := t.GlbEq(d + 1) 236 kle, le := t.LubEq(d - 1) 237 if d != kge { 238 te.Errorf("d(%v) != kge(%v)", d, kge) 239 } 240 if d != kle { 241 te.Errorf("d(%v) != kle(%v)", d, kle) 242 } 243 if s != fmt.Sprintf("%v", ge) { 244 te.Errorf("s(%v) != ge(%v)", s, ge) 245 } 246 if s != fmt.Sprintf("%v", le) { 247 te.Errorf("s(%v) != le(%v)", s, le) 248 } 249 } 250 251 kg, g := t.Glb(min) 252 kge, ge := t.GlbEq(min - 1) 253 kl, l := t.Lub(max) 254 kle, le := t.LubEq(max + 1) 255 fmin := t.Find(min - 1) 256 fmax := t.Find(min + 11) 257 258 if kg != 0 || kge != 0 || kl != 0 || kle != 0 { 259 te.Errorf("Got non-zero-key for missing query") 260 } 261 262 if g != nil || ge != nil || l != nil || le != nil || fmin != nil || fmax != nil { 263 te.Errorf("Got non-error-data for missing query") 264 } 265 266 } 267 } 268 269 func TestAllRBTreeOps(t *testing.T) { 270 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}) 271 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}) 272 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}) 273 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}) 274 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}) 275 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}) 276 } 277
