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