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
17package com.google.common.collect;
18
19import static java.util.Arrays.asList;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.annotations.GwtIncompatible;
23import com.google.common.collect.Multiset.Entry;
24import com.google.common.collect.testing.google.UnmodifiableCollectionTests;
25import com.google.common.testing.SerializableTester;
26
27import java.util.Collections;
28import java.util.HashSet;
29import java.util.Iterator;
30import java.util.NoSuchElementException;
31import java.util.Set;
32
33/**
34 * Common tests for a {@link Multiset}.
35 *
36 * @author Kevin Bourrillion
37 */
38@GwtCompatible(emulated = true)
39public 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