changeset 6079:f55d346fb998

Refactor StreamBuilder to be a NodeBuilder that extends from Node.
author psandoz
date Mon, 15 Oct 2012 15:44:27 -0700
parents 121debc3d4be
children b04cf326ce82
files src/share/classes/java/util/streams/AbstractPipeline.java src/share/classes/java/util/streams/StreamBuilder.java src/share/classes/java/util/streams/StreamBuilders.java src/share/classes/java/util/streams/ValuePipeline.java src/share/classes/java/util/streams/ops/ConcatOp.java src/share/classes/java/util/streams/ops/CumulateOp.java src/share/classes/java/util/streams/ops/FlatMapOp.java src/share/classes/java/util/streams/ops/GroupByOp.java src/share/classes/java/util/streams/ops/LimitOp.java src/share/classes/java/util/streams/ops/MapLimitOp.java src/share/classes/java/util/streams/ops/Node.java src/share/classes/java/util/streams/ops/NodeBuilder.java src/share/classes/java/util/streams/ops/Nodes.java src/share/classes/java/util/streams/ops/StatefulOp.java src/share/classes/java/util/streams/ops/ToArrayOp.java src/share/classes/java/util/streams/ops/TreeUtils.java src/share/classes/java/util/streams/ops/UniqOp.java test-ng/tests/org/openjdk/tests/java/util/streams/StreamBuilderTest.java test-ng/tests/org/openjdk/tests/java/util/streams/ops/NodeBuilderTest.java
diffstat 19 files changed, 809 insertions(+), 849 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/streams/AbstractPipeline.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/AbstractPipeline.java	Mon Oct 15 15:44:27 2012 -0700
@@ -110,7 +110,7 @@
 
             if (upToOp < ops.length) {
                 StatefulOp op = (StatefulOp) ops[upToOp];
-                TreeUtils.Node<?> intermediateResult = evaluateParallel(accessor, ops, fromOp, upToOp, op);
+                Node<?> intermediateResult = evaluateParallel(accessor, ops, fromOp, upToOp, op);
                 // @@@ Inherit other flags from pipeline e.g. the intermediate result may be sorted and/or distinct,
                 //     and is ordered
                 accessor = new Streams.SpliteratorStreamAccessor(intermediateResult.spliterator(),
@@ -124,9 +124,9 @@
         }
     }
 
