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