| OLD | NEW |
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 library test.index.b_plus_tree; | 5 library test.index.b_plus_tree; |
| 6 | 6 |
| 7 import 'dart:math'; | 7 import 'dart:math'; |
| 8 | 8 |
| 9 import 'package:analysis_server/src/index/b_plus_tree.dart'; | 9 import 'package:analysis_server/src/index/b_plus_tree.dart'; |
| 10 import 'package:unittest/unittest.dart'; | 10 import 'package:unittest/unittest.dart'; |
| (...skipping 624 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 635 expect(tree.find(i), isNull); | 635 expect(tree.find(i), isNull); |
| 636 } | 636 } |
| 637 } | 637 } |
| 638 | 638 |
| 639 void test_stress_random() { | 639 void test_stress_random() { |
| 640 tree = _createTree(10, 10); | 640 tree = _createTree(10, 10); |
| 641 int maxKey = 1000000; | 641 int maxKey = 1000000; |
| 642 int tryCount = 1000; | 642 int tryCount = 1000; |
| 643 Set<int> keys = new Set<int>(); | 643 Set<int> keys = new Set<int>(); |
| 644 { | 644 { |
| 645 Random random = new Random(); | 645 Random random = new Random(37); |
| 646 for (int i = 0; i < tryCount; i++) { | 646 for (int i = 0; i < tryCount; i++) { |
| 647 int key = random.nextInt(maxKey); | 647 int key = random.nextInt(maxKey); |
| 648 keys.add(key); | 648 keys.add(key); |
| 649 _insert(key, 'V$key'); | 649 _insert(key, 'V$key'); |
| 650 } | 650 } |
| 651 } | 651 } |
| 652 // find every | 652 // find every |
| 653 for (int key in keys) { | 653 for (int key in keys) { |
| 654 expect(tree.find(key), 'V$key'); | 654 expect(tree.find(key), 'V$key'); |
| 655 } | 655 } |
| 656 // remove random keys | 656 // remove random keys |
| 657 { | 657 { |
| 658 Random random = new Random(); | 658 Random random = new Random(37); |
| 659 for (int key in new Set<int>.from(keys)) { | 659 for (int key in new Set<int>.from(keys)) { |
| 660 if (random.nextBool()) { | 660 if (random.nextBool()) { |
| 661 keys.remove(key); | 661 keys.remove(key); |
| 662 expect(tree.remove(key), 'V$key'); | 662 expect(tree.remove(key), 'V$key'); |
| 663 } | 663 } |
| 664 } | 664 } |
| 665 } | 665 } |
| 666 // find every remaining key | 666 // find every remaining key |
| 667 for (int key in keys) { | 667 for (int key in keys) { |
| 668 expect(tree.find(key), 'V$key'); | 668 expect(tree.find(key), 'V$key'); |
| 669 } | 669 } |
| 670 } | 670 } |
| 671 | 671 |
| 672 void _insert(int key, String value) { | 672 void _insert(int key, String value) { |
| 673 tree.insert(key, value); | 673 tree.insert(key, value); |
| 674 } | 674 } |
| 675 | 675 |
| 676 void _insertValues(int count) { | 676 void _insertValues(int count) { |
| 677 for (int i = 0; i < count; i++) { | 677 for (int i = 0; i < count; i++) { |
| 678 _insert(i, 'V$i'); | 678 _insert(i, 'V$i'); |
| 679 } | 679 } |
| 680 } | 680 } |
| 681 } | 681 } |
| 682 | 682 |
| 683 class _TestBTree<K, V> extends BPlusTree<K, V, int> { | 683 class _TestBTree<K, V> extends BPlusTree<K, V, int> { |
| 684 _TestBTree(int maxIndexKeys, int maxLeafKeys, Comparator<K> comparator) : | 684 _TestBTree(int maxIndexKeys, int maxLeafKeys, Comparator<K> comparator) : |
| 685 super(comparator, new MemoryNodeManager(maxIndexKeys, maxLeafKeys)); | 685 super(comparator, new MemoryNodeManager(maxIndexKeys, maxLeafKeys)); |
| 686 } | 686 } |
| OLD | NEW |