-    private <R> TreeUtils.Node<R> evaluateParallel(StreamAccessor source, IntermediateOp[] ops, int from, int to,
+    private <R> Node<R> evaluateParallel(StreamAccessor source, IntermediateOp[] ops, int from, int to,
                                                    StatefulOp<?, R> terminal) {
-        return (TreeUtils.Node<R>) terminal.evaluateParallel(new ParallelImplPipelineHelper(source, ops, from, to));
+        return (Node<R>) terminal.evaluateParallel(new ParallelImplPipelineHelper(source, ops, from, to));
     }
 
     private <R> R evaluateParallel(StreamAccessor<?> source, IntermediateOp[] ops, int from, int to,
--- a/src/share/classes/java/util/streams/StreamBuilder.java	Mon Oct 15 15:35:20 2012 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,43 +0,0 @@
-/*
- * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.  Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package java.util.streams;
-
-import java.util.*;
-import java.util.functions.Block;
-
-/**
- * StreamBuilder
- *
- * @author Brian Goetz
- */
-public interface StreamBuilder<T> extends Sized, Streamable<Stream<T>>, Traversable<T>, Collection<T>, Sink.OfValue<T> {
-
-    @Override
-    void forEach(Block<? super T> block);
-
-    void clear();
-
-    Object[] toArray();
-}
--- a/src/share/classes/java/util/streams/StreamBuilders.java	Mon Oct 15 15:35:20 2012 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,391 +0,0 @@
-/*
- * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.  Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package java.util.streams;
-
-import java.util.*;
-import java.util.functions.Block;
-import java.util.logging.Logger;
-
-/**
- * Utilities for building streams.
- * <p/>
- * @author Brian Goetz
- */
-public class StreamBuilders {
-    // No instances
-
-    private StreamBuilders() {
-    }
-
-    public static <T> StreamBuilder<T> makeFixed(int size) {
-        return new FixedStreamBuilder<>(size);
-    }
-
-    public static <T> StreamBuilder<T> make() {
-        return new SimpleSpinedStreamBuilder<>();
-    }
-
-    public static <T> StreamBuilder<T> make(int initialSize) {
-        return new SimpleSpinedStreamBuilder<>(initialSize);
-    }
-
-    private static boolean equals(StreamBuilder a, StreamBuilder b) {
-        if (a.size() != b.size())
-            return false;
-        Iterator it1 = a.iterator();
-        Iterator it2 = b.iterator();
-        while (it1.hasNext()) {
-            Object x1 = it1.next();
-            Object x2 = it2.next();
-            if (!x1.equals(x2))
-                return false;
-        }
-        return true;
-    }
-
-    private static <T> int hashCode(StreamBuilder<T> sb) {
-        int h = 0;
-        for (T t : sb) {
-            h = 31 * h + Objects.hashCode(t);
-        }
-        return h;
-    }
-
-    private static class FixedStreamBuilder<T> extends AbstractCollection<T> implements StreamBuilder<T> {
-
-        private final T[] array;
-        private int curSize;
-
-        public FixedStreamBuilder(int size) {
-            array = (T[])new Object[size];
-        }
-
-        @Override
-        public void begin(int size) {
-            curSize = 0;
-            if (size > array.length) {
-                Logger.getLogger(StreamBuilders.class.getName()).warning("Estimate greater than length. There might be blood.");
-            }
-        }
-
-        @Override
-        public void accept(T t) {
-            if (curSize < array.length) {
-                array[curSize++] = t;
-            } else {
-                throw new IllegalStateException("Exceeded maximum size for FixedStreamBuilder");
-            }
-        }
-
-        @Override
-        public void forEach(Block<? super T> block) {
-            for (int i = 0; i < curSize; i++) {
-                block.apply(array[i]);
-            }
-        }
-
-        @Override
-        public Stream<T> stream() {
-            return Streams.stream(this, size());
-        }
-
-        @Override
-        public Iterator<T> iterator() {
-            return Arrays.iterator(array, 0, curSize);
-        }
-
-        @Override
-        public void clear() {
-            curSize = 0;
-        }
-
-        @Override
-        public int size() {
-            return curSize;
-        }
-
-        @Override
-        public Object[] toArray() {
-            if (curSize == array.length) {
-                return array;
-            } else {
-                // @@@ Should this throw ISE instead?
-                return Arrays.copyOf(array, curSize);
-            }
-        }
-
-        @Override
-        public int hashCode() {
-            return StreamBuilders.hashCode(this);
-        }
-
-        @Override
-        public boolean equals(Object obj) {
-            if (!(obj instanceof StreamBuilder))
-                return false;
-            return StreamBuilders.equals(this, (StreamBuilder)obj);
-        }
-
-        @Override
-        public String toString() {
-            return String.format("FixedStreamBuilder[%d][%s]", array.length - curSize, Arrays.toString(array));
-        }
-    }
-
-    private static class SimpleSpinedStreamBuilder<T> extends AbstractCollection<T> implements StreamBuilder<T> {
-
-        private final static int CHUNKS_SIZE = 32;
-        private final static int CHUNK_SIZE = 1024;
-        private T[][] chunks = (T[][])new Object[CHUNKS_SIZE][];
-        private int size = 0;
-        private int capacity = 0;
-
-        private SimpleSpinedStreamBuilder(int initialSize) {
-            ensureCapacity(initialSize);
-        }
-
-        private SimpleSpinedStreamBuilder() {
-            this(16);
-        }
-
-        private void ensureCapacity(int capacity) {
-            while (this.capacity < capacity) {
-                int chunk = this.capacity / CHUNK_SIZE;
-                if (chunk >= chunks.length) {
-                    chunks = Arrays.copyOf(chunks, chunks.length + CHUNKS_SIZE);
-                }
-
-                chunks[chunk] = (T[])new Object[CHUNK_SIZE];
-                this.capacity += CHUNK_SIZE;
-            }
-        }
-
-        @Override
-        public void begin(int size) {
-            clear();
-            if (size >= 0) {
-                ensureCapacity(size);
-            }
-        }
-
-        @Override
-        public void accept(T t) {
-            int chunk = size / CHUNK_SIZE;
-            int inChunk = size % CHUNK_SIZE;
-            if (0 == inChunk) {
-                ensureCapacity(size + 1);
-            }
-
-            chunks[chunk][inChunk] = t;
-            size++;
-        }
-
-        @Override
-        public int size() {
-            return size;
-        }
-
-        @Override
-        public Stream<T> stream() {
-            return Streams.stream(this, size());
-        }
-
-        @Override
-        public void forEach(Block<? super T> block) {
-            int finalChunk = size / CHUNK_SIZE;
-            int finalIndex = size % CHUNK_SIZE;
-
-            for (int chunk = 0; chunk < finalChunk; chunk++) {
-                for (T t : chunks[chunk]) {
-                    block.apply(t);
-                }
-            }
-
-            if (finalIndex > 0) {
-                // final chunk.
-                T[] partialChunk = chunks[finalChunk];
-                for (int index = 0; index < finalIndex; index++) {
-                    block.apply(partialChunk[index]);
-                }
-            }
-        }
-
-        @Override
-        public Iterator<T> iterator() {
-            Iterator<T> result = new Iterator<T>() {
-                final int finalChunk = size / CHUNK_SIZE;
-                final int finalIndex = size % CHUNK_SIZE;
-
-                int chunk = 0;
-                int index = 0;
-
-                @Override
-                public boolean hasNext() {
-                    return chunk < finalChunk || index < finalIndex;
-                }
-
-                @Override
-                public T next() {
-                    if (!hasNext()) {
-                        throw new NoSuchElementException();
-                    }
-
-                    T result = chunks[chunk][index++];
-
-                    if (index == CHUNK_SIZE) {
-                        index = 0;
-                        chunk++;
-                    }
-
-                    return result;
-                }
-            };
-
-            return result;
-        }
-
-        @Override
-        public void clear() {
-            size = 0;
-        }
-
-        @Override
-        public Object[] toArray() {
-            Object[] result = new Object[size];
-
-            int finalChunk = size / CHUNK_SIZE;
-            int finalIndex = size % CHUNK_SIZE;
-            int index = 0;
-            int chunk = 0;
-
-            // full chunks
-            while (chunk < finalChunk) {
-                System.arraycopy(chunks[chunk++], 0, result, index, CHUNK_SIZE);
-                index += CHUNK_SIZE;
-            }
-
-            // final bit.
-            System.arraycopy(chunks[chunk], 0, result, index, finalIndex);
-
-            return result;
-        }
-
-        @Override
-        public int hashCode() {
-            return StreamBuilders.hashCode(this);
-        }
-
-        @Override
-        public String toString() {
-            return String.format("SimpleSpinedStreamBuilder[%s]", Arrays.toString(toArray()));
-        }
-
-        @Override
-        public boolean equals(Object obj) {
-            if (!(obj instanceof StreamBuilder))
-                return false;
-            return StreamBuilders.equals(this, (StreamBuilder)obj);
-        }
-
-        @Override
-        public boolean isEmpty() {
-            return size != 0;
-        }
-    }
-
-    private static class VariableStreamBuilder<T> extends AbstractCollection<T> implements StreamBuilder<T> {
-        // Junky initial implementation that involves excessive copying.
-
-        private final ArrayList<T> list;
-
-        private VariableStreamBuilder(int initialSize) {
-            list = new ArrayList<>(initialSize);
-        }
-
-        private VariableStreamBuilder() {
-            this(16);
-        }
-
-        @Override
-        public void begin(int size) {
-            list.clear();
-            if (size >= 0) {
-                list.ensureCapacity(size);
-            }
-        }
-
-        @Override
-        public void accept(T t) {
-            list.add(t);
-        }
-
-        @Override
-        public int size() {
-            return list.size();
-        }
-
-        @Override
-        public Stream<T> stream() {
-            return Streams.stream(this, size());
-        }
-
-        @Override
-        public void forEach(Block<? super T> block) {
-            list.forEach(block);
-        }
-
-        @Override
-        public Iterator<T> iterator() {
-            return list.iterator();
-        }
-
-        @Override
-        public void clear() {
-            list.clear();
-        }
-
-        @Override
-        public Object[] toArray() {
-            return list.toArray();
-        }
-
-        @Override
-        public int hashCode() {
-            return StreamBuilders.hashCode(this);
-        }
-
-        @Override
-        public String toString() {
-            return String.format("VariableStreamBuilder[%s]", list);
-        }
-
-        @Override
-        public boolean equals(Object obj) {
-            if (!(obj instanceof StreamBuilder))
-                return false;
-            return StreamBuilders.equals(this, (StreamBuilder)obj);
-        }
-    }
-}
--- a/src/share/classes/java/util/streams/ValuePipeline.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ValuePipeline.java	Mon Oct 15 15:44:27 2012 -0700
@@ -164,7 +164,7 @@
             return this;
         }
         else {
-            TreeUtils.Node<U> collected = evaluate(TreeUtils.CollectorOp.<U>singleton());
+            Node<U> collected = evaluate(TreeUtils.CollectorOp.<U>singleton());
             return Streams.stream(collected, collected.size());
         }
     }
--- a/src/share/classes/java/util/streams/ops/ConcatOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/ConcatOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -57,18 +57,18 @@
     }
 
     @Override
-    public <S> TreeUtils.Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
+    public <S> Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
         // Get all stuff from upstream
-        TreeUtils.Node<T> upStreamNode = TreeUtils.collect(helper, false);
+        Node<T> upStreamNode = TreeUtils.collect(helper, false);
 
         // Get stuff from concatenation
-        TreeUtils.Node<T> concatStreamNode = computeParallelFromConcatenatingStream();
+        Node<T> concatStreamNode = computeParallelFromConcatenatingStream();
 
         // Combine
