changeset 7048:46fff268b702

Add spliterator methods to TreeMap Contributed-by: dl
author briangoetz
date Thu, 10 Jan 2013 19:00:36 -0500
parents 52fcc7897ce1
children cf94c0668cf1
files src/share/classes/java/util/TreeMap.java
diffstat 1 files changed, 467 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/util/TreeMap.java	Thu Jan 10 18:40:41 2013 -0500
+++ b/src/share/classes/java/util/TreeMap.java	Thu Jan 10 19:00:36 2013 -0500
@@ -25,6 +25,11 @@
 
 package java.util;
 
+import java.util.stream.StreamOpFlag;
+import java.util.stream.Stream;
+import java.util.stream.Streams;
+import java.util.function.Block;
+
 /**
  * A Red-Black tree based {@link NavigableMap} implementation.
  * The map is sorted according to the {@linkplain Comparable natural
@@ -971,6 +976,20 @@
         public void clear() {
             TreeMap.this.clear();
         }
+
+        public Stream<V> stream() {
+            return Streams.stream
+                (() -> new ValueSpliterator<K,V>(TreeMap.this, getFirstEntry(),
+                                                 null, 0, size, modCount),
+                 StreamOpFlag.IS_SIZED | StreamOpFlag.IS_ORDERED);
+        }
+
+        public Stream<V> parallelStream() {
+            return Streams.parallelStream
+                (() -> new ValueSpliterator<K,V>(TreeMap.this, getFirstEntry(),
+                                                 null, 0, size, modCount),
+                 StreamOpFlag.IS_SIZED | StreamOpFlag.IS_ORDERED);
+        }
     }
 
     class EntrySet extends AbstractSet<Map.Entry<K,V>> {
@@ -1007,6 +1026,23 @@
         public void clear() {
             TreeMap.this.clear();
         }
+
+        public Stream<Map.Entry<K,V>> stream() {
+            return Streams.stream
+                (() -> new EntrySpliterator<K,V>(TreeMap.this, getFirstEntry(),
+                                                 null, 0, size, modCount),
+                 StreamOpFlag.IS_SIZED | StreamOpFlag.IS_DISTINCT | 
+                 StreamOpFlag.IS_ORDERED);
+        }
+
+        public Stream<Map.Entry<K,V>> parallelStream() {
+            return Streams.parallelStream
+                (() -> new EntrySpliterator<K,V>(TreeMap.this, getFirstEntry(),
+                                                 null, 0, size, modCount),
+                 StreamOpFlag.IS_SIZED | StreamOpFlag.IS_DISTINCT | 
+                 StreamOpFlag.IS_ORDERED);
+        }
+
     }
 
     /*
@@ -1025,6 +1061,17 @@
         return new DescendingKeyIterator(getLastEntry());
     }
 
+    final Spliterator<K> keySpliterator() {
+        return new KeySpliterator<K,V>
+            (this, getFirstEntry(), null, 0, size, modCount);
+    }
+
+    final Spliterator<K> descendingKeySpliterator() {
+        return new DescendingKeySpliterator<K,V>
+            (this, getLastEntry(), null, 0, size, modCount);
+    }
+
+
     static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
         private final NavigableMap<E, ?> m;
         KeySet(NavigableMap<E,?> map) { m = map; }
@@ -1090,6 +1137,60 @@
         public NavigableSet<E> descendingSet() {
             return new KeySet<>(m.descendingMap());
         }
+
+        /**
+         * Currently, we support Spliterator-based versions only for
+         * the full map, in either plain of descending form, otherwise
+         * relying on defaults because size estimation for submaps
+         * would dominate costs. The type tests needed to check these
+         * are not very nice but avoid disrupting existing class
+         * structures.
+         */
+        @Override
+        @SuppressWarnings("unchecked") public Stream<E> stream() {
+            int flags = StreamOpFlag.IS_DISTINCT |
+                StreamOpFlag.IS_SORTED | StreamOpFlag.IS_ORDERED;
+            int sizedFlags = flags | StreamOpFlag.IS_SIZED;
+            if (m instanceof TreeMap)
+                return Streams.stream
+                    (() -> ((TreeMap<E,?>)m).keySpliterator(), sizedFlags);
+            else {
+                if (m instanceof DescendingSubMap) {
+                    DescendingSubMap<E, ?> dm = (DescendingSubMap<E, ?>)m;
+                    if (dm.m instanceof TreeMap) {
+                        TreeMap<E,?> tm = (TreeMap<E,?>)dm.m;
+                        if (dm == tm.descendingMap)
+                            return Streams.stream
+                                (() -> tm.descendingKeySpliterator(), sizedFlags);
+                    }
+                }
+                return Streams.stream
+                    (Iterators.spliterator(iterator(), -1), flags);
+            }
+        }
+
+        @Override
+        @SuppressWarnings("unchecked") public Stream<E> parallelStream() {
+            int flags = StreamOpFlag.IS_DISTINCT |
+                StreamOpFlag.IS_SORTED | StreamOpFlag.IS_ORDERED;
+            int sizedFlags = flags | StreamOpFlag.IS_SIZED;
+            if (m instanceof TreeMap)
+                return Streams.parallelStream
+                    (() -> ((TreeMap<E,?>)m).keySpliterator(), sizedFlags);
+            else {
+                if (m instanceof DescendingSubMap) {
+                    DescendingSubMap<E, ?> dm = (DescendingSubMap<E, ?>)m;
+                    if (dm.m instanceof TreeMap) {
+                        TreeMap<E,?> tm = (TreeMap<E,?>)dm.m;
+                        if (dm == tm.descendingMap)
+                            return Streams.parallelStream
+                                (() -> tm.descendingKeySpliterator(), sizedFlags);
+                    }
+                }
+                return Streams.parallelStream
+                    (Iterators.spliterator(iterator(), -1), flags);
+            }
+        }
     }
 
     /**
@@ -2444,4 +2545,370 @@
             level++;
         return level;
     }
+
+    /**
+     * Base class for spliterators.  Iteration starts at a given
+     * origin and continues up to but not including a given fence (or
+     * null for end).  At top-level, for ascending cases, the first
+     * split uses the root as left-fence/right-origin. From there,
+     * right-hand splits replace the current fence with its left
+     * child, also serving as origin for the split-off spliterator.
+     * Left-hands are symmetric. Descending versions place the origin
+     * at the end and invert ascending split rules.  This base class
+     * is non-commital about directionality, or whether the top-level
+     * spliterator covers the whole tree. This means that the actual
+     * split mechanics are located in subclasses. Some of the subclass
+     * trySplit methods are identical (except for return types), but
+     * not nicely factorable.
+     *
+     * Currently, subclass versions exist only for the full map
+     * (including descending keys via its descendingMap).  Others are
+     * possible but currently not worthwhile because submaps require
+     * O(n) computations to determine size, which substantially limits
+     * potential speed-ups of using custom Spliterators versus default
+     * mechanics.
+     */
+    static class SpliteratorBase<K,V> {
+        final TreeMap<K,V> tree;
+        TreeMap.Entry<K,V> next;    // for iterator
+        TreeMap.Entry<K,V> origin;  // first node in range
+        TreeMap.Entry<K,V> fence;   // one past last, or null
+        int side;                   // 0: top, -1: is a left split, +1: right
+        int est;                    // size estimate (exact only for top-level)
+        final int expectedModCount; // for CME checks
+
+        SpliteratorBase(TreeMap<K,V> tree,
+                        TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                        int side, int est, int expectedModCount) {
+            this.tree = tree; this.origin = origin; this.fence = fence;
+            this.side = side; this.est = est;
+            this.expectedModCount = expectedModCount;
+        }
+
+        public final boolean hasExactSize() {
+            return side == 0;
+        }
+        
+        public final boolean hasExactSplits() {
+            return false;
+        }
+        
+        public final long estimateSize() {
+            return (long)est;
+        }
+
+        public final boolean hasNext() {
+            TreeMap.Entry<K,V> e;
+            return ((e = next) != null && e != fence);
+        }
+
+        final TreeMap.Entry<K,V> nextEntry() {
+            TreeMap.Entry<K,V> e;
+            if ((e = next) == null || e == fence)
+                throw new NoSuchElementException();
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            next = successor(e);
+            return e;
+        }
+
+        final TreeMap.Entry<K,V> prevEntry() {
+            TreeMap.Entry<K,V> e;
+            if ((e = next) == null || e == fence)
+                throw new NoSuchElementException();
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            next = predecessor(e);
+            return e;
+        }
+
+        public final void remove() { throw new UnsupportedOperationException(); }
+    }
+
+    static final class KeySpliterator<K,V> extends SpliteratorBase<K,V>
+        implements Spliterator<K>, Iterator<K> {
+        KeySpliterator(TreeMap<K,V> tree,
+                       TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                       int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        public KeySpliterator<K,V> trySplit() {
+            if (next != null) throw new IllegalStateException();
+            TreeMap.Entry<K,V> o = origin, f = fence, so = null, sf = null;
+            int s = side, ss = 0; // ss remains 0 if cannot split
+            if (s == 0 && (so = tree.root) != null && o != so) { // was top
+                fence = so; side = -1; sf = null; ss = 1; // become left
+            }
+            else if (s < 0 && f != null && (so = f.left) != null) { // left
+                fence = so; sf = f; ss = 1;
+            }
+            else if (s > 0 && o != null && (sf = o.right) != null) { // right
+                origin = sf; so = o; ss = -1;
+            }
+            return (ss == 0) ? null :
+                new KeySpliterator<K,V>(tree, so, sf, ss, est >>>= 1,
+                                        expectedModCount);
+        }
+
+        public Iterator<K> AsIterator() {
+            next = origin;
+            return this;
+        }
+
+        public K next() {
+            return nextEntry().key;
+        }
+
+        public void forEach(Block<? super K> action) {
+            // customize and streamline all traversal mechanics
+            if (action == null) throw new NullPointerException();
+            int mc = expectedModCount;
+            TreeMap<K,V> t = tree;
+            TreeMap.Entry<K,V> f = fence, e, p, pl;
+            if ((e = next) == null)
+                e = next = origin;
+            while (e != null && e != f) {
+                if (t.modCount != mc)
+                    throw new ConcurrentModificationException();
+                action.accept(e.key);
+                if ((p = e.right) != null) {
+                    while ((pl = p.left) != null)
+                        p = pl;
+                }
+                else {
+                    while ((p = e.parent) != null && e == p.right)
+                        e = p;
+                }
+                e = p;
+            }
+        }
+
+        public boolean tryAdvance(Block<? super K> block) {
+            if (block == null) throw new NullPointerException();
+            TreeMap.Entry<K,V> e;
+            if ((e = next) == null && (e = next = origin) == null || e == fence)
+                return false;
+            next = successor(e);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            block.accept(e.key);
+            return true;
+        }            
+
+    }
+
+    static final class DescendingKeySpliterator<K,V> extends SpliteratorBase<K,V>
+        implements Spliterator<K>, Iterator<K> {
+        DescendingKeySpliterator(TreeMap<K,V> tree,
+                       TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                       int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        public DescendingKeySpliterator<K,V> trySplit() {
+            if (next != null) throw new IllegalStateException();
+            TreeMap.Entry<K,V> o = origin, f = fence, so = null, sf = null;
+            int s = side, ss = 0;
+            if (s == 0 && (so = tree.root) != null && o != so) { // was top
+                fence = so; side = 1; sf = null; ss = -1; // become right
+            }
+            else if (s > 0 && f != null && (so = f.right) != null) { // right
+                fence = so; sf = f; ss = -1;
+            }
+            else if (s < 0 && o != null && (sf = o.left) != null) { // left
+                origin = sf; so = o; ss = 1;
+            }
+            return (ss == 0) ? null :
+                new DescendingKeySpliterator<K,V>(tree, so, sf, ss, est >>>= 1,
+                                                  expectedModCount);
+        }
+
+        public Iterator<K> iterator() {
+            next = origin;
+            return this;
+        }
+
+        public K next() {
+            return prevEntry().key;
+        }
+
+        public void forEach(Block<? super K> action) {
+            if (action == null) throw new NullPointerException();
+            int mc = expectedModCount;
+            TreeMap<K,V> t = tree;
+            TreeMap.Entry<K,V> f = fence, e, p, pr;
+            if ((e = next) == null)
+                e = next = origin;
+            while (e != null && e != f) {
+                if (t.modCount != mc)
+                    throw new ConcurrentModificationException();
+                action.accept(e.key);
+                if ((p = e.left) != null) {
+                    while ((pr = p.right) != null)
+                        p = pr;
+                }
+                else {
+                    while ((p = e.parent) != null && e == p.left)
+                        e = p;
+                }
+                e = p;
+            }
+        }
+
+        public boolean tryAdvance(Block<? super K> block) {
+            if (block == null) throw new NullPointerException();
+            TreeMap.Entry<K,V> e;
+            if ((e = next) == null && (e = next = origin) == null || e == fence)
+                return false;
+            next = predecessor(e);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            block.accept(e.key);
+            return true;
+        }            
+    }
+
+    static final class ValueSpliterator<K,V> extends SpliteratorBase<K,V>
+        implements Spliterator<V>, Iterator<V> {
+        ValueSpliterator(TreeMap<K,V> tree,
+                         TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                         int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        public ValueSpliterator<K,V> trySplit() {
+            if (next != null) throw new IllegalStateException();
+            TreeMap.Entry<K,V> o = origin, f = fence, so = null, sf = null;
+            int s = side, ss = 0; // ss remains 0 if cannot split
+            if (s == 0 && (so = tree.root) != null && o != so) { // was top
+                fence = so; side = -1; sf = null; ss = 1; // become left
+            }
+            else if (s < 0 && f != null && (so = f.left) != null) { // left
+                fence = so; sf = f; ss = 1;
+            }
+            else if (s > 0 && o != null && (sf = o.right) != null) { // right
+                origin = sf; so = o; ss = -1;
+            }
+            return (ss == 0) ? null :
+                new ValueSpliterator<K,V>(tree, so, sf, ss, est >>>= 1,
+                                        expectedModCount);
+        }
+
+        public Iterator<V> iterator() {
+            next = origin;
+            return this;
+        }
+
+        public V next() {
+            return nextEntry().value;
+        }
+
+        public void forEach(Block<? super V> action) {
+            if (action == null) throw new NullPointerException();
+            int mc = expectedModCount;
+            TreeMap<K,V> t = tree;
+            TreeMap.Entry<K,V> f = fence, e, p, pl;
+            if ((e = next) == null)
+                e = next = origin;
+            while (e != null && e != f) {
+                if (t.modCount != mc)
+                    throw new ConcurrentModificationException();
+                action.accept(e.value);
+                if ((p = e.right) != null) {
+                    while ((pl = p.left) != null)
+                        p = pl;
+                }
+                else {
+                    while ((p = e.parent) != null && e == p.right)
+                        e = p;
+                }
+                e = p;
+            }
+        }
+
+        public boolean tryAdvance(Block<? super V> block) {
+            if (block == null) throw new NullPointerException();
+            TreeMap.Entry<K,V> e;
+            if ((e = next) == null && (e = next = origin) == null || e == fence)
+                return false;
+            next = successor(e);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            block.accept(e.value);
+            return true;
+        }            
+    }
+
+    static final class EntrySpliterator<K,V> extends SpliteratorBase<K,V>
+        implements Spliterator<Map.Entry<K,V>>, Iterator<Map.Entry<K,V>> {
+        EntrySpliterator(TreeMap<K,V> tree,
+                         TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+                         int side, int est, int expectedModCount) {
+            super(tree, origin, fence, side, est, expectedModCount);
+        }
+
+        public EntrySpliterator<K,V> trySplit() {
+            if (next != null) throw new IllegalStateException();
+            TreeMap.Entry<K,V> o = origin, f = fence, so = null, sf = null;
+            int s = side, ss = 0; // ss remains 0 if cannot split
+            if (s == 0 && (so = tree.root) != null && o != so) { // was top
+                fence = so; side = -1; sf = null; ss = 1; // become left
+            }
+            else if (s < 0 && f != null && (so = f.left) != null) { // left
+                fence = so; sf = f; ss = 1;
+            }
+            else if (s > 0 && o != null && (sf = o.right) != null) { // right
+                origin = sf; so = o; ss = -1;
+            }
+            return (ss == 0) ? null :
+                new EntrySpliterator<K,V>(tree, so, sf, ss, est >>>= 1,
+                                          expectedModCount);
+        }
+
+        public Iterator<Map.Entry<K,V>> iterator() {
+            next = origin;
+            return this;
+        }
+
+        public Map.Entry<K,V> next() {
+            return nextEntry();
+        }
+
+        public void forEach(Block<? super Map.Entry<K,V>> action) {
+            if (action == null) throw new NullPointerException();
+            int mc = expectedModCount;
+            TreeMap<K,V> t = tree;
+            TreeMap.Entry<K,V> f = fence, e, p, pl;
+            if ((e = next) == null)
+                e = next = origin;
+            while (e != null && e != f) {
+                if (t.modCount != mc)
+                    throw new ConcurrentModificationException();
+                action.accept(e);
+                if ((p = e.right) != null) {
+                    while ((pl = p.left) != null)
+                        p = pl;
+                }
+                else {
+                    while ((p = e.parent) != null && e == p.right)
+                        e = p;
+                }
+                e = p;
+            }
+        }
+
+        public boolean tryAdvance(Block<? super Map.Entry<K,V>> block) {
+            if (block == null) throw new NullPointerException();
+            TreeMap.Entry<K,V> e;
+            if ((e = next) == null && (e = next = origin) == null || e == fence)
+                return false;
+            next = successor(e);
+            if (tree.modCount != expectedModCount)
+                throw new ConcurrentModificationException();
+            block.accept(e);
+            return true;
+        }            
+    }
+
 }