627 lines
20 KiB
Java
627 lines
20 KiB
Java
|
package com.google.common.collect;
|
||
|
|
|
||
|
|
import com.google.common.base.Preconditions;
|
||
|
|
import com.google.common.math.IntMath;
|
||
|
|
import java.util.AbstractQueue;
|
||
|
|
import java.util.ArrayDeque;
|
||
|
|
import java.util.ArrayList;
|
||
|
|
import java.util.Collection;
|
||
|
|
import java.util.Collections;
|
||
|
|
import java.util.Comparator;
|
||
|
|
import java.util.ConcurrentModificationException;
|
||
|
|
import java.util.Iterator;
|
||
|
|
import java.util.List;
|
||
|
|
import java.util.NoSuchElementException;
|
||
|
|
import java.util.Queue;
|
||
|
|
|
||
|
|
/* loaded from: classes2.dex */
|
||
|
|
public final class MinMaxPriorityQueue<E> extends AbstractQueue<E> {
|
||
|
|
private static final int DEFAULT_CAPACITY = 11;
|
||
|
|
private static final int EVEN_POWERS_OF_TWO = 1431655765;
|
||
|
|
private static final int ODD_POWERS_OF_TWO = -1431655766;
|
||
|
|
private final MinMaxPriorityQueue<E>.Heap maxHeap;
|
||
|
|
final int maximumSize;
|
||
|
|
private final MinMaxPriorityQueue<E>.Heap minHeap;
|
||
|
|
private int modCount;
|
||
|
|
private Object[] queue;
|
||
|
|
private int size;
|
||
|
|
|
||
|
|
public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create() {
|
||
|
|
return new Builder(Ordering.natural()).create();
|
||
|
|
}
|
||
|
|
|
||
|
|
public static <E extends Comparable<E>> MinMaxPriorityQueue<E> create(Iterable<? extends E> iterable) {
|
||
|
|
return new Builder(Ordering.natural()).create(iterable);
|
||
|
|
}
|
||
|
|
|
||
|
|
public static <B> Builder<B> orderedBy(Comparator<B> comparator) {
|
||
|
|
return new Builder<>(comparator);
|
||
|
|
}
|
||
|
|
|
||
|
|
public static Builder<Comparable> expectedSize(int i) {
|
||
|
|
return new Builder(Ordering.natural()).expectedSize(i);
|
||
|
|
}
|
||
|
|
|
||
|
|
public static Builder<Comparable> maximumSize(int i) {
|
||
|
|
return new Builder(Ordering.natural()).maximumSize(i);
|
||
|
|
}
|
||
|
|
|
||
|
|
/* loaded from: classes2.dex */
|
||
|
|
public static final class Builder<B> {
|
||
|
|
private static final int UNSET_EXPECTED_SIZE = -1;
|
||
|
|
private final Comparator<B> comparator;
|
||
|
|
private int expectedSize;
|
||
|
|
private int maximumSize;
|
||
|
|
|
||
|
|
private Builder(Comparator<B> comparator) {
|
||
|
|
this.expectedSize = -1;
|
||
|
|
this.maximumSize = Integer.MAX_VALUE;
|
||
|
|
this.comparator = (Comparator) Preconditions.checkNotNull(comparator);
|
||
|
|
}
|
||
|
|
|
||
|
|
public final Builder<B> expectedSize(int i) {
|
||
|
|
Preconditions.checkArgument(i >= 0);
|
||
|
|
this.expectedSize = i;
|
||
|
|
return this;
|
||
|
|
}
|
||
|
|
|
||
|
|
public final Builder<B> maximumSize(int i) {
|
||
|
|
Preconditions.checkArgument(i > 0);
|
||
|
|
this.maximumSize = i;
|
||
|
|
return this;
|
||
|
|
}
|
||
|
|
|
||
|
|
public final <T extends B> MinMaxPriorityQueue<T> create() {
|
||
|
|
return create(Collections.emptySet());
|
||
|
|
}
|
||
|
|
|
||
|
|
public final <T extends B> MinMaxPriorityQueue<T> create(Iterable<? extends T> iterable) {
|
||
|
|
MinMaxPriorityQueue<T> minMaxPriorityQueue = new MinMaxPriorityQueue<>(this, MinMaxPriorityQueue.initialQueueSize(this.expectedSize, this.maximumSize, iterable));
|
||
|
|
Iterator<? extends T> it = iterable.iterator();
|
||
|
|
while (it.hasNext()) {
|
||
|
|
minMaxPriorityQueue.offer(it.next());
|
||
|
|
}
|
||
|
|
return minMaxPriorityQueue;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: private */
|
||
|
|
public <T extends B> Ordering<T> ordering() {
|
||
|
|
return Ordering.from(this.comparator);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
private MinMaxPriorityQueue(Builder<? super E> builder, int i) {
|
||
|
|
Ordering ordering = builder.ordering();
|
||
|
|
MinMaxPriorityQueue<E>.Heap heap = new Heap(this, ordering);
|
||
|
|
this.minHeap = heap;
|
||
|
|
MinMaxPriorityQueue<E>.Heap heap2 = new Heap(this, ordering.reverse());
|
||
|
|
this.maxHeap = heap2;
|
||
|
|
heap.otherHeap = heap2;
|
||
|
|
heap2.otherHeap = heap;
|
||
|
|
this.maximumSize = ((Builder) builder).maximumSize;
|
||
|
|
this.queue = new Object[i];
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractQueue, java.util.AbstractCollection, java.util.Collection, java.util.Queue
|
||
|
|
public final boolean add(E e) {
|
||
|
|
offer(e);
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractQueue, java.util.AbstractCollection, java.util.Collection
|
||
|
|
public final boolean addAll(Collection<? extends E> collection) {
|
||
|
|
Iterator<? extends E> it = collection.iterator();
|
||
|
|
boolean z = false;
|
||
|
|
while (it.hasNext()) {
|
||
|
|
offer(it.next());
|
||
|
|
z = true;
|
||
|
|
}
|
||
|
|
return z;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.Queue
|
||
|
|
public final boolean offer(E e) {
|
||
|
|
Preconditions.checkNotNull(e);
|
||
|
|
this.modCount++;
|
||
|
|
int i = this.size;
|
||
|
|
this.size = i + 1;
|
||
|
|
growIfNeeded();
|
||
|
|
heapForIndex(i).bubbleUp(i, e);
|
||
|
|
return this.size <= this.maximumSize || pollLast() != e;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.Queue
|
||
|
|
public final E poll() {
|
||
|
|
if (isEmpty()) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
return removeAndGet(0);
|
||
|
|
}
|
||
|
|
|
||
|
|
final E elementData(int i) {
|
||
|
|
return (E) this.queue[i];
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.Queue
|
||
|
|
public final E peek() {
|
||
|
|
if (isEmpty()) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
return elementData(0);
|
||
|
|
}
|
||
|
|
|
||
|
|
private int getMaxElementIndex() {
|
||
|
|
int i = this.size;
|
||
|
|
if (i != 1) {
|
||
|
|
return (i == 2 || this.maxHeap.compareElements(1, 2) <= 0) ? 1 : 2;
|
||
|
|
}
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
public final E pollFirst() {
|
||
|
|
return poll();
|
||
|
|
}
|
||
|
|
|
||
|
|
public final E removeFirst() {
|
||
|
|
return remove();
|
||
|
|
}
|
||
|
|
|
||
|
|
public final E peekFirst() {
|
||
|
|
return peek();
|
||
|
|
}
|
||
|
|
|
||
|
|
public final E pollLast() {
|
||
|
|
if (isEmpty()) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
return removeAndGet(getMaxElementIndex());
|
||
|
|
}
|
||
|
|
|
||
|
|
public final E removeLast() {
|
||
|
|
if (isEmpty()) {
|
||
|
|
throw new NoSuchElementException();
|
||
|
|
}
|
||
|
|
return removeAndGet(getMaxElementIndex());
|
||
|
|
}
|
||
|
|
|
||
|
|
public final E peekLast() {
|
||
|
|
if (isEmpty()) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
return elementData(getMaxElementIndex());
|
||
|
|
}
|
||
|
|
|
||
|
|
final MoveDesc<E> removeAt(int i) {
|
||
|
|
Preconditions.checkPositionIndex(i, this.size);
|
||
|
|
this.modCount++;
|
||
|
|
int i2 = this.size - 1;
|
||
|
|
this.size = i2;
|
||
|
|
if (i2 == i) {
|
||
|
|
this.queue[i2] = null;
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
E elementData = elementData(i2);
|
||
|
|
int swapWithConceptuallyLastElement = heapForIndex(this.size).swapWithConceptuallyLastElement(elementData);
|
||
|
|
if (swapWithConceptuallyLastElement == i) {
|
||
|
|
this.queue[this.size] = null;
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
E elementData2 = elementData(this.size);
|
||
|
|
this.queue[this.size] = null;
|
||
|
|
MoveDesc<E> fillHole = fillHole(i, elementData2);
|
||
|
|
if (swapWithConceptuallyLastElement >= i) {
|
||
|
|
return fillHole;
|
||
|
|
}
|
||
|
|
if (fillHole == null) {
|
||
|
|
return new MoveDesc<>(elementData, elementData2);
|
||
|
|
}
|
||
|
|
return new MoveDesc<>(elementData, fillHole.replaced);
|
||
|
|
}
|
||
|
|
|
||
|
|
private MoveDesc<E> fillHole(int i, E e) {
|
||
|
|
MinMaxPriorityQueue<E>.Heap heapForIndex = heapForIndex(i);
|
||
|
|
int fillHoleAt = heapForIndex.fillHoleAt(i);
|
||
|
|
int bubbleUpAlternatingLevels = heapForIndex.bubbleUpAlternatingLevels(fillHoleAt, e);
|
||
|
|
if (bubbleUpAlternatingLevels == fillHoleAt) {
|
||
|
|
return heapForIndex.tryCrossOverAndBubbleUp(i, fillHoleAt, e);
|
||
|
|
}
|
||
|
|
if (bubbleUpAlternatingLevels < i) {
|
||
|
|
return new MoveDesc<>(e, elementData(i));
|
||
|
|
}
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: package-private */
|
||
|
|
/* loaded from: classes2.dex */
|
||
|
|
public static class MoveDesc<E> {
|
||
|
|
final E replaced;
|
||
|
|
final E toTrickle;
|
||
|
|
|
||
|
|
MoveDesc(E e, E e2) {
|
||
|
|
this.toTrickle = e;
|
||
|
|
this.replaced = e2;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
private E removeAndGet(int i) {
|
||
|
|
E elementData = elementData(i);
|
||
|
|
removeAt(i);
|
||
|
|
return elementData;
|
||
|
|
}
|
||
|
|
|
||
|
|
private MinMaxPriorityQueue<E>.Heap heapForIndex(int i) {
|
||
|
|
return isEvenLevel(i) ? this.minHeap : this.maxHeap;
|
||
|
|
}
|
||
|
|
|
||
|
|
static boolean isEvenLevel(int i) {
|
||
|
|
int i2 = ~(~(i + 1));
|
||
|
|
Preconditions.checkState(i2 > 0, "negative index");
|
||
|
|
return (EVEN_POWERS_OF_TWO & i2) > (i2 & ODD_POWERS_OF_TWO);
|
||
|
|
}
|
||
|
|
|
||
|
|
final boolean isIntact() {
|
||
|
|
for (int i = 1; i < this.size; i++) {
|
||
|
|
if (!heapForIndex(i).verifyIndex(i)) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: package-private */
|
||
|
|
/* loaded from: classes2.dex */
|
||
|
|
public class Heap {
|
||
|
|
final Ordering<E> ordering;
|
||
|
|
MinMaxPriorityQueue<E>.Heap otherHeap;
|
||
|
|
final MinMaxPriorityQueue this$0;
|
||
|
|
|
||
|
|
private int getLeftChildIndex(int i) {
|
||
|
|
return (i << 1) + 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int getRightChildIndex(int i) {
|
||
|
|
return (i << 1) + 2;
|
||
|
|
}
|
||
|
|
|
||
|
|
Heap(MinMaxPriorityQueue minMaxPriorityQueue, Ordering<E> ordering) {
|
||
|
|
this.this$0 = minMaxPriorityQueue;
|
||
|
|
this.ordering = ordering;
|
||
|
|
}
|
||
|
|
|
||
|
|
int compareElements(int i, int i2) {
|
||
|
|
return this.ordering.compare(this.this$0.elementData(i), this.this$0.elementData(i2));
|
||
|
|
}
|
||
|
|
|
||
|
|
MoveDesc<E> tryCrossOverAndBubbleUp(int i, int i2, E e) {
|
||
|
|
Object elementData;
|
||
|
|
int crossOver = crossOver(i2, e);
|
||
|
|
if (crossOver == i2) {
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
if (crossOver < i) {
|
||
|
|
elementData = this.this$0.elementData(i);
|
||
|
|
} else {
|
||
|
|
elementData = this.this$0.elementData(getParentIndex(i));
|
||
|
|
}
|
||
|
|
if (this.otherHeap.bubbleUpAlternatingLevels(crossOver, e) < i) {
|
||
|
|
return new MoveDesc<>(e, elementData);
|
||
|
|
}
|
||
|
|
return null;
|
||
|
|
}
|
||
|
|
|
||
|
|
void bubbleUp(int i, E e) {
|
||
|
|
Heap heap;
|
||
|
|
int crossOverUp = crossOverUp(i, e);
|
||
|
|
if (crossOverUp == i) {
|
||
|
|
crossOverUp = i;
|
||
|
|
heap = this;
|
||
|
|
} else {
|
||
|
|
heap = this.otherHeap;
|
||
|
|
}
|
||
|
|
heap.bubbleUpAlternatingLevels(crossOverUp, e);
|
||
|
|
}
|
||
|
|
|
||
|
|
int bubbleUpAlternatingLevels(int i, E e) {
|
||
|
|
while (i > 2) {
|
||
|
|
int grandparentIndex = getGrandparentIndex(i);
|
||
|
|
Object elementData = this.this$0.elementData(grandparentIndex);
|
||
|
|
if (this.ordering.compare(elementData, e) <= 0) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
this.this$0.queue[i] = elementData;
|
||
|
|
i = grandparentIndex;
|
||
|
|
}
|
||
|
|
this.this$0.queue[i] = e;
|
||
|
|
return i;
|
||
|
|
}
|
||
|
|
|
||
|
|
int findMin(int i, int i2) {
|
||
|
|
if (i >= this.this$0.size) {
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
Preconditions.checkState(i > 0);
|
||
|
|
int min = Math.min(i, this.this$0.size - i2);
|
||
|
|
for (int i3 = i + 1; i3 < min + i2; i3++) {
|
||
|
|
if (compareElements(i3, i) < 0) {
|
||
|
|
i = i3;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return i;
|
||
|
|
}
|
||
|
|
|
||
|
|
int findMinChild(int i) {
|
||
|
|
return findMin(getLeftChildIndex(i), 2);
|
||
|
|
}
|
||
|
|
|
||
|
|
int findMinGrandChild(int i) {
|
||
|
|
int leftChildIndex = getLeftChildIndex(i);
|
||
|
|
if (leftChildIndex < 0) {
|
||
|
|
return -1;
|
||
|
|
}
|
||
|
|
return findMin(getLeftChildIndex(leftChildIndex), 4);
|
||
|
|
}
|
||
|
|
|
||
|
|
int crossOverUp(int i, E e) {
|
||
|
|
int rightChildIndex;
|
||
|
|
if (i == 0) {
|
||
|
|
this.this$0.queue[0] = e;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
int parentIndex = getParentIndex(i);
|
||
|
|
Object elementData = this.this$0.elementData(parentIndex);
|
||
|
|
if (parentIndex != 0 && (rightChildIndex = getRightChildIndex(getParentIndex(parentIndex))) != parentIndex && getLeftChildIndex(rightChildIndex) >= this.this$0.size) {
|
||
|
|
Object elementData2 = this.this$0.elementData(rightChildIndex);
|
||
|
|
if (this.ordering.compare(elementData2, elementData) < 0) {
|
||
|
|
parentIndex = rightChildIndex;
|
||
|
|
elementData = elementData2;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
if (this.ordering.compare(elementData, e) < 0) {
|
||
|
|
this.this$0.queue[i] = elementData;
|
||
|
|
this.this$0.queue[parentIndex] = e;
|
||
|
|
return parentIndex;
|
||
|
|
}
|
||
|
|
this.this$0.queue[i] = e;
|
||
|
|
return i;
|
||
|
|
}
|
||
|
|
|
||
|
|
int swapWithConceptuallyLastElement(E e) {
|
||
|
|
int rightChildIndex;
|
||
|
|
int parentIndex = getParentIndex(this.this$0.size);
|
||
|
|
if (parentIndex != 0 && (rightChildIndex = getRightChildIndex(getParentIndex(parentIndex))) != parentIndex && getLeftChildIndex(rightChildIndex) >= this.this$0.size) {
|
||
|
|
Object elementData = this.this$0.elementData(rightChildIndex);
|
||
|
|
if (this.ordering.compare(elementData, e) < 0) {
|
||
|
|
this.this$0.queue[rightChildIndex] = e;
|
||
|
|
this.this$0.queue[this.this$0.size] = elementData;
|
||
|
|
return rightChildIndex;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return this.this$0.size;
|
||
|
|
}
|
||
|
|
|
||
|
|
int crossOver(int i, E e) {
|
||
|
|
int findMinChild = findMinChild(i);
|
||
|
|
if (findMinChild > 0 && this.ordering.compare(this.this$0.elementData(findMinChild), e) < 0) {
|
||
|
|
this.this$0.queue[i] = this.this$0.elementData(findMinChild);
|
||
|
|
this.this$0.queue[findMinChild] = e;
|
||
|
|
return findMinChild;
|
||
|
|
}
|
||
|
|
return crossOverUp(i, e);
|
||
|
|
}
|
||
|
|
|
||
|
|
int fillHoleAt(int i) {
|
||
|
|
while (true) {
|
||
|
|
int findMinGrandChild = findMinGrandChild(i);
|
||
|
|
if (findMinGrandChild <= 0) {
|
||
|
|
return i;
|
||
|
|
}
|
||
|
|
this.this$0.queue[i] = this.this$0.elementData(findMinGrandChild);
|
||
|
|
i = findMinGrandChild;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: private */
|
||
|
|
public boolean verifyIndex(int i) {
|
||
|
|
if (getLeftChildIndex(i) < this.this$0.size && compareElements(i, getLeftChildIndex(i)) > 0) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
if (getRightChildIndex(i) < this.this$0.size && compareElements(i, getRightChildIndex(i)) > 0) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
if (i <= 0 || compareElements(i, getParentIndex(i)) <= 0) {
|
||
|
|
return i <= 2 || compareElements(getGrandparentIndex(i), i) <= 0;
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int getParentIndex(int i) {
|
||
|
|
return (i - 1) / 2;
|
||
|
|
}
|
||
|
|
|
||
|
|
private int getGrandparentIndex(int i) {
|
||
|
|
return getParentIndex(getParentIndex(i));
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* loaded from: classes2.dex */
|
||
|
|
class QueueIterator implements Iterator<E> {
|
||
|
|
private boolean canRemove;
|
||
|
|
private int cursor;
|
||
|
|
private int expectedModCount;
|
||
|
|
private Queue<E> forgetMeNot;
|
||
|
|
private E lastFromForgetMeNot;
|
||
|
|
private int nextCursor;
|
||
|
|
private List<E> skipMe;
|
||
|
|
final MinMaxPriorityQueue this$0;
|
||
|
|
|
||
|
|
private QueueIterator(MinMaxPriorityQueue minMaxPriorityQueue) {
|
||
|
|
this.this$0 = minMaxPriorityQueue;
|
||
|
|
this.cursor = -1;
|
||
|
|
this.nextCursor = -1;
|
||
|
|
this.expectedModCount = minMaxPriorityQueue.modCount;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.Iterator
|
||
|
|
public boolean hasNext() {
|
||
|
|
checkModCount();
|
||
|
|
nextNotInSkipMe(this.cursor + 1);
|
||
|
|
if (this.nextCursor < this.this$0.size()) {
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
Queue<E> queue = this.forgetMeNot;
|
||
|
|
return (queue == null || queue.isEmpty()) ? false : true;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.Iterator
|
||
|
|
public E next() {
|
||
|
|
checkModCount();
|
||
|
|
nextNotInSkipMe(this.cursor + 1);
|
||
|
|
if (this.nextCursor < this.this$0.size()) {
|
||
|
|
int i = this.nextCursor;
|
||
|
|
this.cursor = i;
|
||
|
|
this.canRemove = true;
|
||
|
|
return (E) this.this$0.elementData(i);
|
||
|
|
}
|
||
|
|
if (this.forgetMeNot != null) {
|
||
|
|
this.cursor = this.this$0.size();
|
||
|
|
E poll = this.forgetMeNot.poll();
|
||
|
|
this.lastFromForgetMeNot = poll;
|
||
|
|
if (poll != null) {
|
||
|
|
this.canRemove = true;
|
||
|
|
return poll;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
throw new NoSuchElementException("iterator moved past last element in queue.");
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.Iterator
|
||
|
|
public void remove() {
|
||
|
|
CollectPreconditions.checkRemove(this.canRemove);
|
||
|
|
checkModCount();
|
||
|
|
this.canRemove = false;
|
||
|
|
this.expectedModCount++;
|
||
|
|
if (this.cursor < this.this$0.size()) {
|
||
|
|
MoveDesc<E> removeAt = this.this$0.removeAt(this.cursor);
|
||
|
|
if (removeAt != null) {
|
||
|
|
if (this.forgetMeNot == null) {
|
||
|
|
this.forgetMeNot = new ArrayDeque();
|
||
|
|
this.skipMe = new ArrayList(3);
|
||
|
|
}
|
||
|
|
if (!foundAndRemovedExactReference(this.skipMe, removeAt.toTrickle)) {
|
||
|
|
this.forgetMeNot.add(removeAt.toTrickle);
|
||
|
|
}
|
||
|
|
if (!foundAndRemovedExactReference(this.forgetMeNot, removeAt.replaced)) {
|
||
|
|
this.skipMe.add(removeAt.replaced);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
this.cursor--;
|
||
|
|
this.nextCursor--;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
Preconditions.checkState(removeExact(this.lastFromForgetMeNot));
|
||
|
|
this.lastFromForgetMeNot = null;
|
||
|
|
}
|
||
|
|
|
||
|
|
private boolean foundAndRemovedExactReference(Iterable<E> iterable, E e) {
|
||
|
|
Iterator<E> it = iterable.iterator();
|
||
|
|
while (it.hasNext()) {
|
||
|
|
if (it.next() == e) {
|
||
|
|
it.remove();
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
private boolean removeExact(Object obj) {
|
||
|
|
for (int i = 0; i < this.this$0.size; i++) {
|
||
|
|
if (this.this$0.queue[i] == obj) {
|
||
|
|
this.this$0.removeAt(i);
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
private void checkModCount() {
|
||
|
|
if (this.this$0.modCount != this.expectedModCount) {
|
||
|
|
throw new ConcurrentModificationException();
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX WARN: Multi-variable type inference failed */
|
||
|
|
private void nextNotInSkipMe(int i) {
|
||
|
|
if (this.nextCursor < i) {
|
||
|
|
if (this.skipMe != null) {
|
||
|
|
while (i < this.this$0.size() && foundAndRemovedExactReference(this.skipMe, this.this$0.elementData(i))) {
|
||
|
|
i++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
this.nextCursor = i;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection, java.lang.Iterable
|
||
|
|
public final Iterator<E> iterator() {
|
||
|
|
return new QueueIterator();
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractQueue, java.util.AbstractCollection, java.util.Collection
|
||
|
|
public final void clear() {
|
||
|
|
for (int i = 0; i < this.size; i++) {
|
||
|
|
this.queue[i] = null;
|
||
|
|
}
|
||
|
|
this.size = 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection
|
||
|
|
public final Object[] toArray() {
|
||
|
|
int i = this.size;
|
||
|
|
Object[] objArr = new Object[i];
|
||
|
|
System.arraycopy(this.queue, 0, objArr, 0, i);
|
||
|
|
return objArr;
|
||
|
|
}
|
||
|
|
|
||
|
|
public final Comparator<? super E> comparator() {
|
||
|
|
return this.minHeap.ordering;
|
||
|
|
}
|
||
|
|
|
||
|
|
final int capacity() {
|
||
|
|
return this.queue.length;
|
||
|
|
}
|
||
|
|
|
||
|
|
static int initialQueueSize(int i, int i2, Iterable<?> iterable) {
|
||
|
|
if (i == -1) {
|
||
|
|
i = 11;
|
||
|
|
}
|
||
|
|
if (iterable instanceof Collection) {
|
||
|
|
i = Math.max(i, ((Collection) iterable).size());
|
||
|
|
}
|
||
|
|
return capAtMaximumSize(i, i2);
|
||
|
|
}
|
||
|
|
|
||
|
|
private void growIfNeeded() {
|
||
|
|
if (this.size > this.queue.length) {
|
||
|
|
Object[] objArr = new Object[calculateNewCapacity()];
|
||
|
|
Object[] objArr2 = this.queue;
|
||
|
|
System.arraycopy(objArr2, 0, objArr, 0, objArr2.length);
|
||
|
|
this.queue = objArr;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
private int calculateNewCapacity() {
|
||
|
|
int length = this.queue.length;
|
||
|
|
return capAtMaximumSize(length < 64 ? (length + 1) << 1 : IntMath.checkedMultiply(length / 2, 3), this.maximumSize);
|
||
|
|
}
|
||
|
|
|
||
|
|
private static int capAtMaximumSize(int i, int i2) {
|
||
|
|
return Math.min(i - 1, i2) + 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection
|
||
|
|
public final int size() {
|
||
|
|
return this.size;
|
||
|
|
}
|
||
|
|
}
|