common/collect/MinMaxPriorityQueueTest.java

/*
 * 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.base.Objects.equal;
import static com.google.common.collect.Platform.reduceExponentIfGwt;
import static com.google.common.collect.Platform.reduceIterationsIfGwt;
import static com.google.common.truth.Truth.assertThat;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.collect.testing.IteratorFeature;
import com.google.common.collect.testing.IteratorTester;
import com.google.common.collect.testing.QueueTestSuiteBuilder;
import com.google.common.collect.testing.TestStringQueueGenerator;
import com.google.common.collect.testing.features.CollectionFeature;
import com.google.common.collect.testing.features.CollectionSize;
import com.google.common.testing.NullPointerTester;
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.Queue;
import java.util.Random;
import java.util.SortedMap;
import java.util.concurrent.atomic.AtomicInteger;
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

/**
 * Unit test for {@link MinMaxPriorityQueue}.
 *
 * @author Alexei Stolboushkin
 * @author Sverre Sundsdal
 */
@GwtCompatible(emulated = true)
public class MinMaxPriorityQueueTest extends TestCase {
  private static final Ordering<Integer> SOME_COMPARATOR = Ordering.natural().reverse();

  @GwtIncompatible // suite
  public static Test suite() {
    TestSuite suite = new TestSuite();
    suite.addTestSuite(MinMaxPriorityQueueTest.class);
    suite.addTest(
        QueueTestSuiteBuilder.using(
                new TestStringQueueGenerator() {
                  @Override
                  protected Queue<String> create(String[] elements) {
                    return MinMaxPriorityQueue.create(Arrays.asList(elements));
                  }
                })
            .named("MinMaxPriorityQueue")
            .withFeatures(CollectionSize.ANY, CollectionFeature.GENERAL_PURPOSE)
            .createTestSuite());
    return suite;
  }

