1package gtreap 2 3import ( 4 "bytes" 5 "testing" 6) 7 8func stringCompare(a, b interface{}) int { 9 return bytes.Compare([]byte(a.(string)), []byte(b.(string))) 10} 11 12func TestTreap(t *testing.T) { 13 x := NewTreap(stringCompare) 14 if x == nil { 15 t.Errorf("expected NewTreap to work") 16 } 17 18 tests := []struct { 19 op string 20 val string 21 pri int 22 exp string 23 }{ 24 {"get", "not-there", -1, "NIL"}, 25 {"ups", "a", 100, ""}, 26 {"get", "a", -1, "a"}, 27 {"ups", "b", 200, ""}, 28 {"get", "a", -1, "a"}, 29 {"get", "b", -1, "b"}, 30 {"ups", "c", 300, ""}, 31 {"get", "a", -1, "a"}, 32 {"get", "b", -1, "b"}, 33 {"get", "c", -1, "c"}, 34 {"get", "not-there", -1, "NIL"}, 35 {"ups", "a", 400, ""}, 36 {"get", "a", -1, "a"}, 37 {"get", "b", -1, "b"}, 38 {"get", "c", -1, "c"}, 39 {"get", "not-there", -1, "NIL"}, 40 {"del", "a", -1, ""}, 41 {"get", "a", -1, "NIL"}, 42 {"get", "b", -1, "b"}, 43 {"get", "c", -1, "c"}, 44 {"get", "not-there", -1, "NIL"}, 45 {"ups", "a", 10, ""}, 46 {"get", "a", -1, "a"}, 47 {"get", "b", -1, "b"}, 48 {"get", "c", -1, "c"}, 49 {"get", "not-there", -1, "NIL"}, 50 {"del", "a", -1, ""}, 51 {"del", "b", -1, ""}, 52 {"del", "c", -1, ""}, 53 {"get", "a", -1, "NIL"}, 54 {"get", "b", -1, "NIL"}, 55 {"get", "c", -1, "NIL"}, 56 {"get", "not-there", -1, "NIL"}, 57 {"del", "a", -1, ""}, 58 {"del", "b", -1, ""}, 59 {"del", "c", -1, ""}, 60 {"get", "a", -1, "NIL"}, 61 {"get", "b", -1, "NIL"}, 62 {"get", "c", -1, "NIL"}, 63 {"get", "not-there", -1, "NIL"}, 64 {"ups", "a", 10, ""}, 65 {"get", "a", -1, "a"}, 66 {"get", "b", -1, "NIL"}, 67 {"get", "c", -1, "NIL"}, 68 {"get", "not-there", -1, "NIL"}, 69 {"ups", "b", 1000, "b"}, 70 {"del", "b", -1, ""}, // cover join that is nil 71 {"ups", "b", 20, "b"}, 72 {"ups", "c", 12, "c"}, 73 {"del", "b", -1, ""}, // cover join second return 74 {"ups", "a", 5, "a"}, // cover upsert existing with lower priority 75 } 76 77 for testIdx, test := range tests { 78 switch test.op { 79 case "get": 80 i := x.Get(test.val) 81 if i != test.exp && !(i == nil && test.exp == "NIL") { 82 t.Errorf("test: %v, on Get, expected: %v, got: %v", testIdx, test.exp, i) 83 } 84 case "ups": 85 x = x.Upsert(test.val, test.pri) 86 case "del": 87 x = x.Delete(test.val) 88 } 89 } 90} 91 92func load(x *Treap, arr []string) *Treap { 93 for i, s := range arr { 94 x = x.Upsert(s, i) 95 } 96 return x 97} 98 99func visitExpect(t *testing.T, x *Treap, start string, arr []string) { 100 n := 0 101 x.VisitAscend(start, func(i Item) bool { 102 if i.(string) != arr[n] { 103 t.Errorf("expected visit item: %v, saw: %v", arr[n], i) 104 } 105 n++ 106 return true 107 }) 108 if n != len(arr) { 109 t.Errorf("expected # visit callbacks: %v, saw: %v", len(arr), n) 110 } 111} 112 113func TestVisit(t *testing.T) { 114 x := NewTreap(stringCompare) 115 visitExpect(t, x, "a", []string{}) 116 117 x = load(x, []string{"e", "d", "c", "c", "a", "b", "a"}) 118 119 visitX := func() { 120 visitExpect(t, x, "a", []string{"a", "b", "c", "d", "e"}) 121 visitExpect(t, x, "a1", []string{"b", "c", "d", "e"}) 122 visitExpect(t, x, "b", []string{"b", "c", "d", "e"}) 123 visitExpect(t, x, "b1", []string{"c", "d", "e"}) 124 visitExpect(t, x, "c", []string{"c", "d", "e"}) 125 visitExpect(t, x, "c1", []string{"d", "e"}) 126 visitExpect(t, x, "d", []string{"d", "e"}) 127 visitExpect(t, x, "d1", []string{"e"}) 128 visitExpect(t, x, "e", []string{"e"}) 129 visitExpect(t, x, "f", []string{}) 130 } 131 visitX() 132 133 var y *Treap 134 y = x.Upsert("f", 1) 135 y = y.Delete("a") 136 y = y.Upsert("cc", 2) 137 y = y.Delete("c") 138 139 visitExpect(t, y, "a", []string{"b", "cc", "d", "e", "f"}) 140 visitExpect(t, y, "a1", []string{"b", "cc", "d", "e", "f"}) 141 visitExpect(t, y, "b", []string{"b", "cc", "d", "e", "f"}) 142 visitExpect(t, y, "b1", []string{"cc", "d", "e", "f"}) 143 visitExpect(t, y, "c", []string{"cc", "d", "e", "f"}) 144 visitExpect(t, y, "c1", []string{"cc", "d", "e", "f"}) 145 visitExpect(t, y, "d", []string{"d", "e", "f"}) 146 visitExpect(t, y, "d1", []string{"e", "f"}) 147 visitExpect(t, y, "e", []string{"e", "f"}) 148 visitExpect(t, y, "f", []string{"f"}) 149 visitExpect(t, y, "z", []string{}) 150 151 // an uninitialized treap 152 z := NewTreap(stringCompare) 153 154 // a treap to force left traversal of min 155 lmt := NewTreap(stringCompare) 156 lmt = lmt.Upsert("b", 2) 157 lmt = lmt.Upsert("a", 1) 158 159 // The x treap should be unchanged. 160 visitX() 161 162 if x.Min() != "a" { 163 t.Errorf("expected min of a") 164 } 165 if x.Max() != "e" { 166 t.Errorf("expected max of d") 167 } 168 if y.Min() != "b" { 169 t.Errorf("expected min of b") 170 } 171 if y.Max() != "f" { 172 t.Errorf("expected max of f") 173 } 174 if z.Min() != nil { 175 t.Errorf("expected min of nil") 176 } 177 if z.Max() != nil { 178 t.Error("expected max of nil") 179 } 180 if lmt.Min() != "a" { 181 t.Errorf("expected min of a") 182 } 183 if lmt.Max() != "b" { 184 t.Errorf("expeced max of b") 185 } 186} 187 188func visitExpectEndAtC(t *testing.T, x *Treap, start string, arr []string) { 189 n := 0 190 x.VisitAscend(start, func(i Item) bool { 191 if stringCompare(i, "c") > 0 { 192 return false 193 } 194 if i.(string) != arr[n] { 195 t.Errorf("expected visit item: %v, saw: %v", arr[n], i) 196 } 197 n++ 198 return true 199 }) 200 if n != len(arr) { 201 t.Errorf("expected # visit callbacks: %v, saw: %v", len(arr), n) 202 } 203} 204 205func TestVisitEndEarly(t *testing.T) { 206 x := NewTreap(stringCompare) 207 visitExpectEndAtC(t, x, "a", []string{}) 208 209 x = load(x, []string{"e", "d", "c", "c", "a", "b", "a", "e"}) 210 211 visitX := func() { 212 visitExpectEndAtC(t, x, "a", []string{"a", "b", "c"}) 213 visitExpectEndAtC(t, x, "a1", []string{"b", "c"}) 214 visitExpectEndAtC(t, x, "b", []string{"b", "c"}) 215 visitExpectEndAtC(t, x, "b1", []string{"c"}) 216 visitExpectEndAtC(t, x, "c", []string{"c"}) 217 visitExpectEndAtC(t, x, "c1", []string{}) 218 visitExpectEndAtC(t, x, "d", []string{}) 219 visitExpectEndAtC(t, x, "d1", []string{}) 220 visitExpectEndAtC(t, x, "e", []string{}) 221 visitExpectEndAtC(t, x, "f", []string{}) 222 } 223 visitX() 224} 225 226func TestPriorityAfterUpsert(t *testing.T) { 227 // See https://github.com/steveyen/gtreap/issues/3 found by icexin. 228 229 var check func(n *node, level int, expectedPriority map[string]int) 230 check = func(n *node, level int, expectedPriority map[string]int) { 231 if n == nil { 232 return 233 } 234 if n.priority != expectedPriority[n.item.(string)] { 235 t.Errorf("wrong priority") 236 } 237 check(n.left, level+1, expectedPriority) 238 check(n.right, level+1, expectedPriority) 239 } 240 241 s := NewTreap(stringCompare) 242 s = s.Upsert("m", 20) 243 s = s.Upsert("l", 18) 244 s = s.Upsert("n", 19) 245 246 check(s.root, 0, map[string]int{ 247 "m": 20, 248 "l": 18, 249 "n": 19, 250 }) 251 252 s = s.Upsert("m", 4) 253 254 check(s.root, 0, map[string]int{ 255 "m": 20, 256 "l": 18, 257 "n": 19, 258 }) 259} 260