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 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);
    }
  }
}