Backport B+ tree implementation from Dart to Java.

Backport B+ tree implementation from Dart to Java.

Only in-memory implementation for in this CL.

Helper classes don't have separate tests yet.

R=brianwilkerson@google.com
BUG=

Committed: https://code.google.com/p/dart/source/detail?r=37316

[Brian Wilkerson, 2014-06-13 13:55:01]

LGTM

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java:31:
public class BTree<K, V, N> {
I thought we had renamed this to BPlusTree.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java:35:
class IndexNode extends Node {
I thought we had renamed this to InternalNode.

Mark this class as private too?

Do the nested classes really need internal state from the tree? If not, they
should be marked as "static".

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java:197:
void writeOn(StringBuffer buffer, String indent) {
StringBuilder is more efficient, so if this is called often it would be worth
changing.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/IndexNodeData.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/IndexNodeData.java:1:
package com.google.dart.engine.internal.index.structure.btree;
Copyright

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/LeafNodeData.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/LeafNodeData.java:1:
package com.google.dart.engine.internal.index.structure.btree;
Copyright

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/MemoryNodeManager.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/MemoryNodeManager.java:1:
package com.google.dart.engine.internal.index.structure.btree;
Copyright

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/NodeManager.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/NodeManager.java:1:
package com.google.dart.engine.internal.index.structure.btree;
Copyright

[scheglov, 2014-06-13 15:32:54]

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java:31:
public class BTree<K, V, N> {
On 2014/06/13 13:55:00, Brian Wilkerson wrote:
> I thought we had renamed this to BPlusTree.

Fixed.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java:35:
class IndexNode extends Node {
On 2014/06/13 13:55:00, Brian Wilkerson wrote:
> I thought we had renamed this to InternalNode.

Renamed.


> Mark this class as private too?

Done.

> 
> Do the nested classes really need internal state from the tree? If not, they
> should be marked as "static".

Yes, we access type variables, manager and comparator from the enclosed class.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/BTree.java:197:
void writeOn(StringBuffer buffer, String indent) {
On 2014/06/13 13:55:00, Brian Wilkerson wrote:
> StringBuilder is more efficient, so if this is called often it would be worth
> changing.

Done.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/IndexNodeData.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/IndexNodeData.java:1:
package com.google.dart.engine.internal.index.structure.btree;
On 2014/06/13 13:55:01, Brian Wilkerson wrote:
> Copyright

Done.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/LeafNodeData.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/LeafNodeData.java:1:
package com.google.dart.engine.internal.index.structure.btree;
On 2014/06/13 13:55:01, Brian Wilkerson wrote:
> Copyright

Done.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/MemoryNodeManager.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/MemoryNodeManager.java:1:
package com.google.dart.engine.internal.index.structure.btree;
On 2014/06/13 13:55:01, Brian Wilkerson wrote:
> Copyright

Done.

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
File
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/NodeManager.java
(right):

https://codereview.chromium.org/338503002/diff/20001/editor/tools/plugins/com...
editor/tools/plugins/com.google.dart.engine/src/com/google/dart/engine/internal/index/structure/btree/NodeManager.java:1:
package com.google.dart.engine.internal.index.structure.btree;
On 2014/06/13 13:55:01, Brian Wilkerson wrote:
> Copyright

Done.

[scheglov, 2014-06-13 15:33:33]

Committed patchset #3 manually as r37316 (presubmit successful).