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.124 by jsr166, Sun May 6 19:35:51 2018 UTC vs.
Revision 1.129 by jsr166, Mon Oct 1 00:10:53 2018 UTC

# Line 26 | Line 26
26   package java.util;
27  
28   import java.util.function.Consumer;
29 + import java.util.function.Predicate;
30   import jdk.internal.misc.SharedSecrets;
31  
32   /**
# Line 74 | Line 75 | import jdk.internal.misc.SharedSecrets;
75   * ({@code peek}, {@code element}, and {@code size}).
76   *
77   * <p>This class is a member of the
78 < * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">
78 > * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
79   * Java Collections Framework</a>.
80   *
81   * @since 1.5
# Line 242 | Line 243 | public class PriorityQueue<E> extends Ab
243          initElementsFromCollection(c);
244      }
245  
246 +    /** Ensures that queue[0] exists, helping peek() and poll(). */
247 +    private static Object[] ensureNonEmpty(Object[] es) {
248 +        return (es.length > 0) ? es : new Object[1];
249 +    }
250 +
251      private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
252          if (c.getClass() == PriorityQueue.class) {
253 <            this.queue = c.toArray();
253 >            this.queue = ensureNonEmpty(c.toArray());
254              this.size = c.size();
255          } else {
256              initFromCollection(c);
# Line 261 | Line 267 | public class PriorityQueue<E> extends Ab
267              for (Object e : es)
268                  if (e == null)
269                      throw new NullPointerException();
270 <        this.queue = es;
270 >        this.queue = ensureNonEmpty(es);
271          this.size = len;
272      }
273  
# Line 343 | Line 349 | public class PriorityQueue<E> extends Ab
349      }
350  
351      public E peek() {
352 <        return (size == 0) ? null : (E) queue[0];
352 >        return (E) queue[0];
353      }
354  
355      private int indexOf(Object o) {
# Line 579 | Line 585 | public class PriorityQueue<E> extends Ab
585      }
586  
587      public E poll() {
588 <        if (size == 0)
589 <            return null;
590 <        int s = --size;
591 <        modCount++;
592 <        E result = (E) queue[0];
593 <        E x = (E) queue[s];
594 <        queue[s] = null;
595 <        if (s != 0)
596 <            siftDown(0, x);
588 >        final Object[] es;
589 >        final E result;
590 >
591 >        if ((result = (E) ((es = queue)[0])) != null) {
592 >            modCount++;
593 >            final int n;
594 >            final E x = (E) es[(n = --size)];
595 >            es[n] = null;
596 >            if (n > 0) {
597 >                final Comparator<? super E> cmp;
598 >                if ((cmp = comparator) == null)
599 >                    siftDownComparable(0, x, es, n);
600 >                else
601 >                    siftDownUsingComparator(0, x, es, n, cmp);
602 >            }
603 >        }
604          return result;
605      }
606  
# Line 605 | Line 618 | public class PriorityQueue<E> extends Ab
618       */
619      E removeAt(int i) {
620          // assert i >= 0 && i < size;
621 +        final Object[] es = queue;
622          modCount++;
623          int s = --size;
624          if (s == i) // removed last element
625 <            queue[i] = null;
625 >            es[i] = null;
626          else {
627 <            E moved = (E) queue[s];
628 <            queue[s] = null;
627 >            E moved = (E) es[s];
628 >            es[s] = null;
629              siftDown(i, moved);
630 <            if (queue[i] == moved) {
630 >            if (es[i] == moved) {
631                  siftUp(i, moved);
632 <                if (queue[i] != moved)
632 >                if (es[i] != moved)
633                      return moved;
634              }
635          }
# Line 727 | Line 741 | public class PriorityQueue<E> extends Ab
741      private void heapify() {
742          final Object[] es = queue;
743          int n = size, i = (n >>> 1) - 1;
744 <        Comparator<? super E> cmp = comparator;
745 <        if (cmp == null)
744 >        final Comparator<? super E> cmp;
745 >        if ((cmp = comparator) == null)
746              for (; i >= 0; i--)
747                  siftDownComparable(i, (E) es[i], es, n);
748          else
# Line 790 | Line 804 | public class PriorityQueue<E> extends Ab
804          s.readInt();
805  
806          SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
807 <        queue = new Object[size];
807 >        final Object[] es = queue = new Object[Math.max(size, 1)];
808  
809          // Read in all elements.
796 –        final Object[] es = queue;
810          for (int i = 0, n = size; i < n; i++)
811              es[i] = s.readObject();
812  
# Line 889 | Line 902 | public class PriorityQueue<E> extends Ab
902      }
903  
904      /**
905 +     * @throws NullPointerException {@inheritDoc}
906 +     */
907 +    public boolean removeIf(Predicate<? super E> filter) {
908 +        Objects.requireNonNull(filter);
909 +        return bulkRemove(filter);
910 +    }
911 +
912 +    /**
913 +     * @throws NullPointerException {@inheritDoc}
914 +     */
915 +    public boolean removeAll(Collection<?> c) {
916 +        Objects.requireNonNull(c);
917 +        return bulkRemove(e -> c.contains(e));
918 +    }
919 +
920 +    /**
921 +     * @throws NullPointerException {@inheritDoc}
922 +     */
923 +    public boolean retainAll(Collection<?> c) {
924 +        Objects.requireNonNull(c);
925 +        return bulkRemove(e -> !c.contains(e));
926 +    }
927 +
928 +    // A tiny bit set implementation
929 +
930 +    private static long[] nBits(int n) {
931 +        return new long[((n - 1) >> 6) + 1];
932 +    }
933 +    private static void setBit(long[] bits, int i) {
934 +        bits[i >> 6] |= 1L << i;
935 +    }
936 +    private static boolean isClear(long[] bits, int i) {
937 +        return (bits[i >> 6] & (1L << i)) == 0;
938 +    }
939 +
940 +    /** Implementation of bulk remove methods. */
941 +    private boolean bulkRemove(Predicate<? super E> filter) {
942 +        final int expectedModCount = ++modCount;
943 +        final Object[] es = queue;
944 +        final int end = size;
945 +        int i;
946 +        // Optimize for initial run of survivors
947 +        for (i = 0; i < end && !filter.test((E) es[i]); i++)
948 +            ;
949 +        if (i >= end) {
950 +            if (modCount != expectedModCount)
951 +                throw new ConcurrentModificationException();
952 +            return false;
953 +        }
954 +        // Tolerate predicates that reentrantly access the collection for
955 +        // read (but writers still get CME), so traverse once to find
956 +        // elements to delete, a second pass to physically expunge.
957 +        final int beg = i;
958 +        final long[] deathRow = nBits(end - beg);
959 +        deathRow[0] = 1L;   // set bit 0
960 +        for (i = beg + 1; i < end; i++)
961 +            if (filter.test((E) es[i]))
962 +                setBit(deathRow, i - beg);
963 +        if (modCount != expectedModCount)
964 +            throw new ConcurrentModificationException();
965 +        int w = beg;
966 +        for (i = beg; i < end; i++)
967 +            if (isClear(deathRow, i - beg))
968 +                es[w++] = es[i];
969 +        for (i = size = w; i < end; i++)
970 +            es[i] = null;
971 +        heapify();
972 +        return true;
973 +    }
974 +
975 +    /**
976       * @throws NullPointerException {@inheritDoc}
977       */
978      public void forEach(Consumer<? super E> action) {

Diff Legend

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