| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 library test.index.btree; | |
| 6 | |
| 7 import 'dart:math'; | |
| 8 | |
| 9 import 'package:analysis_server/src/index/btree.dart'; | |
| 10 import 'package:unittest/unittest.dart'; | |
| 11 | |
| 12 import '../reflective_tests.dart'; | |
| 13 | |
| 14 | |
| 15 main() { | |
| 16 groupSep = ' | '; | |
| 17 group('BTree', () { | |
| 18 runReflectiveTests(BTreeTest); | |
| 19 }); | |
| 20 } | |
| 21 | |
| 22 | |
| 23 void _assertDebugString(BTree tree, String expected) { | |
| 24 String dump = _getDebugString(tree); | |
| 25 expect(dump, expected); | |
| 26 } | |
| 27 | |
| 28 | |
| 29 String _getDebugString(BTree tree) { | |
| 30 StringBuffer buffer = new StringBuffer(); | |
| 31 tree.writeOn(buffer); | |
| 32 return buffer.toString(); | |
| 33 } | |
| 34 | |
| 35 | |
| 36 int _intComparator(int a, int b) => a - b; | |
| 37 | |
| 38 | |
| 39 @ReflectiveTestCase() | |
| 40 class BTreeTest { | |
| 41 BTree<int, String> tree = new BTree<int, String>(4, 4, _intComparator); | |
| 42 | |
| 43 test_NoSuchMethodError() { | |
| 44 expect(() { | |
| 45 (tree as dynamic).thereIsNoSuchMethod(); | |
| 46 }, throwsA(new isInstanceOf<NoSuchMethodError>())); | |
| 47 } | |
| 48 | |
| 49 void test_find() { | |
| 50 _insertValues(12); | |
| 51 expect(tree.find(-1), isNull); | |
| 52 expect(tree.find(1000), isNull); | |
| 53 for (int key = 0; key < 12; key++) { | |
| 54 expect(tree.find(key), 'V$key'); | |
| 55 } | |
| 56 } | |
| 57 | |
| 58 void test_insert_01() { | |
| 59 _insert(0, 'A'); | |
| 60 _assertDebugString(tree, 'LNode {0: A}\n'); | |
| 61 } | |
| 62 | |
| 63 void test_insert_02() { | |
| 64 _insert(1, 'B'); | |
| 65 _insert(0, 'A'); | |
| 66 _assertDebugString(tree, 'LNode {0: A, 1: B}\n'); | |
| 67 } | |
| 68 | |
| 69 void test_insert_03() { | |
| 70 _insert(2, 'C'); | |
| 71 _insert(0, 'A'); | |
| 72 _insert(1, 'B'); | |
| 73 _assertDebugString(tree, 'LNode {0: A, 1: B, 2: C}\n'); | |
| 74 } | |
| 75 | |
| 76 void test_insert_05() { | |
| 77 _insertValues(5); | |
| 78 _assertDebugString(tree, ''' | |
| 79 INode { | |
| 80 LNode {0: V0, 1: V1} | |
| 81 2 | |
| 82 LNode {2: V2, 3: V3, 4: V4} | |
| 83 } | |
| 84 '''); | |
| 85 } | |
| 86 | |
| 87 void test_insert_09() { | |
| 88 _insertValues(9); | |
| 89 _assertDebugString(tree, ''' | |
| 90 INode { | |
| 91 LNode {0: V0, 1: V1} | |
| 92 2 | |
| 93 LNode {2: V2, 3: V3} | |
| 94 4 | |
| 95 LNode {4: V4, 5: V5} | |
| 96 6 | |
| 97 LNode {6: V6, 7: V7, 8: V8} | |
| 98 } | |
| 99 '''); | |
| 100 } | |
| 101 | |
| 102 void test_insert_innerSplitLeft() { | |
| 103 // Prepare a tree with '0' key missing. | |
| 104 for (int i = 1; i < 12; i++) { | |
| 105 _insert(i, "V$i"); | |
| 106 } | |
| 107 _assertDebugString(tree, ''' | |
| 108 INode { | |
| 109 LNode {1: V1, 2: V2} | |
| 110 3 | |
| 111 LNode {3: V3, 4: V4} | |
| 112 5 | |
| 113 LNode {5: V5, 6: V6} | |
| 114 7 | |
| 115 LNode {7: V7, 8: V8} | |
| 116 9 | |
| 117 LNode {9: V9, 10: V10, 11: V11} | |
| 118 } | |
| 119 '''); | |
| 120 // Split and insert into the 'left' child. | |
| 121 _insert(0, 'V0'); | |
| 122 _assertDebugString(tree, ''' | |
| 123 INode { | |
| 124 INode { | |
| 125 LNode {0: V0, 1: V1, 2: V2} | |
| 126 3 | |
| 127 LNode {3: V3, 4: V4} | |
| 128 5 | |
| 129 LNode {5: V5, 6: V6} | |
| 130 } | |
| 131 7 | |
| 132 INode { | |
| 133 LNode {7: V7, 8: V8} | |
| 134 9 | |
| 135 LNode {9: V9, 10: V10, 11: V11} | |
| 136 } | |
| 137 } | |
| 138 '''); | |
| 139 } | |
| 140 | |
| 141 void test_insert_innerSplitRight() { | |
| 142 _insertValues(12); | |
| 143 _assertDebugString(tree, ''' | |
| 144 INode { | |
| 145 INode { | |
| 146 LNode {0: V0, 1: V1} | |
| 147 2 | |
| 148 LNode {2: V2, 3: V3} | |
| 149 4 | |
| 150 LNode {4: V4, 5: V5} | |
| 151 } | |
| 152 6 | |
| 153 INode { | |
| 154 LNode {6: V6, 7: V7} | |
| 155 8 | |
| 156 LNode {8: V8, 9: V9, 10: V10, 11: V11} | |
| 157 } | |
| 158 } | |
| 159 '''); | |
| 160 } | |
| 161 | |
| 162 void test_insert_replace() { | |
| 163 _insert(0, 'A'); | |
| 164 _insert(1, 'B'); | |
| 165 _insert(2, 'C'); | |
| 166 _assertDebugString(tree, 'LNode {0: A, 1: B, 2: C}\n'); | |
| 167 _insert(2, 'C2'); | |
| 168 _insert(1, 'B2'); | |
| 169 _insert(0, 'A2'); | |
| 170 _assertDebugString(tree, 'LNode {0: A2, 1: B2, 2: C2}\n'); | |
| 171 } | |
| 172 | |
| 173 void test_remove_inner_borrowLeft() { | |
| 174 tree = new BTree<int, String>(10, 4, _intComparator); | |
| 175 for (int i = 100; i < 125; i++) { | |
| 176 _insert(i, 'V$i'); | |
| 177 } | |
| 178 for (int i = 0; i < 10; i++) { | |
| 179 _insert(i, 'V$i'); | |
| 180 } | |
| 181 _assertDebugString(tree, ''' | |
| 182 INode { | |
| 183 INode { | |
| 184 LNode {0: V0, 1: V1} | |
| 185 2 | |
| 186 LNode {2: V2, 3: V3} | |
| 187 4 | |
| 188 LNode {4: V4, 5: V5} | |
| 189 6 | |
| 190 LNode {6: V6, 7: V7} | |
| 191 8 | |
| 192 LNode {8: V8, 9: V9, 100: V100, 101: V101} | |
| 193 102 | |
| 194 LNode {102: V102, 103: V103} | |
| 195 104 | |
| 196 LNode {104: V104, 105: V105} | |
| 197 106 | |
| 198 LNode {106: V106, 107: V107} | |
| 199 108 | |
| 200 LNode {108: V108, 109: V109} | |
| 201 110 | |
| 202 LNode {110: V110, 111: V111} | |
| 203 } | |
| 204 112 | |
| 205 INode { | |
| 206 LNode {112: V112, 113: V113} | |
| 207 114 | |
| 208 LNode {114: V114, 115: V115} | |
| 209 116 | |
| 210 LNode {116: V116, 117: V117} | |
| 211 118 | |
| 212 LNode {118: V118, 119: V119} | |
| 213 120 | |
| 214 LNode {120: V120, 121: V121} | |
| 215 122 | |
| 216 LNode {122: V122, 123: V123, 124: V124} | |
| 217 } | |
| 218 } | |
| 219 '''); | |
| 220 expect(tree.remove(112), 'V112'); | |
| 221 _assertDebugString(tree, ''' | |
| 222 INode { | |
| 223 INode { | |
| 224 LNode {0: V0, 1: V1} | |
| 225 2 | |
| 226 LNode {2: V2, 3: V3} | |
| 227 4 | |
| 228 LNode {4: V4, 5: V5} | |
| 229 6 | |
| 230 LNode {6: V6, 7: V7} | |
| 231 8 | |
| 232 LNode {8: V8, 9: V9, 100: V100, 101: V101} | |
| 233 102 | |
| 234 LNode {102: V102, 103: V103} | |
| 235 104 | |
| 236 LNode {104: V104, 105: V105} | |
| 237 } | |
| 238 106 | |
| 239 INode { | |
| 240 LNode {106: V106, 107: V107} | |
| 241 108 | |
| 242 LNode {108: V108, 109: V109} | |
| 243 110 | |
| 244 LNode {110: V110, 111: V111} | |
| 245 112 | |
| 246 LNode {113: V113, 114: V114, 115: V115} | |
| 247 116 | |
| 248 LNode {116: V116, 117: V117} | |
| 249 118 | |
| 250 LNode {118: V118, 119: V119} | |
| 251 120 | |
| 252 LNode {120: V120, 121: V121} | |
| 253 122 | |
| 254 LNode {122: V122, 123: V123, 124: V124} | |
| 255 } | |
| 256 } | |
| 257 '''); | |
| 258 } | |
| 259 | |
| 260 void test_remove_inner_borrowRight() { | |
| 261 tree = new BTree<int, String>(10, 4, _intComparator); | |
| 262 for (int i = 100; i < 135; i++) { | |
| 263 _insert(i, 'V$i'); | |
| 264 } | |
| 265 _assertDebugString(tree, ''' | |
| 266 INode { | |
| 267 INode { | |
| 268 LNode {100: V100, 101: V101} | |
| 269 102 | |
| 270 LNode {102: V102, 103: V103} | |
| 271 104 | |
| 272 LNode {104: V104, 105: V105} | |
| 273 106 | |
| 274 LNode {106: V106, 107: V107} | |
| 275 108 | |
| 276 LNode {108: V108, 109: V109} | |
| 277 110 | |
| 278 LNode {110: V110, 111: V111} | |
| 279 } | |
| 280 112 | |
| 281 INode { | |
| 282 LNode {112: V112, 113: V113} | |
| 283 114 | |
| 284 LNode {114: V114, 115: V115} | |
| 285 116 | |
| 286 LNode {116: V116, 117: V117} | |
| 287 118 | |
| 288 LNode {118: V118, 119: V119} | |
| 289 120 | |
| 290 LNode {120: V120, 121: V121} | |
| 291 122 | |
| 292 LNode {122: V122, 123: V123} | |
| 293 124 | |
| 294 LNode {124: V124, 125: V125} | |
| 295 126 | |
| 296 LNode {126: V126, 127: V127} | |
| 297 128 | |
| 298 LNode {128: V128, 129: V129} | |
| 299 130 | |
| 300 LNode {130: V130, 131: V131} | |
| 301 132 | |
| 302 LNode {132: V132, 133: V133, 134: V134} | |
| 303 } | |
| 304 } | |
| 305 '''); | |
| 306 expect(tree.remove(100), 'V100'); | |
| 307 _assertDebugString(tree, ''' | |
| 308 INode { | |
| 309 INode { | |
| 310 LNode {101: V101, 102: V102, 103: V103} | |
| 311 104 | |
| 312 LNode {104: V104, 105: V105} | |
| 313 106 | |
| 314 LNode {106: V106, 107: V107} | |
| 315 108 | |
| 316 LNode {108: V108, 109: V109} | |
| 317 110 | |
| 318 LNode {110: V110, 111: V111} | |
| 319 112 | |
| 320 LNode {112: V112, 113: V113} | |
| 321 114 | |
| 322 LNode {114: V114, 115: V115} | |
| 323 116 | |
| 324 LNode {116: V116, 117: V117} | |
| 325 } | |
| 326 118 | |
| 327 INode { | |
| 328 LNode {118: V118, 119: V119} | |
| 329 120 | |
| 330 LNode {120: V120, 121: V121} | |
| 331 122 | |
| 332 LNode {122: V122, 123: V123} | |
| 333 124 | |
| 334 LNode {124: V124, 125: V125} | |
| 335 126 | |
| 336 LNode {126: V126, 127: V127} | |
| 337 128 | |
| 338 LNode {128: V128, 129: V129} | |
| 339 130 | |
| 340 LNode {130: V130, 131: V131} | |
| 341 132 | |
| 342 LNode {132: V132, 133: V133, 134: V134} | |
| 343 } | |
| 344 } | |
| 345 '''); | |
| 346 } | |
| 347 | |
| 348 void test_remove_inner_mergeLeft() { | |
| 349 _insertValues(15); | |
| 350 _assertDebugString(tree, ''' | |
| 351 INode { | |
| 352 INode { | |
| 353 LNode {0: V0, 1: V1} | |
| 354 2 | |
| 355 LNode {2: V2, 3: V3} | |
| 356 4 | |
| 357 LNode {4: V4, 5: V5} | |
| 358 } | |
| 359 6 | |
| 360 INode { | |
| 361 LNode {6: V6, 7: V7} | |
| 362 8 | |
| 363 LNode {8: V8, 9: V9} | |
| 364 10 | |
| 365 LNode {10: V10, 11: V11} | |
| 366 12 | |
| 367 LNode {12: V12, 13: V13, 14: V14} | |
| 368 } | |
| 369 } | |
| 370 '''); | |
| 371 expect(tree.remove(12), 'V12'); | |
| 372 expect(tree.remove(13), 'V13'); | |
| 373 expect(tree.remove(14), 'V14'); | |
| 374 _assertDebugString(tree, ''' | |
| 375 INode { | |
| 376 INode { | |
| 377 LNode {0: V0, 1: V1} | |
| 378 2 | |
| 379 LNode {2: V2, 3: V3} | |
| 380 4 | |
| 381 LNode {4: V4, 5: V5} | |
| 382 } | |
| 383 6 | |
| 384 INode { | |
| 385 LNode {6: V6, 7: V7} | |
| 386 8 | |
| 387 LNode {8: V8, 9: V9} | |
| 388 10 | |
| 389 LNode {10: V10, 11: V11} | |
| 390 } | |
| 391 } | |
| 392 '''); | |
| 393 expect(tree.remove(8), 'V8'); | |
| 394 _assertDebugString(tree, ''' | |
| 395 INode { | |
| 396 LNode {0: V0, 1: V1} | |
| 397 2 | |
| 398 LNode {2: V2, 3: V3} | |
| 399 4 | |
| 400 LNode {4: V4, 5: V5} | |
| 401 6 | |
| 402 LNode {6: V6, 7: V7, 9: V9} | |
| 403 10 | |
| 404 LNode {10: V10, 11: V11} | |
| 405 } | |
| 406 '''); | |
| 407 } | |
| 408 | |
| 409 void test_remove_inner_mergeRight() { | |
| 410 _insertValues(12); | |
| 411 _assertDebugString(tree, ''' | |
| 412 INode { | |
| 413 INode { | |
| 414 LNode {0: V0, 1: V1} | |
| 415 2 | |
| 416 LNode {2: V2, 3: V3} | |
| 417 4 | |
| 418 LNode {4: V4, 5: V5} | |
| 419 } | |
| 420 6 | |
| 421 INode { | |
| 422 LNode {6: V6, 7: V7} | |
| 423 8 | |
| 424 LNode {8: V8, 9: V9, 10: V10, 11: V11} | |
| 425 } | |
| 426 } | |
| 427 '''); | |
| 428 expect(tree.remove(0), 'V0'); | |
| 429 _assertDebugString(tree, ''' | |
| 430 INode { | |
| 431 LNode {1: V1, 2: V2, 3: V3} | |
| 432 4 | |
| 433 LNode {4: V4, 5: V5} | |
| 434 6 | |
| 435 LNode {6: V6, 7: V7} | |
| 436 8 | |
| 437 LNode {8: V8, 9: V9, 10: V10, 11: V11} | |
| 438 } | |
| 439 '''); | |
| 440 } | |
| 441 | |
| 442 void test_remove_inner_notFound() { | |
| 443 _insertValues(20); | |
| 444 expect(tree.remove(100), isNull); | |
| 445 } | |
| 446 | |
| 447 void test_remove_leafRoot_becomesEmpty() { | |
| 448 _insertValues(1); | |
| 449 _assertDebugString(tree, 'LNode {0: V0}\n'); | |
| 450 expect(tree.remove(0), 'V0'); | |
| 451 _assertDebugString(tree, 'LNode {}\n'); | |
| 452 } | |
| 453 | |
| 454 void test_remove_leafRoot_first() { | |
| 455 _insertValues(3); | |
| 456 _assertDebugString(tree, 'LNode {0: V0, 1: V1, 2: V2}\n'); | |
| 457 expect(tree.remove(0), 'V0'); | |
| 458 _assertDebugString(tree, 'LNode {1: V1, 2: V2}\n'); | |
| 459 } | |
| 460 | |
| 461 void test_remove_leafRoot_last() { | |
| 462 _insertValues(3); | |
| 463 _assertDebugString(tree, 'LNode {0: V0, 1: V1, 2: V2}\n'); | |
| 464 expect(tree.remove(2), 'V2'); | |
| 465 _assertDebugString(tree, 'LNode {0: V0, 1: V1}\n'); | |
| 466 } | |
| 467 | |
| 468 void test_remove_leafRoot_middle() { | |
| 469 _insertValues(3); | |
| 470 _assertDebugString(tree, 'LNode {0: V0, 1: V1, 2: V2}\n'); | |
| 471 expect(tree.remove(1), 'V1'); | |
| 472 _assertDebugString(tree, 'LNode {0: V0, 2: V2}\n'); | |
| 473 } | |
| 474 | |
| 475 void test_remove_leafRoot_notFound() { | |
| 476 _insertValues(1); | |
| 477 _assertDebugString(tree, 'LNode {0: V0}\n'); | |
| 478 expect(tree.remove(10), null); | |
| 479 _assertDebugString(tree, 'LNode {0: V0}\n'); | |
| 480 } | |
| 481 | |
| 482 void test_remove_leaf_borrowLeft() { | |
| 483 tree = new BTree<int, String>(10, 10, _intComparator); | |
| 484 for (int i = 20; i < 40; i++) { | |
| 485 _insert(i, 'V$i'); | |
| 486 } | |
| 487 for (int i = 0; i < 5; i++) { | |
| 488 _insert(i, 'V$i'); | |
| 489 } | |
| 490 _assertDebugString(tree, ''' | |
| 491 INode { | |
| 492 LNode {0: V0, 1: V1, 2: V2, 3: V3, 4: V4, 20: V20, 21: V21, 22: V22, 23: V23
, 24: V24} | |
| 493 25 | |
| 494 LNode {25: V25, 26: V26, 27: V27, 28: V28, 29: V29} | |
| 495 30 | |
| 496 LNode {30: V30, 31: V31, 32: V32, 33: V33, 34: V34, 35: V35, 36: V36, 37: V3
7, 38: V38, 39: V39} | |
| 497 } | |
| 498 '''); | |
| 499 expect(tree.remove(25), 'V25'); | |
| 500 _assertDebugString(tree, ''' | |
| 501 INode { | |
| 502 LNode {0: V0, 1: V1, 2: V2, 3: V3, 4: V4, 20: V20, 21: V21} | |
| 503 22 | |
| 504 LNode {22: V22, 23: V23, 24: V24, 26: V26, 27: V27, 28: V28, 29: V29} | |
| 505 30 | |
| 506 LNode {30: V30, 31: V31, 32: V32, 33: V33, 34: V34, 35: V35, 36: V36, 37: V3
7, 38: V38, 39: V39} | |
| 507 } | |
| 508 '''); | |
| 509 } | |
| 510 | |
| 511 void test_remove_leaf_borrowRight() { | |
| 512 tree = new BTree<int, String>(10, 10, _intComparator); | |
| 513 _insertValues(15); | |
| 514 _assertDebugString(tree, ''' | |
| 515 INode { | |
| 516 LNode {0: V0, 1: V1, 2: V2, 3: V3, 4: V4} | |
| 517 5 | |
| 518 LNode {5: V5, 6: V6, 7: V7, 8: V8, 9: V9, 10: V10, 11: V11, 12: V12, 13: V13
, 14: V14} | |
| 519 } | |
| 520 '''); | |
| 521 expect(tree.remove(0), 'V0'); | |
| 522 _assertDebugString(tree, ''' | |
| 523 INode { | |
| 524 LNode {1: V1, 2: V2, 3: V3, 4: V4, 5: V5, 6: V6, 7: V7} | |
| 525 8 | |
| 526 LNode {8: V8, 9: V9, 10: V10, 11: V11, 12: V12, 13: V13, 14: V14} | |
| 527 } | |
| 528 '''); | |
| 529 } | |
| 530 | |
| 531 void test_remove_leaf_mergeLeft() { | |
| 532 _insertValues(9); | |
| 533 _assertDebugString(tree, ''' | |
| 534 INode { | |
| 535 LNode {0: V0, 1: V1} | |
| 536 2 | |
| 537 LNode {2: V2, 3: V3} | |
| 538 4 | |
| 539 LNode {4: V4, 5: V5} | |
| 540 6 | |
| 541 LNode {6: V6, 7: V7, 8: V8} | |
| 542 } | |
| 543 '''); | |
| 544 expect(tree.remove(2), 'V2'); | |
| 545 _assertDebugString(tree, ''' | |
| 546 INode { | |
| 547 LNode {0: V0, 1: V1, 3: V3} | |
| 548 4 | |
| 549 LNode {4: V4, 5: V5} | |
| 550 6 | |
| 551 LNode {6: V6, 7: V7, 8: V8} | |
| 552 } | |
| 553 '''); | |
| 554 } | |
| 555 | |
| 556 void test_remove_leaf_mergeRight() { | |
| 557 _insertValues(9); | |
| 558 _assertDebugString(tree, ''' | |
| 559 INode { | |
| 560 LNode {0: V0, 1: V1} | |
| 561 2 | |
| 562 LNode {2: V2, 3: V3} | |
| 563 4 | |
| 564 LNode {4: V4, 5: V5} | |
| 565 6 | |
| 566 LNode {6: V6, 7: V7, 8: V8} | |
| 567 } | |
| 568 '''); | |
| 569 expect(tree.remove(1), 'V1'); | |
| 570 _assertDebugString(tree, ''' | |
| 571 INode { | |
| 572 LNode {0: V0, 2: V2, 3: V3} | |
| 573 4 | |
| 574 LNode {4: V4, 5: V5} | |
| 575 6 | |
| 576 LNode {6: V6, 7: V7, 8: V8} | |
| 577 } | |
| 578 '''); | |
| 579 } | |
| 580 | |
| 581 void test_remove_leaf_noReorder() { | |
| 582 _insertValues(5); | |
| 583 _assertDebugString(tree, ''' | |
| 584 INode { | |
| 585 LNode {0: V0, 1: V1} | |
| 586 2 | |
| 587 LNode {2: V2, 3: V3, 4: V4} | |
| 588 } | |
| 589 '''); | |
| 590 expect(tree.remove(3), 'V3'); | |
| 591 _assertDebugString(tree, ''' | |
| 592 INode { | |
| 593 LNode {0: V0, 1: V1} | |
| 594 2 | |
| 595 LNode {2: V2, 4: V4} | |
| 596 } | |
| 597 '''); | |
| 598 } | |
| 599 | |
| 600 void test_stress_evenOdd() { | |
| 601 int count = 1000; | |
| 602 // insert odd, forward | |
| 603 for (int i = 1; i < count; i += 2) { | |
| 604 _insert(i, 'V$i'); | |
| 605 } | |
| 606 // insert even, backward | |
| 607 for (int i = count - 2; i >= 0; i -= 2) { | |
| 608 _insert(i, 'V$i'); | |
| 609 } | |
| 610 // find every | |
| 611 for (int i = 0; i < count; i++) { | |
| 612 expect(tree.find(i), 'V$i'); | |
| 613 } | |
| 614 // remove odd, backward | |
| 615 for (int i = count - 1; i >= 1; i -= 2) { | |
| 616 expect(tree.remove(i), 'V$i'); | |
| 617 } | |
| 618 for (int i = 0; i < count; i++) { | |
| 619 if (i.isEven) { | |
| 620 expect(tree.find(i), 'V$i'); | |
| 621 } else { | |
| 622 expect(tree.find(i), isNull); | |
| 623 } | |
| 624 } | |
| 625 // remove even, forward | |
| 626 for (int i = 0; i < count; i += 2) { | |
| 627 tree.remove(i); | |
| 628 } | |
| 629 for (int i = 0; i < count; i++) { | |
| 630 expect(tree.find(i), isNull); | |
| 631 } | |
| 632 } | |
| 633 | |
| 634 void test_stress_random() { | |
| 635 tree = new BTree<int, String>(10, 10, _intComparator); | |
| 636 int maxKey = 1000000; | |
| 637 int tryCount = 1000; | |
| 638 Set<int> keys = new Set<int>(); | |
| 639 { | |
| 640 Random random = new Random(); | |
| 641 for (int i = 0; i < tryCount; i++) { | |
| 642 int key = random.nextInt(maxKey); | |
| 643 keys.add(key); | |
| 644 _insert(key, 'V$key'); | |
| 645 } | |
| 646 } | |
| 647 // find every | |
| 648 for (int key in keys) { | |
| 649 expect(tree.find(key), 'V$key'); | |
| 650 } | |
| 651 // remove random keys | |
| 652 { | |
| 653 Random random = new Random(); | |
| 654 for (int key in new Set<int>.from(keys)) { | |
| 655 if (random.nextBool()) { | |
| 656 keys.remove(key); | |
| 657 expect(tree.remove(key), 'V$key'); | |
| 658 } | |
| 659 } | |
| 660 } | |
| 661 // find every remaining key | |
| 662 for (int key in keys) { | |
| 663 expect(tree.find(key), 'V$key'); | |
| 664 } | |
| 665 } | |
| 666 | |
| 667 void _insert(int key, String value) { | |
| 668 tree.insert(key, value); | |
| 669 } | |
| 670 | |
| 671 void _insertValues(int count) { | |
| 672 for (int i = 0; i < count; i++) { | |
| 673 _insert(i, 'V$i'); | |
| 674 } | |
| 675 } | |
| 676 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 320723002:
Rename to BPlusTree. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart