/*
* Copyright (C) 2008 The Guava Authors
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.common.collect;
import static com.google.common.truth.Truth.assertThat;
import com.google.common.collect.testing.IteratorFeature;
import com.google.common.collect.testing.IteratorTester;
import com.google.common.testing.NullPointerTester;
import junit.framework.TestCase;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.SortedMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
* Unit test for {@link MinMaxPriorityQueue}.
*
* @author Alexei Stolboushkin
* @author Sverre Sundsdal
*/
public class MinMaxPriorityQueueTest extends TestCase {
private Ordering<Integer> SOME_COMPARATOR = Ordering.natural().reverse();
// Overkill alert! Test all combinations of 0-2 options during creation.
public void testCreation_simple() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.create();
assertEquals(11, queue.capacity());
checkUnbounded(queue);
checkNatural(queue);
}
public void testCreation_comparator() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.orderedBy(SOME_COMPARATOR)
.create();
assertEquals(11, queue.capacity());
checkUnbounded(queue);
assertSame(SOME_COMPARATOR, queue.comparator());
}
public void testCreation_expectedSize() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.expectedSize(8)
.create();
assertEquals(8, queue.capacity());
checkUnbounded(queue);
checkNatural(queue);
}
public void testCreation_expectedSize_comparator() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.orderedBy(SOME_COMPARATOR)
.expectedSize(8)
.create();
assertEquals(8, queue.capacity());
checkUnbounded(queue);
assertSame(SOME_COMPARATOR, queue.comparator());
}
public void testCreation_maximumSize() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.maximumSize(42)
.create();
assertEquals(11, queue.capacity());
assertEquals(42, queue.maximumSize);
checkNatural(queue);
}
public void testCreation_comparator_maximumSize() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.orderedBy(SOME_COMPARATOR)
.maximumSize(42)
.create();
assertEquals(11, queue.capacity());
assertEquals(42, queue.maximumSize);
assertSame(SOME_COMPARATOR, queue.comparator());
}
public void testCreation_expectedSize_maximumSize() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.expectedSize(8)
.maximumSize(42)
.create();
assertEquals(8, queue.capacity());
assertEquals(42, queue.maximumSize);
checkNatural(queue);
}
private static final List<Integer> NUMBERS =
ImmutableList.of(4, 8, 15, 16, 23, 42);
public void testCreation_withContents() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.create(NUMBERS);
assertEquals(6, queue.size());
assertEquals(11, queue.capacity());
checkUnbounded(queue);
checkNatural(queue);
}
public void testCreation_comparator_withContents() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.orderedBy(SOME_COMPARATOR)
.create(NUMBERS);
assertEquals(6, queue.size());
assertEquals(11, queue.capacity());
checkUnbounded(queue);
assertSame(SOME_COMPARATOR, queue.comparator());
}
public void testCreation_expectedSize_withContents() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.expectedSize(8)
.create(NUMBERS);
assertEquals(6, queue.size());
assertEquals(8, queue.capacity());
checkUnbounded(queue);
checkNatural(queue);
}
public void testCreation_maximumSize_withContents() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.maximumSize(42)
.create(NUMBERS);
assertEquals(6, queue.size());
assertEquals(11, queue.capacity());
assertEquals(42, queue.maximumSize);
checkNatural(queue);
}
// Now test everything at once
public void testCreation_allOptions() {
MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
.orderedBy(SOME_COMPARATOR)
.expectedSize(8)
.maximumSize(42)
.create(NUMBERS);
assertEquals(6, queue.size());
assertEquals(8, queue.capacity());
assertEquals(42, queue.maximumSize);
assertSame(SOME_COMPARATOR, queue.comparator());
}
// TODO: tests that check the weird interplay between expected size,
// maximum size, size of initial contents, default capacity...
private static void checkNatural(MinMaxPriorityQueue<Integer> queue) {
assertSame(Ordering.natural(), queue.comparator());
}
private static void checkUnbounded(MinMaxPriorityQueue<Integer> queue) {
assertEquals(Integer.MAX_VALUE, queue.maximumSize);
}
public void testHeapIntact() {
Random random = new Random(0);
int heapSize = 999;
int numberOfModifications = 500;
MinMaxPriorityQueue<Integer> mmHeap =
MinMaxPriorityQueue.expectedSize(heapSize).create();
/*
* this map would contain the same exact elements as the MinMaxHeap; the
* value in the map is the number of occurrences of the key.
*/
SortedMap<Integer, AtomicInteger> replica = Maps.newTreeMap();
assertTrue("Empty heap should be OK", mmHeap.isIntact());
for (int i = 0; i < heapSize; i++) {
int randomInt = random.nextInt();
mmHeap.offer(randomInt);
insertIntoReplica(replica, randomInt);
}
assertTrue("MinMaxHeap not intact after " + heapSize + " insertions",
mmHeap.isIntact());
assertEquals(heapSize, mmHeap.size());
int currentHeapSize = heapSize;
for (int i = 0; i < numberOfModifications; i++) {
if (random.nextBoolean()) {
/* insert a new element */
int randomInt = random.nextInt();
mmHeap.offer(randomInt);
insertIntoReplica(replica, randomInt);
currentHeapSize++;
} else {
/* remove either min or max */
if (random.nextBoolean()) {
removeMinFromReplica(replica, mmHeap.poll());
} else {
removeMaxFromReplica(replica, mmHeap.pollLast());
}
for (Integer v : replica.keySet()) {
assertTrue("MinMax queue has lost " + v, mmHeap.contains(v));
}
assertTrue(mmHeap.isIntact());
currentHeapSize--;
assertEquals(currentHeapSize, mmHeap.size());
}
}
assertEquals(currentHeapSize, mmHeap.size());
assertTrue("Heap not intact after " + numberOfModifications +
" random mixture of operations", mmHeap.isIntact());
}
public void testSmall() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.add(1);
mmHeap.add(4);
mmHeap.add(2);
mmHeap.add(3);
assertEquals(4, (int) mmHeap.pollLast());
assertEquals(3, (int) mmHeap.peekLast());
assertEquals(3, (int) mmHeap.pollLast());
assertEquals(1, (int) mmHeap.peek());
assertEquals(2, (int) mmHeap.peekLast());
assertEquals(2, (int) mmHeap.pollLast());
assertEquals(1, (int) mmHeap.peek());
assertEquals(1, (int) mmHeap.peekLast());
assertEquals(1, (int) mmHeap.pollLast());
assertNull(mmHeap.peek());
assertNull(mmHeap.peekLast());
assertNull(mmHeap.pollLast());
}
public void testSmallMinHeap() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.add(1);
mmHeap.add(3);
mmHeap.add(2);
assertEquals(1, (int) mmHeap.peek());
assertEquals(1, (int) mmHeap.poll());
assertEquals(3, (int) mmHeap.peekLast());
assertEquals(2, (int) mmHeap.peek());
assertEquals(2, (int) mmHeap.poll());
assertEquals(3, (int) mmHeap.peekLast());
assertEquals(3, (int) mmHeap.peek());
assertEquals(3, (int) mmHeap.poll());
assertNull(mmHeap.peekLast());
assertNull(mmHeap.peek());
assertNull(mmHeap.poll());
}
public void testRemove() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4, 47, 1, 5, 3, 0));
assertTrue("Heap is not intact initally", mmHeap.isIntact());
assertEquals(9, mmHeap.size());
mmHeap.remove(5);
assertEquals(8, mmHeap.size());
assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
assertEquals(47, (int) mmHeap.pollLast());
assertEquals(4, (int) mmHeap.pollLast());
mmHeap.removeAll(Lists.newArrayList(2, 3));
assertEquals(3, mmHeap.size());
assertTrue("Heap is not intact after removeAll()", mmHeap.isIntact());
}
public void testContains() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(1, 1, 2));
assertEquals(3, mmHeap.size());
assertFalse("Heap does not contain null", mmHeap.contains(null));
assertFalse("Heap does not contain 3", mmHeap.contains(3));
assertFalse("Heap does not contain 3", mmHeap.remove(3));
assertEquals(3, mmHeap.size());
assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
assertTrue("Heap contains two 1's", mmHeap.contains(1));
assertTrue("Heap contains two 1's", mmHeap.remove(1));
assertTrue("Heap contains 1", mmHeap.contains(1));
assertTrue("Heap contains 1", mmHeap.remove(1));
assertFalse("Heap does not contain 1", mmHeap.contains(1));
assertTrue("Heap contains 2", mmHeap.remove(2));
assertEquals(0, mmHeap.size());
assertFalse("Heap does not contain anything", mmHeap.contains(1));
assertFalse("Heap does not contain anything", mmHeap.remove(2));
}
public void testIteratorPastEndException() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(1, 2));
Iterator<Integer> it = mmHeap.iterator();
assertTrue("Iterator has reached end prematurely", it.hasNext());
it.next();
it.next();
try {
it.next();
fail("No exception thrown when iterating past end of heap");
} catch (NoSuchElementException e) {
// expected error
}
}
public void testIteratorConcurrentModification() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4));
Iterator<Integer> it = mmHeap.iterator();
assertTrue("Iterator has reached end prematurely", it.hasNext());
it.next();
it.next();
mmHeap.remove(4);
try {
it.next();
fail("No exception thrown when iterating a modified heap");
} catch (ConcurrentModificationException e) {
// expected error
}
}
/**
* Tests a failure caused by fix to childless uncle issue.
*/
public void testIteratorRegressionChildlessUncle() {
final ArrayList<Integer> initial = Lists.newArrayList(
1, 15, 13, 8, 9, 10, 11, 14);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(initial);
assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
q.remove(9);
q.remove(11);
q.remove(10);
// Now we're in the critical state: [1, 15, 13, 8, 14]
// Removing 8 while iterating caused duplicates in iteration result.
List<Integer> result = Lists.newArrayListWithCapacity(initial.size());
for (Iterator<Integer> iter = q.iterator(); iter.hasNext();) {
Integer value = iter.next();
result.add(value);
if (value == 8) {
iter.remove();
}
}
assertTrue(q.isIntact());
assertThat(result).containsExactly(1, 15, 13, 8, 14);
}
/**
* This tests a special case of the removeAt() call. Moving an element
* sideways on the heap could break the invariants. Sometimes we need to
* bubble an element up instead of trickling down. See implementation.
*/
public void testInvalidatingRemove() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(
1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600));
assertEquals(15, mmHeap.size());
assertTrue("Heap is not intact initially", mmHeap.isIntact());
mmHeap.remove(12);
assertEquals(14, mmHeap.size());
assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
}
/**
* This tests a more obscure special case, but otherwise similar to above.
*/
public void testInvalidatingRemove2() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
List<Integer> values = Lists.newArrayList(
1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600, 4, 5,
6, 7, 8, 9, 4, 5, 200, 250);
mmHeap.addAll(values);
assertEquals(25, mmHeap.size());
assertTrue("Heap is not intact initially", mmHeap.isIntact());
mmHeap.remove(2);
assertEquals(24, mmHeap.size());
assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
values.removeAll(Lists.newArrayList(2));
assertEquals(values.size(), mmHeap.size());
assertTrue(values.containsAll(mmHeap));
assertTrue(mmHeap.containsAll(values));
}
public void testIteratorInvalidatingIteratorRemove() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(
1, 20, 100, 2, 3, 30, 40));
assertEquals(7, mmHeap.size());
assertTrue("Heap is not intact initially", mmHeap.isIntact());
Iterator<Integer> it = mmHeap.iterator();
assertEquals((Integer) 1, it.next());
assertEquals((Integer) 20, it.next());
assertEquals((Integer) 100, it.next());
assertEquals((Integer) 2, it.next());
it.remove();
assertFalse(mmHeap.contains(2));
assertTrue(it.hasNext());
assertEquals((Integer) 3, it.next());
assertTrue(it.hasNext());
assertEquals((Integer) 30, it.next());
assertTrue(it.hasNext());
assertEquals((Integer) 40, it.next());
assertFalse(it.hasNext());
assertEquals(6, mmHeap.size());
assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
assertFalse(mmHeap.contains(2));
// This tests that it.remove() above actually changed the order. It
// indicates that the value 40 was stored in forgetMeNot, so it is
// returned in the last call to it.next(). Without it, 30 should be the last
// item returned by the iterator.
Integer lastItem = 0;
for (Integer tmp : mmHeap) {
lastItem = tmp;
}
assertEquals((Integer) 30, lastItem);
}
/**
* This tests a special case where removeAt has to trickle an element
* first down one level from a min to a max level, then up one level above
* the index of the removed element.
* It also tests that skipMe in the iterator plays nicely with
* forgetMeNot.
*/
public void testIteratorInvalidatingIteratorRemove2() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
mmHeap.addAll(Lists.newArrayList(
1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 200, 300, 500, 400));
assertTrue("Heap is not intact initially", mmHeap.isIntact());
Iterator<Integer> it = mmHeap.iterator();
assertEquals((Integer) 1, it.next());
assertEquals((Integer) 20, it.next());
assertEquals((Integer) 1000, it.next());
assertEquals((Integer) 2, it.next());
it.remove();
assertTrue("Heap is not intact after remove", mmHeap.isIntact());
assertEquals((Integer) 10, it.next());
assertEquals((Integer) 3, it.next());
it.remove();
assertTrue("Heap is not intact after remove", mmHeap.isIntact());
assertEquals((Integer) 12, it.next());
assertEquals((Integer) 30, it.next());
assertEquals((Integer) 40, it.next());
// Skipping 20
assertEquals((Integer) 11, it.next());
// Skipping 400
assertEquals((Integer) 13, it.next());
assertEquals((Integer) 200, it.next());
assertEquals((Integer) 300, it.next());
// Last two from forgetMeNot.
assertEquals((Integer) 400, it.next());
assertEquals((Integer) 500, it.next());
}
public void testRemoveFromStringHeap() {
MinMaxPriorityQueue<String> mmHeap =
MinMaxPriorityQueue.expectedSize(5).create();
Collections.addAll(mmHeap,
"foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric");
assertTrue("Heap is not intact initially", mmHeap.isIntact());
assertEquals("bar", mmHeap.peek());
assertEquals("sergey", mmHeap.peekLast());
assertEquals(7, mmHeap.size());
assertTrue("Could not remove larry", mmHeap.remove("larry"));
assertEquals(6, mmHeap.size());
assertFalse("heap contains larry which has been removed",
mmHeap.contains("larry"));
assertTrue("heap does not contain sergey",
mmHeap.contains("sergey"));
assertTrue("Could not remove larry", mmHeap.removeAll(
Lists.newArrayList("sergey", "eric")));
assertFalse("Could remove nikesh which is not in the heap",
mmHeap.remove("nikesh"));
assertEquals(4, mmHeap.size());
}
public void testCreateWithOrdering() {
MinMaxPriorityQueue<String> mmHeap =
MinMaxPriorityQueue.orderedBy(Ordering.natural().reverse()).create();
Collections.addAll(mmHeap,
"foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric");
assertTrue("Heap is not intact initially", mmHeap.isIntact());
assertEquals("sergey", mmHeap.peek());
assertEquals("bar", mmHeap.peekLast());
}
public void testCreateWithCapacityAndOrdering() {
MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.orderedBy(
Ordering.natural().reverse()).expectedSize(5).create();
Collections.addAll(mmHeap, 1, 7, 2, 56, 2, 5, 23, 68, 0, 3);
assertTrue("Heap is not intact initially", mmHeap.isIntact());
assertEquals(68, (int) mmHeap.peek());
assertEquals(0, (int) mmHeap.peekLast());
}
private <T extends Comparable<T>> void runIterator(
final List<T> values, int steps) throws Exception {
IteratorTester<T> tester =
new IteratorTester<T>(
steps,
IteratorFeature.MODIFIABLE,
Lists.newLinkedList(values),
IteratorTester.KnownOrder.UNKNOWN_ORDER) {
private MinMaxPriorityQueue<T> mmHeap;
@Override protected Iterator<T> newTargetIterator() {
mmHeap = MinMaxPriorityQueue.create(values);
return mmHeap.iterator();
}
@Override protected void verify(List<T> elements) {
assertEquals(Sets.newHashSet(elements),
Sets.newHashSet(mmHeap.iterator()));
assertTrue("Invalid MinMaxHeap: " + mmHeap, mmHeap.isIntact());
}
};
tester.test();
}
public void testIteratorTester() throws Exception {
Random random = new Random(0);
List<Integer> list = Lists.newArrayList();
for (int i = 0; i < 3; i++) {
list.add(random.nextInt());
}
runIterator(list, 6);
}
public void testIteratorTesterLarger() throws Exception {
runIterator(Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 5);
}
public void testRemoveAt() {
long seed = new Random().nextLong();
Random random = new Random(seed);
int heapSize = 999;
int numberOfModifications = 500;
MinMaxPriorityQueue<Integer> mmHeap =
MinMaxPriorityQueue.expectedSize(heapSize).create();
for (int i = 0; i < heapSize; i++) {
mmHeap.add(random.nextInt());
}
for (int i = 0; i < numberOfModifications; i++) {
mmHeap.removeAt(random.nextInt(mmHeap.size()));
assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact());
mmHeap.add(random.nextInt());
assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact());
}
}
public void testRemoveAt_exhaustive() {
int size = 8;
List<Integer> expected = createOrderedList(size);
for (Collection<Integer> perm : Collections2.permutations(expected)) {
for (int i = 0; i < perm.size(); i++) {
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm);
q.removeAt(i);
assertTrue("Remove at " + i + " perm " + perm, q.isIntact());
}
}
}
/**
* Regression test for bug found.
*/
public void testCorrectOrdering_regression() {
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue
.create(ImmutableList.of(3, 5, 1, 4, 7));
List<Integer> expected = ImmutableList.of(1, 3, 4, 5, 7);
List<Integer> actual = new ArrayList<Integer>(5);
for (int i = 0; i < expected.size(); i++) {
actual.add(q.pollFirst());
}
assertEquals(expected, actual);
}
public void testCorrectOrdering_smallHeapsPollFirst() {
for (int size = 2; size < 16; size++) {
for (int attempts = 0; attempts < size * (size - 1); attempts++) {
ArrayList<Integer> elements = createOrderedList(size);
List<Integer> expected = ImmutableList.copyOf(elements);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
long seed = insertRandomly(elements, q);
while (!q.isEmpty()) {
elements.add(q.pollFirst());
}
assertEquals("Using seed " + seed, expected, elements);
}
}
}
public void testCorrectOrdering_smallHeapsPollLast() {
for (int size = 2; size < 16; size++) {
for (int attempts = 0; attempts < size * (size - 1); attempts++) {
ArrayList<Integer> elements = createOrderedList(size);
List<Integer> expected = ImmutableList.copyOf(elements);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
long seed = insertRandomly(elements, q);
while (!q.isEmpty()) {
elements.add(0, q.pollLast());
}
assertEquals("Using seed " + seed, expected, elements);
}
}
}
public void testCorrectOrdering_mediumHeapsPollFirst() {
for (int attempts = 0; attempts < 5000; attempts++) {
int size = new Random().nextInt(256) + 16;
ArrayList<Integer> elements = createOrderedList(size);
List<Integer> expected = ImmutableList.copyOf(elements);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
long seed = insertRandomly(elements, q);
while (!q.isEmpty()) {
elements.add(q.pollFirst());
}
assertEquals("Using seed " + seed, expected, elements);
}
}
/**
* Regression test for bug found in random testing.
*/
public void testCorrectOrdering_73ElementBug() {
int size = 73;
long seed = 7522346378524621981L;
ArrayList<Integer> elements = createOrderedList(size);
List<Integer> expected = ImmutableList.copyOf(elements);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
insertRandomly(elements, q, new Random(seed));
assertTrue(q.isIntact());
while (!q.isEmpty()) {
elements.add(q.pollFirst());
assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
}
assertEquals("Using seed " + seed, expected, elements);
}
public void testCorrectOrdering_mediumHeapsPollLast() {
for (int attempts = 0; attempts < 5000; attempts++) {
int size = new Random().nextInt(256) + 16;
ArrayList<Integer> elements = createOrderedList(size);
List<Integer> expected = ImmutableList.copyOf(elements);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
long seed = insertRandomly(elements, q);
while (!q.isEmpty()) {
elements.add(0, q.pollLast());
}
assertEquals("Using seed " + seed, expected, elements);
}
}
public void testCorrectOrdering_randomAccess() {
long seed = new Random().nextLong();
Random random = new Random(seed);
PriorityQueue<Integer> control = new PriorityQueue<Integer>();
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
for (int i = 0; i < 73; i++) { // 73 is a childless uncle case.
Integer element = random.nextInt();
control.add(element);
assertTrue(q.add(element));
}
assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
for (int i = 0; i < 500000; i++) {
if (random.nextBoolean()) {
Integer element = random.nextInt();
control.add(element);
q.add(element);
} else {
assertEquals("Using seed " + seed, control.poll(), q.pollFirst());
}
}
while (!control.isEmpty()) {
assertEquals("Using seed " + seed, control.poll(), q.pollFirst());
}
assertTrue(q.isEmpty());
}
public void testExhaustive_pollAndPush() {
int size = 8;
List<Integer> expected = createOrderedList(size);
for (Collection<Integer> perm : Collections2.permutations(expected)) {
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm);
List<Integer> elements = Lists.newArrayListWithCapacity(size);
while (!q.isEmpty()) {
Integer next = q.pollFirst();
for (int i = 0; i <= size; i++) {
assertTrue(q.add(i));
assertTrue(q.add(next));
assertTrue(q.remove(i));
assertEquals(next, q.poll());
}
elements.add(next);
}
assertEquals("Started with " + perm, expected, elements);
}
}
/**
* Regression test for b/4124577
*/
public void testRegression_dataCorruption() {
int size = 8;
List<Integer> expected = createOrderedList(size);
MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(expected);
List<Integer> contents = Lists.newArrayList(expected);
List<Integer> elements = Lists.newArrayListWithCapacity(size);
while (!q.isEmpty()) {
assertThat(q).containsExactlyElementsIn(contents);
Integer next = q.pollFirst();
contents.remove(next);
assertThat(q).containsExactlyElementsIn(contents);
for (int i = 0; i <= size; i++) {
q.add(i);
contents.add(i);
assertThat(q).containsExactlyElementsIn(contents);
q.add(next);
contents.add(next);
assertThat(q).containsExactlyElementsIn(contents);
q.remove(i);
assertTrue(contents.remove(Integer.valueOf(i)));
assertThat(q).containsExactlyElementsIn(contents);
assertEquals(next, q.poll());
contents.remove(next);
assertThat(q).containsExactlyElementsIn(contents);
}
elements.add(next);
}
assertEquals(expected, elements);
}
/**
* Returns the seed used for the randomization.
*/
private long insertRandomly(ArrayList<Integer> elements,
MinMaxPriorityQueue<Integer> q) {
long seed = new Random().nextLong();
Random random = new Random(seed);
insertRandomly(elements, q, random);
return seed;
}
private void insertRandomly(ArrayList<Integer> elements, MinMaxPriorityQueue<Integer> q,
Random random) {
while (!elements.isEmpty()) {
int selectedIndex = random.nextInt(elements.size());
q.offer(elements.remove(selectedIndex));
}
}
private ArrayList<Integer> createOrderedList(int size) {
ArrayList<Integer> elements = new ArrayList<Integer>(size);
for (int i = 0; i < size; i++) {
elements.add(i);
}
return elements;
}
public void testIsEvenLevel() {
assertTrue(MinMaxPriorityQueue.isEvenLevel(0));
assertFalse(MinMaxPriorityQueue.isEvenLevel(1));
assertFalse(MinMaxPriorityQueue.isEvenLevel(2));
assertTrue(MinMaxPriorityQueue.isEvenLevel(3));
assertFalse(MinMaxPriorityQueue.isEvenLevel((1 << 10) - 2));
assertTrue(MinMaxPriorityQueue.isEvenLevel((1 << 10) - 1));
int i = 1 << 29;
assertTrue(MinMaxPriorityQueue.isEvenLevel(i - 2));
assertFalse(MinMaxPriorityQueue.isEvenLevel(i - 1));
assertFalse(MinMaxPriorityQueue.isEvenLevel(i));
i = 1 << 30;
assertFalse(MinMaxPriorityQueue.isEvenLevel(i - 2));
assertTrue(MinMaxPriorityQueue.isEvenLevel(i - 1));
assertTrue(MinMaxPriorityQueue.isEvenLevel(i));
// 1 << 31 is negative because of overflow, 1 << 31 - 1 is positive
// since isEvenLevel adds 1, we need to do - 2.
assertTrue(MinMaxPriorityQueue.isEvenLevel((1 << 31) - 2));
assertTrue(MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE - 1));
try {
MinMaxPriorityQueue.isEvenLevel((1 << 31) - 1);
fail("Should overflow");
} catch (IllegalStateException e) {
// expected
}
try {
MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE);
fail("Should overflow");
} catch (IllegalStateException e) {
// expected
}
try {
MinMaxPriorityQueue.isEvenLevel(1 << 31);
fail("Should be negative");
} catch (IllegalStateException e) {
// expected
}
try {
MinMaxPriorityQueue.isEvenLevel(Integer.MIN_VALUE);
fail("Should be negative");
} catch (IllegalStateException e) {
// expected
}
}
public void testNullPointers() {
NullPointerTester tester = new NullPointerTester();
tester.testAllPublicConstructors(MinMaxPriorityQueue.class);
tester.testAllPublicStaticMethods(MinMaxPriorityQueue.class);
tester.testAllPublicInstanceMethods(MinMaxPriorityQueue.<String>create());
}
private static void insertIntoReplica(
Map<Integer, AtomicInteger> replica,
int newValue) {
if (replica.containsKey(newValue)) {
replica.get(newValue).incrementAndGet();
} else {
replica.put(newValue, new AtomicInteger(1));
}
}
private static void removeMinFromReplica(
SortedMap<Integer, AtomicInteger> replica,
int minValue) {
Integer replicatedMinValue = replica.firstKey();
assertEquals(replicatedMinValue, (Integer) minValue);
removeFromReplica(replica, replicatedMinValue);
}
private static void removeMaxFromReplica(
SortedMap<Integer, AtomicInteger> replica,
int maxValue) {
Integer replicatedMaxValue = replica.lastKey();
assertTrue("maxValue is incorrect", replicatedMaxValue == maxValue);
removeFromReplica(replica, replicatedMaxValue);
}
private static void removeFromReplica(
Map<Integer, AtomicInteger> replica, int value) {
AtomicInteger numOccur = replica.get(value);
if (numOccur.decrementAndGet() == 0) {
replica.remove(value);
}
}
}