ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/PriorityQueue.java
(Generate patch)

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.88 by dl, Fri Feb 1 16:23:04 2013 UTC vs.
Revision 1.111 by jsr166, Wed Nov 23 20:36:31 2016 UTC

# Line 1 | Line 1
1   /*
2 < * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
2 > * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
3   * 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
# Line 24 | Line 24
24   */
25  
26   package java.util;
27 < import java.util.stream.Stream;
28 < import java.util.Spliterator;
29 < import java.util.stream.Streams;
27 >
28   import java.util.function.Consumer;
29  
30   /**
# Line 56 | Line 54 | import java.util.function.Consumer;
54   * <p>This class and its iterator implement all of the
55   * <em>optional</em> methods of the {@link Collection} and {@link
56   * Iterator} interfaces.  The Iterator provided in method {@link
57 < * #iterator()} is <em>not</em> guaranteed to traverse the elements of
57 > * #iterator()} and the Spliterator provided in method {@link #spliterator()}
58 > * are <em>not</em> guaranteed to traverse the elements of
59   * the priority queue in any particular order. If you need ordered
60   * traversal, consider using {@code Arrays.sort(pq.toArray())}.
61   *
# Line 67 | Line 66 | import java.util.function.Consumer;
66   * java.util.concurrent.PriorityBlockingQueue} class.
67   *
68   * <p>Implementation note: this implementation provides
69 < * O(log(n)) time for the enqueing and dequeing methods
69 > * O(log(n)) time for the enqueuing and dequeuing methods
70   * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
71   * linear time for the {@code remove(Object)} and {@code contains(Object)}
72   * methods; and constant time for the retrieval methods
# Line 79 | Line 78 | import java.util.function.Consumer;
78   *
79   * @since 1.5
80   * @author Josh Bloch, Doug Lea
81 < * @param <E> the type of elements held in this collection
81 > * @param <E> the type of elements held in this queue
82   */
83   public class PriorityQueue<E> extends AbstractQueue<E>
84      implements java.io.Serializable {
# Line 101 | Line 100 | public class PriorityQueue<E> extends Ab
100      /**
101       * The number of elements in the priority queue.
102       */
103 <    private int size = 0;
103 >    int size;
104  
105      /**
106       * The comparator, or null if priority queue uses elements'
# Line 113 | Line 112 | public class PriorityQueue<E> extends Ab
112       * The number of times this priority queue has been
113       * <i>structurally modified</i>.  See AbstractList for gory details.
114       */
115 <    transient int modCount = 0; // non-private to simplify nested class access
115 >    transient int modCount;     // non-private to simplify nested class access
116  
117      /**
118       * Creates a {@code PriorityQueue} with the default initial
# Line 138 | Line 137 | public class PriorityQueue<E> extends Ab
137      }
138  
139      /**
140 +     * Creates a {@code PriorityQueue} with the default initial capacity and
141 +     * whose elements are ordered according to the specified comparator.
142 +     *
143 +     * @param  comparator the comparator that will be used to order this
144 +     *         priority queue.  If {@code null}, the {@linkplain Comparable
145 +     *         natural ordering} of the elements will be used.
146 +     * @since 1.8
147 +     */
148 +    public PriorityQueue(Comparator<? super E> comparator) {
149 +        this(DEFAULT_INITIAL_CAPACITY, comparator);
150 +    }
151 +
152 +    /**
153       * Creates a {@code PriorityQueue} with the specified initial capacity
154       * that orders its elements according to the specified comparator.
155       *
# Line 247 | Line 259 | public class PriorityQueue<E> extends Ab
259              a = Arrays.copyOf(a, a.length, Object[].class);
260          int len = a.length;
261          if (len == 1 || this.comparator != null)
262 <            for (int i = 0; i < len; i++)
263 <                if (a[i] == null)
262 >            for (Object e : a)
263 >                if (e == null)
264                      throw new NullPointerException();
265          this.queue = a;
266          this.size = a.length;
# Line 326 | Line 338 | public class PriorityQueue<E> extends Ab
338          int i = size;
339          if (i >= queue.length)
340              grow(i + 1);
341 +        siftUp(i, e);
342          size = i + 1;
330 –        if (i == 0)
331 –            queue[0] = e;
332 –        else
333 –            siftUp(i, e);
343          return true;
344      }
345  
# Line 395 | Line 404 | public class PriorityQueue<E> extends Ab
404       * @return {@code true} if this queue contains the specified element
405       */
406      public boolean contains(Object o) {
407 <        return indexOf(o) != -1;
407 >        return indexOf(o) >= 0;
408      }
409  
410      /**
# Line 437 | Line 446 | public class PriorityQueue<E> extends Ab
446       * The following code can be used to dump the queue into a newly
447       * allocated array of {@code String}:
448       *
449 <     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
449 >     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
450       *
451       * Note that {@code toArray(new Object[0])} is identical in function to
452       * {@code toArray()}.
# Line 478 | Line 487 | public class PriorityQueue<E> extends Ab
487           * Index (into queue array) of element to be returned by
488           * subsequent call to next.
489           */
490 <        private int cursor = 0;
490 >        private int cursor;
491  
492          /**
493           * Index of element returned by most recent call to next,
# Line 498 | Line 507 | public class PriorityQueue<E> extends Ab
507           * We expect that most iterations, even those involving removals,
508           * will not need to store elements in this field.
509           */
510 <        private ArrayDeque<E> forgetMeNot = null;
510 >        private ArrayDeque<E> forgetMeNot;
511  
512          /**
513           * Element returned by the most recent call to next iff that
514           * element was drawn from the forgetMeNot list.
515           */
516 <        private E lastRetElt = null;
516 >        private E lastRetElt;
517  
518          /**
519           * The modCount value that the iterator believes that the backing
# Line 543 | Line 552 | public class PriorityQueue<E> extends Ab
552                      cursor--;
553                  else {
554                      if (forgetMeNot == null)
555 <                        forgetMeNot = new ArrayDeque<E>();
555 >                        forgetMeNot = new ArrayDeque<>();
556                      forgetMeNot.add(moved);
557                  }
558              } else if (lastRetElt != null) {
# Line 598 | Line 607 | public class PriorityQueue<E> extends Ab
607       * avoid missing traversing elements.
608       */
609      @SuppressWarnings("unchecked")
610 <    private E removeAt(int i) {
610 >    E removeAt(int i) {
611          // assert i >= 0 && i < size;
612          modCount++;
613          int s = --size;
# Line 741 | Line 750 | public class PriorityQueue<E> extends Ab
750      /**
751       * Saves this queue to a stream (that is, serializes it).
752       *
753 +     * @param s the stream
754 +     * @throws java.io.IOException if an I/O error occurs
755       * @serialData The length of the array backing the instance is
756       *             emitted (int), followed by all of its elements
757       *             (each an {@code Object}) in the proper order.
747 –     * @param s the stream
758       */
759      private void writeObject(java.io.ObjectOutputStream s)
760          throws java.io.IOException {
# Line 764 | Line 774 | public class PriorityQueue<E> extends Ab
774       * (that is, deserializes it).
775       *
776       * @param s the stream
777 +     * @throws ClassNotFoundException if the class of a serialized object
778 +     *         could not be found
779 +     * @throws java.io.IOException if an I/O error occurs
780       */
781      private void readObject(java.io.ObjectInputStream s)
782          throws java.io.IOException, ClassNotFoundException {
# Line 784 | Line 797 | public class PriorityQueue<E> extends Ab
797          heapify();
798      }
799  
800 <    // wrapping constructor in method avoids transient javac problems
801 <    final PriorityQueueSpliterator<E> spliterator(int origin, int fence,
802 <                                                  int expectedModCount) {
803 <        return new PriorityQueueSpliterator<E>(this, origin, fence,
804 <                                               expectedModCount);
805 <    }
806 <
807 <    public Stream<E> stream() {
808 <        int flags = Streams.STREAM_IS_SIZED;
809 <        return Streams.stream
810 <            (() -> spliterator(0, size, modCount), flags);
811 <    }
812 <    public Stream<E> parallelStream() {
813 <        int flags = Streams.STREAM_IS_SIZED;
814 <        return Streams.parallelStream
815 <            (() -> spliterator(0, size, modCount), flags);
800 >    /**
801 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
802 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
803 >     * queue. The spliterator does not traverse elements in any particular order
804 >     * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
805 >     *
806 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
807 >     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
808 >     * Overriding implementations should document the reporting of additional
809 >     * characteristic values.
810 >     *
811 >     * @return a {@code Spliterator} over the elements in this queue
812 >     * @since 1.8
813 >     */
814 >    public final Spliterator<E> spliterator() {
815 >        return new PriorityQueueSpliterator<>(this, 0, -1, 0);
816      }
817  
805 –    /** Index-based split-by-two Spliterator */
818      static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
819 +        /*
820 +         * This is very similar to ArrayList Spliterator, except for
821 +         * extra null checks.
822 +         */
823          private final PriorityQueue<E> pq;
824 <        private int index;           // current index, modified on advance/split
825 <        private final int fence;     // one past last index
826 <        private final int expectedModCount; // for comodification checks
824 >        private int index;            // current index, modified on advance/split
825 >        private int fence;            // -1 until first use
826 >        private int expectedModCount; // initialized when fence set
827  
828 <        /** Create new spliterator covering the given  range */
828 >        /** Creates new spliterator covering the given range. */
829          PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
830 <                             int expectedModCount) {
831 <            this.pq = pq; this.index = origin; this.fence = fence;
830 >                                 int expectedModCount) {
831 >            this.pq = pq;
832 >            this.index = origin;
833 >            this.fence = fence;
834              this.expectedModCount = expectedModCount;
835          }
836  
837 +        private int getFence() { // initialize fence to size on first use
838 +            int hi;
839 +            if ((hi = fence) < 0) {
840 +                expectedModCount = pq.modCount;
841 +                hi = fence = pq.size;
842 +            }
843 +            return hi;
844 +        }
845 +
846          public PriorityQueueSpliterator<E> trySplit() {
847 <            int lo = index, mid = (lo + fence) >>> 1;
847 >            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
848              return (lo >= mid) ? null :
849 <                new PriorityQueueSpliterator<E>(pq, lo, index = mid,
850 <                                                expectedModCount);
849 >                new PriorityQueueSpliterator<>(pq, lo, index = mid,
850 >                                               expectedModCount);
851          }
852  
853 <        public void forEach(Consumer<? super E> block) {
854 <            Object[] a; int i, hi; // hoist accesses and checks from loop
855 <            if (block == null)
853 >        @SuppressWarnings("unchecked")
854 >        public void forEachRemaining(Consumer<? super E> action) {
855 >            int i, hi, mc; // hoist accesses and checks from loop
856 >            PriorityQueue<E> q; Object[] a;
857 >            if (action == null)
858                  throw new NullPointerException();
859 <            if ((a = pq.queue).length >= (hi = fence) &&
860 <                (i = index) >= 0 && i < hi) {
861 <                index = hi;
862 <                do {
863 <                    @SuppressWarnings("unchecked") E e = (E) a[i];
864 <                    block.accept(e);
865 <                } while (++i < hi);
866 <                if (pq.modCount != expectedModCount)
867 <                    throw new ConcurrentModificationException();
859 >            if ((q = pq) != null && (a = q.queue) != null) {
860 >                if ((hi = fence) < 0) {
861 >                    mc = q.modCount;
862 >                    hi = q.size;
863 >                }
864 >                else
865 >                    mc = expectedModCount;
866 >                if ((i = index) >= 0 && (index = hi) <= a.length) {
867 >                    for (E e;; ++i) {
868 >                        if (i < hi) {
869 >                            if ((e = (E) a[i]) == null) // must be CME
870 >                                break;
871 >                            action.accept(e);
872 >                        }
873 >                        else if (q.modCount != mc)
874 >                            break;
875 >                        else
876 >                            return;
877 >                    }
878 >                }
879              }
880 +            throw new ConcurrentModificationException();
881          }
882  
883 <        public boolean tryAdvance(Consumer<? super E> block) {
884 <            if (index >= 0 && index < fence) {
885 <                @SuppressWarnings("unchecked") E e =
886 <                    (E)pq.queue[index++];
887 <                block.accept(e);
883 >        public boolean tryAdvance(Consumer<? super E> action) {
884 >            if (action == null)
885 >                throw new NullPointerException();
886 >            int hi = getFence(), lo = index;
887 >            if (lo >= 0 && lo < hi) {
888 >                index = lo + 1;
889 >                @SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
890 >                if (e == null)
891 >                    throw new ConcurrentModificationException();
892 >                action.accept(e);
893                  if (pq.modCount != expectedModCount)
894                      throw new ConcurrentModificationException();
895                  return true;
# Line 851 | Line 897 | public class PriorityQueue<E> extends Ab
897              return false;
898          }
899  
900 <        public long estimateSize() { return (long)(fence - index); }
901 <        public boolean hasExactSize() { return true; }
902 <        public boolean hasExactSplits() { return true; }
900 >        public long estimateSize() {
901 >            return (long) (getFence() - index);
902 >        }
903 >
904 >        public int characteristics() {
905 >            return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
906 >        }
907      }
908   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines