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