1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.truth.Truth.assertThat;
20
21import com.google.common.collect.testing.IteratorFeature;
22import com.google.common.collect.testing.IteratorTester;
23import com.google.common.testing.NullPointerTester;
24
25import junit.framework.TestCase;
26
27import java.util.ArrayList;
28import java.util.Arrays;
29import java.util.Collection;
30import java.util.Collections;
31import java.util.ConcurrentModificationException;
32import java.util.Iterator;
33import java.util.List;
34import java.util.Map;
35import java.util.NoSuchElementException;
36import java.util.PriorityQueue;
37import java.util.Random;
38import java.util.SortedMap;
39import java.util.concurrent.atomic.AtomicInteger;
40
41/**
42 * Unit test for {@link MinMaxPriorityQueue}.
43 *
44 * @author Alexei Stolboushkin
45 * @author Sverre Sundsdal
46 */
47public class MinMaxPriorityQueueTest extends TestCase {
48  private Ordering<Integer> SOME_COMPARATOR = Ordering.natural().reverse();
49
50  // Overkill alert!  Test all combinations of 0-2 options during creation.
51
52  public void testCreation_simple() {
53    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
54        .create();
55    assertEquals(11, queue.capacity());
56    checkUnbounded(queue);
57    checkNatural(queue);
58  }
59
60  public void testCreation_comparator() {
61    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
62        .orderedBy(SOME_COMPARATOR)
63        .create();
64    assertEquals(11, queue.capacity());
65    checkUnbounded(queue);
66    assertSame(SOME_COMPARATOR, queue.comparator());
67  }
68
69  public void testCreation_expectedSize() {
70    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
71        .expectedSize(8)
72        .create();
73    assertEquals(8, queue.capacity());
74    checkUnbounded(queue);
75    checkNatural(queue);
76  }
77
78  public void testCreation_expectedSize_comparator() {
79    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
80        .orderedBy(SOME_COMPARATOR)
81        .expectedSize(8)
82        .create();
83    assertEquals(8, queue.capacity());
84    checkUnbounded(queue);
85    assertSame(SOME_COMPARATOR, queue.comparator());
86  }
87
88  public void testCreation_maximumSize() {
89    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
90        .maximumSize(42)
91        .create();
92    assertEquals(11, queue.capacity());
93    assertEquals(42, queue.maximumSize);
94    checkNatural(queue);
95  }
96
97  public void testCreation_comparator_maximumSize() {
98    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
99        .orderedBy(SOME_COMPARATOR)
100        .maximumSize(42)
101        .create();
102    assertEquals(11, queue.capacity());
103    assertEquals(42, queue.maximumSize);
104    assertSame(SOME_COMPARATOR, queue.comparator());
105  }
106
107  public void testCreation_expectedSize_maximumSize() {
108    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
109        .expectedSize(8)
110        .maximumSize(42)
111        .create();
112    assertEquals(8, queue.capacity());
113    assertEquals(42, queue.maximumSize);
114    checkNatural(queue);
115  }
116
117  private static final List<Integer> NUMBERS =
118      ImmutableList.of(4, 8, 15, 16, 23, 42);
119
120  public void testCreation_withContents() {
121    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
122        .create(NUMBERS);
123    assertEquals(6, queue.size());
124    assertEquals(11, queue.capacity());
125    checkUnbounded(queue);
126    checkNatural(queue);
127  }
128
129  public void testCreation_comparator_withContents() {
130    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
131        .orderedBy(SOME_COMPARATOR)
132        .create(NUMBERS);
133    assertEquals(6, queue.size());
134    assertEquals(11, queue.capacity());
135    checkUnbounded(queue);
136    assertSame(SOME_COMPARATOR, queue.comparator());
137  }
138
139  public void testCreation_expectedSize_withContents() {
140    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
141        .expectedSize(8)
142        .create(NUMBERS);
143    assertEquals(6, queue.size());
144    assertEquals(8, queue.capacity());
145    checkUnbounded(queue);
146    checkNatural(queue);
147  }
148
149  public void testCreation_maximumSize_withContents() {
150    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
151        .maximumSize(42)
152        .create(NUMBERS);
153    assertEquals(6, queue.size());
154    assertEquals(11, queue.capacity());
155    assertEquals(42, queue.maximumSize);
156    checkNatural(queue);
157  }
158
159  // Now test everything at once
160
161  public void testCreation_allOptions() {
162    MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue
163        .orderedBy(SOME_COMPARATOR)
164        .expectedSize(8)
165        .maximumSize(42)
166        .create(NUMBERS);
167    assertEquals(6, queue.size());
168    assertEquals(8, queue.capacity());
169    assertEquals(42, queue.maximumSize);
170    assertSame(SOME_COMPARATOR, queue.comparator());
171  }
172
173  // TODO: tests that check the weird interplay between expected size,
174  // maximum size, size of initial contents, default capacity...
175
176  private static void checkNatural(MinMaxPriorityQueue<Integer> queue) {
177    assertSame(Ordering.natural(), queue.comparator());
178  }
179
180  private static void checkUnbounded(MinMaxPriorityQueue<Integer> queue) {
181    assertEquals(Integer.MAX_VALUE, queue.maximumSize);
182  }
183
184  public void testHeapIntact() {
185    Random random = new Random(0);
186    int heapSize = 999;
187    int numberOfModifications = 500;
188    MinMaxPriorityQueue<Integer> mmHeap =
189        MinMaxPriorityQueue.expectedSize(heapSize).create();
190    /*
191     * this map would contain the same exact elements as the MinMaxHeap; the
192     * value in the map is the number of occurrences of the key.
193     */
194    SortedMap<Integer, AtomicInteger> replica = Maps.newTreeMap();
195    assertTrue("Empty heap should be OK", mmHeap.isIntact());
196    for (int i = 0; i < heapSize; i++) {
197      int randomInt = random.nextInt();
198      mmHeap.offer(randomInt);
199      insertIntoReplica(replica, randomInt);
200    }
201    assertTrue("MinMaxHeap not intact after " + heapSize + " insertions",
202        mmHeap.isIntact());
203    assertEquals(heapSize, mmHeap.size());
204    int currentHeapSize = heapSize;
205    for (int i = 0; i < numberOfModifications; i++) {
206      if (random.nextBoolean()) {
207        /* insert a new element */
208        int randomInt = random.nextInt();
209        mmHeap.offer(randomInt);
210        insertIntoReplica(replica, randomInt);
211        currentHeapSize++;
212      } else {
213        /* remove either min or max */
214        if (random.nextBoolean()) {
215          removeMinFromReplica(replica, mmHeap.poll());
216        } else {
217          removeMaxFromReplica(replica, mmHeap.pollLast());
218        }
219        for (Integer v : replica.keySet()) {
220          assertTrue("MinMax queue has lost " + v, mmHeap.contains(v));
221        }
222        assertTrue(mmHeap.isIntact());
223        currentHeapSize--;
224        assertEquals(currentHeapSize, mmHeap.size());
225      }
226    }
227    assertEquals(currentHeapSize, mmHeap.size());
228    assertTrue("Heap not intact after " + numberOfModifications +
229        " random mixture of operations", mmHeap.isIntact());
230  }
231
232  public void testSmall() {
233    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
234    mmHeap.add(1);
235    mmHeap.add(4);
236    mmHeap.add(2);
237    mmHeap.add(3);
238    assertEquals(4, (int) mmHeap.pollLast());
239    assertEquals(3, (int) mmHeap.peekLast());
240    assertEquals(3, (int) mmHeap.pollLast());
241    assertEquals(1, (int) mmHeap.peek());
242    assertEquals(2, (int) mmHeap.peekLast());
243    assertEquals(2, (int) mmHeap.pollLast());
244    assertEquals(1, (int) mmHeap.peek());
245    assertEquals(1, (int) mmHeap.peekLast());
246    assertEquals(1, (int) mmHeap.pollLast());
247    assertNull(mmHeap.peek());
248    assertNull(mmHeap.peekLast());
249    assertNull(mmHeap.pollLast());
250  }
251
252  public void testSmallMinHeap() {
253    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
254    mmHeap.add(1);
255    mmHeap.add(3);
256    mmHeap.add(2);
257    assertEquals(1, (int) mmHeap.peek());
258    assertEquals(1, (int) mmHeap.poll());
259    assertEquals(3, (int) mmHeap.peekLast());
260    assertEquals(2, (int) mmHeap.peek());
261    assertEquals(2, (int) mmHeap.poll());
262    assertEquals(3, (int) mmHeap.peekLast());
263    assertEquals(3, (int) mmHeap.peek());
264    assertEquals(3, (int) mmHeap.poll());
265    assertNull(mmHeap.peekLast());
266    assertNull(mmHeap.peek());
267    assertNull(mmHeap.poll());
268  }
269
270  public void testRemove() {
271    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
272    mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4, 47, 1, 5, 3, 0));
273    assertTrue("Heap is not intact initally", mmHeap.isIntact());
274    assertEquals(9, mmHeap.size());
275    mmHeap.remove(5);
276    assertEquals(8, mmHeap.size());
277    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
278    assertEquals(47, (int) mmHeap.pollLast());
279    assertEquals(4, (int) mmHeap.pollLast());
280    mmHeap.removeAll(Lists.newArrayList(2, 3));
281    assertEquals(3, mmHeap.size());
282    assertTrue("Heap is not intact after removeAll()", mmHeap.isIntact());
283  }
284
285  public void testContains() {
286    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
287    mmHeap.addAll(Lists.newArrayList(1, 1, 2));
288    assertEquals(3, mmHeap.size());
289    assertFalse("Heap does not contain null", mmHeap.contains(null));
290    assertFalse("Heap does not contain 3", mmHeap.contains(3));
291    assertFalse("Heap does not contain 3", mmHeap.remove(3));
292    assertEquals(3, mmHeap.size());
293    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
294    assertTrue("Heap contains two 1's", mmHeap.contains(1));
295    assertTrue("Heap contains two 1's", mmHeap.remove(1));
296    assertTrue("Heap contains 1", mmHeap.contains(1));
297    assertTrue("Heap contains 1", mmHeap.remove(1));
298    assertFalse("Heap does not contain 1", mmHeap.contains(1));
299    assertTrue("Heap contains 2", mmHeap.remove(2));
300    assertEquals(0, mmHeap.size());
301    assertFalse("Heap does not contain anything", mmHeap.contains(1));
302    assertFalse("Heap does not contain anything", mmHeap.remove(2));
303  }
304
305  public void testIteratorPastEndException() {
306    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
307    mmHeap.addAll(Lists.newArrayList(1, 2));
308    Iterator<Integer> it = mmHeap.iterator();
309    assertTrue("Iterator has reached end prematurely", it.hasNext());
310    it.next();
311    it.next();
312    try {
313      it.next();
314      fail("No exception thrown when iterating past end of heap");
315    } catch (NoSuchElementException e) {
316      // expected error
317    }
318  }
319
320  public void testIteratorConcurrentModification() {
321    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
322    mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4));
323    Iterator<Integer> it = mmHeap.iterator();
324    assertTrue("Iterator has reached end prematurely", it.hasNext());
325    it.next();
326    it.next();
327    mmHeap.remove(4);
328    try {
329      it.next();
330      fail("No exception thrown when iterating a modified heap");
331    } catch (ConcurrentModificationException e) {
332      // expected error
333    }
334  }
335
336  /**
337   * Tests a failure caused by fix to childless uncle issue.
338   */
339  public void testIteratorRegressionChildlessUncle() {
340    final ArrayList<Integer> initial = Lists.newArrayList(
341        1, 15, 13, 8, 9, 10, 11, 14);
342    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(initial);
343    assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
344    q.remove(9);
345    q.remove(11);
346    q.remove(10);
347    // Now we're in the critical state: [1, 15, 13, 8, 14]
348    // Removing 8 while iterating caused duplicates in iteration result.
349    List<Integer> result = Lists.newArrayListWithCapacity(initial.size());
350    for (Iterator<Integer> iter = q.iterator(); iter.hasNext();) {
351      Integer value = iter.next();
352      result.add(value);
353      if (value == 8) {
354        iter.remove();
355      }
356    }
357    assertTrue(q.isIntact());
358    assertThat(result).has().exactly(1, 15, 13, 8, 14);
359  }
360
361  /**
362   * This tests a special case of the removeAt() call. Moving an element
363   * sideways on the heap could break the invariants. Sometimes we need to
364   * bubble an element up instead of trickling down. See implementation.
365   */
366  public void testInvalidatingRemove() {
367    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
368    mmHeap.addAll(Lists.newArrayList(
369            1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600));
370    assertEquals(15, mmHeap.size());
371    assertTrue("Heap is not intact initially", mmHeap.isIntact());
372    mmHeap.remove(12);
373    assertEquals(14, mmHeap.size());
374    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
375  }
376
377  /**
378   * This tests a more obscure special case, but otherwise similar to above.
379   */
380  public void testInvalidatingRemove2() {
381    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
382    List<Integer> values = Lists.newArrayList(
383        1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600, 4, 5,
384        6, 7, 8, 9, 4, 5, 200, 250);
385    mmHeap.addAll(values);
386    assertEquals(25, mmHeap.size());
387    assertTrue("Heap is not intact initially", mmHeap.isIntact());
388    mmHeap.remove(2);
389    assertEquals(24, mmHeap.size());
390    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
391    values.removeAll(Lists.newArrayList(2));
392    assertEquals(values.size(), mmHeap.size());
393    assertTrue(values.containsAll(mmHeap));
394    assertTrue(mmHeap.containsAll(values));
395  }
396
397  public void testIteratorInvalidatingIteratorRemove() {
398    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
399    mmHeap.addAll(Lists.newArrayList(
400            1, 20, 100, 2, 3, 30, 40));
401    assertEquals(7, mmHeap.size());
402    assertTrue("Heap is not intact initially", mmHeap.isIntact());
403    Iterator<Integer> it = mmHeap.iterator();
404    assertEquals((Integer) 1, it.next());
405    assertEquals((Integer) 20, it.next());
406    assertEquals((Integer) 100, it.next());
407    assertEquals((Integer) 2, it.next());
408    it.remove();
409    assertFalse(mmHeap.contains(2));
410    assertTrue(it.hasNext());
411    assertEquals((Integer) 3, it.next());
412    assertTrue(it.hasNext());
413    assertEquals((Integer) 30, it.next());
414    assertTrue(it.hasNext());
415    assertEquals((Integer) 40, it.next());
416    assertFalse(it.hasNext());
417    assertEquals(6, mmHeap.size());
418    assertTrue("Heap is not intact after remove()", mmHeap.isIntact());
419    assertFalse(mmHeap.contains(2));
420
421    // This tests that it.remove() above actually changed the order. It
422    // indicates that the value 40 was stored in forgetMeNot, so it is
423    // returned in the last call to it.next(). Without it, 30 should be the last
424    // item returned by the iterator.
425    Integer lastItem = 0;
426    for (Integer tmp : mmHeap) {
427      lastItem = tmp;
428    }
429    assertEquals((Integer) 30, lastItem);
430  }
431
432  /**
433   * This tests a special case where removeAt has to trickle an element
434   * first down one level from a min to a max level, then up one level above
435   * the index of the removed element.
436   * It also tests that skipMe in the iterator plays nicely with
437   * forgetMeNot.
438   */
439  public void testIteratorInvalidatingIteratorRemove2() {
440    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create();
441    mmHeap.addAll(Lists.newArrayList(
442        1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 200, 300, 500, 400));
443    assertTrue("Heap is not intact initially", mmHeap.isIntact());
444    Iterator<Integer> it = mmHeap.iterator();
445    assertEquals((Integer) 1, it.next());
446    assertEquals((Integer) 20, it.next());
447    assertEquals((Integer) 1000, it.next());
448    assertEquals((Integer) 2, it.next());
449    it.remove();
450    assertTrue("Heap is not intact after remove", mmHeap.isIntact());
451    assertEquals((Integer) 10, it.next());
452    assertEquals((Integer) 3, it.next());
453    it.remove();
454    assertTrue("Heap is not intact after remove", mmHeap.isIntact());
455    assertEquals((Integer) 12, it.next());
456    assertEquals((Integer) 30, it.next());
457    assertEquals((Integer) 40, it.next());
458    // Skipping 20
459    assertEquals((Integer) 11, it.next());
460    // Skipping 400
461    assertEquals((Integer) 13, it.next());
462    assertEquals((Integer) 200, it.next());
463    assertEquals((Integer) 300, it.next());
464    // Last two from forgetMeNot.
465    assertEquals((Integer) 400, it.next());
466    assertEquals((Integer) 500, it.next());
467  }
468
469  public void testRemoveFromStringHeap() {
470    MinMaxPriorityQueue<String> mmHeap =
471        MinMaxPriorityQueue.expectedSize(5).create();
472    Collections.addAll(mmHeap,
473        "foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric");
474    assertTrue("Heap is not intact initially", mmHeap.isIntact());
475    assertEquals("bar", mmHeap.peek());
476    assertEquals("sergey", mmHeap.peekLast());
477    assertEquals(7, mmHeap.size());
478    assertTrue("Could not remove larry", mmHeap.remove("larry"));
479    assertEquals(6, mmHeap.size());
480    assertFalse("heap contains larry which has been removed",
481        mmHeap.contains("larry"));
482    assertTrue("heap does not contain sergey",
483        mmHeap.contains("sergey"));
484    assertTrue("Could not remove larry", mmHeap.removeAll(
485        Lists.newArrayList("sergey", "eric")));
486    assertFalse("Could remove nikesh which is not in the heap",
487        mmHeap.remove("nikesh"));
488    assertEquals(4, mmHeap.size());
489  }
490
491  public void testCreateWithOrdering() {
492    MinMaxPriorityQueue<String> mmHeap =
493        MinMaxPriorityQueue.orderedBy(Ordering.natural().reverse()).create();
494    Collections.addAll(mmHeap,
495        "foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric");
496    assertTrue("Heap is not intact initially", mmHeap.isIntact());
497    assertEquals("sergey", mmHeap.peek());
498    assertEquals("bar", mmHeap.peekLast());
499  }
500
501  public void testCreateWithCapacityAndOrdering() {
502    MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.orderedBy(
503        Ordering.natural().reverse()).expectedSize(5).create();
504    Collections.addAll(mmHeap, 1, 7, 2, 56, 2, 5, 23, 68, 0, 3);
505    assertTrue("Heap is not intact initially", mmHeap.isIntact());
506    assertEquals(68, (int) mmHeap.peek());
507    assertEquals(0, (int) mmHeap.peekLast());
508  }
509
510  private <T extends Comparable<T>> void runIterator(
511      final List<T> values, int steps) throws Exception {
512    IteratorTester<T> tester =
513        new IteratorTester<T>(
514            steps,
515            IteratorFeature.MODIFIABLE,
516            Lists.newLinkedList(values),
517            IteratorTester.KnownOrder.UNKNOWN_ORDER) {
518          private MinMaxPriorityQueue<T> mmHeap;
519          @Override protected Iterator<T> newTargetIterator() {
520            mmHeap = MinMaxPriorityQueue.create(values);
521            return mmHeap.iterator();
522          }
523          @Override protected void verify(List<T> elements) {
524            assertEquals(Sets.newHashSet(elements),
525                Sets.newHashSet(mmHeap.iterator()));
526            assertTrue("Invalid MinMaxHeap: " + mmHeap, mmHeap.isIntact());
527          }
528        };
529    tester.test();
530  }
531
532  public void testIteratorTester() throws Exception {
533    Random random = new Random(0);
534    List<Integer> list = Lists.newArrayList();
535    for (int i = 0; i < 3; i++) {
536      list.add(random.nextInt());
537    }
538    runIterator(list, 6);
539  }
540
541  public void testIteratorTesterLarger() throws Exception {
542    runIterator(Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 5);
543  }
544
545  public void testRemoveAt() {
546    long seed = new Random().nextLong();
547    Random random = new Random(seed);
548    int heapSize = 999;
549    int numberOfModifications = 500;
550    MinMaxPriorityQueue<Integer> mmHeap =
551        MinMaxPriorityQueue.expectedSize(heapSize).create();
552    for (int i = 0; i < heapSize; i++) {
553      mmHeap.add(random.nextInt());
554    }
555    for (int i = 0; i < numberOfModifications; i++) {
556      mmHeap.removeAt(random.nextInt(mmHeap.size()));
557      assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact());
558      mmHeap.add(random.nextInt());
559      assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact());
560    }
561  }
562
563  public void testRemoveAt_exhaustive() {
564    int size = 8;
565    List<Integer> expected = createOrderedList(size);
566    for (Collection<Integer> perm : Collections2.permutations(expected)) {
567      for (int i = 0; i < perm.size(); i++) {
568        MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm);
569        q.removeAt(i);
570        assertTrue("Remove at " + i + " perm " + perm, q.isIntact());
571      }
572    }
573  }
574
575  /**
576   * Regression test for bug found.
577   */
578  public void testCorrectOrdering_regression() {
579    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue
580        .create(ImmutableList.of(3, 5, 1, 4, 7));
581    List<Integer> expected = ImmutableList.of(1, 3, 4, 5, 7);
582    List<Integer> actual = new ArrayList<Integer>(5);
583    for (int i = 0; i < expected.size(); i++) {
584      actual.add(q.pollFirst());
585    }
586    assertEquals(expected, actual);
587  }
588
589  public void testCorrectOrdering_smallHeapsPollFirst() {
590    for (int size = 2; size < 16; size++) {
591      for (int attempts = 0; attempts < size * (size - 1); attempts++) {
592        ArrayList<Integer> elements = createOrderedList(size);
593        List<Integer> expected = ImmutableList.copyOf(elements);
594        MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
595        long seed = insertRandomly(elements, q);
596        while (!q.isEmpty()) {
597          elements.add(q.pollFirst());
598        }
599        assertEquals("Using seed " + seed, expected, elements);
600      }
601    }
602  }
603
604  public void testCorrectOrdering_smallHeapsPollLast() {
605    for (int size = 2; size < 16; size++) {
606      for (int attempts = 0; attempts < size * (size - 1); attempts++) {
607        ArrayList<Integer> elements = createOrderedList(size);
608        List<Integer> expected = ImmutableList.copyOf(elements);
609        MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
610        long seed = insertRandomly(elements, q);
611        while (!q.isEmpty()) {
612          elements.add(0, q.pollLast());
613        }
614        assertEquals("Using seed " + seed, expected, elements);
615      }
616    }
617  }
618
619  public void testCorrectOrdering_mediumHeapsPollFirst() {
620    for (int attempts = 0; attempts < 5000; attempts++) {
621      int size = new Random().nextInt(256) + 16;
622      ArrayList<Integer> elements = createOrderedList(size);
623      List<Integer> expected = ImmutableList.copyOf(elements);
624      MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
625      long seed = insertRandomly(elements, q);
626      while (!q.isEmpty()) {
627        elements.add(q.pollFirst());
628      }
629      assertEquals("Using seed " + seed, expected, elements);
630    }
631  }
632
633  /**
634   * Regression test for bug found in random testing.
635   */
636  public void testCorrectOrdering_73ElementBug() {
637    int size = 73;
638    long seed = 7522346378524621981L;
639    ArrayList<Integer> elements = createOrderedList(size);
640    List<Integer> expected = ImmutableList.copyOf(elements);
641    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
642    insertRandomly(elements, q, new Random(seed));
643    assertTrue(q.isIntact());
644    while (!q.isEmpty()) {
645      elements.add(q.pollFirst());
646      assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
647    }
648    assertEquals("Using seed " + seed, expected, elements);
649  }
650
651  public void testCorrectOrdering_mediumHeapsPollLast() {
652    for (int attempts = 0; attempts < 5000; attempts++) {
653      int size = new Random().nextInt(256) + 16;
654      ArrayList<Integer> elements = createOrderedList(size);
655      List<Integer> expected = ImmutableList.copyOf(elements);
656      MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
657      long seed = insertRandomly(elements, q);
658      while (!q.isEmpty()) {
659        elements.add(0, q.pollLast());
660      }
661      assertEquals("Using seed " + seed, expected, elements);
662    }
663  }
664
665  public void testCorrectOrdering_randomAccess() {
666    long seed = new Random().nextLong();
667    Random random = new Random(seed);
668    PriorityQueue<Integer> control = new PriorityQueue<Integer>();
669    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create();
670    for (int i = 0; i < 73; i++) { // 73 is a childless uncle case.
671      Integer element = random.nextInt();
672      control.add(element);
673      assertTrue(q.add(element));
674    }
675    assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact());
676    for (int i = 0; i < 500000; i++) {
677      if (random.nextBoolean()) {
678        Integer element = random.nextInt();
679        control.add(element);
680        q.add(element);
681      } else {
682        assertEquals("Using seed " + seed, control.poll(), q.pollFirst());
683      }
684    }
685    while (!control.isEmpty()) {
686      assertEquals("Using seed " + seed, control.poll(), q.pollFirst());
687    }
688    assertTrue(q.isEmpty());
689  }
690
691  public void testExhaustive_pollAndPush() {
692    int size = 8;
693    List<Integer> expected = createOrderedList(size);
694    for (Collection<Integer> perm : Collections2.permutations(expected)) {
695      MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm);
696      List<Integer> elements = Lists.newArrayListWithCapacity(size);
697      while (!q.isEmpty()) {
698        Integer next = q.pollFirst();
699        for (int i = 0; i <= size; i++) {
700          assertTrue(q.add(i));
701          assertTrue(q.add(next));
702          assertTrue(q.remove(i));
703          assertEquals(next, q.poll());
704        }
705        elements.add(next);
706      }
707      assertEquals("Started with " + perm, expected, elements);
708    }
709  }
710
711  /**
712   * Regression test for b/4124577
713   */
714  public void testRegression_dataCorruption() {
715    int size = 8;
716    List<Integer> expected = createOrderedList(size);
717    MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(expected);
718    List<Integer> contents = Lists.newArrayList(expected);
719    List<Integer> elements = Lists.newArrayListWithCapacity(size);
720    while (!q.isEmpty()) {
721      assertThat(q).has().exactlyAs(contents);
722      Integer next = q.pollFirst();
723      contents.remove(next);
724      assertThat(q).has().exactlyAs(contents);
725      for (int i = 0; i <= size; i++) {
726        q.add(i);
727        contents.add(i);
728        assertThat(q).has().exactlyAs(contents);
729        q.add(next);
730        contents.add(next);
731        assertThat(q).has().exactlyAs(contents);
732        q.remove(i);
733        assertTrue(contents.remove(Integer.valueOf(i)));
734        assertThat(q).has().exactlyAs(contents);
735        assertEquals(next, q.poll());
736        contents.remove(next);
737        assertThat(q).has().exactlyAs(contents);
738      }
739      elements.add(next);
740    }
741    assertEquals(expected, elements);
742  }
743
744  /**
745   * Returns the seed used for the randomization.
746   */
747  private long insertRandomly(ArrayList<Integer> elements,
748      MinMaxPriorityQueue<Integer> q) {
749    long seed = new Random().nextLong();
750    Random random = new Random(seed);
751    insertRandomly(elements, q, random);
752    return seed;
753  }
754
755  private void insertRandomly(ArrayList<Integer> elements, MinMaxPriorityQueue<Integer> q,
756      Random random) {
757    while (!elements.isEmpty()) {
758      int selectedIndex = random.nextInt(elements.size());
759      q.offer(elements.remove(selectedIndex));
760    }
761  }
762
763  private ArrayList<Integer> createOrderedList(int size) {
764    ArrayList<Integer> elements = new ArrayList<Integer>(size);
765    for (int i = 0; i < size; i++) {
766      elements.add(i);
767    }
768    return elements;
769  }
770
771  public void testIsEvenLevel() {
772    assertTrue(MinMaxPriorityQueue.isEvenLevel(0));
773    assertFalse(MinMaxPriorityQueue.isEvenLevel(1));
774    assertFalse(MinMaxPriorityQueue.isEvenLevel(2));
775    assertTrue(MinMaxPriorityQueue.isEvenLevel(3));
776
777    assertFalse(MinMaxPriorityQueue.isEvenLevel((1 << 10) - 2));
778    assertTrue(MinMaxPriorityQueue.isEvenLevel((1 << 10) - 1));
779
780    int i = 1 << 29;
781    assertTrue(MinMaxPriorityQueue.isEvenLevel(i - 2));
782    assertFalse(MinMaxPriorityQueue.isEvenLevel(i - 1));
783    assertFalse(MinMaxPriorityQueue.isEvenLevel(i));
784
785    i = 1 << 30;
786    assertFalse(MinMaxPriorityQueue.isEvenLevel(i - 2));
787    assertTrue(MinMaxPriorityQueue.isEvenLevel(i - 1));
788    assertTrue(MinMaxPriorityQueue.isEvenLevel(i));
789
790    // 1 << 31 is negative because of overflow, 1 << 31 - 1 is positive
791    // since isEvenLevel adds 1, we need to do - 2.
792    assertTrue(MinMaxPriorityQueue.isEvenLevel((1 << 31) - 2));
793    assertTrue(MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE - 1));
794    try {
795      MinMaxPriorityQueue.isEvenLevel((1 << 31) - 1);
796      fail("Should overflow");
797    } catch (IllegalStateException e) {
798      // expected
799    }
800    try {
801      MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE);
802      fail("Should overflow");
803    } catch (IllegalStateException e) {
804      // expected
805    }
806    try {
807      MinMaxPriorityQueue.isEvenLevel(1 << 31);
808      fail("Should be negative");
809    } catch (IllegalStateException e) {
810      // expected
811    }
812    try {
813      MinMaxPriorityQueue.isEvenLevel(Integer.MIN_VALUE);
814      fail("Should be negative");
815    } catch (IllegalStateException e) {
816      // expected
817    }
818  }
819
820  public void testNullPointers() {
821    NullPointerTester tester = new NullPointerTester();
822    tester.testAllPublicConstructors(MinMaxPriorityQueue.class);
823    tester.testAllPublicStaticMethods(MinMaxPriorityQueue.class);
824    tester.testAllPublicInstanceMethods(MinMaxPriorityQueue.<String>create());
825  }
826
827  private static void insertIntoReplica(
828      Map<Integer, AtomicInteger> replica,
829      int newValue) {
830    if (replica.containsKey(newValue)) {
831      replica.get(newValue).incrementAndGet();
832    } else {
833      replica.put(newValue, new AtomicInteger(1));
834    }
835  }
836
837  private static void removeMinFromReplica(
838      SortedMap<Integer, AtomicInteger> replica,
839      int minValue) {
840    Integer replicatedMinValue = replica.firstKey();
841    assertEquals(replicatedMinValue, (Integer) minValue);
842    removeFromReplica(replica, replicatedMinValue);
843  }
844
845  private static void removeMaxFromReplica(
846      SortedMap<Integer, AtomicInteger> replica,
847      int maxValue) {
848    Integer replicatedMaxValue = replica.lastKey();
849    assertTrue("maxValue is incorrect", replicatedMaxValue == maxValue);
850    removeFromReplica(replica, replicatedMaxValue);
851  }
852
853  private static void removeFromReplica(
854      Map<Integer, AtomicInteger> replica, int value) {
855    AtomicInteger numOccur = replica.get(value);
856    if (numOccur.decrementAndGet() == 0) {
857      replica.remove(value);
858    }
859  }
860}
861