Create/read/write/delete nodes using NodeManager.

pkg/analysis_server/test/index/b_plus_tree_test.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library test.index.b_plus_tree;
 
 import 'dart:math';
 
 import 'package:analysis_server/src/index/b_plus_tree.dart';
 import 'package:unittest/unittest.dart';
 
 import '../reflective_tests.dart';
 
 
 main() {
   groupSep = ' | ';
   group('BTree', () {
     runReflectiveTests(BPlusTreeTest);
   });
 }
 
 
 void _assertDebugString(BPlusTree tree, String expected) {
   String dump = _getDebugString(tree);
   expect(dump, expected);
 }
 
 
+_TestBTree<int, String> _createTree(int maxIndexKeys, int maxLeafKeys) {
+  return new _TestBTree<int, String>(maxIndexKeys, maxLeafKeys, _intComparator);
+}
+
+
 String _getDebugString(BPlusTree tree) {
   StringBuffer buffer = new StringBuffer();
   tree.writeOn(buffer);
   return buffer.toString();
 }
 
 
 int _intComparator(int a, int b) => a - b;
 
 
 @ReflectiveTestCase()
 class BPlusTreeTest {
-  BPlusTree<int, String> tree = new BPlusTree<int, String>(4, 4, _intComparator);
+  BPlusTree<int, String, dynamic> tree = _createTree(4, 4);
 
   test_NoSuchMethodError() {
     expect(() {
       (tree as dynamic).thereIsNoSuchMethod();
     }, throwsA(new isInstanceOf<NoSuchMethodError>()));
   }
 
   void test_find() {
     _insertValues(12);
     expect(tree.find(-1), isNull);
@@ skipping 112 matching lines @@
     _insert(1, 'B');
     _insert(2, 'C');
     _assertDebugString(tree, 'LNode {0: A, 1: B, 2: C}\n');
     _insert(2, 'C2');
     _insert(1, 'B2');
     _insert(0, 'A2');
     _assertDebugString(tree, 'LNode {0: A2, 1: B2, 2: C2}\n');
   }
 
   void test_remove_inner_borrowLeft() {
-    tree = new BPlusTree<int, String>(10, 4, _intComparator);
+    tree = _createTree(10, 4);
     for (int i = 100; i < 125; i++) {
       _insert(i, 'V$i');
     }
     for (int i = 0; i < 10; i++) {
       _insert(i, 'V$i');
     }
     _assertDebugString(tree, '''
 INode {
     INode {
         LNode {0: V0, 1: V1}
@@ skipping 66 matching lines @@
       120
         LNode {120: V120, 121: V121}
       122
         LNode {122: V122, 123: V123, 124: V124}
     }
 }
 ''');
   }
 
   void test_remove_inner_borrowRight() {
-    tree = new BPlusTree<int, String>(10, 4, _intComparator);
+    tree = _createTree(10, 4);
     for (int i = 100; i < 135; i++) {
       _insert(i, 'V$i');
     }
     _assertDebugString(tree, '''
 INode {
     INode {
         LNode {100: V100, 101: V101}
       102
         LNode {102: V102, 103: V103}
       104
@@ skipping 201 matching lines @@
   }
 
   void test_remove_leafRoot_notFound() {
     _insertValues(1);
     _assertDebugString(tree, 'LNode {0: V0}\n');
     expect(tree.remove(10), null);
     _assertDebugString(tree, 'LNode {0: V0}\n');
   }
 
   void test_remove_leaf_borrowLeft() {
-    tree = new BPlusTree<int, String>(10, 10, _intComparator);
+    tree = _createTree(10, 10);
     for (int i = 20; i < 40; i++) {
       _insert(i, 'V$i');
     }
     for (int i = 0; i < 5; i++) {
       _insert(i, 'V$i');
     }
     _assertDebugString(tree, '''
 INode {
     LNode {0: V0, 1: V1, 2: V2, 3: V3, 4: V4, 20: V20, 21: V21, 22: V22, 23: V23, 24: V24}
   25
     LNode {25: V25, 26: V26, 27: V27, 28: V28, 29: V29}
   30
     LNode {30: V30, 31: V31, 32: V32, 33: V33, 34: V34, 35: V35, 36: V36, 37: V37, 38: V38, 39: V39}
 }
 ''');
     expect(tree.remove(25), 'V25');
     _assertDebugString(tree, '''
 INode {
     LNode {0: V0, 1: V1, 2: V2, 3: V3, 4: V4, 20: V20, 21: V21}
   22
     LNode {22: V22, 23: V23, 24: V24, 26: V26, 27: V27, 28: V28, 29: V29}
   30
     LNode {30: V30, 31: V31, 32: V32, 33: V33, 34: V34, 35: V35, 36: V36, 37: V37, 38: V38, 39: V39}
 }
 ''');
   }
 
   void test_remove_leaf_borrowRight() {
-    tree = new BPlusTree<int, String>(10, 10, _intComparator);
+    tree = _createTree(10, 10);
     _insertValues(15);
     _assertDebugString(tree, '''
 INode {
     LNode {0: V0, 1: V1, 2: V2, 3: V3, 4: V4}
   5
     LNode {5: V5, 6: V6, 7: V7, 8: V8, 9: V9, 10: V10, 11: V11, 12: V12, 13: V13, 14: V14}
 }
 ''');
     expect(tree.remove(0), 'V0');
     _assertDebugString(tree, '''
@@ skipping 102 matching lines @@
     // remove even, forward
     for (int i = 0; i < count; i += 2) {
       tree.remove(i);
     }
     for (int i = 0; i < count; i++) {
       expect(tree.find(i), isNull);
     }
   }
 
   void test_stress_random() {
-    tree = new BPlusTree<int, String>(10, 10, _intComparator);
+    tree = _createTree(10, 10);
     int maxKey = 1000000;
     int tryCount = 1000;
     Set<int> keys = new Set<int>();
     {
       Random random = new Random();
       for (int i = 0; i < tryCount; i++) {
         int key = random.nextInt(maxKey);
         keys.add(key);
         _insert(key, 'V$key');
       }
@@ skipping 21 matching lines @@
   void _insert(int key, String value) {
     tree.insert(key, value);
   }
 
   void _insertValues(int count) {
     for (int i = 0; i < count; i++) {
       _insert(i, 'V$i');
     }
   }
 }
+
+class _TestBTree<K, V> extends BPlusTree<K, V, int> {
+  _TestBTree(int maxIndexKeys, int maxLeafKeys, Comparator<K> comparator) :
+      super(maxIndexKeys, maxLeafKeys, comparator, new MemoryNodeManager());
+}