[cvs] / jsr166 / src / main / java / util / PriorityQueue.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.88, Fri Feb 1 16:23:04 2013 UTC revision 1.89, Sun Feb 17 23:36:16 2013 UTC
# Line 24  Line 24 
24   */   */
25    
26  package java.util;  package java.util;
27    import java.util.function.Consumer;
28  import java.util.stream.Stream;  import java.util.stream.Stream;
 import java.util.Spliterator;  
29  import java.util.stream.Streams;  import java.util.stream.Streams;
 import java.util.function.Consumer;  
30    
31  /**  /**
32   * An unbounded priority {@linkplain Queue queue} based on a priority heap.   * An unbounded priority {@linkplain Queue queue} based on a priority heap.
# Line 543  Line 542 
542                      cursor--;                      cursor--;
543                  else {                  else {
544                      if (forgetMeNot == null)                      if (forgetMeNot == null)
545                          forgetMeNot = new ArrayDeque<E>();                          forgetMeNot = new ArrayDeque<>();
546                      forgetMeNot.add(moved);                      forgetMeNot.add(moved);
547                  }                  }
548              } else if (lastRetElt != null) {              } else if (lastRetElt != null) {
# Line 784  Line 783 
783          heapify();          heapify();
784      }      }
785    
786      // wrapping constructor in method avoids transient javac problems      final Spliterator<E> spliterator() {
787      final PriorityQueueSpliterator<E> spliterator(int origin, int fence,          return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
                                                   int expectedModCount) {  
         return new PriorityQueueSpliterator<E>(this, origin, fence,  
                                                expectedModCount);  
788      }      }
789    
790      public Stream<E> stream() {      public Stream<E> stream() {
791          int flags = Streams.STREAM_IS_SIZED;          return Streams.stream(spliterator());
         return Streams.stream  
             (() -> spliterator(0, size, modCount), flags);  
792      }      }
793    
794      public Stream<E> parallelStream() {      public Stream<E> parallelStream() {
795          int flags = Streams.STREAM_IS_SIZED;          return Streams.parallelStream(spliterator());
         return Streams.parallelStream  
             (() -> spliterator(0, size, modCount), flags);  
796      }      }
797    
     /** Index-based split-by-two Spliterator */  
798      static final class PriorityQueueSpliterator<E> implements Spliterator<E> {      static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
799            /*
800             * This is very similar to ArrayList Spliterator, except for
801             * extra null checks.
802             */
803          private final PriorityQueue<E> pq;          private final PriorityQueue<E> pq;
804          private int index;           // current index, modified on advance/split          private int index;           // current index, modified on advance/split
805          private final int fence;     // one past last index          private int fence;            // -1 until first use
806          private final int expectedModCount; // for comodification checks          private int expectedModCount; // initialized when fence set
807    
808          /** Create new spliterator covering the given  range */          /** Create new spliterator covering the given  range */
809          PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,          PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
810                               int expectedModCount) {                               int expectedModCount) {
811              this.pq = pq; this.index = origin; this.fence = fence;              this.pq = pq;
812                this.index = origin;
813                this.fence = fence;
814              this.expectedModCount = expectedModCount;              this.expectedModCount = expectedModCount;
815          }          }
816    
817            private int getFence() { // initialize fence to size on first use
818                int hi;
819                if ((hi = fence) < 0) {
820                    expectedModCount = pq.modCount;
821                    hi = fence = pq.size;
822                }
823                return hi;
824            }
825    
826          public PriorityQueueSpliterator<E> trySplit() {          public PriorityQueueSpliterator<E> trySplit() {
827              int lo = index, mid = (lo + fence) >>> 1;              int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
828              return (lo >= mid) ? null :              return (lo >= mid) ? null :
829                  new PriorityQueueSpliterator<E>(pq, lo, index = mid,                  new PriorityQueueSpliterator<E>(pq, lo, index = mid,
830                                                  expectedModCount);                                                  expectedModCount);
831          }          }
832    
833          public void forEach(Consumer<? super E> block) {          @SuppressWarnings("unchecked")
834              Object[] a; int i, hi; // hoist accesses and checks from loop          public void forEach(Consumer<? super E> action) {
835              if (block == null)              int i, hi, mc; // hoist accesses and checks from loop
836                PriorityQueue<E> q; Object[] a;
837                if (action == null)
838                  throw new NullPointerException();                  throw new NullPointerException();
839              if ((a = pq.queue).length >= (hi = fence) &&              if ((q = pq) != null && (a = q.queue) != null) {
840                  (i = index) >= 0 && i < hi) {                  if ((hi = fence) < 0) {
841                  index = hi;                      mc = q.modCount;
842                  do {                      hi = q.size;
843                      @SuppressWarnings("unchecked") E e = (E) a[i];                  }
844                      block.accept(e);                  else
845                  } while (++i < hi);                      mc = expectedModCount;
846                  if (pq.modCount != expectedModCount)                  if ((i = index) >= 0 && (index = hi) <= a.length) {
847                      throw new ConcurrentModificationException();                      for (E e;; ++i) {
848                            if (i < hi) {
849                                if ((e = (E) a[i]) == null) // must be CME
850                                    break;
851                                action.accept(e);
852              }              }
853                            else if (q.modCount != mc)
854                                break;
855                            else
856                                return;
857                        }
858                    }
859                }
860                throw new ConcurrentModificationException();
861          }          }
862    
863          public boolean tryAdvance(Consumer<? super E> block) {          public boolean tryAdvance(Consumer<? super E> action) {
864              if (index >= 0 && index < fence) {              int hi = getFence(), lo = index;
865                  @SuppressWarnings("unchecked") E e =              if (lo >= 0 && lo < hi) {
866                      (E)pq.queue[index++];                  index = lo + 1;
867                  block.accept(e);                  @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
868                    if (e == null)
869                        throw new ConcurrentModificationException();
870                    action.accept(e);
871                  if (pq.modCount != expectedModCount)                  if (pq.modCount != expectedModCount)
872                      throw new ConcurrentModificationException();                      throw new ConcurrentModificationException();
873                  return true;                  return true;
# Line 851  Line 875 
875              return false;              return false;
876          }          }
877    
878          public long estimateSize() { return (long)(fence - index); }          public long estimateSize() {
879          public boolean hasExactSize() { return true; }              return (long) (getFence() - index);
880          public boolean hasExactSplits() { return true; }          }
881    
882            public int characteristics() {
883                return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
884            }
885      }      }
886  }  }

Legend:
Removed from v.1.88  
changed lines
  Added in v.1.89

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8