Rename to BPlusTree.

pkg/analysis_server/lib/src/index/btree.dart

Index: pkg/analysis_server/lib/src/index/btree.dart
diff --git a/pkg/analysis_server/lib/src/index/btree.dart b/pkg/analysis_server/lib/src/index/btree.dart
deleted file mode 100644
index b88789635ed17dc07c9797dc3d252c5f55badbc3..0000000000000000000000000000000000000000
--- a/pkg/analysis_server/lib/src/index/btree.dart
+++ /dev/null
@@ -1,467 +0,0 @@
-// 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 index.btree;
-
-
-/**
- * A simple B+Tree implementation.
- */
-class BTree<K, V> {
-  /**
-   * The [Comparator] to compare keys.
-   */
-  final Comparator<K> _comparator;
-
-  /**
-   * The maximum number of keys in an index node.
-   */
-  final int _maxIndexKeys;
-
-  /**
-   * The maximum number of keys in a leaf node.
-   */
-  final int _maxLeafKeys;
-
-  /**
-   * The root node.
-   */
-  _Node<K, V> _root;
-
-  BTree(this._maxIndexKeys, this._maxLeafKeys, this._comparator) {
-    _root = new _LeafNode(_maxLeafKeys, _comparator);
-  }
-
-  /**
-   * Returns the value for [key] or `null` if [key] is not in the tree.
-   */
-  V find(K key) {
-    return _root.find(key);
-  }
-
-  /**
-   * Associates the [key] with the given [value].
-   *
-   * If the key was already in the tree, its associated value is changed.
-   * Otherwise the key-value pair is added to the tree.
-   */
-  void insert(K key, V value) {
-    _Split<K, V> result = _root.insert(key, value);
-    if (result != null) {
-      _IndexNode<K, V> newRoot = new _IndexNode<K, V>(_maxIndexKeys,
-          _comparator);
-      newRoot.keys.add(result.key);
-      newRoot.children.add(result.left);
-      newRoot.children.add(result.right);
-      _root = newRoot;
-    }
-  }
-
-  /**
-   * Removes the association for the given [key].
-   *
-   * Returns the value associated with [key] in the tree or `null` if [key] is
-   * not in the tree.
-   */
-  V remove(K key) {
-    _Remove<K, V> result = _root.remove(key, null, null, null);
-    if (_root is _IndexNode<K, V>) {
-      List<_Node<K, V>> children = (_root as _IndexNode<K, V>).children;
-      if (children.length == 1) {
-        _root = children[0];
-      }
-    }
-    return result.value;
-  }
-
-  /**
-   * Writes a textual presentation of the tree into [buffer].
-   */
-  void writeOn(StringBuffer buffer) {
-    _root.writeOn(buffer, '');
-  }
-}
-
-
-/**
- * An index node with keys and children references.
- */
-class _IndexNode<K, V> extends _Node<K, V> {
-  final List<_Node<K, V>> children = new List<_Node<K, V>>();
-  final int maxKeys;
-  final int minKeys;
-
-  _IndexNode(int maxKeys, Comparator<K> comparator)
-      : super(comparator),
-        maxKeys = maxKeys,
-        minKeys = maxKeys ~/ 2;
-
-  @override
-  V find(K key) {
-    int index = findChildIndex(key);
-    return children[index].find(key);
-  }
-
-  /**
-   * Returns the index of the child into which [key] should be inserted.
-   */
-  int findChildIndex(K key) {
-    for (int i = 0; i < keys.length; i++) {
-      if (comparator(keys[i], key) > 0) {
-        return i;
-      }
-    }
-    return keys.length;
-  }
-
-  _Split<K, V> insert(K key, V value) {
-    // Early split.
-    if (keys.length == maxKeys) {
-      int middle = (maxKeys + 1) ~/ 2;
-      K splitKey = keys[middle];
-      _IndexNode<K, V> sibling = new _IndexNode<K, V>(maxKeys, comparator);
-      sibling.keys.addAll(keys.getRange(middle + 1, keys.length));
-      sibling.children.addAll(children.getRange(middle + 1, children.length));
-      keys.length = middle;
-      children.length = middle + 1;
-      // Prepare split.
-      _Split<K, V> result = new _Split<K, V>(splitKey, this, sibling);
-      if (comparator(key, result.key) < 0) {
-        insertNotFull(key, value);
-      } else {
-        sibling.insertNotFull(key, value);
-      }
-      return result;
-    }
-    // No split.
-    insertNotFull(key, value);
-    return null;
-  }
-
-  void insertNotFull(K key, V value) {
-    int index = findChildIndex(key);
-    _Split<K, V> result = children[index].insert(key, value);
-    if (result != null) {
-      keys.insert(index, result.key);
-      children[index] = result.left;
-      children.insert(index + 1, result.right);
-    }
-  }
-
-  @override
-  _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right) {
-    int index = findChildIndex(key);
-    K thisAnchor = index == 0 ? keys[0] : keys[index - 1];
-    _Node<K, V> child = children[index];
-    bool hasLeft = index != 0;
-    bool hasRight = index < children.length - 1;
-    _Node<K, V> leftChild = hasLeft ? children[index - 1] : null;
-    _Node<K, V> rightChild = hasRight ? children[index + 1] : null;
-    // Ask child to remove.
-    _Remove<K, V> result = child.remove(key, leftChild, thisAnchor, rightChild);
-    V value = result.value;
-    if (value == null) {
-      return new _Remove<K, V>(value);
-    }
-    // Update anchor if borrowed.
-    if (result.leftAnchor != null) {
-      keys[index - 1] = result.leftAnchor;
-    }
-    if (result.rightAnchor != null) {
-      keys[index] = result.rightAnchor;
-    }
-    // Update keys / children if merged.
-    if (result.mergedLeft) {
-      keys.removeAt(index - 1);
-      children.removeAt(index);
-    }
-    if (result.mergedRight) {
-      keys.removeAt(index);
-      children.removeAt(index);
-    }
-    // Perform balancing.
-    if (keys.length < minKeys) {
-      // Try left sibling.
-      if (left is _IndexNode<K, V>) {
-        // Try to redistribute.
-        int leftLength = left.keys.length;
-        if (leftLength > minKeys) {
-          int halfExcess = (leftLength - minKeys + 1) ~/ 2;
-          int newLeftLength = leftLength - halfExcess;
-          keys.insert(0, anchor);
-          keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength));
-          children.insertAll(0, left.children.getRange(newLeftLength, leftLength
-              + 1));
-          K newAnchor = left.keys[newLeftLength - 1];
-          left.keys.length = newLeftLength - 1;
-          left.children.length = newLeftLength;
-          return new _Remove<K, V>.borrowLeft(value, newAnchor);
-        }
-        // Do merge.
-        left.keys.add(anchor);
-        left.keys.addAll(keys);
-        left.children.addAll(children);
-        return new _Remove<K, V>.mergeLeft(value);
-      }
-      // Try right sibling.
-      if (right is _IndexNode<K, V>) {
-        // Try to redistribute.
-        var rightLength = right.keys.length;
-        if (rightLength > minKeys) {
-          int halfExcess = (rightLength - minKeys + 1) ~/ 2;
-          keys.add(anchor);
-          keys.addAll(right.keys.getRange(0, halfExcess - 1));
-          children.addAll(right.children.getRange(0, halfExcess));
-          K newAnchor = right.keys[halfExcess - 1];
-          right.keys.removeRange(0, halfExcess);
-          right.children.removeRange(0, halfExcess);
-          return new _Remove<K, V>.borrowRight(value, newAnchor);
-        }
-        // Do merge.
-        right.keys.insert(0, anchor);
-        right.keys.insertAll(0, keys);
-        right.children.insertAll(0, children);
-        return new _Remove<K, V>.mergeRight(value);
-      }
-    }
-    // No balancing required.
-    return new _Remove<K, V>(value);
-  }
-
-  @override
-  void writeOn(StringBuffer buffer, String indent) {
-    buffer.write(indent);
-    buffer.write('INode {\n');
-    for (int i = 0; i < keys.length; i++) {
-      children[i].writeOn(buffer, indent + '    ');
-      buffer.write(indent);
-      buffer.write('  ');
-      buffer.write(keys[i]);
-      buffer.write('\n');
-    }
-    children[keys.length].writeOn(buffer, indent + '    ');
-    buffer.write(indent);
-    buffer.write('}\n');
-  }
-}
-
-
-/**
- * A leaf node with keys and values.
- */
-class _LeafNode<K, V> extends _Node<K, V> {
-  final int maxKeys;
-  final int minKeys;
-
-  /**
-   *  The list of values.
-   */
-  final List<V> values = new List<V>();
-
-  _LeafNode(int maxKeys, Comparator<K> comparator)
-      : super(comparator),
-        maxKeys = maxKeys,
-        minKeys = maxKeys ~/ 2;
-
-  @override
-  V find(K key) {
-    int index = findKeyIndex(key);
-    if (index < 0) {
-      return null;
-    }
-    if (index >= keys.length) {
-      return null;
-    }
-    if (keys[index] != key) {
-      return null;
-    }
-    return values[index];
-  }
-
-  /**
-   * Returns the index where [key] should be inserted.
-   */
-  int findKeyIndex(K key) {
-    for (int i = 0; i < keys.length; i++) {
-      if (comparator(keys[i], key) >= 0) {
-        return i;
-      }
-    }
-    return keys.length;
-  }
-
-  _Split<K, V> insert(K key, V value) {
-    int index = findKeyIndex(key);
-    // The node is full.
-    if (keys.length == maxKeys) {
-      int middle = (maxKeys + 1) ~/ 2;
-      _LeafNode<K, V> sibling = new _LeafNode<K, V>(maxKeys, comparator);
-      sibling.keys.addAll(keys.getRange(middle, keys.length));
-      sibling.values.addAll(values.getRange(middle, values.length));
-      keys.length = middle;
-      values.length = middle;
-      // Insert into the left / right sibling.
-      if (index < middle) {
-        insertNotFull(key, value, index);
-      } else {
-        sibling.insertNotFull(key, value, index - middle);
-      }
-      // Notify the parent about the split.
-      return new _Split<K, V>(sibling.keys[0], this, sibling);
-    }
-    // The node was not full.
-    insertNotFull(key, value, index);
-    return null;
-  }
-
-  void insertNotFull(K key, V value, int index) {
-    if (index < keys.length && keys[index] == key) {
-      values[index] = value;
-    } else {
-      keys.insert(index, key);
-      values.insert(index, value);
-    }
-  }
-
-  @override
-  _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right) {
-    // Find the key.
-    int index = keys.indexOf(key);
-    if (index == -1) {
-      return new _Remove<K, V>(null);
-    }
-    // Key key / value.
-    keys.removeAt(index);
-    V value = values.removeAt(index);
-    // Perform balancing.
-    if (keys.length < minKeys) {
-      // Try left sibling.
-      if (left is _LeafNode<K, V>) {
-        // Try to redistribute.
-        int leftLength = left.keys.length;
-        if (leftLength > minKeys) {
-          int halfExcess = (leftLength - minKeys + 1) ~/ 2;
-          int newLeftLength = leftLength - halfExcess;
-          keys.insertAll(0, left.keys.getRange(newLeftLength, leftLength));
-          values.insertAll(0, left.values.getRange(newLeftLength, leftLength));
-          left.keys.length = newLeftLength;
-          left.values.length = newLeftLength;
-          return new _Remove<K, V>.borrowLeft(value, keys.first);
-        }
-        // Do merge.
-        left.keys.addAll(keys);
-        left.values.addAll(values);
-        return new _Remove<K, V>.mergeLeft(value);
-      }
-      // Try right sibling.
-      if (right is _LeafNode<K, V>) {
-        // Try to redistribute.
-        var rightLength = right.keys.length;
-        if (rightLength > minKeys) {
-          int halfExcess = (rightLength - minKeys + 1) ~/ 2;
-          keys.addAll(right.keys.getRange(0, halfExcess));
-          values.addAll(right.values.getRange(0, halfExcess));
-          right.keys.removeRange(0, halfExcess);
-          right.values.removeRange(0, halfExcess);
-          return new _Remove<K, V>.borrowRight(value, right.keys.first);
-        }
-        // Do merge.
-        right.keys.insertAll(0, keys);
-        right.values.insertAll(0, values);
-        return new _Remove<K, V>.mergeRight(value);
-      }
-    }
-    // No balancing required.
-    return new _Remove<K, V>(value);
-  }
-
-  @override
-  void writeOn(StringBuffer buffer, String indent) {
-    buffer.write(indent);
-    buffer.write('LNode {');
-    for (int i = 0; i < keys.length; i++) {
-      if (i != 0) {
-        buffer.write(', ');
-      }
-      buffer.write(keys[i]);
-      buffer.write(': ');
-      buffer.write(values[i]);
-    }
-    buffer.write('}\n');
-  }
-}
-
-
-/**
- * An internal or leaf node.
- */
-abstract class _Node<K, V> {
-  /**
-   * The [Comparator] to compare keys.
-   */
-  Comparator<K> comparator;
-
-  /**
-   *  The list of keys.
-   */
-  List<K> keys = new List<K>();
-
-  _Node(this.comparator);
-
-  /**
-   * Looks for [key].
-   *
-   * Returns the associated value if found.
-   * Returns `null` if not found.
-   */
-  V find(K key);
-
-  /**
-   * Inserts the [key] / [value] pair into this [_Node].
-   *
-   * Returns a [_Split] object if split happens, or `null` otherwise.
-   */
-  _Split<K, V> insert(K key, V value);
-
-  /**
-   * Removes the association for the given [key].
-   *
-   * Returns the [_Remove] information about an operation performed.
-   * It may be restructuring or merging, with [left] or [left] siblings.
-   */
-  _Remove<K, V> remove(K key, _Node<K, V> left, K anchor, _Node<K, V> right);
-
-  /**
-   * Writes a textual presentation of the tree into [buffer].
-   */
-  void writeOn(StringBuffer buffer, String indent);
-}
-
-
-/**
- * A container with information about redistribute / merge.
- */
-class _Remove<K, V> {
-  K leftAnchor;
-  bool mergedLeft = false;
-  bool mergedRight = false;
-  K rightAnchor;
-  final V value;
-  _Remove(this.value);
-  _Remove.borrowLeft(this.value, this.leftAnchor);
-  _Remove.borrowRight(this.value, this.rightAnchor);
-  _Remove.mergeLeft(this.value) : mergedLeft = true;
-  _Remove.mergeRight(this.value) : mergedRight = true;
-}
-
-
-/**
- * A container with information about split during insert.
- */
-class _Split<K, V> {
-  final K key;
-  final _Node<K, V> left;
-  final _Node<K, V> right;
-  _Split(this.key, this.left, this.right);
-}