1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkArgument;
18import static java.util.Arrays.asList;
19import static org.truth0.Truth.ASSERT;
20
21import com.google.common.base.Function;
22import com.google.common.collect.Multiset.Entry;
23import com.google.common.collect.testing.ListTestSuiteBuilder;
24import com.google.common.collect.testing.MinimalCollection;
25import com.google.common.collect.testing.TestStringListGenerator;
26import com.google.common.collect.testing.features.CollectionFeature;
27import com.google.common.collect.testing.features.CollectionSize;
28import com.google.common.collect.testing.google.SortedMultisetTestSuiteBuilder;
29import com.google.common.collect.testing.google.TestStringMultisetGenerator;
30import com.google.common.collect.testing.google.UnmodifiableCollectionTests;
31import com.google.common.testing.NullPointerTester;
32import com.google.common.testing.SerializableTester;
33
34import junit.framework.Test;
35import junit.framework.TestCase;
36import junit.framework.TestSuite;
37
38import org.easymock.EasyMock;
39
40import java.util.ArrayList;
41import java.util.Arrays;
42import java.util.Collection;
43import java.util.Comparator;
44import java.util.HashSet;
45import java.util.Iterator;
46import java.util.List;
47import java.util.Set;
48
49/**
50 * Tests for {@link ImmutableSortedMultiset}.
51 *
52 * @author Louis Wasserman
53 */
54public class ImmutableSortedMultisetTest extends TestCase {
55  public static Test suite() {
56    TestSuite suite = new TestSuite();
57    suite.addTestSuite(ImmutableSortedMultisetTest.class);
58
59    suite.addTest(SortedMultisetTestSuiteBuilder.using(new TestStringMultisetGenerator() {
60        @Override
61        protected Multiset<String> create(String[] elements) {
62          return ImmutableSortedMultiset.copyOf(elements);
63        }
64
65        @Override
66        public List<String> order(List<String> insertionOrder) {
67          return Ordering.natural().sortedCopy(insertionOrder);
68        }
69      })
70      .named("ImmutableSortedMultiset")
71      .withFeatures(CollectionSize.ANY,
72          CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS,
73          CollectionFeature.ALLOWS_NULL_QUERIES)
74        .createTestSuite());
75
76    suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
77        @Override
78        protected List<String> create(String[] elements) {
79          return ImmutableSortedMultiset.copyOf(elements).asList();
80        }
81
82        @Override
83        public List<String> order(List<String> insertionOrder) {
84          return Ordering.natural().sortedCopy(insertionOrder);
85        }
86      })
87      .named("ImmutableSortedMultiset.asList")
88      .withFeatures(CollectionSize.ANY,
89          CollectionFeature.SERIALIZABLE,
90          CollectionFeature.ALLOWS_NULL_QUERIES)
91        .createTestSuite());
92
93    suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() {
94        @Override
95        protected List<String> create(String[] elements) {
96          Set<String> set = Sets.newHashSet();
97          ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder();
98          for (String s : elements) {
99            checkArgument(set.add(s));
100            builder.addCopies(s, 2);
101          }
102          return builder.build().elementSet().asList();
103        }
104
105        @Override
106        public List<String> order(List<String> insertionOrder) {
107          return Ordering.natural().sortedCopy(insertionOrder);
108        }
109      })
110      .named("ImmutableSortedMultiset.elementSet.asList")
111      .withFeatures(CollectionSize.ANY,
112          CollectionFeature.REJECTS_DUPLICATES_AT_CREATION,
113          CollectionFeature.SERIALIZABLE,
114          CollectionFeature.ALLOWS_NULL_QUERIES)
115        .createTestSuite());
116
117    return suite;
118  }
119
120  public void testCreation_noArgs() {
121    Multiset<String> multiset = ImmutableSortedMultiset.of();
122    assertTrue(multiset.isEmpty());
123  }
124
125  public void testCreation_oneElement() {
126    Multiset<String> multiset = ImmutableSortedMultiset.of("a");
127    assertEquals(HashMultiset.create(asList("a")), multiset);
128  }
129
130  public void testCreation_twoElements() {
131    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b");
132    assertEquals(HashMultiset.create(asList("a", "b")), multiset);
133  }
134
135  public void testCreation_threeElements() {
136    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c");
137    assertEquals(HashMultiset.create(asList("a", "b", "c")), multiset);
138  }
139
140  public void testCreation_fourElements() {
141    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d");
142    assertEquals(HashMultiset.create(asList("a", "b", "c", "d")), multiset);
143  }
144
145  public void testCreation_fiveElements() {
146    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d", "e");
147    assertEquals(HashMultiset.create(asList("a", "b", "c", "d", "e")), multiset);
148  }
149
150  public void testCreation_sixElements() {
151    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d", "e", "f");
152    assertEquals(HashMultiset.create(asList("a", "b", "c", "d", "e", "f")), multiset);
153  }
154
155  public void testCreation_sevenElements() {
156    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d", "e", "f", "g");
157    assertEquals(HashMultiset.create(asList("a", "b", "c", "d", "e", "f", "g")), multiset);
158  }
159
160  public void testCreation_emptyArray() {
161    String[] array = new String[0];
162    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(array);
163    assertTrue(multiset.isEmpty());
164  }
165
166  public void testCreation_arrayOfOneElement() {
167    String[] array = new String[] {"a"};
168    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(array);
169    assertEquals(HashMultiset.create(asList("a")), multiset);
170  }
171
172  public void testCreation_arrayOfArray() {
173    Comparator<String[]> comparator =
174        Ordering.natural().lexicographical()
175            .onResultOf(new Function<String[], Iterable<Comparable>>() {
176              @Override
177              public Iterable<Comparable> apply(String[] input) {
178                return Arrays.<Comparable>asList(input);
179              }
180            });
181    String[] array = new String[] {"a"};
182    Multiset<String[]> multiset = ImmutableSortedMultiset.orderedBy(comparator).add(array).build();
183    Multiset<String[]> expected = HashMultiset.create();
184    expected.add(array);
185    assertEquals(expected, multiset);
186  }
187
188  public void testCreation_arrayContainingOnlyNull() {
189    String[] array = new String[] {null};
190    try {
191      ImmutableSortedMultiset.copyOf(array);
192      fail();
193    } catch (NullPointerException expected) {}
194  }
195
196  public void testCopyOf_collection_empty() {
197    // "<String>" is required to work around a javac 1.5 bug.
198    Collection<String> c = MinimalCollection.<String>of();
199    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c);
200    assertTrue(multiset.isEmpty());
201  }
202
203  public void testCopyOf_collection_oneElement() {
204    Collection<String> c = MinimalCollection.of("a");
205    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c);
206    assertEquals(HashMultiset.create(asList("a")), multiset);
207  }
208
209  public void testCopyOf_collection_general() {
210    Collection<String> c = MinimalCollection.of("a", "b", "a");
211    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c);
212    assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset);
213  }
214
215  public void testCopyOf_collectionContainingNull() {
216    Collection<String> c = MinimalCollection.of("a", null, "b");
217    try {
218      ImmutableSortedMultiset.copyOf(c);
219      fail();
220    } catch (NullPointerException expected) {}
221  }
222
223  public void testCopyOf_multiset_empty() {
224    Multiset<String> c = HashMultiset.create();
225    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c);
226    assertTrue(multiset.isEmpty());
227  }
228
229  public void testCopyOf_multiset_oneElement() {
230    Multiset<String> c = HashMultiset.create(asList("a"));
231    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c);
232    assertEquals(HashMultiset.create(asList("a")), multiset);
233  }
234
235  public void testCopyOf_multiset_general() {
236    Multiset<String> c = HashMultiset.create(asList("a", "b", "a"));
237    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c);
238    assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset);
239  }
240
241  public void testCopyOf_multisetContainingNull() {
242    Multiset<String> c = HashMultiset.create(asList("a", null, "b"));
243    try {
244      ImmutableSortedMultiset.copyOf(c);
245      fail();
246    } catch (NullPointerException expected) {}
247  }
248
249  public void testCopyOf_iterator_empty() {
250    Iterator<String> iterator = Iterators.emptyIterator();
251    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterator);
252    assertTrue(multiset.isEmpty());
253  }
254
255  public void testCopyOf_iterator_oneElement() {
256    Iterator<String> iterator = Iterators.singletonIterator("a");
257    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterator);
258    assertEquals(HashMultiset.create(asList("a")), multiset);
259  }
260
261  public void testCopyOf_iterator_general() {
262    Iterator<String> iterator = asList("a", "b", "a").iterator();
263    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterator);
264    assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset);
265  }
266
267  public void testCopyOf_iteratorContainingNull() {
268    Iterator<String> iterator = asList("a", null, "b").iterator();
269    try {
270      ImmutableSortedMultiset.copyOf(iterator);
271      fail();
272    } catch (NullPointerException expected) {}
273  }
274
275  private static class CountingIterable implements Iterable<String> {
276    int count = 0;
277
278    @Override
279    public Iterator<String> iterator() {
280      count++;
281      return asList("a", "b", "a").iterator();
282    }
283  }
284
285  public void testCopyOf_plainIterable() {
286    CountingIterable iterable = new CountingIterable();
287    Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterable);
288    assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset);
289    assertEquals(1, iterable.count);
290  }
291
292  public void testCopyOf_shortcut_empty() {
293    Collection<String> c = ImmutableSortedMultiset.of();
294    assertSame(c, ImmutableSortedMultiset.copyOf(c));
295  }
296
297  public void testCopyOf_shortcut_singleton() {
298    Collection<String> c = ImmutableSortedMultiset.of("a");
299    assertSame(c, ImmutableSortedMultiset.copyOf(c));
300  }
301
302  public void testCopyOf_shortcut_immutableMultiset() {
303    Collection<String> c = ImmutableSortedMultiset.of("a", "b", "c");
304    assertSame(c, ImmutableSortedMultiset.copyOf(c));
305  }
306
307  public void testBuilderAdd() {
308    ImmutableSortedMultiset<String> multiset =
309        ImmutableSortedMultiset.<String>naturalOrder().add("a").add("b").add("a").add("c").build();
310    assertEquals(HashMultiset.create(asList("a", "b", "a", "c")), multiset);
311  }
312
313  public void testBuilderAddAll() {
314    List<String> a = asList("a", "b");
315    List<String> b = asList("c", "d");
316    ImmutableSortedMultiset<String> multiset =
317        ImmutableSortedMultiset.<String>naturalOrder().addAll(a).addAll(b).build();
318    assertEquals(HashMultiset.create(asList("a", "b", "c", "d")), multiset);
319  }
320
321  public void testBuilderAddAllMultiset() {
322    Multiset<String> a = HashMultiset.create(asList("a", "b", "b"));
323    Multiset<String> b = HashMultiset.create(asList("c", "b"));
324    ImmutableSortedMultiset<String> multiset =
325        ImmutableSortedMultiset.<String>naturalOrder().addAll(a).addAll(b).build();
326    assertEquals(HashMultiset.create(asList("a", "b", "b", "b", "c")), multiset);
327  }
328
329  public void testBuilderAddAllIterator() {
330    Iterator<String> iterator = asList("a", "b", "a", "c").iterator();
331    ImmutableSortedMultiset<String> multiset =
332        ImmutableSortedMultiset.<String>naturalOrder().addAll(iterator).build();
333    assertEquals(HashMultiset.create(asList("a", "b", "a", "c")), multiset);
334  }
335
336  public void testBuilderAddCopies() {
337    ImmutableSortedMultiset<String> multiset =
338        ImmutableSortedMultiset.<String>naturalOrder().addCopies("a", 2).addCopies("b", 3)
339            .addCopies("c", 0).build();
340    assertEquals(HashMultiset.create(asList("a", "a", "b", "b", "b")), multiset);
341  }
342
343  public void testBuilderSetCount() {
344    ImmutableSortedMultiset<String> multiset =
345        ImmutableSortedMultiset.<String>naturalOrder().add("a").setCount("a", 2).setCount("b", 3)
346            .build();
347    assertEquals(HashMultiset.create(asList("a", "a", "b", "b", "b")), multiset);
348  }
349
350  public void testBuilderAddHandlesNullsCorrectly() {
351    ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder();
352    try {
353      builder.add((String) null);
354      fail("expected NullPointerException");
355    } catch (NullPointerException expected) {}
356  }
357
358  public void testBuilderAddAllHandlesNullsCorrectly() {
359    ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder();
360    try {
361      builder.addAll((Collection<String>) null);
362      fail("expected NullPointerException");
363    } catch (NullPointerException expected) {}
364
365    builder = ImmutableSortedMultiset.naturalOrder();
366    List<String> listWithNulls = asList("a", null, "b");
367    try {
368      builder.addAll(listWithNulls);
369      fail("expected NullPointerException");
370    } catch (NullPointerException expected) {}
371
372    builder = ImmutableSortedMultiset.naturalOrder();
373    Multiset<String> multisetWithNull = LinkedHashMultiset.create(asList("a", null, "b"));
374    try {
375      builder.addAll(multisetWithNull);
376      fail("expected NullPointerException");
377    } catch (NullPointerException expected) {}
378  }
379
380  public void testBuilderAddCopiesHandlesNullsCorrectly() {
381    ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder();
382    try {
383      builder.addCopies(null, 2);
384      fail("expected NullPointerException");
385    } catch (NullPointerException expected) {}
386  }
387
388  public void testBuilderAddCopiesIllegal() {
389    ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder();
390    try {
391      builder.addCopies("a", -2);
392      fail("expected IllegalArgumentException");
393    } catch (IllegalArgumentException expected) {}
394  }
395
396  public void testBuilderSetCountHandlesNullsCorrectly() {
397    ImmutableSortedMultiset.Builder<String> builder =
398        new ImmutableSortedMultiset.Builder<String>(Ordering.natural().nullsFirst());
399    try {
400      builder.setCount(null, 2);
401      fail("expected NullPointerException");
402    } catch (NullPointerException expected) {}
403  }
404
405  public void testBuilderSetCountIllegal() {
406    ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder();
407    try {
408      builder.setCount("a", -2);
409      fail("expected IllegalArgumentException");
410    } catch (IllegalArgumentException expected) {}
411  }
412
413  public void testNullPointers() {
414    new NullPointerTester().testAllPublicStaticMethods(ImmutableSortedMultiset.class);
415  }
416
417  public void testSerialization_empty() {
418    Collection<String> c = ImmutableSortedMultiset.of();
419    assertSame(c, SerializableTester.reserialize(c));
420  }
421
422  public void testSerialization_multiple() {
423    Collection<String> c = ImmutableSortedMultiset.of("a", "b", "a");
424    Collection<String> copy = SerializableTester.reserializeAndAssert(c);
425    ASSERT.that(copy).has().exactly("a", "a", "b").inOrder();
426  }
427
428  public void testSerialization_elementSet() {
429    Multiset<String> c = ImmutableSortedMultiset.of("a", "b", "a");
430    Collection<String> copy = SerializableTester.reserializeAndAssert(c.elementSet());
431    ASSERT.that(copy).has().exactly("a", "b").inOrder();
432  }
433
434  public void testSerialization_entrySet() {
435    Multiset<String> c = ImmutableSortedMultiset.of("a", "b", "c");
436    SerializableTester.reserializeAndAssert(c.entrySet());
437  }
438
439  public void testEquals_immutableMultiset() {
440    Collection<String> c = ImmutableSortedMultiset.of("a", "b", "a");
441    assertEquals(c, ImmutableSortedMultiset.of("a", "b", "a"));
442    assertEquals(c, ImmutableSortedMultiset.of("a", "a", "b"));
443    ASSERT.that(c).isNotEqualTo(ImmutableSortedMultiset.of("a", "b"));
444    ASSERT.that(c).isNotEqualTo(ImmutableSortedMultiset.of("a", "b", "c", "d"));
445  }
446
447  public void testIterationOrder() {
448    Collection<String> c = ImmutableSortedMultiset.of("a", "b", "a");
449    ASSERT.that(c).has().exactly("a", "a", "b").inOrder();
450  }
451
452  public void testMultisetWrites() {
453    Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "a");
454    UnmodifiableCollectionTests.assertMultisetIsUnmodifiable(multiset, "test");
455  }
456
457  public void testAsList() {
458    ImmutableSortedMultiset<String> multiset = ImmutableSortedMultiset.of("a", "a", "b", "b", "b");
459    ImmutableList<String> list = multiset.asList();
460    assertEquals(ImmutableList.of("a", "a", "b", "b", "b"), list);
461    assertTrue(list instanceof ImmutableAsList);
462    ImmutableList<String> copy = SerializableTester.reserializeAndAssert(list);
463    assertTrue(copy instanceof ImmutableAsList);
464    assertEquals(2, list.indexOf("b"));
465    assertEquals(4, list.lastIndexOf("b"));
466  }
467
468  public void testCopyOfDefensiveCopy() {
469    // Depending on JDK version, either toArray() or toArray(T[]) may be called... use this class
470    // rather than mocking to ensure that one of those methods is called.
471    class TestArrayList<E> extends ArrayList<E> {
472      boolean toArrayCalled = false;
473
474      @Override
475      public Object[] toArray() {
476        toArrayCalled = true;
477        return super.toArray();
478      }
479
480      @Override
481      public <T> T[] toArray(T[] a) {
482        toArrayCalled = true;
483        return super.toArray(a);
484      }
485    }
486
487    // Test that toArray() is used to make a defensive copy in copyOf(), so concurrently modified
488    // synchronized collections can be safely copied.
489    TestArrayList<String> toCopy = new TestArrayList<String>();
490    ImmutableSortedMultiset<String> multiset =
491        ImmutableSortedMultiset.copyOf(Ordering.natural(), toCopy);
492    assertTrue(toCopy.toArrayCalled);
493  }
494
495  @SuppressWarnings("unchecked")
496  public void testCopyOfSortedDefensiveCopy() {
497    // Depending on JDK version, either toArray() or toArray(T[]) may be called... use this class
498    // rather than mocking to ensure that one of those methods is called.
499    class TestHashSet<E> extends HashSet<E> {
500      boolean toArrayCalled = false;
501
502      @Override
503      public Object[] toArray() {
504        toArrayCalled = true;
505        return super.toArray();
506      }
507
508      @Override
509      public <T> T[] toArray(T[] a) {
510        toArrayCalled = true;
511        return super.toArray(a);
512      }
513    }
514
515    // Test that toArray() is used to make a defensive copy in copyOf(), so concurrently modified
516    // synchronized collections can be safely copied.
517    SortedMultiset<String> toCopy = EasyMock.createMock(SortedMultiset.class);
518    TestHashSet<Entry<String>> entrySet = new TestHashSet<Entry<String>>();
519    EasyMock.expect((Comparator<Comparable>) toCopy.comparator())
520      .andReturn(Ordering.natural());
521    EasyMock.expect(toCopy.entrySet()).andReturn(entrySet);
522    EasyMock.replay(toCopy);
523    ImmutableSortedMultiset<String> multiset =
524        ImmutableSortedMultiset.copyOfSorted(toCopy);
525    EasyMock.verify(toCopy);
526    assertTrue(entrySet.toArrayCalled);
527  }
528
529  private static class IntegerDiv10 implements Comparable<IntegerDiv10> {
530    final int value;
531
532    IntegerDiv10(int value) {
533      this.value = value;
534    }
535
536    @Override
537    public int compareTo(IntegerDiv10 o) {
538      return value / 10 - o.value / 10;
539    }
540
541    @Override public String toString() {
542      return Integer.toString(value);
543    }
544  }
545
546  public void testCopyOfDuplicateInconsistentWithEquals() {
547    IntegerDiv10 three = new IntegerDiv10(3);
548    IntegerDiv10 eleven = new IntegerDiv10(11);
549    IntegerDiv10 twelve = new IntegerDiv10(12);
550    IntegerDiv10 twenty = new IntegerDiv10(20);
551
552    List<IntegerDiv10> original = ImmutableList.of(three, eleven, twelve, twenty);
553
554    Multiset<IntegerDiv10> copy = ImmutableSortedMultiset.copyOf(original);
555    assertTrue(copy.contains(eleven));
556    assertTrue(copy.contains(twelve));
557  }
558}
559