[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.80, Wed Jan 16 01:59:47 2013 UTC revision 1.81, Wed Jan 16 15:06:10 2013 UTC
# Line 1  Line 1 
1  /*  /*
2   * Copyright (c) 2003, 2006, Oracle and/or its affiliates. All rights reserved.   * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
3   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4   *   *
5   * This code is free software; you can redistribute it and/or modify it   * This code is free software; you can redistribute it and/or modify it
6   * under the terms of the GNU General Public License version 2 only, as   * under the terms of the GNU General Public License version 2 only, as
7   * published by the Free Software Foundation.  Sun designates this   * published by the Free Software Foundation.  Oracle designates this
8   * particular file as subject to the "Classpath" exception as provided   * particular file as subject to the "Classpath" exception as provided
9   * by Sun in the LICENSE file that accompanied this code.   * by Oracle in the LICENSE file that accompanied this code.
10   *   *
11   * This code is distributed in the hope that it will be useful, but WITHOUT   * This code is distributed in the hope that it will be useful, but WITHOUT
12   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
# Line 24  Line 24 
24   */   */
25    
26  package java.util;  package java.util;
27    import java.util.stream.Stream;
28    import java.util.Spliterator;
29    import java.util.stream.Streams;
30    import java.util.function.Block;
31    
32  /**  /**
33   * An unbounded priority {@linkplain Queue queue} based on a priority heap.   * An unbounded priority {@linkplain Queue queue} based on a priority heap.
# Line 63  Line 67 
67   * java.util.concurrent.PriorityBlockingQueue} class.   * java.util.concurrent.PriorityBlockingQueue} class.
68   *   *
69   * <p>Implementation note: this implementation provides   * <p>Implementation note: this implementation provides
70   * O(log(n)) time for the enqueuing and dequeuing methods   * O(log(n)) time for the enqueing and dequeing methods
71   * ({@code offer}, {@code poll}, {@code remove()} and {@code add});   * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
72   * linear time for the {@code remove(Object)} and {@code contains(Object)}   * linear time for the {@code remove(Object)} and {@code contains(Object)}
73   * methods; and constant time for the retrieval methods   * methods; and constant time for the retrieval methods
# Line 77  Line 81 
81   * @author Josh Bloch, Doug Lea   * @author Josh Bloch, Doug Lea
82   * @param <E> the type of elements held in this collection   * @param <E> the type of elements held in this collection
83   */   */
 @SuppressWarnings("unchecked")  
84  public class PriorityQueue<E> extends AbstractQueue<E>  public class PriorityQueue<E> extends AbstractQueue<E>
85      implements java.io.Serializable {      implements java.io.Serializable {
86    
# Line 93  Line 96 
96       * heap and each descendant d of n, n <= d.  The element with the       * heap and each descendant d of n, n <= d.  The element with the
97       * lowest value is in queue[0], assuming the queue is nonempty.       * lowest value is in queue[0], assuming the queue is nonempty.
98       */       */
99      private transient Object[] queue;      transient Object[] queue; // non-private to simplify nested class access
100    
101      /**      /**
102       * The number of elements in the priority queue.       * The number of elements in the priority queue.
# Line 110  Line 113 
113       * The number of times this priority queue has been       * The number of times this priority queue has been
114       * <i>structurally modified</i>.  See AbstractList for gory details.       * <i>structurally modified</i>.  See AbstractList for gory details.
115       */       */
116      private transient int modCount = 0;      transient int modCount = 0; // non-private to simplify nested class access
117    
118      /**      /**
119       * Creates a {@code PriorityQueue} with the default initial       * Creates a {@code PriorityQueue} with the default initial
# Line 331  Line 334 
334          return true;          return true;
335      }      }
336    
337        @SuppressWarnings("unchecked")
338      public E peek() {      public E peek() {
339          return (size == 0) ? null : (E) queue[0];          return (size == 0) ? null : (E) queue[0];
340      }      }
# Line 512  Line 516 
516                  (forgetMeNot != null && !forgetMeNot.isEmpty());                  (forgetMeNot != null && !forgetMeNot.isEmpty());
517          }          }
518    
519            @SuppressWarnings("unchecked")
520          public E next() {          public E next() {
521              if (expectedModCount != modCount)              if (expectedModCount != modCount)
522                  throw new ConcurrentModificationException();                  throw new ConcurrentModificationException();
# Line 564  Line 569 
569          size = 0;          size = 0;
570      }      }
571    
572        @SuppressWarnings("unchecked")
573      public E poll() {      public E poll() {
574          if (size == 0)          if (size == 0)
575              return null;              return null;
# Line 589  Line 595 
595       * position before i. This fact is used by iterator.remove so as to       * position before i. This fact is used by iterator.remove so as to
596       * avoid missing traversing elements.       * avoid missing traversing elements.
597       */       */
598        @SuppressWarnings("unchecked")
599      private E removeAt(int i) {      private E removeAt(int i) {
600          // assert i >= 0 && i < size;          // assert i >= 0 && i < size;
601          modCount++;          modCount++;
# Line 627  Line 634 
634              siftUpComparable(k, x);              siftUpComparable(k, x);
635      }      }
636    
637        @SuppressWarnings("unchecked")
638      private void siftUpComparable(int k, E x) {      private void siftUpComparable(int k, E x) {
639          Comparable<? super E> key = (Comparable<? super E>) x;          Comparable<? super E> key = (Comparable<? super E>) x;
640          while (k > 0) {          while (k > 0) {
# Line 640  Line 648 
648          queue[k] = key;          queue[k] = key;
649      }      }
650    
651        @SuppressWarnings("unchecked")
652      private void siftUpUsingComparator(int k, E x) {      private void siftUpUsingComparator(int k, E x) {
653          while (k > 0) {          while (k > 0) {
654              int parent = (k - 1) >>> 1;              int parent = (k - 1) >>> 1;
# Line 667  Line 676 
676              siftDownComparable(k, x);              siftDownComparable(k, x);
677      }      }
678    
679        @SuppressWarnings("unchecked")
680      private void siftDownComparable(int k, E x) {      private void siftDownComparable(int k, E x) {
681          Comparable<? super E> key = (Comparable<? super E>)x;          Comparable<? super E> key = (Comparable<? super E>)x;
682          int half = size >>> 1;        // loop while a non-leaf          int half = size >>> 1;        // loop while a non-leaf
# Line 685  Line 695 
695          queue[k] = key;          queue[k] = key;
696      }      }
697    
698        @SuppressWarnings("unchecked")
699      private void siftDownUsingComparator(int k, E x) {      private void siftDownUsingComparator(int k, E x) {
700          int half = size >>> 1;          int half = size >>> 1;
701          while (k < half) {          while (k < half) {
# Line 706  Line 717 
717       * Establishes the heap invariant (described above) in the entire tree,       * Establishes the heap invariant (described above) in the entire tree,
718       * assuming nothing about the order of the elements prior to the call.       * assuming nothing about the order of the elements prior to the call.
719       */       */
720        @SuppressWarnings("unchecked")
721      private void heapify() {      private void heapify() {
722          for (int i = (size >>> 1) - 1; i >= 0; i--)          for (int i = (size >>> 1) - 1; i >= 0; i--)
723              siftDown(i, (E) queue[i]);              siftDown(i, (E) queue[i]);
# Line 730  Line 742 
742       * @serialData The length of the array backing the instance is       * @serialData The length of the array backing the instance is
743       *             emitted (int), followed by all of its elements       *             emitted (int), followed by all of its elements
744       *             (each an {@code Object}) in the proper order.       *             (each an {@code Object}) in the proper order.
745         * @param s the stream
746       */       */
747      private void writeObject(java.io.ObjectOutputStream s)      private void writeObject(java.io.ObjectOutputStream s)
748          throws java.io.IOException {          throws java.io.IOException {
# Line 745  Line 758 
758      }      }
759    
760      /**      /**
761       * Reconstitutes this queue from a stream (that is, deserializes it).       * Reconstitutes the {@code PriorityQueue} instance from a stream
762         * (that is, deserializes it).
763         *
764         * @param s the stream
765       */       */
766      private void readObject(java.io.ObjectInputStream s)      private void readObject(java.io.ObjectInputStream s)
767          throws java.io.IOException, ClassNotFoundException {          throws java.io.IOException, ClassNotFoundException {
# Line 765  Line 781 
781          // spec has never explained what that might be.          // spec has never explained what that might be.
782          heapify();          heapify();
783      }      }
784    
785        // wrapping constructor in method avoids transient javac problems
786        final PriorityQueueSpliterator<E> spliterator(int origin, int fence,
787                                                      int expectedModCount) {
788            return new PriorityQueueSpliterator(this, origin, fence,
789                                                expectedModCount);
790        }
791    
792        public Stream<E> stream() {
793            int flags = Streams.STREAM_IS_SIZED;
794            return Streams.stream
795                (() -> spliterator(0, size, modCount), flags);
796        }
797        public Stream<E> parallelStream() {
798            int flags = Streams.STREAM_IS_SIZED;
799            return Streams.parallelStream
800                (() -> spliterator(0, size, modCount), flags);
801        }
802    
803        /** Index-based split-by-two Spliterator */
804        static final class PriorityQueueSpliterator<E>
805            implements Spliterator<E>, Iterator<E> {
806            private final PriorityQueue<E> pq;
807            private int index;           // current index, modified on advance/split
808            private final int fence;     // one past last index
809            private final int expectedModCount; // for comodification checks
810    
811            /** Create new spliterator covering the given  range */
812            PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
813                                 int expectedModCount) {
814                this.pq = pq; this.index = origin; this.fence = fence;
815                this.expectedModCount = expectedModCount;
816            }
817    
818            public PriorityQueueSpliterator<E> trySplit() {
819                int lo = index, mid = (lo + fence) >>> 1;
820                return (lo >= mid) ? null :
821                    new PriorityQueueSpliterator<E>(pq, lo, index = mid,
822                                                expectedModCount);
823            }
824    
825            public void forEach(Block<? super E> block) {
826                Object[] a; int i, hi; // hoist accesses and checks from loop
827                if (block == null)
828                    throw new NullPointerException();
829                if ((a = pq.queue).length >= (hi = fence) &&
830                    (i = index) >= 0 && i < hi) {
831                    index = hi;
832                    do {
833                        @SuppressWarnings("unchecked") E e = (E) a[i];
834                        block.accept(e);
835                    } while (++i < hi);
836                    if (pq.modCount != expectedModCount)
837                        throw new ConcurrentModificationException();
838                }
839            }
840    
841            public boolean tryAdvance(Block<? super E> block) {
842                if (index >= 0 && index < fence) {
843                    if (pq.modCount != expectedModCount)
844                        throw new ConcurrentModificationException();
845                    @SuppressWarnings("unchecked") E e =
846                        (E)pq.queue[index++];
847                    block.accept(e);
848                    return true;
849                }
850                return false;
851            }
852    
853            public long estimateSize() { return (long)(fence - index); }
854            public boolean hasExactSize() { return true; }
855            public boolean hasExactSplits() { return true; }
856    
857            // Iterator support
858            public Iterator<E> iterator() { return this; }
859            public void remove() { throw new UnsupportedOperationException(); }
860            public boolean hasNext() { return index >= 0 && index < fence; }
861    
862            public E next() {
863                if (index < 0 || index >= fence)
864                    throw new NoSuchElementException();
865                if (pq.modCount != expectedModCount)
866                    throw new ConcurrentModificationException();
867                @SuppressWarnings("unchecked") E e =
868                    (E) pq.queue[index++];
869                return e;
870            }
871        }
872  }  }

Legend:
Removed from v.1.80  
changed lines
  Added in v.1.81

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8