  // 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 ImmutableList<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 = 99;
    int numberOfModifications = 100;
    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);
    }
    assertIntact(mmHeap);
    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()) {
          assertThat(mmHeap).contains(v);
        }
        assertIntact(mmHeap);
        currentHeapSize--;
        assertEquals(currentHeapSize, mmHeap.size());
      }
    }
    assertEquals(currentHeapSize, mmHeap.size());
    assertIntact(mmHeap);
  }

  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 expected) {
    }
  }

  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 expected) {
    }
  }

  /** 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);
    assertIntact(q);
    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();
      }
    }
    assertIntact(q);
    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();
    // After this remove, 400 has moved up and 20 down past cursor
    assertTrue("Heap is not intact after remove", mmHeap.isIntact());
    assertEquals((Integer) 10, it.next());
    assertEquals((Integer) 3, it.next());
    it.remove();
    // After this remove, 400 moved down again and 500 up past the cursor
    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());
    // Not skipping 400, because it moved back down
    assertEquals((Integer) 400, it.next());
    assertEquals((Integer) 13, it.next());
    assertEquals((Integer) 200, it.next());
    assertEquals((Integer) 300, it.next());
    // Last from forgetMeNot.
    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()));
            assertIntact(mmHeap);
          }
        };
    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 = reduceIterationsIfGwt(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()));
      assertIntactUsingSeed(seed, mmHeap);
      mmHeap.add(random.nextInt());
      assertIntactUsingSeed(seed, mmHeap);
    }
  }

  public void testRemoveAt_exhaustive() {
    int size = reduceExponentIfGwt(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);
        assertIntactUsingStartedWith(perm, q);
      }
    }
  }

  /** 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<>(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());
        }
        assertEqualsUsingSeed(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());
        }
        assertEqualsUsingSeed(seed, expected, elements);
      }
    }
  }

  public void testCorrectOrdering_mediumHeapsPollFirst() {
    for (int attempts = 0; attempts < reduceIterationsIfGwt(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());
      }
      assertEqualsUsingSeed(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));
    assertIntact(q);
    while (!q.isEmpty()) {
      elements.add(q.pollFirst());
      assertIntact(q);
    }
    assertEqualsUsingSeed(seed, expected, elements);
  }

  public void testCorrectOrdering_mediumHeapsPollLast() {
    for (int attempts = 0; attempts < reduceIterationsIfGwt(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());
      }
      assertEqualsUsingSeed(seed, expected, elements);
    }
  }

  public void testCorrectOrdering_randomAccess() {
    long seed = new Random().nextLong();
    Random random = new Random(seed);
    PriorityQueue<Integer> control = new PriorityQueue<>();
    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));
    }
    assertIntact(q);
    for (int i = 0; i < reduceIterationsIfGwt(500_000); i++) {
      if (random.nextBoolean()) {
        Integer element = random.nextInt();
        control.add(element);
        q.add(element);
      } else {
        assertEqualsUsingSeed(seed, control.poll(), q.pollFirst());
      }
    }
    while (!control.isEmpty()) {
      assertEqualsUsingSeed(seed, control.poll(), q.pollFirst());
    }
    assertTrue(q.isEmpty());
  }

  public void testExhaustive_pollAndPush() {
    int size = 5;
    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);
      }
      assertEqualsUsingStartedWith(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);
  }

  /** Regression test for https://github.com/google/guava/issues/2658 */
  public void testRemoveRegression() {
    MinMaxPriorityQueue<Long> queue =
        MinMaxPriorityQueue.create(ImmutableList.of(2L, 3L, 0L, 4L, 1L));
    queue.remove(4L);
    queue.remove(1L);
    assertThat(queue).doesNotContain(1L);
  }

  public void testRandomRemoves() {
    Random random = new Random(0);
    for (int attempts = 0; attempts < reduceIterationsIfGwt(1000); attempts++) {
      ArrayList<Integer> elements = createOrderedList(10);
      Collections.shuffle(elements, random);
      MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue.create(elements);
      Collections.shuffle(elements, random);
      for (Integer element : elements) {
        assertThat(queue.remove(element)).isTrue();
        assertIntact(queue);
        assertThat(queue).doesNotContain(element);
      }
      assertThat(queue).isEmpty();
    }
  }

  public void testRandomAddsAndRemoves() {
    Random random = new Random(0);
    Multiset<Integer> elements = HashMultiset.create();
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue.create();
    int range = 10_000; // range should be small enough that equal elements occur semi-frequently
    for (int iter = 0; iter < reduceIterationsIfGwt(1000); iter++) {
      for (int i = 0; i < 100; i++) {
        Integer element = random.nextInt(range);
        elements.add(element);
        queue.add(element);
      }
      Iterator<Integer> queueIterator = queue.iterator();
      int remaining = queue.size();
      while (queueIterator.hasNext()) {
        Integer element = queueIterator.next();
        remaining--;
        assertThat(elements).contains(element);
        if (random.nextBoolean()) {
          elements.remove(element);
          queueIterator.remove();
        }
      }
      assertThat(remaining).isEqualTo(0);
      assertIntact(queue);
      assertThat(queue).containsExactlyElementsIn(elements);
    }
  }

  private enum Element {
    ONE,
    TWO,
    THREE,
    FOUR,
    FIVE;
  }

  public void testRandomAddsAndRemoves_duplicateElements() {
    Random random = new Random(0);
    Multiset<Element> elements = HashMultiset.create();
    MinMaxPriorityQueue<Element> queue = MinMaxPriorityQueue.create();
    int range = Element.values().length;
    for (int iter = 0; iter < reduceIterationsIfGwt(1000); iter++) {
      for (int i = 0; i < 100; i++) {
        Element element = Element.values()[random.nextInt(range)];
        elements.add(element);
        queue.add(element);
      }
      Iterator<Element> queueIterator = queue.iterator();
      int remaining = queue.size();
      while (queueIterator.hasNext()) {
        Element element = queueIterator.next();
        remaining--;
        assertThat(elements).contains(element);
        if (random.nextBoolean()) {
          elements.remove(element);
          queueIterator.remove();
        }
      }
      assertThat(remaining).isEqualTo(0);
      assertIntact(queue);
      assertThat(queue).containsExactlyElementsIn(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 static 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<>(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 expected) {
    }
    try {
      MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE);
      fail("Should overflow");
    } catch (IllegalStateException expected) {
    }
    try {
      MinMaxPriorityQueue.isEvenLevel(1 << 31);
      fail("Should be negative");
    } catch (IllegalStateException expected) {
    }
    try {
      MinMaxPriorityQueue.isEvenLevel(Integer.MIN_VALUE);
      fail("Should be negative");
    } catch (IllegalStateException expected) {
    }
  }

  @GwtIncompatible // NullPointerTester
  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);
    }
  }

  private static void assertIntact(MinMaxPriorityQueue<?> q) {
    if (!q.isIntact()) {
      fail("State " + Arrays.toString(q.toArray()));
    }
  }

  private static void assertIntactUsingSeed(long seed, MinMaxPriorityQueue<?> q) {
    if (!q.isIntact()) {
      fail("Using seed " + seed + ". State " + Arrays.toString(q.toArray()));
    }
  }

  private static void assertIntactUsingStartedWith(
      Collection<?> startedWith, MinMaxPriorityQueue<?> q) {
    if (!q.isIntact()) {
      fail("Started with " + startedWith + ". State " + Arrays.toString(q.toArray()));
    }
  }

  private static void assertEqualsUsingSeed(long seed, Object expected, Object actual) {
    if (!equal(actual, expected)) {
      // fail(), but with the JUnit-supplied message.
      assertEquals("Using seed " + seed, expected, actual);
    }
  }

  private static void assertEqualsUsingStartedWith(
      Collection<?> startedWith, Object expected, Object actual) {
    if (!equal(actual, expected)) {
      // fail(), but with the JUnit-supplied message.
      assertEquals("Started with " + startedWith, expected, actual);
    }
  }
}