CrackMe.apk
Download file
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.Objects;
import java.util.Queue;
import javax.annotation.CheckForNull;
@ElementTypesAreNonnullByDefault
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;
/* access modifiers changed from: private */
public int modCount;
/* access modifiers changed from: private */
public Object[] queue;
/* access modifiers changed from: private */
public 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);
}
public static final class Builder<B> {
private static final int UNSET_EXPECTED_SIZE = -1;
private final Comparator<B> comparator;
private int expectedSize;
/* access modifiers changed from: private */
public int maximumSize;
private Builder(Comparator<B> comparator2) {
this.expectedSize = -1;
this.maximumSize = Integer.MAX_VALUE;
this.comparator = (Comparator) Preconditions.checkNotNull(comparator2);
}
public Builder<B> expectedSize(int i) {
Preconditions.checkArgument(i >= 0);
this.expectedSize = i;
return this;
}
public Builder<B> maximumSize(int i) {
Preconditions.checkArgument(i > 0);
this.maximumSize = i;
return this;
}
public <T extends B> MinMaxPriorityQueue<T> create() {
return create(Collections.emptySet());
}
public <T extends B> MinMaxPriorityQueue<T> create(Iterable<? extends T> iterable) {
MinMaxPriorityQueue<T> minMaxPriorityQueue = new MinMaxPriorityQueue<>(this, MinMaxPriorityQueue.initialQueueSize(this.expectedSize, this.maximumSize, iterable));
for (Object offer : iterable) {
minMaxPriorityQueue.offer(offer);
}
return minMaxPriorityQueue;
}
/* 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 access$200 = builder.ordering();
MinMaxPriorityQueue<E>.Heap heap = new Heap(access$200);
this.minHeap = heap;
MinMaxPriorityQueue<E>.Heap heap2 = new Heap(access$200.reverse());
this.maxHeap = heap2;
heap.otherHeap = heap2;
heap2.otherHeap = heap;
this.maximumSize = builder.maximumSize;
this.queue = new Object[i];
}
public int size() {
return this.size;
}
public boolean add(E e) {
offer(e);
return true;
}
public boolean addAll(Collection<? extends E> collection) {
boolean z = false;
for (Object offer : collection) {
offer(offer);
z = true;
}
return z;
}
public boolean offer(E e) {
Preconditions.checkNotNull(e);
this.modCount++;
int i = this.size;
this.size = i + 1;
growIfNeeded();
heapForIndex(i).bubbleUp(i, e);
if (this.size <= this.maximumSize || pollLast() != e) {
return true;
}
return false;
}
@CheckForNull
public E poll() {
if (isEmpty()) {
return null;
}
return removeAndGet(0);
}
/* access modifiers changed from: package-private */
public E elementData(int i) {
E e = this.queue[i];
Objects.requireNonNull(e);
return e;
}
@CheckForNull
public E peek() {
if (isEmpty()) {
return null;
}
return elementData(0);
}
private int getMaxElementIndex() {
int i = this.size;
if (i == 1) {
return 0;
}
if (i == 2 || this.maxHeap.compareElements(1, 2) <= 0) {
return 1;
}
return 2;
}
@CheckForNull
public E pollFirst() {
return poll();
}
public E removeFirst() {
return remove();
}
@CheckForNull
public E peekFirst() {
return peek();
}
@CheckForNull
public E pollLast() {
if (isEmpty()) {
return null;
}
return removeAndGet(getMaxElementIndex());
}
public E removeLast() {
if (!isEmpty()) {
return removeAndGet(getMaxElementIndex());
}
throw new NoSuchElementException();
}
@CheckForNull
public E peekLast() {
if (isEmpty()) {
return null;
}
return elementData(getMaxElementIndex());
}
/* access modifiers changed from: package-private */
@CheckForNull
public 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;
}
Object elementData = elementData(i2);
int swapWithConceptuallyLastElement = heapForIndex(this.size).swapWithConceptuallyLastElement(elementData);
if (swapWithConceptuallyLastElement == i) {
this.queue[this.size] = null;
return null;
}
Object 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);
}
@CheckForNull
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;
}
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);
}
/* access modifiers changed from: package-private */
public boolean isIntact() {
for (int i = 1; i < this.size; i++) {
if (!heapForIndex(i).verifyIndex(i)) {
return false;
}
}
return true;
}
private class Heap {
final Ordering<E> ordering;
MinMaxPriorityQueue<E>.Heap otherHeap;
private int getLeftChildIndex(int i) {
return (i * 2) + 1;
}
private int getRightChildIndex(int i) {
return (i * 2) + 2;
}
Heap(Ordering<E> ordering2) {
this.ordering = ordering2;
}
/* access modifiers changed from: package-private */
public int compareElements(int i, int i2) {
return this.ordering.compare(MinMaxPriorityQueue.this.elementData(i), MinMaxPriorityQueue.this.elementData(i2));
}
/* access modifiers changed from: package-private */
@CheckForNull
public MoveDesc<E> tryCrossOverAndBubbleUp(int i, int i2, E e) {
Object obj;
int crossOver = crossOver(i2, e);
if (crossOver == i2) {
return null;
}
if (crossOver < i) {
obj = MinMaxPriorityQueue.this.elementData(i);
} else {
obj = MinMaxPriorityQueue.this.elementData(getParentIndex(i));
}
if (this.otherHeap.bubbleUpAlternatingLevels(crossOver, e) < i) {
return new MoveDesc<>(e, obj);
}
return null;
}
/* access modifiers changed from: package-private */
public 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);
}
/* access modifiers changed from: package-private */
public int bubbleUpAlternatingLevels(int i, E e) {
while (i > 2) {
int grandparentIndex = getGrandparentIndex(i);
Object elementData = MinMaxPriorityQueue.this.elementData(grandparentIndex);
if (this.ordering.compare(elementData, e) <= 0) {
break;
}
MinMaxPriorityQueue.this.queue[i] = elementData;
i = grandparentIndex;
}
MinMaxPriorityQueue.this.queue[i] = e;
return i;
}
/* access modifiers changed from: package-private */
public int findMin(int i, int i2) {
if (i >= MinMaxPriorityQueue.this.size) {
return -1;
}
Preconditions.checkState(i > 0);
int min = Math.min(i, MinMaxPriorityQueue.this.size - i2) + i2;
for (int i3 = i + 1; i3 < min; i3++) {
if (compareElements(i3, i) < 0) {
i = i3;
}
}
return i;
}
/* access modifiers changed from: package-private */
public int findMinChild(int i) {
return findMin(getLeftChildIndex(i), 2);
}
/* access modifiers changed from: package-private */
public int findMinGrandChild(int i) {
int leftChildIndex = getLeftChildIndex(i);
if (leftChildIndex < 0) {
return -1;
}
return findMin(getLeftChildIndex(leftChildIndex), 4);
}
/* access modifiers changed from: package-private */
public int crossOverUp(int i, E e) {
int rightChildIndex;
if (i == 0) {
MinMaxPriorityQueue.this.queue[0] = e;
return 0;
}
int parentIndex = getParentIndex(i);
Object elementData = MinMaxPriorityQueue.this.elementData(parentIndex);
if (!(parentIndex == 0 || (rightChildIndex = getRightChildIndex(getParentIndex(parentIndex))) == parentIndex || getLeftChildIndex(rightChildIndex) < MinMaxPriorityQueue.this.size)) {
Object elementData2 = MinMaxPriorityQueue.this.elementData(rightChildIndex);
if (this.ordering.compare(elementData2, elementData) < 0) {
parentIndex = rightChildIndex;
elementData = elementData2;
}
}
if (this.ordering.compare(elementData, e) < 0) {
MinMaxPriorityQueue.this.queue[i] = elementData;
MinMaxPriorityQueue.this.queue[parentIndex] = e;
return parentIndex;
}
MinMaxPriorityQueue.this.queue[i] = e;
return i;
}
/* access modifiers changed from: package-private */
public int swapWithConceptuallyLastElement(E e) {
int rightChildIndex;
int parentIndex = getParentIndex(MinMaxPriorityQueue.this.size);
if (!(parentIndex == 0 || (rightChildIndex = getRightChildIndex(getParentIndex(parentIndex))) == parentIndex || getLeftChildIndex(rightChildIndex) < MinMaxPriorityQueue.this.size)) {
Object elementData = MinMaxPriorityQueue.this.elementData(rightChildIndex);
if (this.ordering.compare(elementData, e) < 0) {
MinMaxPriorityQueue.this.queue[rightChildIndex] = e;
MinMaxPriorityQueue.this.queue[MinMaxPriorityQueue.this.size] = elementData;
return rightChildIndex;
}
}
return MinMaxPriorityQueue.this.size;
}
/* access modifiers changed from: package-private */
public int crossOver(int i, E e) {
int findMinChild = findMinChild(i);
if (findMinChild <= 0 || this.ordering.compare(MinMaxPriorityQueue.this.elementData(findMinChild), e) >= 0) {
return crossOverUp(i, e);
}
MinMaxPriorityQueue.this.queue[i] = MinMaxPriorityQueue.this.elementData(findMinChild);
MinMaxPriorityQueue.this.queue[findMinChild] = e;
return findMinChild;
}
/* access modifiers changed from: package-private */
public int fillHoleAt(int i) {
while (true) {
int findMinGrandChild = findMinGrandChild(i);
if (findMinGrandChild <= 0) {
return i;
}
MinMaxPriorityQueue.this.queue[i] = MinMaxPriorityQueue.this.elementData(findMinGrandChild);
i = findMinGrandChild;
}
}
/* access modifiers changed from: private */
public boolean verifyIndex(int i) {
if (getLeftChildIndex(i) < MinMaxPriorityQueue.this.size && compareElements(i, getLeftChildIndex(i)) > 0) {
return false;
}
if (getRightChildIndex(i) < MinMaxPriorityQueue.this.size && compareElements(i, getRightChildIndex(i)) > 0) {
return false;
}
if (i > 0 && compareElements(i, getParentIndex(i)) > 0) {
return false;
}
if (i <= 2 || compareElements(getGrandparentIndex(i), i) <= 0) {
return true;
}
return false;
}
private int getParentIndex(int i) {
return (i - 1) / 2;
}
private int getGrandparentIndex(int i) {
return getParentIndex(getParentIndex(i));
}
}
private class QueueIterator implements Iterator<E> {
private boolean canRemove;
private int cursor;
private int expectedModCount;
@CheckForNull
private Queue<E> forgetMeNot;
@CheckForNull
private E lastFromForgetMeNot;
private int nextCursor;
@CheckForNull
private List<E> skipMe;
private QueueIterator() {
this.cursor = -1;
this.nextCursor = -1;
this.expectedModCount = MinMaxPriorityQueue.this.modCount;
}
public boolean hasNext() {
checkModCount();
nextNotInSkipMe(this.cursor + 1);
if (this.nextCursor < MinMaxPriorityQueue.this.size()) {
return true;
}
Queue<E> queue = this.forgetMeNot;
if (queue == null || queue.isEmpty()) {
return false;
}
return true;
}
public E next() {
checkModCount();
nextNotInSkipMe(this.cursor + 1);
if (this.nextCursor < MinMaxPriorityQueue.this.size()) {
int i = this.nextCursor;
this.cursor = i;
this.canRemove = true;
return MinMaxPriorityQueue.this.elementData(i);
}
if (this.forgetMeNot != null) {
this.cursor = MinMaxPriorityQueue.this.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.");
}
public void remove() {
CollectPreconditions.checkRemove(this.canRemove);
checkModCount();
this.canRemove = false;
this.expectedModCount++;
if (this.cursor < MinMaxPriorityQueue.this.size()) {
MoveDesc removeAt = MinMaxPriorityQueue.this.removeAt(this.cursor);
if (removeAt != null) {
if (this.forgetMeNot == null || this.skipMe == 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;
}
E e = this.lastFromForgetMeNot;
Objects.requireNonNull(e);
Preconditions.checkState(removeExact(e));
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 < MinMaxPriorityQueue.this.size; i++) {
if (MinMaxPriorityQueue.this.queue[i] == obj) {
MinMaxPriorityQueue.this.removeAt(i);
return true;
}
}
return false;
}
private void checkModCount() {
if (MinMaxPriorityQueue.this.modCount != this.expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void nextNotInSkipMe(int i) {
if (this.nextCursor < i) {
if (this.skipMe != null) {
while (i < MinMaxPriorityQueue.this.size() && foundAndRemovedExactReference(this.skipMe, MinMaxPriorityQueue.this.elementData(i))) {
i++;
}
}
this.nextCursor = i;
}
}
}
public Iterator<E> iterator() {
return new QueueIterator();
}
public void clear() {
for (int i = 0; i < this.size; i++) {
this.queue[i] = null;
}
this.size = 0;
}
public Object[] toArray() {
int i = this.size;
Object[] objArr = new Object[i];
System.arraycopy(this.queue, 0, objArr, 0, i);
return objArr;
}
public Comparator<? super E> comparator() {
return this.minHeap.ordering;
}
/* access modifiers changed from: package-private */
public 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 i;
int length = this.queue.length;
if (length < 64) {
i = (length + 1) * 2;
} else {
i = IntMath.checkedMultiply(length / 2, 3);
}
return capAtMaximumSize(i, this.maximumSize);
}
private static int capAtMaximumSize(int i, int i2) {
return Math.min(i - 1, i2) + 1;
}
}
Download file