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.125 by jsr166, Sun May 6 21:07:41 2018 UTC vs.
Revision 1.128 by jsr166, Sun May 6 23:29:25 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 617 | 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 900 | 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