1 /* 2 * Copyright (C) 2007 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 java.util.Arrays.asList; 20 21 import com.google.common.annotations.GwtCompatible; 22 import com.google.common.annotations.GwtIncompatible; 23 import com.google.common.collect.Multiset.Entry; 24 import com.google.common.collect.testing.google.UnmodifiableCollectionTests; 25 import com.google.common.testing.SerializableTester; 26 27 import java.util.Collections; 28 import java.util.HashSet; 29 import java.util.Iterator; 30 import java.util.NoSuchElementException; 31 import java.util.Set; 32 33 /** 34 * Common tests for a {@link Multiset}. 35 * 36 * @author Kevin Bourrillion 37 */ 38 @GwtCompatible(emulated = true) 39 public abstract class AbstractMultisetTest extends AbstractCollectionTest { 40 41 @Override protected abstract <E> Multiset<E> create(); 42 43 protected Multiset<String> ms; 44 45 // public for GWT 46 @Override public void setUp() throws Exception { 47 super.setUp(); 48 c = ms = create(); 49 } 50 51 /** 52 * Validates that multiset size returned by {@code size()} is the same as the 53 * size generated by summing the counts of all multiset entries. 54 */ 55 protected void assertSize(Multiset<String> multiset) { 56 long size = 0; 57 for (Multiset.Entry<String> entry : multiset.entrySet()) { 58 size += entry.getCount(); 59 } 60 assertEquals((int) Math.min(size, Integer.MAX_VALUE), multiset.size()); 61 } 62 63 protected void assertSize() { 64 assertSize(ms); 65 } 66 67 @Override protected void assertContents(String... expected) { 68 super.assertContents(expected); 69 assertSize(); 70 } 71 72 /** 73 * Don't run {@code NullPointerTester} on multisets, since they fail with 74 * Java 6 due to a bug in the JDK, as illustrated in the commented out 75 * method {@code HashMultisetTest#testAnnotations()}. 76 */ 77 // TODO: Figure out if this is still true... 78 @GwtIncompatible("NullPointerTester") 79 @Override public void testNullPointerExceptions() throws Exception {} 80 81 public void testCountZero() { 82 assertEquals(0, ms.count("a")); 83 assertSize(); 84 } 85 86 public void testCountOne() { 87 ms.add("a"); 88 assertEquals(1, ms.count("a")); 89 assertSize(); 90 } 91 92 public void testCountTwo() { 93 ms.add("a"); 94 ms.add("a"); 95 assertEquals(2, ms.count("a")); 96 assertSize(); 97 } 98 99 public void testCountAfterRemoval() { 100 ms.add("a"); 101 ms.remove("a"); 102 assertEquals(0, ms.count("a")); 103 assertSize(); 104 } 105 106 public void testCountNull() { 107 assertEquals(0, ms.count(null)); 108 } 109 110 public void testCountWrongType() { 111 assertEquals(0, ms.count(new WrongType())); 112 } 113 114 static class WrongType {} 115 116 public void testAddNoneToNone() { 117 assertEquals(0, ms.add("a", 0)); 118 assertContents(); 119 } 120 121 public void testAddNoneToSome() { 122 ms.add("a"); 123 assertEquals(1, ms.add("a", 0)); 124 assertContents("a"); 125 } 126 127 public void testAddSeveralAtOnce() { 128 assertEquals(0, ms.add("a", 3)); 129 assertContents("a", "a", "a"); 130 } 131 132 public void testAddSomeToSome() { 133 ms.add("a", 2); 134 assertEquals(2, ms.add("a", 3)); 135 assertContents("a", "a", "a", "a", "a"); 136 } 137 138 @Override public void testAddSeveralTimes() { 139 assertTrue(ms.add("a")); 140 assertTrue(ms.add("b")); 141 assertTrue(ms.add("a")); 142 assertTrue(ms.add("b")); 143 assertContents("a", "b", "a", "b"); 144 } 145 146 public void testAddNegative() { 147 try { 148 ms.add("a", -1); 149 fail(); 150 } catch (IllegalArgumentException expected) { 151 } 152 assertSize(); 153 } 154 155 @Override public void testEqualsNo() { 156 ms.add("a"); 157 ms.add("b"); 158 ms.add("b"); 159 160 Multiset<String> ms2 = create(); 161 ms2.add("a", 2); 162 ms2.add("b"); 163 164 assertFalse(ms.equals(ms2)); 165 assertSize(); 166 } 167 168 public void testAddTooMany() { 169 ms.add("a", Integer.MAX_VALUE); // so far so good 170 ms.add("b", Integer.MAX_VALUE); // so far so good 171 try { 172 ms.add("a"); 173 fail(); 174 } catch (IllegalArgumentException expected) { 175 } 176 assertSize(); 177 } 178 179 public void testAddAllEmptySet() { 180 c = ms = createSample(); 181 assertFalse(ms.addAll(Collections.<String>emptySet())); 182 assertEquals(createSample(), ms); 183 assertSize(); 184 } 185 186 public void testAddAllEmptyMultiset() { 187 c = ms = createSample(); 188 Multiset<String> empty = create(); 189 assertFalse(ms.addAll(empty)); 190 assertEquals(createSample(), ms); 191 assertSize(); 192 } 193 194 public void testAddAllSet() { 195 c = ms = createSample(); 196 Set<String> more = ImmutableSet.of("c", "d", "e"); 197 assertTrue(ms.addAll(more)); 198 assertContents("a", "b", "b", "c", "c", "d", "d", "d", "d", "e"); 199 } 200 201 public void testAddAllMultiset() { 202 c = ms = createSample(); 203 Multiset<String> more = HashMultiset.create( 204 asList("c", "c", "d", "d", "e")); 205 assertTrue(ms.addAll(more)); 206 assertContents("a", "b", "b", "c", "c", "c", "d", "d", "d", "d", "d", "e"); 207 } 208 209 public void testRemoveNoneFromNone() { 210 assertEquals(0, ms.remove("a", 0)); 211 assertContents(); 212 } 213 214 public void testRemoveNoneFromSome() { 215 ms.add("a"); 216 assertEquals(1, ms.remove("a", 0)); 217 assertContents("a"); 218 } 219 220 public void testRemoveOneFromNone() { 221 assertEquals(0, ms.remove("a", 1)); 222 assertContents(); 223 } 224 225 public void testRemoveOneFromOne() { 226 ms.add("a"); 227 assertEquals(1, ms.remove("a", 1)); 228 assertContents(); 229 } 230 231 public void testRemoveSomeFromSome() { 232 ms.add("a", 5); 233 assertEquals(5, ms.remove("a", 3)); 234 assertContents("a", "a"); 235 } 236 237 public void testRemoveTooMany() { 238 ms.add("a", 3); 239 assertEquals(3, ms.remove("a", 5)); 240 assertContents(); 241 } 242 243 public void testRemoveNegative() { 244 try { 245 ms.remove("a", -1); 246 fail(); 247 } catch (IllegalArgumentException expected) { 248 } 249 assertSize(); 250 } 251 252 public void testContainsSeveral() { 253 ms.add("a", 3); 254 assertTrue(ms.contains(new String("a"))); 255 assertSize(); 256 } 257 258 public void testContainsAllNo() { 259 ms.add("a", 2); 260 ms.add("b", 3); 261 assertFalse(ms.containsAll(asList("a", "c"))); 262 assertSize(); 263 } 264 265 public void testContainsAllYes() { 266 ms.add("a", 2); 267 ms.add("b", 3); 268 ms.add("c", 4); 269 assertTrue(ms.containsAll(asList("a", "c"))); 270 assertSize(); 271 } 272 273 public void testRemoveAllOfOne() { 274 ms.add("a", 2); 275 ms.add("b"); 276 assertTrue(ms.removeAll(asList("a", "c"))); 277 assertContents("b"); 278 } 279 280 public void testRemoveAllOfDisjoint() { 281 ms.add("a", 2); 282 ms.add("b"); 283 assertFalse(ms.removeAll(asList("c", "d"))); 284 assertContents("a", "a", "b"); 285 } 286 287 public void testRemoveAllOfEverything() { 288 ms.add("a", 2); 289 ms.add("b"); 290 assertTrue(ms.removeAll(asList("a", "b"))); 291 assertContents(); 292 } 293 294 public void testRetainAllOfOne() { 295 ms.add("a", 2); 296 ms.add("b"); 297 assertTrue(ms.retainAll(asList("a", "c"))); 298 assertContents("a", "a"); 299 } 300 301 public void testRetainAllOfDisjoint() { 302 ms.add("a", 2); 303 ms.add("b"); 304 assertTrue(ms.retainAll(asList("c", "d"))); 305 assertContents(); 306 } 307 308 public void testRetainAllOfEverything() { 309 ms.add("a", 2); 310 ms.add("b"); 311 assertFalse(ms.retainAll(asList("a", "b"))); 312 assertContents("a", "a", "b"); 313 } 314 315 public void testContainsAllVacuousViaElementSet() { 316 assertTrue(ms.elementSet().containsAll(Collections.emptySet())); 317 } 318 319 public void testContainsAllNoViaElementSet() { 320 ms.add("a", 2); 321 ms.add("b", 3); 322 assertFalse(ms.elementSet().containsAll(asList("a", "c"))); 323 assertSize(); 324 } 325 326 public void testContainsAllYesViaElementSet() { 327 ms.add("a", 2); 328 ms.add("b", 3); 329 ms.add("c", 4); 330 assertTrue(ms.elementSet().containsAll(asList("a", "c"))); 331 assertSize(); 332 } 333 334 public void testRemoveAllVacuousViaElementSet() { 335 assertFalse(ms.elementSet().removeAll(Collections.emptySet())); 336 assertSize(); 337 } 338 339 public void testRemoveAllOfOneViaElementSet() { 340 ms.add("a", 2); 341 ms.add("b"); 342 assertTrue(ms.elementSet().removeAll(asList("a", "c"))); 343 assertContents("b"); 344 } 345 346 public void testRemoveAllOfDisjointViaElementSet() { 347 ms.add("a", 2); 348 ms.add("b"); 349 assertFalse(ms.elementSet().removeAll(asList("c", "d"))); 350 assertContents("a", "a", "b"); 351 } 352 353 public void testRemoveAllOfEverythingViaElementSet() { 354 ms.add("a", 2); 355 ms.add("b"); 356 assertTrue(ms.elementSet().removeAll(asList("a", "b"))); 357 assertContents(); 358 } 359 360 public void testRetainAllVacuousViaElementSet() { 361 assertFalse(ms.elementSet().retainAll(asList("a"))); 362 assertContents(); 363 } 364 365 public void testRetainAllOfNothingViaElementSet() { 366 ms.add("a"); 367 assertTrue(ms.elementSet().retainAll(Collections.emptySet())); 368 assertContents(); 369 } 370 371 public void testRetainAllOfOneViaElementSet() { 372 ms.add("a", 2); 373 ms.add("b"); 374 assertTrue(ms.elementSet().retainAll(asList("a", "c"))); 375 assertContents("a", "a"); 376 } 377 378 public void testRetainAllOfDisjointViaElementSet() { 379 ms.add("a", 2); 380 ms.add("b"); 381 assertTrue(ms.elementSet().retainAll(asList("c", "d"))); 382 assertContents(); 383 } 384 385 public void testRetainAllOfEverythingViaElementSet() { 386 ms.add("a", 2); 387 ms.add("b"); 388 assertFalse(ms.elementSet().retainAll(asList("a", "b"))); 389 assertContents("a", "a", "b"); 390 } 391 392 public void testElementSetBasic() { 393 ms.add("a", 3); 394 ms.add("b", 2); 395 ms.add("c", 1); 396 HashSet<String> expected = Sets.newHashSet("a", "b", "c"); 397 Set<String> actual = ms.elementSet(); 398 assertEquals(expected, actual); 399 assertEquals(actual, expected); 400 assertSize(); 401 } 402 403 public void testElementSetIsNotACopy() { 404 ms.add("a", 1); 405 ms.add("b", 2); 406 Set<String> elementSet = ms.elementSet(); 407 ms.add("c", 3); 408 ms.setCount("b", 0); 409 assertEquals(Sets.newHashSet("a", "c"), elementSet); 410 assertSize(); 411 } 412 413 public void testRemoveFromElementSetYes() { 414 ms.add("a", 1); 415 ms.add("b", 2); 416 Set<String> elementSet = ms.elementSet(); 417 assertTrue(elementSet.remove("b")); 418 assertContents("a"); 419 } 420 421 public void testRemoveFromElementSetNo() { 422 ms.add("a", 1); 423 Set<String> elementSet = ms.elementSet(); 424 assertFalse(elementSet.remove("b")); 425 assertContents("a"); 426 } 427 428 public void testRemoveFromElementSetNull() { 429 assertEquals(false, ms.elementSet().remove(null)); 430 } 431 432 public void testRemoveFromElementSetWrongType() { 433 assertEquals(false, ms.elementSet().remove(new WrongType())); 434 } 435 436 public void testCantAddToElementSet() { 437 try { 438 ms.elementSet().add("a"); 439 fail(); 440 } catch (UnsupportedOperationException expected) { 441 } 442 assertSize(); 443 } 444 445 public void testClearViaElementSet() { 446 ms = createSample(); 447 ms.elementSet().clear(); 448 assertContents(); 449 } 450 451 public void testClearViaEntrySet() { 452 ms = createSample(); 453 ms.entrySet().clear(); 454 assertContents(); 455 } 456 457 public void testEntrySet() { 458 ms = createSample(); 459 for (Multiset.Entry<String> entry : ms.entrySet()) { 460 assertEquals(entry, entry); 461 String element = entry.getElement(); 462 if (element.equals("a")) { 463 assertEquals(1, entry.getCount()); 464 } else if (element.equals("b")) { 465 assertEquals(2, entry.getCount()); 466 } else if (element.equals("c")) { 467 assertEquals(1, entry.getCount()); 468 } else if (element.equals("d")) { 469 assertEquals(3, entry.getCount()); 470 } else { 471 fail(); 472 } 473 } 474 assertSize(); 475 } 476 477 public void testEntrySetEmpty() { 478 assertEquals(Collections.emptySet(), ms.entrySet()); 479 } 480 481 public void testReallyBig() { 482 ms.add("a", Integer.MAX_VALUE - 1); 483 assertEquals(Integer.MAX_VALUE - 1, ms.size()); 484 ms.add("b", 3); 485 486 // See Collection.size() contract 487 assertEquals(Integer.MAX_VALUE, ms.size()); 488 489 // Make sure we didn't forget our size 490 ms.remove("a", 4); 491 assertEquals(Integer.MAX_VALUE - 2, ms.size()); 492 assertSize(); 493 } 494 495 public void testToStringNull() { 496 ms.add("a", 3); 497 ms.add("c", 1); 498 ms.add("b", 2); 499 ms.add(null, 4); 500 501 // This test is brittle. The original test was meant to validate the 502 // contents of the string itself, but key ordering tended to change 503 // under unpredictable circumstances. Instead, we're just ensuring 504 // that the string not return null, and implicitly, not throw an exception. 505 assertNotNull(ms.toString()); 506 assertSize(); 507 } 508 509 @GwtIncompatible("SerializableTester") 510 public void testSerializable() { 511 ms = createSample(); 512 assertEquals(ms, SerializableTester.reserialize(ms)); 513 assertSize(); 514 } 515 516 public void testIteratorRemove() { 517 ms.add("a"); 518 ms.add("b"); 519 ms.add("c"); 520 Iterator<String> iterator = ms.iterator(); 521 String element1 = iterator.next(); 522 iterator.remove(); 523 String element2 = iterator.next(); 524 assertFalse(ms.contains(element1)); 525 assertTrue(ms.contains(element2)); 526 assertSize(); 527 } 528 529 public void testIteratorRemoveRepeated() { 530 ms.add("a", 3); 531 ms.add("b", 1); 532 ms.add("c", 2); 533 Iterator<String> iterator = ms.iterator(); 534 for (int i = 0; i < 6; i++) { 535 assertTrue(iterator.hasNext()); 536 iterator.next(); 537 iterator.remove(); 538 } 539 assertFalse(iterator.hasNext()); 540 assertTrue(ms.isEmpty()); 541 assertSize(); 542 } 543 544 public void testIteratorRemoveTooSoon() { 545 ms.add("a"); 546 ms.add("b"); 547 ms.add("c"); 548 Iterator<String> iterator = ms.iterator(); 549 try { 550 iterator.remove(); 551 fail(); 552 } catch (IllegalStateException expected) {} 553 assertSize(); 554 } 555 556 public void testIteratorRemoveTwiceConsecutive() { 557 ms.add("a"); 558 ms.add("b"); 559 ms.add("c"); 560 Iterator<String> iterator = ms.iterator(); 561 iterator.next(); 562 iterator.remove(); 563 try { 564 iterator.remove(); 565 fail(); 566 } catch (IllegalStateException expected) {} 567 assertSize(); 568 } 569 570 public void testIteratorNoSuchElementException() { 571 ms.add("a"); 572 ms.add("b"); 573 ms.add("c"); 574 Iterator<String> iterator = ms.iterator(); 575 iterator.next(); 576 iterator.next(); 577 iterator.next(); 578 try { 579 iterator.next(); 580 fail(); 581 } catch (NoSuchElementException expected) {} 582 assertSize(); 583 } 584 585 public void testEntryAfterRemove() { 586 ms.add("a", 8); 587 Multiset.Entry<String> entry = ms.entrySet().iterator().next(); 588 assertEquals(8, entry.getCount()); 589 ms.remove("a"); 590 assertEquals(7, entry.getCount()); 591 ms.remove("a", 4); 592 assertEquals(3, entry.getCount()); 593 ms.elementSet().remove("a"); 594 assertEquals(0, entry.getCount()); 595 ms.add("a", 5); 596 assertEquals(5, entry.getCount()); 597 } 598 599 public void testEntryAfterClear() { 600 ms.add("a", 3); 601 Multiset.Entry<String> entry = ms.entrySet().iterator().next(); 602 ms.clear(); 603 assertEquals(0, entry.getCount()); 604 ms.add("a", 5); 605 assertEquals(5, entry.getCount()); 606 } 607 608 public void testEntryAfterEntrySetClear() { 609 ms.add("a", 3); 610 Multiset.Entry<String> entry = ms.entrySet().iterator().next(); 611 ms.entrySet().clear(); 612 assertEquals(0, entry.getCount()); 613 ms.add("a", 5); 614 assertEquals(5, entry.getCount()); 615 } 616 617 public void testEntryAfterEntrySetIteratorRemove() { 618 ms.add("a", 3); 619 Iterator<Multiset.Entry<String>> iterator = ms.entrySet().iterator(); 620 Multiset.Entry<String> entry = iterator.next(); 621 iterator.remove(); 622 assertEquals(0, entry.getCount()); 623 try { 624 iterator.remove(); 625 fail(); 626 } catch (IllegalStateException expected) {} 627 ms.add("a", 5); 628 assertEquals(5, entry.getCount()); 629 } 630 631 public void testEntryAfterElementSetIteratorRemove() { 632 ms.add("a", 3); 633 Multiset.Entry<String> entry = ms.entrySet().iterator().next(); 634 Iterator<String> iterator = ms.elementSet().iterator(); 635 iterator.next(); 636 iterator.remove(); 637 assertEquals(0, entry.getCount()); 638 ms.add("a", 5); 639 assertEquals(5, entry.getCount()); 640 } 641 642 public void testEntrySetContains() { 643 ms.add("a", 3); 644 Set<Entry<String>> es = ms.entrySet(); 645 assertTrue(es.contains(Multisets.immutableEntry("a", 3))); 646 assertFalse(es.contains(null)); 647 assertFalse(es.contains(Maps.immutableEntry("a", 3))); 648 assertFalse(es.contains(Multisets.immutableEntry("a", 2))); 649 assertFalse(es.contains(Multisets.immutableEntry("b", 3))); 650 assertFalse(es.contains(Multisets.immutableEntry("b", 0))); 651 } 652 653 public void testEntrySetRemove() { 654 ms.add("a", 3); 655 Set<Entry<String>> es = ms.entrySet(); 656 assertFalse(es.remove(null)); 657 assertFalse(es.remove(Maps.immutableEntry("a", 3))); 658 assertFalse(es.remove(Multisets.immutableEntry("a", 2))); 659 assertFalse(es.remove(Multisets.immutableEntry("b", 3))); 660 assertFalse(es.remove(Multisets.immutableEntry("b", 0))); 661 assertEquals(3, ms.count("a")); 662 assertTrue(es.remove(Multisets.immutableEntry("a", 3))); 663 assertEquals(0, ms.count("a")); 664 } 665 666 public void testEntrySetToArray() { 667 ms.add("a", 3); 668 Set<Multiset.Entry<String>> es = ms.entrySet(); 669 Entry<?>[] array = new Entry<?>[3]; 670 assertSame(array, es.toArray(array)); 671 assertEquals(Multisets.immutableEntry("a", 3), array[0]); 672 assertNull(array[1]); 673 } 674 675 public void testUnmodifiableMultiset() { 676 ms.add("a", 3); 677 ms.add("b"); 678 ms.add("c", 2); 679 Multiset<Object> unmodifiable = Multisets.<Object>unmodifiableMultiset(ms); 680 UnmodifiableCollectionTests.assertMultisetIsUnmodifiable(unmodifiable, "a"); 681 } 682 683 @Override protected Multiset<String> createSample() { 684 Multiset<String> ms = create(); 685 ms.add("a", 1); 686 ms.add("b", 2); 687 ms.add("c", 1); 688 ms.add("d", 3); 689 return ms; 690 } 691 } 692