-        return TreeUtils.node(upStreamNode, concatStreamNode);
+        return Nodes.node(upStreamNode, concatStreamNode);
     }
 
-    protected abstract TreeUtils.Node<T> computeParallelFromConcatenatingStream();
+    protected abstract Node<T> computeParallelFromConcatenatingStream();
 
     // @@@ Support Streamable
     //     This will ensure the operation can be used in detached pipelines
@@ -112,7 +112,7 @@
             }
 
             @Override
-            protected TreeUtils.Node<T> computeParallelFromConcatenatingStream() {
+            protected Node<T> computeParallelFromConcatenatingStream() {
                 // Get stuff from concat stream
                 if (stream.isParallel() && stream instanceof AbstractPipeline) {
                     // @@@ Yuk! the cast sucks, but it avoids uncessary wrapping
@@ -121,18 +121,18 @@
                 }
                 else {
                     // @@@ Yuk! too much copying
-                    final StreamBuilder<T> sb = StreamBuilders.make();
+                    final NodeBuilder<T> nb = Nodes.makeBuilder();
 
-                    // @@@ stream.into(sb) fails because the StreamBuilder does not implement the full contract
+                    // @@@ stream.into(sb) fails because the NodeBuilder does not implement the full contract
                     // of Collection
 
-                    sb.begin(-1);
+                    nb.begin(-1);
                     Iterator<? extends T> i = stream.iterator();
                     while (i.hasNext())
-                        sb.accept(i.next());
-                    sb.end();
+                        nb.accept(i.next());
+                    nb.end();
 
-                    return TreeUtils.node(sb);
+                    return nb;
                 }
             }
 
@@ -175,7 +175,7 @@
             }
 
             @Override
-            protected TreeUtils.Node<Mapping<K, V>> computeParallelFromConcatenatingStream() {
+            protected Node<Mapping<K, V>> computeParallelFromConcatenatingStream() {
                 // @@@ Not currently possible to create TreeUtils.Node from a MapStream source
                 throw new UnsupportedOperationException();
             }
--- a/src/share/classes/java/util/streams/ops/CumulateOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/CumulateOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -113,7 +113,7 @@
     }
 
     @Override
-    public <S> TreeUtils.Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
+    public <S> Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
         return helper.invoke(new CumulateTask<>(helper.spliterator(), op, helper));
     }
 
@@ -130,17 +130,17 @@
         }
     }
 
-    private class CumulateTask<S> extends RecursiveTask<TreeUtils.Node<T>> {
+    private class CumulateTask<S> extends RecursiveTask<Node<T>> {
         private final Problem<S, T> problem;
         private final Spliterator<S> spliterator;
         private final boolean isRoot;
         private CumulateTask<S> left, right;
-        private StreamBuilder<T> leafData;
+        private NodeBuilder<T> leafData;
         private boolean isLeaf;
         private T upward;
         private T downward;
         private boolean downwardZero = false;
-        private StreamBuilder<T> result;
+        private NodeBuilder<T> result;
 
         private CumulateTask(Spliterator<S> spliterator,
                              BinaryOperator<T> op,
@@ -157,7 +157,7 @@
         }
 
         @Override
-        protected TreeUtils.Node<T> compute() {
+        protected Node<T> compute() {
             switch (problem.pass) {
                 case 0:
                     int remaining = spliterator.estimateSize();
@@ -177,13 +177,13 @@
                         }
                     }
                     else {
-                        leafData = StreamBuilders.make();
+                        leafData = Nodes.makeBuilder();
                         TerminalSink<T, T> terminalSink = wrapSink(leafData);
                         problem.helper.into(spliterator, terminalSink);
                         upward = terminalSink.getAndClearState();
                         // Special case -- if problem.depth == 0, just wrap the result and be done
                         if (isRoot)
-                            return TreeUtils.node(leafData);
+                            return leafData;
                     }
                     return null;
 
@@ -200,13 +200,13 @@
                             right.downward = problem.op.operate(downward, left.upward);
                         }
                         right.fork();
-                        TreeUtils.Node<T> leftResult = left.compute();
-                        TreeUtils.Node<T> rightResult = right.join();
-                        return TreeUtils.node(leftResult, rightResult);
+                        Node<T> leftResult = left.compute();
+                        Node<T> rightResult = right.join();
+                        return Nodes.node(leftResult, rightResult);
                     }
                     else {
-                        // @@@ Pretty inefficient; should update in place when we have a better StreamBuilder representation
-                        result = StreamBuilders.makeFixed(leafData.size());
+                        // @@@ Pretty inefficient; should update in place when we have a better NodeBuilder representation
+                        result = Nodes.makeBuilder(leafData.size());
                         if (downwardZero) {
                             leafData.forEach(result);
                         }
@@ -214,7 +214,7 @@
                             for (T t : leafData)
                                 result.accept(problem.op.operate(downward, t));
                         }
-                        return TreeUtils.node(result);
+                        return result;
                     }
 
                 default:
