Java example source code file (MinMaxPriorityQueueTest.java)

This example Java source code file (MinMaxPriorityQueueTest.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

arraylist, atomicinteger, could, heap, illegalstateexception, integer, iterator, list, minmaxheap, minmaxpriorityqueue, random, should, sortedmap, using, util

The MinMaxPriorityQueueTest.java Java example source code

/*
 * Copyright (C) 2008 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.truth.Truth.assertThat;

import com.google.common.collect.testing.IteratorFeature;
import com.google.common.collect.testing.IteratorTester;
import com.google.common.testing.NullPointerTester;

import junit.framework.TestCase;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.SortedMap;
import java.util.concurrent.atomic.AtomicInteger;

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

  // Overkill alert!  Test all combinations of 0-2 options during creation.

  public void testCreation_simple() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .create();
    assertEquals(11, queue.capacity());
    checkUnbounded(queue);
    checkNatural(queue);
  }

  public void testCreation_comparator() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .orderedBy(SOME_COMPARATOR)
        .create();
    assertEquals(11, queue.capacity());
    checkUnbounded(queue);
    assertSame(SOME_COMPARATOR, queue.comparator());
  }

  public void testCreation_expectedSize() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .expectedSize(8)
        .create();
    assertEquals(8, queue.capacity());
    checkUnbounded(queue);
    checkNatural(queue);
  }

  public void testCreation_expectedSize_comparator() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .orderedBy(SOME_COMPARATOR)
        .expectedSize(8)
        .create();
    assertEquals(8, queue.capacity());
    checkUnbounded(queue);
    assertSame(SOME_COMPARATOR, queue.comparator());
  }

  public void testCreation_maximumSize() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .maximumSize(42)
        .create();
    assertEquals(11, queue.capacity());
    assertEquals(42, queue.maximumSize);
    checkNatural(queue);
  }

  public void testCreation_comparator_maximumSize() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .orderedBy(SOME_COMPARATOR)
        .maximumSize(42)
        .create();
    assertEquals(11, queue.capacity());
    assertEquals(42, queue.maximumSize);
    assertSame(SOME_COMPARATOR, queue.comparator());
  }

  public void testCreation_expectedSize_maximumSize() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .expectedSize(8)
        .maximumSize(42)
        .create();
    assertEquals(8, queue.capacity());
    assertEquals(42, queue.maximumSize);
    checkNatural(queue);
  }

  private static final List<Integer> NUMBERS =
      ImmutableList.of(4, 8, 15, 16, 23, 42);

  public void testCreation_withContents() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .create(NUMBERS);
    assertEquals(6, queue.size());
    assertEquals(11, queue.capacity());
    checkUnbounded(queue);
    checkNatural(queue);
  }

  public void testCreation_comparator_withContents() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .orderedBy(SOME_COMPARATOR)
        .create(NUMBERS);
    assertEquals(6, queue.size());
    assertEquals(11, queue.capacity());
    checkUnbounded(queue);
    assertSame(SOME_COMPARATOR, queue.comparator());
  }

  public void testCreation_expectedSize_withContents() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .expectedSize(8)
        .create(NUMBERS);
    assertEquals(6, queue.size());
    assertEquals(8, queue.capacity());
    checkUnbounded(queue);
    checkNatural(queue);
  }

  public void testCreation_maximumSize_withContents() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .maximumSize(42)
        .create(NUMBERS);
    assertEquals(6, queue.size());
    assertEquals(11, queue.capacity());
    assertEquals(42, queue.maximumSize);
    checkNatural(queue);
  }

  // Now test everything at once

  public void testCreation_allOptions() {
    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
        .orderedBy(SOME_COMPARATOR)
        .expectedSize(8)
        .maximumSize(42)
        .create(NUMBERS);
    assertEquals(6, queue.size());
    assertEquals(8, queue.capacity());
    assertEquals(42, queue.maximumSize);
    assertSame(SOME_COMPARATOR, queue.comparator());
  }

  // TODO: tests that check the weird interplay between expected size,
  // maximum size, size of initial contents, default capacity...

  private static void checkNatural(MinMaxPriorityQueue<Integer> queue) {
    assertSame(Ordering.natural(), queue.comparator());
  }

  private static void checkUnbounded(MinMaxPriorityQueue<Integer> queue) {
    assertEquals(Integer.MAX_VALUE, queue.maximumSize);
  }

  public void testHeapIntact() {
    Random random = new Random(0);
    int heapSize = 999;
    int numberOfModifications = 500;
    MinMaxPriorityQueue<Integer> mmHeap =
        MinMaxPriorityQueue.expectedSize(heapSize).create();
    /*
     * this map would contain the same exact elements as the MinMaxHeap; the
     * value in the map is the number of occurrences of the key.
     */
    SortedMap<Integer, AtomicInteger> replica = Maps.newTreeMap();
    assertTrue("Empty heap should be OK", mmHeap.isIntact());
    for (int i = 0; i < heapSize; i++) {
      int randomInt = random.nextInt();
      mmHeap.offer(randomInt);
      insertIntoReplica(replica, randomInt);
    }
    assertTrue("MinMaxHeap not intact after " + heapSize + " insertions",
        mmHeap.isIntact());
    assertEquals(heapSize, mmHeap.size());
    int currentHeapSize = heapSize;
    for (int i = 0; i < numberOfModifications; i++) {
      if (random.nextBoolean()) {
        /* insert a new element */
        int randomInt = random.nextInt();
        mmHeap.offer(randomInt);
        insertIntoReplica(replica, randomInt);
        currentHeapSize++;
      } else {
        /* remove either min or max */
        if (random.nextBoolean()) {
          removeMinFromReplica(replica, mmHeap.poll());
        } else {
          removeMaxFromReplica(replica, mmHeap.pollLast());
        }
        for (Integer v : replica.keySet()) {
          assertTrue("MinMax queue has lost " + v, mmHeap.contains(v));
        }
        assertTrue(mmHeap.isIntact());
        currentHeapSize--;
        assertEquals(currentHeapSize, mmHeap.size());
      }
    }
    assertEquals(currentHeapSize, mmHeap.size());
    assertTrue("Heap not intact after " + numberOfModifications +
        " random mixture of operations", mmHeap.isIntact());
  }

  public void testSmall() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.add(1);
    mmHeap.add(4);
    mmHeap.add(2);
    mmHeap.add(3);
    assertEquals(4, (int) mmHeap.pollLast());
    assertEquals(3, (int) mmHeap.peekLast());
    assertEquals(3, (int) mmHeap.pollLast());
    assertEquals(1, (int) mmHeap.peek());
    assertEquals(2, (int) mmHeap.peekLast());
    assertEquals(2, (int) mmHeap.pollLast());
    assertEquals(1, (int) mmHeap.peek());
    assertEquals(1, (int) mmHeap.peekLast());
    assertEquals(1, (int) mmHeap.pollLast());
    assertNull(mmHeap.peek());
    assertNull(mmHeap.peekLast());
    assertNull(mmHeap.pollLast());
  }

  public void testSmallMinHeap() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.add(1);
    mmHeap.add(3);
    mmHeap.add(2);
    assertEquals(1, (int) mmHeap.peek());
    assertEquals(1, (int) mmHeap.poll());
    assertEquals(3, (int) mmHeap.peekLast());
    assertEquals(2, (int) mmHeap.peek());
    assertEquals(2, (int) mmHeap.poll());
    assertEquals(3, (int) mmHeap.peekLast());
    assertEquals(3, (int) mmHeap.peek());
    assertEquals(3, (int) mmHeap.poll());
    assertNull(mmHeap.peekLast());
    assertNull(mmHeap.peek());
    assertNull(mmHeap.poll());
  }

  public void testRemove() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4, 47, 1, 5, 3, 0));
    assertTrue("Heap is not intact initally", mmHeap.isIntact());
    assertEquals(9, mmHeap.size());
    mmHeap.remove(5);
    assertEquals(8, mmHeap.size());
    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
    assertEquals(47, (int) mmHeap.pollLast());
    assertEquals(4, (int) mmHeap.pollLast());
    mmHeap.removeAll(Lists.newArrayList(2, 3));
    assertEquals(3, mmHeap.size());
    assertTrue("Heap is not intact after removeAll()", mmHeap.isIntact());
  }

  public void testContains() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(1, 1, 2));
    assertEquals(3, mmHeap.size());
    assertFalse("Heap does not contain null", mmHeap.contains(null));
    assertFalse("Heap does not contain 3", mmHeap.contains(3));
    assertFalse("Heap does not contain 3", mmHeap.remove(3));
    assertEquals(3, mmHeap.size());
    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
    assertTrue("Heap contains two 1's", mmHeap.contains(1));
    assertTrue("Heap contains two 1's", mmHeap.remove(1));
    assertTrue("Heap contains 1", mmHeap.contains(1));
    assertTrue("Heap contains 1", mmHeap.remove(1));
    assertFalse("Heap does not contain 1", mmHeap.contains(1));
    assertTrue("Heap contains 2", mmHeap.remove(2));
    assertEquals(0, mmHeap.size());
    assertFalse("Heap does not contain anything", mmHeap.contains(1));
    assertFalse("Heap does not contain anything", mmHeap.remove(2));
  }

  public void testIteratorPastEndException() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(1, 2));
    Iterator<Integer> it = mmHeap.iterator();
    assertTrue("Iterator has reached end prematurely", it.hasNext());
    it.next();
    it.next();
    try {
      it.next();
      fail("No exception thrown when iterating past end of heap");
    } catch (NoSuchElementException e) {
      // expected error
    }
  }

  public void testIteratorConcurrentModification() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4));
    Iterator<Integer> it = mmHeap.iterator();
    assertTrue("Iterator has reached end prematurely", it.hasNext());
    it.next();
    it.next();
    mmHeap.remove(4);
    try {
      it.next();
      fail("No exception thrown when iterating a modified heap");
    } catch (ConcurrentModificationException e) {
      // expected error
    }
  }

  /**
   * Tests a failure caused by fix to childless uncle issue.
   */
  public void testIteratorRegressionChildlessUncle() {
    final ArrayList<Integer> initial = Lists.newArrayList(
        1, 15, 13, 8, 9, 10, 11, 14);
    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(initial);
    assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
    q.remove(9);
    q.remove(11);
    q.remove(10);
    // Now we're in the critical state: [1, 15, 13, 8, 14]
    // Removing 8 while iterating caused duplicates in iteration result.
    List<Integer> result = Lists.newArrayListWithCapacity(initial.size());
    for (Iterator<Integer> iter = q.iterator(); iter.hasNext();) {
      Integer value = iter.next();
      result.add(value);
      if (value == 8) {
        iter.remove();
      }
    }
    assertTrue(q.isIntact());
    assertThat(result).containsExactly(1, 15, 13, 8, 14);
  }

  /**
   * This tests a special case of the removeAt() call. Moving an element
   * sideways on the heap could break the invariants. Sometimes we need to
   * bubble an element up instead of trickling down. See implementation.
   */
  public void testInvalidatingRemove() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(
            1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600));
    assertEquals(15, mmHeap.size());
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    mmHeap.remove(12);
    assertEquals(14, mmHeap.size());
    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
  }

  /**
   * This tests a more obscure special case, but otherwise similar to above.
   */
  public void testInvalidatingRemove2() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    List<Integer> values = Lists.newArrayList(
        1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600, 4, 5,
        6, 7, 8, 9, 4, 5, 200, 250);
    mmHeap.addAll(values);
    assertEquals(25, mmHeap.size());
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    mmHeap.remove(2);
    assertEquals(24, mmHeap.size());
    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
    values.removeAll(Lists.newArrayList(2));
    assertEquals(values.size(), mmHeap.size());
    assertTrue(values.containsAll(mmHeap));
    assertTrue(mmHeap.containsAll(values));
  }

  public void testIteratorInvalidatingIteratorRemove() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(
            1, 20, 100, 2, 3, 30, 40));
    assertEquals(7, mmHeap.size());
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    Iterator<Integer> it = mmHeap.iterator();
    assertEquals((Integer) 1, it.next());
    assertEquals((Integer) 20, it.next());
    assertEquals((Integer) 100, it.next());
    assertEquals((Integer) 2, it.next());
    it.remove();
    assertFalse(mmHeap.contains(2));
    assertTrue(it.hasNext());
    assertEquals((Integer) 3, it.next());
    assertTrue(it.hasNext());
    assertEquals((Integer) 30, it.next());
    assertTrue(it.hasNext());
    assertEquals((Integer) 40, it.next());
    assertFalse(it.hasNext());
    assertEquals(6, mmHeap.size());
    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
    assertFalse(mmHeap.contains(2));

    // This tests that it.remove() above actually changed the order. It
    // indicates that the value 40 was stored in forgetMeNot, so it is
    // returned in the last call to it.next(). Without it, 30 should be the last
    // item returned by the iterator.
    Integer lastItem = 0;
    for (Integer tmp : mmHeap) {
      lastItem = tmp;
    }
    assertEquals((Integer) 30, lastItem);
  }

  /**
   * This tests a special case where removeAt has to trickle an element
   * first down one level from a min to a max level, then up one level above
   * the index of the removed element.
   * It also tests that skipMe in the iterator plays nicely with
   * forgetMeNot.
   */
  public void testIteratorInvalidatingIteratorRemove2() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
    mmHeap.addAll(Lists.newArrayList(
        1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 200, 300, 500, 400));
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    Iterator<Integer> it = mmHeap.iterator();
    assertEquals((Integer) 1, it.next());
    assertEquals((Integer) 20, it.next());
    assertEquals((Integer) 1000, it.next());
    assertEquals((Integer) 2, it.next());
    it.remove();
    assertTrue("Heap is not intact after remove", mmHeap.isIntact());
    assertEquals((Integer) 10, it.next());
    assertEquals((Integer) 3, it.next());
    it.remove();
    assertTrue("Heap is not intact after remove", mmHeap.isIntact());
    assertEquals((Integer) 12, it.next());
    assertEquals((Integer) 30, it.next());
    assertEquals((Integer) 40, it.next());
    // Skipping 20
    assertEquals((Integer) 11, it.next());
    // Skipping 400
    assertEquals((Integer) 13, it.next());
    assertEquals((Integer) 200, it.next());
    assertEquals((Integer) 300, it.next());
    // Last two from forgetMeNot.
    assertEquals((Integer) 400, it.next());
    assertEquals((Integer) 500, it.next());
  }

  public void testRemoveFromStringHeap() {
    MinMaxPriorityQueue<String> mmHeap =
        MinMaxPriorityQueue.expectedSize(5).create();
    Collections.addAll(mmHeap,
        "foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric");
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    assertEquals("bar", mmHeap.peek());
    assertEquals("sergey", mmHeap.peekLast());
    assertEquals(7, mmHeap.size());
    assertTrue("Could not remove larry", mmHeap.remove("larry"));
    assertEquals(6, mmHeap.size());
    assertFalse("heap contains larry which has been removed",
        mmHeap.contains("larry"));
    assertTrue("heap does not contain sergey",
        mmHeap.contains("sergey"));
    assertTrue("Could not remove larry", mmHeap.removeAll(
        Lists.newArrayList("sergey", "eric")));
    assertFalse("Could remove nikesh which is not in the heap",
        mmHeap.remove("nikesh"));
    assertEquals(4, mmHeap.size());
  }

  public void testCreateWithOrdering() {
    MinMaxPriorityQueue<String> mmHeap =
        MinMaxPriorityQueue.orderedBy(Ordering.natural().reverse()).create();
    Collections.addAll(mmHeap,
        "foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric");
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    assertEquals("sergey", mmHeap.peek());
    assertEquals("bar", mmHeap.peekLast());
  }

  public void testCreateWithCapacityAndOrdering() {
    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.orderedBy(
        Ordering.natural().reverse()).expectedSize(5).create();
    Collections.addAll(mmHeap, 1, 7, 2, 56, 2, 5, 23, 68, 0, 3);
    assertTrue("Heap is not intact initially", mmHeap.isIntact());
    assertEquals(68, (int) mmHeap.peek());
    assertEquals(0, (int) mmHeap.peekLast());
  }

  private <T extends Comparable void runIterator(
      final List<T> values, int steps) throws Exception {
    IteratorTester<T> tester =
        new IteratorTester<T>(
            steps,
            IteratorFeature.MODIFIABLE,
            Lists.newLinkedList(values),
            IteratorTester.KnownOrder.UNKNOWN_ORDER) {
          private MinMaxPriorityQueue<T> mmHeap;
          @Override protected Iterator<T> newTargetIterator() {
            mmHeap = MinMaxPriorityQueue.create(values);
            return mmHeap.iterator();
          }
          @Override protected void verify(List<T> elements) {
            assertEquals(Sets.newHashSet(elements),
                Sets.newHashSet(mmHeap.iterator()));
            assertTrue("Invalid MinMaxHeap: " + mmHeap, mmHeap.isIntact());
          }
        };
    tester.test();
  }

  public void testIteratorTester() throws Exception {
    Random random = new Random(0);
    List<Integer> list = Lists.newArrayList();
    for (int i = 0; i < 3; i++) {
      list.add(random.nextInt());
    }
    runIterator(list, 6);
  }

  public void testIteratorTesterLarger() throws Exception {
    runIterator(Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 5);
  }

  public void testRemoveAt() {
    long seed = new Random().nextLong();
    Random random = new Random(seed);
    int heapSize = 999;
    int numberOfModifications = 500;
    MinMaxPriorityQueue<Integer> mmHeap =
        MinMaxPriorityQueue.expectedSize(heapSize).create();
    for (int i = 0; i < heapSize; i++) {
      mmHeap.add(random.nextInt());
    }
    for (int i = 0; i < numberOfModifications; i++) {
      mmHeap.removeAt(random.nextInt(mmHeap.size()));
      assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact());
      mmHeap.add(random.nextInt());
      assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact());
    }
  }

  public void testRemoveAt_exhaustive() {
    int size = 8;
    List<Integer> expected = createOrderedList(size);
    for (Collection<Integer> perm : Collections2.permutations(expected)) {
      for (int i = 0; i < perm.size(); i++) {
        MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm);
        q.removeAt(i);
        assertTrue("Remove at " + i + " perm " + perm, q.isIntact());
      }
    }
  }

  /**
   * Regression test for bug found.
   */
  public void testCorrectOrdering_regression() {
    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue
        .create(ImmutableList.of(3, 5, 1, 4, 7));
    List<Integer> expected = ImmutableList.of(1, 3, 4, 5, 7);
    List<Integer> actual = new ArrayList(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();
    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
    for (int i = 0; i < 73; i++) { // 73 is a childless uncle case.
      Integer element = random.nextInt();
      control.add(element);
      assertTrue(q.add(element));
    }
    assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
    for (int i = 0; i < 500000; i++) {
      if (random.nextBoolean()) {
        Integer element = random.nextInt();
        control.add(element);
        q.add(element);
      } else {
        assertEquals("Using seed " + seed, control.poll(), q.pollFirst());
      }
    }
    while (!control.isEmpty()) {
      assertEquals("Using seed " + seed, control.poll(), q.pollFirst());
    }
    assertTrue(q.isEmpty());
  }

  public void testExhaustive_pollAndPush() {
    int size = 8;
    List<Integer> expected = createOrderedList(size);
    for (Collection<Integer> perm : Collections2.permutations(expected)) {
      MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm);
      List<Integer> elements = Lists.newArrayListWithCapacity(size);
      while (!q.isEmpty()) {
        Integer next = q.pollFirst();
        for (int i = 0; i <= size; i++) {
          assertTrue(q.add(i));
          assertTrue(q.add(next));
          assertTrue(q.remove(i));
          assertEquals(next, q.poll());
        }
        elements.add(next);
      }
      assertEquals("Started with " + perm, expected, elements);
    }
  }

  /**
   * Regression test for b/4124577
   */
  public void testRegression_dataCorruption() {
    int size = 8;
    List<Integer> expected = createOrderedList(size);
    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(expected);
    List<Integer> contents = Lists.newArrayList(expected);
    List<Integer> elements = Lists.newArrayListWithCapacity(size);
    while (!q.isEmpty()) {
      assertThat(q).containsExactlyElementsIn(contents);
      Integer next = q.pollFirst();
      contents.remove(next);
      assertThat(q).containsExactlyElementsIn(contents);
      for (int i = 0; i <= size; i++) {
        q.add(i);
        contents.add(i);
        assertThat(q).containsExactlyElementsIn(contents);
        q.add(next);
        contents.add(next);
        assertThat(q).containsExactlyElementsIn(contents);
        q.remove(i);
        assertTrue(contents.remove(Integer.valueOf(i)));
        assertThat(q).containsExactlyElementsIn(contents);
        assertEquals(next, q.poll());
        contents.remove(next);
        assertThat(q).containsExactlyElementsIn(contents);
      }
      elements.add(next);
    }
    assertEquals(expected, elements);
  }

  /**
   * Returns the seed used for the randomization.
   */
  private long insertRandomly(ArrayList<Integer> elements,
      MinMaxPriorityQueue<Integer> q) {
    long seed = new Random().nextLong();
    Random random = new Random(seed);
    insertRandomly(elements, q, random);
    return seed;
  }

  private static void insertRandomly(
      ArrayList<Integer> elements, MinMaxPriorityQueue 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 e) {
      // expected
    }
    try {
      MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE);
      fail("Should overflow");
    } catch (IllegalStateException e) {
      // expected
    }
    try {
      MinMaxPriorityQueue.isEvenLevel(1 << 31);
      fail("Should be negative");
    } catch (IllegalStateException e) {
      // expected
    }
    try {
      MinMaxPriorityQueue.isEvenLevel(Integer.MIN_VALUE);
      fail("Should be negative");
    } catch (IllegalStateException e) {
      // expected
    }
  }

  public void testNullPointers() {
    NullPointerTester tester = new NullPointerTester();
    tester.testAllPublicConstructors(MinMaxPriorityQueue.class);
    tester.testAllPublicStaticMethods(MinMaxPriorityQueue.class);
    tester.testAllPublicInstanceMethods(MinMaxPriorityQueue.<String>create());
  }

  private static void insertIntoReplica(
      Map<Integer, AtomicInteger> replica,
      int newValue) {
    if (replica.containsKey(newValue)) {
      replica.get(newValue).incrementAndGet();
    } else {
      replica.put(newValue, new AtomicInteger(1));
    }
  }

  private static void removeMinFromReplica(
      SortedMap<Integer, AtomicInteger> replica,
      int minValue) {
    Integer replicatedMinValue = replica.firstKey();
    assertEquals(replicatedMinValue, (Integer) minValue);
    removeFromReplica(replica, replicatedMinValue);
  }

  private static void removeMaxFromReplica(
      SortedMap<Integer, AtomicInteger> replica,
      int maxValue) {
    Integer replicatedMaxValue = replica.lastKey();
    assertTrue("maxValue is incorrect", replicatedMaxValue == maxValue);
    removeFromReplica(replica, replicatedMaxValue);
  }

  private static void removeFromReplica(
      Map<Integer, AtomicInteger> replica, int value) {
    AtomicInteger numOccur = replica.get(value);
    if (numOccur.decrementAndGet() == 0) {
      replica.remove(value);
    }
  }
}