11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2008 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport static com.google.common.truth.Truth.assertThat; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffin 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.testing.IteratorFeature; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.testing.IteratorTester; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.testing.NullPointerTester; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 250888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport junit.framework.TestCase; 260888a09821a98ac0680fad765217302858e70fa4Paul Duffin 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.ArrayList; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Arrays; 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Collection; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.ConcurrentModificationException; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.NoSuchElementException; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.PriorityQueue; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Random; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.SortedMap; 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.atomic.AtomicInteger; 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unit test for {@link MinMaxPriorityQueue}. 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Alexei Stolboushkin 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Sverre Sundsdal 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class MinMaxPriorityQueueTest extends TestCase { 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Ordering<Integer> SOME_COMPARATOR = Ordering.natural().reverse(); 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Overkill alert! Test all combinations of 0-2 options during creation. 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_simple() { 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_comparator() { 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .orderedBy(SOME_COMPARATOR) 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(SOME_COMPARATOR, queue.comparator()); 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_expectedSize() { 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .expectedSize(8) 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(8, queue.capacity()); 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_expectedSize_comparator() { 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .orderedBy(SOME_COMPARATOR) 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .expectedSize(8) 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(8, queue.capacity()); 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(SOME_COMPARATOR, queue.comparator()); 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_maximumSize() { 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .maximumSize(42) 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(42, queue.maximumSize); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_comparator_maximumSize() { 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .orderedBy(SOME_COMPARATOR) 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .maximumSize(42) 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(42, queue.maximumSize); 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(SOME_COMPARATOR, queue.comparator()); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_expectedSize_maximumSize() { 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .expectedSize(8) 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .maximumSize(42) 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(); 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(8, queue.capacity()); 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(42, queue.maximumSize); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final List<Integer> NUMBERS = 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableList.of(4, 8, 15, 16, 23, 42); 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_withContents() { 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(NUMBERS); 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, queue.size()); 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_comparator_withContents() { 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .orderedBy(SOME_COMPARATOR) 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(NUMBERS); 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, queue.size()); 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(SOME_COMPARATOR, queue.comparator()); 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_expectedSize_withContents() { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .expectedSize(8) 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(NUMBERS); 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, queue.size()); 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(8, queue.capacity()); 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkUnbounded(queue); 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_maximumSize_withContents() { 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .maximumSize(42) 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(NUMBERS); 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, queue.size()); 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(11, queue.capacity()); 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(42, queue.maximumSize); 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNatural(queue); 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Now test everything at once 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreation_allOptions() { 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> queue = MinMaxPriorityQueue 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .orderedBy(SOME_COMPARATOR) 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .expectedSize(8) 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .maximumSize(42) 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(NUMBERS); 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, queue.size()); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(8, queue.capacity()); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(42, queue.maximumSize); 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(SOME_COMPARATOR, queue.comparator()); 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO: tests that check the weird interplay between expected size, 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // maximum size, size of initial contents, default capacity... 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static void checkNatural(MinMaxPriorityQueue<Integer> queue) { 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertSame(Ordering.natural(), queue.comparator()); 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static void checkUnbounded(MinMaxPriorityQueue<Integer> queue) { 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(Integer.MAX_VALUE, queue.maximumSize); 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testHeapIntact() { 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(0); 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int heapSize = 999; 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int numberOfModifications = 500; 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.expectedSize(heapSize).create(); 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this map would contain the same exact elements as the MinMaxHeap; the 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * value in the map is the number of occurrences of the key. 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<Integer, AtomicInteger> replica = Maps.newTreeMap(); 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Empty heap should be OK", mmHeap.isIntact()); 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < heapSize; i++) { 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int randomInt = random.nextInt(); 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.offer(randomInt); 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert insertIntoReplica(replica, randomInt); 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("MinMaxHeap not intact after " + heapSize + " insertions", 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.isIntact()); 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(heapSize, mmHeap.size()); 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int currentHeapSize = heapSize; 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < numberOfModifications; i++) { 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (random.nextBoolean()) { 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* insert a new element */ 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int randomInt = random.nextInt(); 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.offer(randomInt); 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert insertIntoReplica(replica, randomInt); 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert currentHeapSize++; 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* remove either min or max */ 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (random.nextBoolean()) { 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert removeMinFromReplica(replica, mmHeap.poll()); 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert removeMaxFromReplica(replica, mmHeap.pollLast()); 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Integer v : replica.keySet()) { 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("MinMax queue has lost " + v, mmHeap.contains(v)); 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(mmHeap.isIntact()); 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert currentHeapSize--; 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(currentHeapSize, mmHeap.size()); 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(currentHeapSize, mmHeap.size()); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap not intact after " + numberOfModifications + 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert " random mixture of operations", mmHeap.isIntact()); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testSmall() { 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(1); 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(4); 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(2); 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(3); 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(4, (int) mmHeap.pollLast()); 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, (int) mmHeap.peekLast()); 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, (int) mmHeap.pollLast()); 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, (int) mmHeap.peek()); 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(2, (int) mmHeap.peekLast()); 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(2, (int) mmHeap.pollLast()); 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, (int) mmHeap.peek()); 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, (int) mmHeap.peekLast()); 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, (int) mmHeap.pollLast()); 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNull(mmHeap.peek()); 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNull(mmHeap.peekLast()); 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNull(mmHeap.pollLast()); 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testSmallMinHeap() { 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(1); 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(3); 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(2); 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, (int) mmHeap.peek()); 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(1, (int) mmHeap.poll()); 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, (int) mmHeap.peekLast()); 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(2, (int) mmHeap.peek()); 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(2, (int) mmHeap.poll()); 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, (int) mmHeap.peekLast()); 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, (int) mmHeap.peek()); 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, (int) mmHeap.poll()); 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNull(mmHeap.peekLast()); 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNull(mmHeap.peek()); 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertNull(mmHeap.poll()); 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRemove() { 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4, 47, 1, 5, 3, 0)); 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initally", mmHeap.isIntact()); 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(9, mmHeap.size()); 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.remove(5); 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(8, mmHeap.size()); 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove()", mmHeap.isIntact()); 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(47, (int) mmHeap.pollLast()); 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(4, (int) mmHeap.pollLast()); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.removeAll(Lists.newArrayList(2, 3)); 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, mmHeap.size()); 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after removeAll()", mmHeap.isIntact()); 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testContains() { 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList(1, 1, 2)); 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, mmHeap.size()); 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Heap does not contain null", mmHeap.contains(null)); 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Heap does not contain 3", mmHeap.contains(3)); 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Heap does not contain 3", mmHeap.remove(3)); 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(3, mmHeap.size()); 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove()", mmHeap.isIntact()); 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap contains two 1's", mmHeap.contains(1)); 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap contains two 1's", mmHeap.remove(1)); 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap contains 1", mmHeap.contains(1)); 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap contains 1", mmHeap.remove(1)); 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Heap does not contain 1", mmHeap.contains(1)); 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap contains 2", mmHeap.remove(2)); 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, mmHeap.size()); 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Heap does not contain anything", mmHeap.contains(1)); 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Heap does not contain anything", mmHeap.remove(2)); 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorPastEndException() { 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList(1, 2)); 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Integer> it = mmHeap.iterator(); 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Iterator has reached end prematurely", it.hasNext()); 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.next(); 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.next(); 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.next(); 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail("No exception thrown when iterating past end of heap"); 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NoSuchElementException e) { 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // expected error 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorConcurrentModification() { 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList(1, 2, 3, 4)); 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Integer> it = mmHeap.iterator(); 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Iterator has reached end prematurely", it.hasNext()); 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.next(); 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.next(); 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.remove(4); 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.next(); 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail("No exception thrown when iterating a modified heap"); 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ConcurrentModificationException e) { 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // expected error 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Tests a failure caused by fix to childless uncle issue. 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorRegressionChildlessUncle() { 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ArrayList<Integer> initial = Lists.newArrayList( 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 15, 13, 8, 9, 10, 11, 14); 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(initial); 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact()); 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.remove(9); 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.remove(11); 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.remove(10); 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Now we're in the critical state: [1, 15, 13, 8, 14] 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Removing 8 while iterating caused duplicates in iteration result. 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> result = Lists.newArrayListWithCapacity(initial.size()); 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Iterator<Integer> iter = q.iterator(); iter.hasNext();) { 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer value = iter.next(); 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert result.add(value); 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (value == 8) { 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert iter.remove(); 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(q.isIntact()); 3583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(result).has().exactly(1, 15, 13, 8, 14); 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This tests a special case of the removeAt() call. Moving an element 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sideways on the heap could break the invariants. Sometimes we need to 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * bubble an element up instead of trickling down. See implementation. 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testInvalidatingRemove() { 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList( 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600)); 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(15, mmHeap.size()); 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.remove(12); 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(14, mmHeap.size()); 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove()", mmHeap.isIntact()); 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This tests a more obscure special case, but otherwise similar to above. 3791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testInvalidatingRemove2() { 3811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 3821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> values = Lists.newArrayList( 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 300, 400, 500, 600, 4, 5, 3841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6, 7, 8, 9, 4, 5, 200, 250); 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(values); 3861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(25, mmHeap.size()); 3871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 3881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.remove(2); 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(24, mmHeap.size()); 3901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove()", mmHeap.isIntact()); 3911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert values.removeAll(Lists.newArrayList(2)); 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(values.size(), mmHeap.size()); 3931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(values.containsAll(mmHeap)); 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(mmHeap.containsAll(values)); 3951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorInvalidatingIteratorRemove() { 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 3991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList( 4001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 20, 100, 2, 3, 30, 40)); 4011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(7, mmHeap.size()); 4021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 4031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Integer> it = mmHeap.iterator(); 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 1, it.next()); 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 20, it.next()); 4061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 100, it.next()); 4071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 2, it.next()); 4081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.remove(); 4091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(mmHeap.contains(2)); 4101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(it.hasNext()); 4111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 3, it.next()); 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(it.hasNext()); 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 30, it.next()); 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(it.hasNext()); 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 40, it.next()); 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(it.hasNext()); 4171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, mmHeap.size()); 4181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove()", mmHeap.isIntact()); 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(mmHeap.contains(2)); 4201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This tests that it.remove() above actually changed the order. It 4221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // indicates that the value 40 was stored in forgetMeNot, so it is 4231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // returned in the last call to it.next(). Without it, 30 should be the last 4241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // item returned by the iterator. 4251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer lastItem = 0; 4261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Integer tmp : mmHeap) { 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert lastItem = tmp; 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 30, lastItem); 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This tests a special case where removeAt has to trickle an element 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * first down one level from a min to a max level, then up one level above 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the index of the removed element. 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * It also tests that skipMe in the iterator plays nicely with 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * forgetMeNot. 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorInvalidatingIteratorRemove2() { 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.create(); 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.addAll(Lists.newArrayList( 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1, 20, 1000, 2, 3, 30, 40, 10, 11, 12, 13, 200, 300, 500, 400)); 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 4441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Integer> it = mmHeap.iterator(); 4451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 1, it.next()); 4461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 20, it.next()); 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 1000, it.next()); 4481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 2, it.next()); 4491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.remove(); 4501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove", mmHeap.isIntact()); 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 10, it.next()); 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 3, it.next()); 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert it.remove(); 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact after remove", mmHeap.isIntact()); 4551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 12, it.next()); 4561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 30, it.next()); 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 40, it.next()); 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Skipping 20 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 11, it.next()); 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Skipping 400 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 13, it.next()); 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 200, it.next()); 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 300, it.next()); 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Last two from forgetMeNot. 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 400, it.next()); 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals((Integer) 500, it.next()); 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRemoveFromStringHeap() { 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<String> mmHeap = 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.expectedSize(5).create(); 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.addAll(mmHeap, 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert "foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric"); 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("bar", mmHeap.peek()); 4761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("sergey", mmHeap.peekLast()); 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(7, mmHeap.size()); 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Could not remove larry", mmHeap.remove("larry")); 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(6, mmHeap.size()); 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("heap contains larry which has been removed", 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.contains("larry")); 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("heap does not contain sergey", 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.contains("sergey")); 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Could not remove larry", mmHeap.removeAll( 4851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Lists.newArrayList("sergey", "eric"))); 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse("Could remove nikesh which is not in the heap", 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.remove("nikesh")); 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(4, mmHeap.size()); 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreateWithOrdering() { 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<String> mmHeap = 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.orderedBy(Ordering.natural().reverse()).create(); 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.addAll(mmHeap, 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert "foo", "bar", "foobar", "barfoo", "larry", "sergey", "eric"); 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("sergey", mmHeap.peek()); 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("bar", mmHeap.peekLast()); 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCreateWithCapacityAndOrdering() { 5021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = MinMaxPriorityQueue.orderedBy( 5031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Ordering.natural().reverse()).expectedSize(5).create(); 5041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collections.addAll(mmHeap, 1, 7, 2, 56, 2, 5, 23, 68, 0, 3); 5051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Heap is not intact initially", mmHeap.isIntact()); 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(68, (int) mmHeap.peek()); 5071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(0, (int) mmHeap.peekLast()); 5081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private <T extends Comparable<T>> void runIterator( 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final List<T> values, int steps) throws Exception { 5121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert IteratorTester<T> tester = 5131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new IteratorTester<T>( 5141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert steps, 5151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert IteratorFeature.MODIFIABLE, 5161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Lists.newLinkedList(values), 5171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert IteratorTester.KnownOrder.UNKNOWN_ORDER) { 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private MinMaxPriorityQueue<T> mmHeap; 5191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected Iterator<T> newTargetIterator() { 5201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap = MinMaxPriorityQueue.create(values); 5211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return mmHeap.iterator(); 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected void verify(List<T> elements) { 5241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(Sets.newHashSet(elements), 5251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Sets.newHashSet(mmHeap.iterator())); 5260888a09821a98ac0680fad765217302858e70fa4Paul Duffin assertTrue("Invalid MinMaxHeap: " + mmHeap, mmHeap.isIntact()); 5271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 5291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.test(); 5301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorTester() throws Exception { 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(0); 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> list = Lists.newArrayList(); 5351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 3; i++) { 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert list.add(random.nextInt()); 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert runIterator(list, 6); 5391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIteratorTesterLarger() throws Exception { 5421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert runIterator(Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 5); 5431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRemoveAt() { 5461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = new Random().nextLong(); 5471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(seed); 5481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int heapSize = 999; 5491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int numberOfModifications = 500; 5501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> mmHeap = 5511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.expectedSize(heapSize).create(); 5521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < heapSize; i++) { 5531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(random.nextInt()); 5541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < numberOfModifications; i++) { 5561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.removeAt(random.nextInt(mmHeap.size())); 5571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact()); 5581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert mmHeap.add(random.nextInt()); 5591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("Modification " + i + " of seed " + seed, mmHeap.isIntact()); 5601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5637dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testRemoveAt_exhaustive() { 5647dd252788645e940eada959bdde927426e2531c9Paul Duffin int size = 8; 5657dd252788645e940eada959bdde927426e2531c9Paul Duffin List<Integer> expected = createOrderedList(size); 5667dd252788645e940eada959bdde927426e2531c9Paul Duffin for (Collection<Integer> perm : Collections2.permutations(expected)) { 5677dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < perm.size(); i++) { 5687dd252788645e940eada959bdde927426e2531c9Paul Duffin MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm); 5697dd252788645e940eada959bdde927426e2531c9Paul Duffin q.removeAt(i); 5707dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue("Remove at " + i + " perm " + perm, q.isIntact()); 5717dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5727dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5747dd252788645e940eada959bdde927426e2531c9Paul Duffin 5751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Regression test for bug found. 5771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 5781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_regression() { 5791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue 5801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .create(ImmutableList.of(3, 5, 1, 4, 7)); 5811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = ImmutableList.of(1, 3, 4, 5, 7); 5821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> actual = new ArrayList<Integer>(5); 5831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < expected.size(); i++) { 5841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert actual.add(q.pollFirst()); 5851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(expected, actual); 5871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_smallHeapsPollFirst() { 5901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int size = 2; size < 16; size++) { 5911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int attempts = 0; attempts < size * (size - 1); attempts++) { 5921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Integer> elements = createOrderedList(size); 5931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = ImmutableList.copyOf(elements); 5941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(); 5951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = insertRandomly(elements, q); 5961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!q.isEmpty()) { 5971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(q.pollFirst()); 5981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 5991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, expected, elements); 6001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_smallHeapsPollLast() { 6051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int size = 2; size < 16; size++) { 6061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int attempts = 0; attempts < size * (size - 1); attempts++) { 6071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Integer> elements = createOrderedList(size); 6081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = ImmutableList.copyOf(elements); 6091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(); 6101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = insertRandomly(elements, q); 6111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!q.isEmpty()) { 6121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(0, q.pollLast()); 6131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, expected, elements); 6151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_mediumHeapsPollFirst() { 6201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int attempts = 0; attempts < 5000; attempts++) { 6211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int size = new Random().nextInt(256) + 16; 6221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Integer> elements = createOrderedList(size); 6231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = ImmutableList.copyOf(elements); 6241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(); 6251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = insertRandomly(elements, q); 6261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!q.isEmpty()) { 6271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(q.pollFirst()); 6281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, expected, elements); 6301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 6341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Regression test for bug found in random testing. 6351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_73ElementBug() { 6371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int size = 73; 6381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = 7522346378524621981L; 6391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Integer> elements = createOrderedList(size); 6401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = ImmutableList.copyOf(elements); 6411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(); 6421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert insertRandomly(elements, q, new Random(seed)); 6431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(q.isIntact()); 6441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!q.isEmpty()) { 6451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(q.pollFirst()); 6461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact()); 6471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, expected, elements); 6491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_mediumHeapsPollLast() { 6521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int attempts = 0; attempts < 5000; attempts++) { 6531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int size = new Random().nextInt(256) + 16; 6541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Integer> elements = createOrderedList(size); 6551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = ImmutableList.copyOf(elements); 6561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(); 6571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = insertRandomly(elements, q); 6581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!q.isEmpty()) { 6591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(0, q.pollLast()); 6601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, expected, elements); 6621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testCorrectOrdering_randomAccess() { 6661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = new Random().nextLong(); 6671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(seed); 6681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert PriorityQueue<Integer> control = new PriorityQueue<Integer>(); 6691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(); 6701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 73; i++) { // 73 is a childless uncle case. 6711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer element = random.nextInt(); 6721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert control.add(element); 6731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(q.add(element)); 6741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("State " + Arrays.toString(q.toArray()), q.isIntact()); 6761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < 500000; i++) { 6771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (random.nextBoolean()) { 6781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer element = random.nextInt(); 6791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert control.add(element); 6801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.add(element); 6811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 6821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, control.poll(), q.pollFirst()); 6831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!control.isEmpty()) { 6861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals("Using seed " + seed, control.poll(), q.pollFirst()); 6871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(q.isEmpty()); 6891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6917dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testExhaustive_pollAndPush() { 6927dd252788645e940eada959bdde927426e2531c9Paul Duffin int size = 8; 6937dd252788645e940eada959bdde927426e2531c9Paul Duffin List<Integer> expected = createOrderedList(size); 6947dd252788645e940eada959bdde927426e2531c9Paul Duffin for (Collection<Integer> perm : Collections2.permutations(expected)) { 6957dd252788645e940eada959bdde927426e2531c9Paul Duffin MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(perm); 6967dd252788645e940eada959bdde927426e2531c9Paul Duffin List<Integer> elements = Lists.newArrayListWithCapacity(size); 6977dd252788645e940eada959bdde927426e2531c9Paul Duffin while (!q.isEmpty()) { 6987dd252788645e940eada959bdde927426e2531c9Paul Duffin Integer next = q.pollFirst(); 6997dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i <= size; i++) { 7007dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(q.add(i)); 7017dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(q.add(next)); 7027dd252788645e940eada959bdde927426e2531c9Paul Duffin assertTrue(q.remove(i)); 7037dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals(next, q.poll()); 7047dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7057dd252788645e940eada959bdde927426e2531c9Paul Duffin elements.add(next); 7067dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7077dd252788645e940eada959bdde927426e2531c9Paul Duffin assertEquals("Started with " + perm, expected, elements); 7087dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7097dd252788645e940eada959bdde927426e2531c9Paul Duffin } 7107dd252788645e940eada959bdde927426e2531c9Paul Duffin 7111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Regression test for b/4124577 7131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testRegression_dataCorruption() { 7151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int size = 8; 7161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> expected = createOrderedList(size); 7171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q = MinMaxPriorityQueue.create(expected); 7181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> contents = Lists.newArrayList(expected); 7191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Integer> elements = Lists.newArrayListWithCapacity(size); 7201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!q.isEmpty()) { 7213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(q).has().exactlyAs(contents); 7221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer next = q.pollFirst(); 7231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert contents.remove(next); 7243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(q).has().exactlyAs(contents); 7251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i <= size; i++) { 7261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.add(i); 7271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert contents.add(i); 7283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(q).has().exactlyAs(contents); 7291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.add(next); 7301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert contents.add(next); 7313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(q).has().exactlyAs(contents); 7321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.remove(i); 7331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(contents.remove(Integer.valueOf(i))); 7343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(q).has().exactlyAs(contents); 7351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(next, q.poll()); 7361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert contents.remove(next); 7373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin assertThat(q).has().exactlyAs(contents); 7381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(next); 7401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(expected, elements); 7421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the seed used for the randomization. 7461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private long insertRandomly(ArrayList<Integer> elements, 7481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue<Integer> q) { 7491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long seed = new Random().nextLong(); 7501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random = new Random(seed); 7511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert insertRandomly(elements, q, random); 7521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return seed; 7531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void insertRandomly(ArrayList<Integer> elements, MinMaxPriorityQueue<Integer> q, 7561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Random random) { 7571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (!elements.isEmpty()) { 7581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int selectedIndex = random.nextInt(elements.size()); 7591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert q.offer(elements.remove(selectedIndex)); 7601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private ArrayList<Integer> createOrderedList(int size) { 7641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Integer> elements = new ArrayList<Integer>(size); 7651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < size; i++) { 7661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements.add(i); 7671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elements; 7691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void testIsEvenLevel() { 7721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel(0)); 7731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(MinMaxPriorityQueue.isEvenLevel(1)); 7741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(MinMaxPriorityQueue.isEvenLevel(2)); 7751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel(3)); 7761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(MinMaxPriorityQueue.isEvenLevel((1 << 10) - 2)); 7781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel((1 << 10) - 1)); 7791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int i = 1 << 29; 7811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel(i - 2)); 7821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(MinMaxPriorityQueue.isEvenLevel(i - 1)); 7831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(MinMaxPriorityQueue.isEvenLevel(i)); 7841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert i = 1 << 30; 7861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertFalse(MinMaxPriorityQueue.isEvenLevel(i - 2)); 7871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel(i - 1)); 7881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel(i)); 7891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // 1 << 31 is negative because of overflow, 1 << 31 - 1 is positive 7911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // since isEvenLevel adds 1, we need to do - 2. 7921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel((1 << 31) - 2)); 7931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue(MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE - 1)); 7941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 7951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.isEvenLevel((1 << 31) - 1); 7961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail("Should overflow"); 7971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalStateException e) { 7981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // expected 7991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 8011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.isEvenLevel(Integer.MAX_VALUE); 8021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail("Should overflow"); 8031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalStateException e) { 8041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // expected 8051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 8071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.isEvenLevel(1 << 31); 8081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail("Should be negative"); 8091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalStateException e) { 8101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // expected 8111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 8131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MinMaxPriorityQueue.isEvenLevel(Integer.MIN_VALUE); 8141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert fail("Should be negative"); 8151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (IllegalStateException e) { 8161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // expected 8171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8207dd252788645e940eada959bdde927426e2531c9Paul Duffin public void testNullPointers() { 8211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NullPointerTester tester = new NullPointerTester(); 8221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.testAllPublicConstructors(MinMaxPriorityQueue.class); 8231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.testAllPublicStaticMethods(MinMaxPriorityQueue.class); 8241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert tester.testAllPublicInstanceMethods(MinMaxPriorityQueue.<String>create()); 8251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static void insertIntoReplica( 8281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<Integer, AtomicInteger> replica, 8291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int newValue) { 8301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (replica.containsKey(newValue)) { 8311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert replica.get(newValue).incrementAndGet(); 8321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 8331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert replica.put(newValue, new AtomicInteger(1)); 8341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static void removeMinFromReplica( 8381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<Integer, AtomicInteger> replica, 8391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int minValue) { 8401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer replicatedMinValue = replica.firstKey(); 8411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertEquals(replicatedMinValue, (Integer) minValue); 8421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert removeFromReplica(replica, replicatedMinValue); 8431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static void removeMaxFromReplica( 8461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<Integer, AtomicInteger> replica, 8471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int maxValue) { 8481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Integer replicatedMaxValue = replica.lastKey(); 8491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert assertTrue("maxValue is incorrect", replicatedMaxValue == maxValue); 8501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert removeFromReplica(replica, replicatedMaxValue); 8511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static void removeFromReplica( 8541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<Integer, AtomicInteger> replica, int value) { 8551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AtomicInteger numOccur = replica.get(value); 8561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (numOccur.decrementAndGet() == 0) { 8571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert replica.remove(value); 8581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 861