--- a/src/share/classes/java/util/streams/ops/FlatMapOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/FlatMapOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -67,7 +67,7 @@
     public static<T, R> Iterator<R> iterator(final Iterator<T> iterator, final FlatMapper<? super T, R> mapper) {
         return new Iterator<R>() {
             final Iterator<? extends T> source = iterator;
-            StreamBuilder<R> buffer = StreamBuilders.make();
+            NodeBuilder<R> buffer = Nodes.makeBuilder();
             Iterator<R> currentMapped = null;
 
             @Override
--- a/src/share/classes/java/util/streams/ops/GroupByOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/GroupByOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -54,7 +54,7 @@
     // Public for tests
     public TerminalSink<T, Map<K, Collection<T>>> sink() {
         return new TerminalSink<T, Map<K, Collection<T>>>() {
-            private Map<K, StreamBuilder<T>> map;
+            private Map<K, NodeBuilder<T>> map;
 
             @Override
             public void begin(int size) {
@@ -63,7 +63,7 @@
 
             @Override
             public Map<K, Collection<T>> getAndClearState() {
-                // @@@ Fragile cast, need a better way to switch StreamBuilder into Collection
+                // @@@ Fragile cast, need a better way to switch NodeBuilder into Collection
                 Map<K, Collection<T>> result = (Map) map;
                 map = null;
                 return result;
@@ -72,9 +72,9 @@
             @Override
             public void accept(T t) {
                 K key = Objects.requireNonNull(mapper.map(t), String.format("The element %s cannot be mapped to a null key", t));
-                StreamBuilder<T> sb = map.get(key);
+                NodeBuilder<T> sb = map.get(key);
                 if (sb == null) {
-                    sb = StreamBuilders.make();
+                    sb = Nodes.makeBuilder();
                     map.put(key, sb);
                 }
                 sb.accept(t);
@@ -95,14 +95,14 @@
             Logger.getLogger(getClass().getName()).log(Level.WARNING, "GroupByOp.evaluateParallel does not preserve encounter order");
         }
 
-        final ConcurrentHashMap<K, StreamBuilder<T>> map = new ConcurrentHashMap<>();
+        final ConcurrentHashMap<K, NodeBuilder<T>> map = new ConcurrentHashMap<>();
 
         // Cache the sink chain, so it can be reused by all F/J leaf tasks
         Sink<S, ?, ?> sinkChain = helper.wrapSink(new Sink.OfValue<T>() {
             @Override
             public void accept(T t) {
                 K key = Objects.requireNonNull(mapper.map(t), String.format("The element %s cannot be mapped to a null key", t));
-                StreamBuilder<T> sb = map.computeIfAbsent(key, (k) -> StreamBuilders.make());
+                NodeBuilder<T> sb = map.computeIfAbsent(key, (k) -> Nodes.makeBuilder());
                 synchronized (sb) {
                     sb.accept(t);
                 }
@@ -112,7 +112,7 @@
         GroupByTask<S, T> task = new GroupByTask<>(helper, sinkChain);
         helper.invoke(task);
 
-        // @@@ Fragile cast, need a better way to switch StreamBuilder into Collection
+        // @@@ Fragile cast, need a better way to switch NodeBuilder into Collection
         return (Map) map;
     }
 
--- a/src/share/classes/java/util/streams/ops/LimitOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/LimitOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -60,18 +60,18 @@
     }
 
     @Override
-    public <S> TreeUtils.Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
+    public <S> Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
         // Dumb serial implementation defering to iterator
         final Iterator<T> i = wrapIterator(helper.iterator());
 
         // @@@ if limit is small enough can use fixed size builder
-        final StreamBuilder<T> sb = StreamBuilders.make();
-        sb.begin(limit); // @@@ what if source is smaller than limit?
+        final NodeBuilder<T> nb = Nodes.makeBuilder();
+        nb.begin(limit); // @@@ what if source is smaller than limit?
         while (i.hasNext())
-            sb.accept(i.next());
-        sb.end();
+            nb.accept(i.next());
+        nb.end();
 
-        return TreeUtils.node(sb);
+        return nb;
     }
 
     public static <T> Iterator<T> iterator(Iterator<T> source, int limit) {
--- a/src/share/classes/java/util/streams/ops/MapLimitOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/MapLimitOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -56,18 +56,18 @@
     }
 
     @Override
-    public <S> TreeUtils.Node<Mapping<K, V>> evaluateParallel(ParallelPipelineHelper<S, Mapping<K, V>> helper) {
+    public <S> Node<Mapping<K, V>> evaluateParallel(ParallelPipelineHelper<S, Mapping<K, V>> helper) {
         // Dumb serial implementation defering to iterator
         final MapIterator<K, V> i = (MapIterator<K,V>) helper.iterator();
 
         // @@@ if limit is small enough can use fixed size builder
-        final StreamBuilder<Mapping<K, V>> sb = StreamBuilders.make();
-        sb.begin(limit);
+        final NodeBuilder<Mapping<K, V>> nb = Nodes.makeBuilder();
+        nb.begin(limit);
         while (i.hasNext())
-            sb.accept(i.nextKey(), i.curValue());
-        sb.end();
+            nb.accept(i.nextKey(), i.curValue());
+        nb.end();
 
-        return TreeUtils.node(sb);
+        return nb;
     }
 
     public static <K, V> MapIterator<K, V> iterator(final MapIterator<K, V> source,
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/streams/ops/Node.java	Mon Oct 15 15:44:27 2012 -0700
@@ -0,0 +1,41 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package java.util.streams.ops;
+
+import java.util.Sized;
+import java.util.Traversable;
+import java.util.streams.Spliterator;
+
+public interface Node<T> extends Traversable<T>, Sized {
+
+    void copyTo(T[] array, int offset);
+
+    Spliterator<T> spliterator();
+
+    interface ConcNode<T> extends Node<T> {
+
+        Node<T>[] nodes();
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/streams/ops/NodeBuilder.java	Mon Oct 15 15:44:27 2012 -0700
@@ -0,0 +1,55 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package java.util.streams.ops;
+
+import java.util.*;
+import java.util.functions.Block;
+import java.util.streams.Sink;
+import java.util.streams.ops.Node;
+
+/**
+ * NodeBuilder
+ *
+ * @author Brian Goetz
+ */
+// @@@ Support in place update for CumulateOp use-case
+public interface NodeBuilder<T> extends Node<T>, Collection<T>, Sink.OfValue<T> {
+
+    @Override
+    void forEach(Block<? super T> block);
+
+    @Override
+    void clear();
+
+    @Override
+    Object[] toArray();
+
+    /**
+     * View the node builder as a collection.
+     *
+     * @return the collection.
+     */
+    Collection<T> asCollection();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/streams/ops/Nodes.java	Mon Oct 15 15:44:27 2012 -0700
@@ -0,0 +1,556 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package java.util.streams.ops;
+
+import java.util.*;
+import java.util.functions.Block;
+import java.util.logging.Logger;
+import java.util.streams.*;
+
+public class Nodes {
+
+    public static<T> Node<T> node(final T[] array) {
+        return new ArrayNode<>(array);
+    }
+
+    private static class ArrayNode<T> extends AbstractCollection<T> implements Node<T> {
+
+        final T[] array;
+        int curSize;
+
+        ArrayNode(int size) {
+            array = (T[])new Object[size];
+        }
+
+        ArrayNode(T[] array) {
+            this.array = array;
+            this.curSize = array.length;
+        }
+
+        //
+
+        @Override
+        public Spliterator<T> spliterator() {
+            return Arrays.spliterator(array, 0, curSize);
+        }
+
+        @Override
+        public void copyTo(T[] dest, int destOffset) {
+            System.arraycopy(array, 0, dest, destOffset, curSize);
+        }
+
+        //
+
+        @Override
+        public void forEach(Block<? super T> block) {
+            for (int i = 0; i < curSize; i++) {
+                block.apply(array[i]);
+            }
+        }
+
+        @Override
+        public Stream<T> stream() {
+            return Streams.stream(this, size());
+        }
+
+        @Override
+        public Iterator<T> iterator() {
+            return Arrays.iterator(array, 0, curSize);
+        }
+
+        @Override
+        public void clear() {
+            curSize = 0;
+        }
+
+        @Override
+        public int size() {
+            return curSize;
+        }
+
+        @Override
+        public Object[] toArray() {
+            if (curSize == array.length) {
+                return array;
+            } else {
+                // @@@ Should this throw ISE instead?
+                return Arrays.copyOf(array, curSize);
+            }
+        }
+
+        @Override
+        public String toString() {
+            return String.format("ArrayNode[%d][%s]", array.length - curSize, Arrays.toString(array));
+        }
+    }
+
+    @SafeVarargs
+    public static<T> Node.ConcNode<T> node(Node<T>... nodes) {
+        return new ConcNodeImpl<>(nodes);
+    }
+
+    private static class ConcNodeImpl<T> implements Node.ConcNode<T> {
+        final Node<T>[] nodes;
+        int size = 0;
+
+        private ConcNodeImpl(Node<T>[] nodes) {
+            this.nodes = nodes;
+        }
+
+        @Override
+        public int size() {
+            if (size == 0) {
+                for (Node<T> n : nodes)
+                    size += n.size();
+            }
+            return size;
+        }
+
+        @Override
+        public void forEach(Block<? super T> block) {
+            for (Node<T> n : nodes)
+                n.forEach(block);
+        }
+
+        @Override
+        public Iterator<T> iterator() {
+            return Iterators.concat(Arrays.stream(nodes).map(n -> n.iterator()).iterator());
+        }
+
+        @Override
+        public Spliterator<T> spliterator() {
+            return new ConcNodeSpliterator<>(this);
+        }
+
+        @Override
+        public void copyTo(T[] array, int offset) {
+            int s = 0;
+            for (Node<T> n : nodes) {
+                n.copyTo(array, offset+s);
+                s += n.size();
+            }
+        }
+
+        @Override
+        public String toString() {
+            return String.format("ConcNode[%s]", Arrays.stream(nodes).map(n -> n.toString()).into(new StringJoiner(",")).toString());
+        }
+
+        @Override
+        public Node<T>[] nodes() {
+            return nodes;
+        }
+
+        private static class ConcNodeSpliterator<T> implements Spliterator<T>, Iterator<T> {
+            private Node<T> cur;
+            private int splitsLeft;
+            private int nextSplitIndex;
+            private Iterator<T> iterator;
+
+            private ConcNodeSpliterator(ConcNodeImpl<T> cur) {
+                this.cur = cur;
+                splitsLeft = cur.nodes.length - 1;
+            }
+
+            public Iterator<T> iterator() {
+                if (iterator == null)
+                    iterator = cur.iterator();
+                return iterator;
+            }
+
+            @Override
+            public int getNaturalSplits() {
+                return splitsLeft;
+            }
+
+            @Override
+            public Spliterator<T> split() {
+                if (iterator != null)
+                    throw new IllegalStateException("split after iterate");
+                else if (splitsLeft == 0 || !(cur instanceof ConcNode))
+                    return Streams.emptySpliterator();
+                else {
+                    Node<T>[] nodes = ((ConcNode<T>) cur).nodes();
+                    Spliterator<T> ret = nodes[nextSplitIndex++].spliterator();
+                    if (--splitsLeft == 0) {
+                        cur = nodes[nextSplitIndex];
+                        if (cur instanceof ConcNode) {
+                            Node<T>[] newNodes  = ((ConcNode<T>) cur).nodes();
+                            splitsLeft = newNodes.length - 1;
+                            nextSplitIndex = 0;
+                        }
+                        else {
+                            splitsLeft = 0;
+                            nextSplitIndex = -1;
+                        }
+                    }
+                    return ret;
+                }
+            }
+
+            @Override
+            public void into(Sink<T, ?, ?> sink) {
+                sink.begin(getSizeIfKnown());
+                if (iterator == null) {
+                    cur.forEach(sink);
+                    iterator = Collections.emptyIterator();
+                }
+                else {
+                    while (iterator.hasNext())
+                        sink.accept(iterator.next());
+                }
+                sink.end();
+            }
+
+            @Override
+            public int getSizeIfKnown() {
+                return (iterator == null) ? cur.size() : -1;
+            }
+
+            @Override
+            public boolean isPredictableSplits() {
+                return true;
+            }
+
+            @Override
+            public boolean hasNext() {
+                return iterator().hasNext();
+            }
+
+            @Override
+            public T next() {
+                return iterator().next();
+            }
+        }
+    }
+
+    // Node builders
+
+    /**
+     * Make a fixed node builder of known size, unless the size is negative, in which case make a non-fixed size
+     * node builder.
+     *
+     * @param size the known size, or -1 if the size is not known.
+     * @return the node builder.
+     */
+    public static <T> NodeBuilder<T> makeBuilder(int size) {
+        return (size >= 0) ? new FixedNodeBuilder<T>(size)
+                           : Nodes.<T>makeBuilder();
+    }
+
+    /**
+     * Make a non-fixed stream builder.
+     *
+     * @return the stream builder.
+     */
+    public static <T> NodeBuilder<T> makeBuilder() {
+        return new SimpleSpinedNodeBuilder<>();
+    }
+
+    public static <T> NodeBuilder<T> makeBuilderWithInitialSize(int initialSize) {
+        return new SimpleSpinedNodeBuilder<>(initialSize);
+    }
+
+    private static class FixedNodeBuilder<T> extends ArrayNode<T> implements NodeBuilder<T> {
+
+        private FixedNodeBuilder(int size) {
+            super(size);
+        }
+
+        @Override
+        public Collection<T> asCollection() {
+            return this;
+        }
+
+        //
+
+        @Override
+        public Stream<T> stream() {
+            return Streams.stream(this, size());
+        }
+
+        @Override
+        public Stream<T> parallel() {
+            return Streams.parallel(spliterator(), size());
+        }
+
+        //
+
+        @Override
+        public void begin(int size) {
+            curSize = 0;
+            if (size > array.length) {
+                Logger.getLogger(Nodes.class.getName()).warning("Estimate greater than length. There might be blood.");
+            }
+        }
+
+        @Override
+        public void accept(T t) {
+            if (curSize < array.length) {
+                array[curSize++] = t;
+            } else {
+                throw new IllegalStateException("Exceeded maximum size for FixedNodeBuilder");
+            }
+        }
+
+        @Override
+        public void end() {
+            // @@@ begin(size ) and curSize
+        }
+
+        //
+
+        @Override
+        public int hashCode() {
+            return Nodes.hashCode(this);
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (!(obj instanceof NodeBuilder))
+                return false;
+            return Nodes.equals(this, (NodeBuilder) obj);
+        }
+
+        @Override
+        public String toString() {
+            return String.format("FixedNodeBuilder[%d][%s]", array.length - curSize, Arrays.toString(array));
+        }
+    }
+
+    private static class SimpleSpinedNodeBuilder<T> extends AbstractCollection<T> implements NodeBuilder<T> {
+
+        private final static int CHUNKS_SIZE = 32;
+        private final static int CHUNK_SIZE = 1024;
+        private T[][] chunks = (T[][])new Object[CHUNKS_SIZE][];
+        private int size = 0;
+        private int capacity = 0;
+
+        private SimpleSpinedNodeBuilder(int initialSize) {
+            ensureCapacity(initialSize);
+        }
+
+        private SimpleSpinedNodeBuilder() {
+            this(16);
+        }
+
+        private void ensureCapacity(int capacity) {
+            while (this.capacity < capacity) {
+                int chunk = this.capacity / CHUNK_SIZE;
+                if (chunk >= chunks.length) {
+                    chunks = Arrays.copyOf(chunks, chunks.length + CHUNKS_SIZE);
+                }
+
+                chunks[chunk] = (T[])new Object[CHUNK_SIZE];
+                this.capacity += CHUNK_SIZE;
+            }
+        }
+
+        @Override
+        public Collection<T> asCollection() {
+            return this;
+        }
+
+        @Override
+        public Spliterator<T> spliterator() {
+            // @@@ Not very efficient
+            return Arrays.spliterator((T[]) toArray());
+        }
+
+        @Override
+        public void copyTo(T[] array, int offset) {
+            int i = offset;
+            for (T t : this)
+                array[i++] = t;
+        }
+
+        //
+
+        @Override
+        public void begin(int size) {
+            clear();
+            if (size >= 0) {
+                ensureCapacity(size);
+            }
+        }
+
+        @Override
+        public void accept(T t) {
+            int chunk = size / CHUNK_SIZE;
+            int inChunk = size % CHUNK_SIZE;
+            if (0 == inChunk) {
+                ensureCapacity(size + 1);
+            }
+
+            chunks[chunk][inChunk] = t;
+            size++;
+        }
+
+        @Override
+        public void end() {
+            // @@@ check begin(size) and size
+        }
+
+        @Override
+        public int size() {
+            return size;
+        }
+
+        @Override
+        public Stream<T> stream() {
+            return Streams.stream(this, size());
+        }
+
+        @Override
+        public Stream<T> parallel() {
+            return Streams.parallel(spliterator(), size());
+        }
+
+        @Override
+        public void forEach(Block<? super T> block) {
+            int finalChunk = size / CHUNK_SIZE;
+            int finalIndex = size % CHUNK_SIZE;
+
+            for (int chunk = 0; chunk < finalChunk; chunk++) {
+                for (T t : chunks[chunk]) {
+                    block.apply(t);
+                }
+            }
+
+            if (finalIndex > 0) {
+                // final chunk.
+                T[] partialChunk = chunks[finalChunk];
+                for (int index = 0; index < finalIndex; index++) {
+                    block.apply(partialChunk[index]);
+                }
+            }
+        }
+
+        @Override
+        public Iterator<T> iterator() {
+            Iterator<T> result = new Iterator<T>() {
+                final int finalChunk = size / CHUNK_SIZE;
+                final int finalIndex = size % CHUNK_SIZE;
+
+                int chunk = 0;
+                int index = 0;
+
+                @Override
+                public boolean hasNext() {
+                    return chunk < finalChunk || index < finalIndex;
+                }
+
+                @Override
+                public T next() {
+                    if (!hasNext()) {
+                        throw new NoSuchElementException();
+                    }
+
+                    T result = chunks[chunk][index++];
+
+                    if (index == CHUNK_SIZE) {
+                        index = 0;
+                        chunk++;
+                    }
+
+                    return result;
+                }
+            };
+
+            return result;
+        }
+
+        @Override
+        public void clear() {
+            size = 0;
+        }
+
+        @Override
+        public Object[] toArray() {
+            Object[] result = new Object[size];
+
+            int finalChunk = size / CHUNK_SIZE;
+            int finalIndex = size % CHUNK_SIZE;
+            int index = 0;
+            int chunk = 0;
+
+            // full chunks
+            while (chunk < finalChunk) {
+                System.arraycopy(chunks[chunk++], 0, result, index, CHUNK_SIZE);
+                index += CHUNK_SIZE;
+            }
+
+            // final bit.
+            System.arraycopy(chunks[chunk], 0, result, index, finalIndex);
+
+            return result;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return size != 0;
+        }
+
+        @Override
+        public int hashCode() {
+            return Nodes.hashCode(this);
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (!(obj instanceof NodeBuilder))
+                return false;
+            return Nodes.equals(this, (NodeBuilder) obj);
+        }
+
+        @Override
+        public String toString() {
+            return String.format("SimpleSpinedNodeBuilder[%s]", Arrays.toString(toArray()));
+        }
+    }
+
+    private static boolean equals(NodeBuilder a, NodeBuilder b) {
+        if (a.size() != b.size())
+            return false;
+        Iterator it1 = a.iterator();
+        Iterator it2 = b.iterator();
+        while (it1.hasNext()) {
+            Object x1 = it1.next();
+            Object x2 = it2.next();
+            if (!x1.equals(x2))
+                return false;
+        }
+        return true;
+    }
+
+    private static <T> int hashCode(NodeBuilder<T> sb) {
+        int h = 0;
+        for (T t : sb) {
+            h = 31 * h + Objects.hashCode(t);
+        }
+        return h;
+    }
+
+}
--- a/src/share/classes/java/util/streams/ops/StatefulOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/StatefulOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -11,7 +11,7 @@
  *
  */
 public interface StatefulOp<E_IN, E_OUT>
-        extends IntermediateOp<E_IN, E_OUT>, EvaluableOp<E_IN, TreeUtils.Node<E_OUT>> {
+        extends IntermediateOp<E_IN, E_OUT>, EvaluableOp<E_IN, Node<E_OUT>> {
 
     @Override
     public boolean isStateful() default {
@@ -19,9 +19,9 @@
     }
 
     @Override
-    <P_IN> TreeUtils.Node<E_OUT> evaluateSequential(PipelineHelper<P_IN, E_IN> helper) default {
-        final StreamBuilder<E_OUT> sb = StreamBuilders.make();
-        helper.into(wrapSink(sb));
-        return TreeUtils.node(sb);
+    <P_IN> Node<E_OUT> evaluateSequential(PipelineHelper<P_IN, E_IN> helper) default {
+        final NodeBuilder<E_OUT> nb = Nodes.makeBuilder();
+        helper.into(wrapSink(nb));
+        return nb;
     }
 }
--- a/src/share/classes/java/util/streams/ops/ToArrayOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/ToArrayOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -96,7 +96,7 @@
         //     Require Spliterator.toArray with default method
 
         // Ensure tree is flattened
-        TreeUtils.Node<T> node = TreeUtils.collect(helper, true);
+        Node<T> node = TreeUtils.collect(helper, true);
         @SuppressWarnings("unchecked")
         T[] array = (T[]) new Object[node.size()];
 
--- a/src/share/classes/java/util/streams/ops/TreeUtils.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/TreeUtils.java	Mon Oct 15 15:44:27 2012 -0700
@@ -26,7 +26,6 @@
 
 import java.util.*;
 import java.util.concurrent.CountedCompleter;
-import java.util.functions.Block;
 import java.util.streams.*;
 
 /**
@@ -47,21 +46,21 @@
                           || (spliterator.getNaturalSplits() == 0);
         boolean splitSizesKnown = StreamOpFlags.SIZED.isKnown(helper.getFlags());
         if (noSplit) {
-            StreamBuilder<P_OUT> builder;
+            NodeBuilder<P_OUT> builder;
             if (size >= 0 && splitSizesKnown) {
-                builder = StreamBuilders.makeFixed(size);
+                builder = Nodes.makeBuilder(size);
                 helper.into(spliterator, builder);
-                return node((P_OUT[]) builder.toArray());
+                return builder;
             } else {
-                builder = StreamBuilders.make();
+                builder = Nodes.makeBuilder();
                 helper.into(spliterator, builder);
-                return node(builder);
+                return builder;
             }
         } else {
             if (size != -1 && spliterator.isPredictableSplits() && splitSizesKnown) {
                 P_OUT[] array = (P_OUT[]) new Object[size];
                 helper.invoke(new SizedCollectorTask<>(spliterator, helper, helper.suggestTargetSize(), array));
-                return node(array);
+                return Nodes.node(array);
             } else {
                 CollectorTask<P_IN, P_OUT> task = new CollectorTask<>(helper);
                 helper.invoke(task);
@@ -69,14 +68,14 @@
                 if (flattenTree) {
                     P_OUT[] array = (P_OUT[]) new Object[node.size()];
                     helper.invoke(new ToArrayTask<>(node, array, 0));
-                    return node(array);
+                    return Nodes.node(array);
                 }
                 return node;
             }
         }
     }
 
-    public static class CollectorOp<E_IN> implements TerminalOp<E_IN, TreeUtils.Node<E_IN>> {
+    public static class CollectorOp<E_IN> implements TerminalOp<E_IN, Node<E_IN>> {
 
         private static CollectorOp<?> INSTANCE = new CollectorOp<>();
 
@@ -90,7 +89,7 @@
         }
 
         @Override
-        public <P_IN> TreeUtils.Node<E_IN> evaluateParallel(ParallelPipelineHelper<P_IN, E_IN> helper) {
+        public <P_IN> Node<E_IN> evaluateParallel(ParallelPipelineHelper<P_IN, E_IN> helper) {
             return TreeUtils.collect(helper, false);
         }
     }
@@ -115,10 +114,10 @@
 
         @Override
         protected Node<U> doLeaf() {
-            // @@@ Usual comment about using fixed stream builders if we know enough to do so
-            StreamBuilder<U> builder = StreamBuilders.make();
+            boolean sizeKnown = StreamOpFlags.SIZED.isKnown(helper.getFlags());
+            NodeBuilder<U> builder = Nodes.makeBuilder(sizeKnown ? spliterator.getSizeIfKnown() : -1);
             helper.into(spliterator, builder);
-            return node(builder);
+            return builder;
         }
 
         @Override
@@ -129,7 +128,7 @@
                 int idx = 0;
                 for (CollectorTask<T, U> cur = children; cur != null; cur = cur.nextSibling)
                     nodes[idx++] = cur.getRawResult();
-                setRawResult(node(nodes));
+                setRawResult(Nodes.node(nodes));
             }
         }
     }
@@ -215,8 +214,8 @@
 
         @Override
         public void compute() {
-            if (node instanceof InternalNode) {
-                Node<T>[] nodes = ((InternalNode<T>) node).nodes();
+            if (node instanceof Node.ConcNode) {
+                Node<T>[] nodes = ((Node.ConcNode<T>) node).nodes();
                 setPendingCount(nodes.length - 1);
                 ToArrayTask<T> firstTask = new ToArrayTask<>(this, nodes[0], offset);
                 int size = nodes[0].size();
@@ -234,259 +233,4 @@
             }
         }
     }
-
-    public static interface Node<T> extends Traversable<T>, Streamable<Stream<T>>, Sized {
-        void copyTo(T[] array, int offset);
-
-        Spliterator<T> spliterator();
-    }
-
-    public static interface InternalNode<T> extends Node<T> {
-        Node<T>[] nodes();
-    }
-
-    public static<T> Node<T> node(final T[] array) {
-        return new Node<T>() {
-            private final T[] data = array;
-
-            @Override
-            public int size() {
-                return data.length;
-            }
-
-            @Override
-            public void forEach(Block<? super T> block) {
-                for (T t : data)
-                    block.apply(t);
-            }
-
-            @Override
-            public Iterator<T> iterator() {
-                return Arrays.iterator(data, 0, data.length);
-            }
-
-            @Override
-            public Stream<T> stream() {
-                return Arrays.stream(data);
-            }
-
-            @Override
-            public Stream<T> parallel() {
-                return Arrays.parallel(data);
-            }
-
-            @Override
-            public Spliterator<T> spliterator() {
-                return Arrays.spliterator(data);
-            }
-
-            @Override
-            public void copyTo(T[] dest, int destOffset) {
-                System.arraycopy(data, 0, dest, destOffset, data.length);
-            }
-
-            @Override
-            public String toString() {
-                return "ArrayNode" + Arrays.toString(data);
-            }
-        };
-    }
-
-    public static<T> Node<T> node(final StreamBuilder<T> stream) {
-        return new Node<T>() {
-            private final StreamBuilder<T> data = stream;
-
-            @Override
-            public int size() {
-                return data.size();
-            }
-
-            @Override
-            public void forEach(Block<? super T> block) {
-                data.forEach(block);
-            }
-
-            @Override
-            public Stream<T> stream() {
-                return Streams.stream(data.iterator(), data.size(), StreamOpFlags.IS_ORDERED);
-            }
-
-            @Override
-            public Stream<T> parallel() {
-                return Arrays.parallel((T[]) data.toArray());
-            }
-
-            @Override
-            public Iterator<T> iterator() {
-                return data.iterator();
-            }
-
-            @Override
-            public Spliterator<T> spliterator() {
-                return Arrays.spliterator((T[]) data.toArray());
-            }
-
-            @Override
-            public void copyTo(T[] array, int offset) {
-                int i = 0;
-                for (T t : this)
-                    array[offset+(i++)] = t;
-            }
-
-            @Override
-            public String toString() {
-                return "SBNode" + data.toString();
-            }
-        };
-    }
-
-    @SafeVarargs
-    public static<T> Node<T> node(Node<T>... nodes) {
-        return new InternalNodeImpl<>(nodes);
-    }
-
-    private static class InternalNodeImpl<T> implements InternalNode<T> {
-        private final Node<T>[] nodes;
-        int size = 0;
-
-        private InternalNodeImpl(Node<T>[] nodes) {
-            this.nodes = nodes;
-        }
-
-        @Override
-        public int size() {
-            if (size == 0) {
-                for (Node<T> n : nodes)
-                    size += n.size();
-            }
-            return size;
-        }
-
-        @Override
-        public void forEach(Block<? super T> block) {
-            for (Node<T> n : nodes)
-                n.forEach(block);
-        }
-
-        @Override
-        public Iterator<T> iterator() {
-            return Iterators.concat(Arrays.stream(nodes).map(n -> n.iterator()).iterator());
-        }
-
-        @Override
-        public Stream<T> stream() {
-            return Streams.stream(iterator(), size(), StreamOpFlags.IS_ORDERED);
-        }
-
-        @Override
-        public Stream<T> parallel() {
-            return Streams.parallel(spliterator(), size(), StreamOpFlags.IS_ORDERED);
-        }
-
-        @Override
-        public Spliterator<T> spliterator() {
-            return new InternalNodeSpliterator<>(this);
-        }
-
-        @Override
-        public void copyTo(T[] array, int offset) {
-            int s = 0;
-            for (Node<T> n : nodes) {
-                n.copyTo(array, offset+s);
-                s += n.size();
-            }
-        }
-
-        @Override
-        public String toString() {
-            return String.format("IntNode[%s]", Arrays.stream(nodes).map(n -> n.toString()).into(new StringJoiner(",")).toString());
-        }
-
-        @Override
-        public Node<T>[] nodes() {
-            return nodes;
-        }
-
-        private static class InternalNodeSpliterator<T> implements Spliterator<T>, Iterator<T> {
-            private Node<T> cur;
-            private int splitsLeft;
-            private int nextSplitIndex;
-            private Iterator<T> iterator;
-
-            private InternalNodeSpliterator(InternalNodeImpl<T> cur) {
-                this.cur = cur;
-                splitsLeft = cur.nodes.length - 1;
-            }
-
-            public Iterator<T> iterator() {
-                if (iterator == null)
-                    iterator = cur.iterator();
-                return iterator;
-            }
-
-            @Override
-            public int getNaturalSplits() {
-                return splitsLeft;
-            }
-
-            @Override
-            public Spliterator<T> split() {
-                if (iterator != null)
-                    throw new IllegalStateException("split after iterate");
-                else if (splitsLeft == 0 || !(cur instanceof InternalNode))
-                    return Streams.emptySpliterator();
-                else {
-                    Node<T>[] nodes = ((InternalNode<T>) cur).nodes();
-                    Spliterator<T> ret = nodes[nextSplitIndex++].spliterator();
-                    if (--splitsLeft == 0) {
-                        cur = nodes[nextSplitIndex];
-                        if (cur instanceof InternalNode) {
-                            Node<T>[] newNodes  = ((InternalNode<T>) cur).nodes();
-                            splitsLeft = newNodes.length - 1;
-                            nextSplitIndex = 0;
-                        }
-                        else {
-                            splitsLeft = 0;
-                            nextSplitIndex = -1;
-                        }
-                    }
-                    return ret;
-                }
-            }
-
-            @Override
-            public void into(Sink<T, ?, ?> sink) {
-                sink.begin(getSizeIfKnown());
-                if (iterator == null) {
-                    cur.forEach(sink);
-                    iterator = Collections.emptyIterator();
-                }
-                else {
-                    while (iterator.hasNext())
-                        sink.accept(iterator.next());
-                }
-                sink.end();
-            }
-
-            @Override
-            public int getSizeIfKnown() {
-                return (iterator == null) ? cur.size() : -1;
-            }
-
-            @Override
-            public boolean isPredictableSplits() {
-                return true;
-            }
-
-            @Override
-            public boolean hasNext() {
-                return iterator().hasNext();
-            }
-
-            @Override
-            public T next() {
-                return iterator().next();
-            }
-        }
-    }
 }
--- a/src/share/classes/java/util/streams/ops/UniqOp.java	Mon Oct 15 15:35:20 2012 -0700
+++ b/src/share/classes/java/util/streams/ops/UniqOp.java	Mon Oct 15 15:44:27 2012 -0700
@@ -30,8 +30,6 @@
 import java.util.logging.Logger;
 import java.util.streams.*;
 
-import static java.util.streams.ops.TreeUtils.node;
-
 /**
  * An stateful operation which eliminates duplicates from the stream.
  *
@@ -122,7 +120,7 @@
     }
 
     @Override
-    public <S> TreeUtils.Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
+    public <S> Node<T> evaluateParallel(ParallelPipelineHelper<S, T> helper) {
         if (StreamOpFlags.ORDERED.isKnown(helper.getFlags())) {
             Logger.getLogger(getClass().getName()).log(Level.WARNING, "UniqOp.evaluateParallel does not preserve encounter order");
         }
@@ -141,7 +139,7 @@
         helper.invoke(task);
 
         // @@@ Not very efficient
-        return node((T[])map.keySet().toArray());
+        return Nodes.node((T[])map.keySet().toArray());
     }
 
     // @@@ This is a lot of boiler plate for "spliterator.into(sinkChain)"
--- a/test-ng/tests/org/openjdk/tests/java/util/streams/StreamBuilderTest.java	Mon Oct 15 15:35:20 2012 -0700
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,84 +0,0 @@
-/*
- * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.  Oracle designates this
- * particular file as subject to the "Classpath" exception as provided
- * by Oracle in the LICENSE file that accompanied this code.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package org.openjdk.tests.java.util.streams;
-
-import org.testng.annotations.DataProvider;
-import org.testng.annotations.Test;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-import java.util.streams.StreamBuilder;
-import java.util.streams.StreamBuilders;
-
-import static org.openjdk.tests.java.util.LambdaTestHelpers.assertContents;
-import static org.openjdk.tests.java.util.LambdaTestHelpers.countTo;
-
-@Test
-public class StreamBuilderTest {
-
-    @DataProvider(name = "sizes")
-    public Object[][] createSizes() {
-        List<Integer> l = Arrays.asList(0, 1, 4, 16, 256,
-                                        1023, 1024, 1025,
-                                        2047, 2048, 2049,
-                                        1024 * 32 - 1, 1024 * 32, 1024 * 32 + 1);
-
-        Object[][] params = new Object[l.size()][];
-        for (int i = 0; i < l.size(); i++) {
-            params[i] = new Object[]{new Integer(l.get(i))};
-        }
-
-        return params;
-    }
-
-    @Test(dataProvider = "sizes")
-    public void testIteration(int size) {
-        StreamBuilder<Integer> sb = StreamBuilders.make();
-
-        List<Integer> l = countTo(size);
-        for (int i : l) {
-            sb.accept(i);
-        }
-
-        {
-            List<Integer> _l = new ArrayList<>();
-            sb.forEach(e -> {
-                _l.add(e);
-            });
-
-            assertContents(_l, l);
-        }
-
-        {
-            List<Integer> _l = new ArrayList<>();
-            for (int i : sb) {
-                _l.add(i);
-            }
-
-            assertContents(_l, l);
-        }
-    }
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test-ng/tests/org/openjdk/tests/java/util/streams/ops/NodeBuilderTest.java	Mon Oct 15 15:44:27 2012 -0700
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.openjdk.tests.java.util.streams.ops;
+
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.streams.ops.NodeBuilder;
+import java.util.streams.ops.Nodes;
+
+import static org.openjdk.tests.java.util.LambdaTestHelpers.assertContents;
+import static org.openjdk.tests.java.util.LambdaTestHelpers.countTo;
+
+@Test
+public class NodeBuilderTest {
+
+    @DataProvider(name = "sizes")
+    public Object[][] createSizes() {
+        List<Integer> l = Arrays.asList(0, 1, 4, 16, 256,
+                                        1023, 1024, 1025,
+                                        2047, 2048, 2049,
+                                        1024 * 32 - 1, 1024 * 32, 1024 * 32 + 1);
+
+        Object[][] params = new Object[l.size()][];
+        for (int i = 0; i < l.size(); i++) {
+            params[i] = new Object[]{new Integer(l.get(i))};
+        }
+
+        return params;
+    }
+
+    @Test(dataProvider = "sizes")
+    public void testIteration(int size) {
+        NodeBuilder<Integer> sb = Nodes.makeBuilder();
+
+        List<Integer> l = countTo(size);
+        for (int i : l) {
+            sb.accept(i);
+        }
+
+        {
+            List<Integer> _l = new ArrayList<>();
+            sb.forEach(e -> {
+                _l.add(e);
+            });
+
+            assertContents(_l, l);
+        }
+
+        {
+            List<Integer> _l = new ArrayList<>();
+            for (int i : sb) {
+                _l.add(i);
+            }
+
+            assertContents(_l, l);
+        }
+    }
+}