/* * 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 org.junit.contrib.truth.Truth.ASSERT; 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.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()); ASSERT.that(result).hasContentsAnyOrder(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.toString(), mmHeap.isIntact()); } }; tester.ignoreSunJavaBug6529795(); 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()); } } /** * 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()); } /** * 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()) { ASSERT.that(q).hasContentsAnyOrder(contents.toArray(new Integer[0])); Integer next = q.pollFirst(); contents.remove(next); ASSERT.that(q).hasContentsAnyOrder(contents.toArray(new Integer[0])); for (int i = 0; i <= size; i++) { q.add(i); contents.add(i); ASSERT.that(q).hasContentsAnyOrder(contents.toArray(new Integer[0])); q.add(next); contents.add(next); ASSERT.that(q).hasContentsAnyOrder(contents.toArray(new Integer[0])); q.remove(i); assertTrue(contents.remove(Integer.valueOf(i))); ASSERT.that(q).hasContentsAnyOrder(contents.toArray(new Integer[0])); assertEquals(next, q.poll()); contents.remove(next); ASSERT.that(q).hasContentsAnyOrder(contents.toArray(new Integer[0])); } 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() throws Exception { 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); } } }