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 com.google.common.collect.Lists.newArrayList;
20 import static com.google.common.collect.Sets.newHashSet;
21 import static com.google.common.collect.Sets.newLinkedHashSet;
22 import static com.google.common.collect.testing.Helpers.mapEntry;
23 import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE;
24 import static java.util.Arrays.asList;
25 import static org.truth0.Truth.ASSERT;
26 
27 import com.google.common.annotations.GwtCompatible;
28 import com.google.common.annotations.GwtIncompatible;
29 import com.google.common.collect.testing.IteratorTester;
30 import com.google.common.collect.testing.features.CollectionFeature;
31 import com.google.common.collect.testing.features.CollectionSize;
32 import com.google.common.collect.testing.features.MapFeature;
33 import com.google.common.collect.testing.google.SetMultimapTestSuiteBuilder;
34 import com.google.common.collect.testing.google.TestStringSetMultimapGenerator;
35 import com.google.common.testing.EqualsTester;
36 import com.google.common.testing.SerializableTester;
37 
38 import junit.framework.Test;
39 import junit.framework.TestCase;
40 import junit.framework.TestSuite;
41 
42 import java.util.Arrays;
43 import java.util.Collection;
44 import java.util.Iterator;
45 import java.util.List;
46 import java.util.Map;
47 import java.util.Map.Entry;
48 import java.util.Set;
49 
50 /**
51  * Unit tests for {@code LinkedHashMultimap}.
52  *
53  * @author Jared Levy
54  */
55 @GwtCompatible(emulated = true)
56 public class LinkedHashMultimapTest extends TestCase {
57 
58   @GwtIncompatible("suite")
suite()59   public static Test suite() {
60     TestSuite suite = new TestSuite();
61     suite.addTest(SetMultimapTestSuiteBuilder.using(new TestStringSetMultimapGenerator() {
62         @Override
63         protected SetMultimap<String, String> create(Entry<String, String>[] entries) {
64           SetMultimap<String, String> multimap = LinkedHashMultimap.create();
65           for (Entry<String, String> entry : entries) {
66             multimap.put(entry.getKey(), entry.getValue());
67           }
68           return multimap;
69         }
70       })
71       .named("LinkedHashMultimap")
72       .withFeatures(
73           MapFeature.ALLOWS_NULL_KEYS,
74           MapFeature.ALLOWS_NULL_VALUES,
75           MapFeature.ALLOWS_ANY_NULL_QUERIES,
76           MapFeature.GENERAL_PURPOSE,
77           MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION,
78           CollectionFeature.SUPPORTS_ITERATOR_REMOVE,
79           CollectionFeature.KNOWN_ORDER,
80           CollectionFeature.SERIALIZABLE,
81           CollectionSize.ANY)
82       .createTestSuite());
83     suite.addTestSuite(LinkedHashMultimapTest.class);
84     return suite;
85   }
86 
testValueSetHashTableExpansion()87   public void testValueSetHashTableExpansion() {
88     LinkedHashMultimap<String, Integer> multimap = LinkedHashMultimap.create();
89     for (int z = 1; z <= 100; z++) {
90       multimap.put("a", z);
91       // The Eclipse compiler (and hence GWT) rejects a parameterized cast.
92       @SuppressWarnings("unchecked")
93       LinkedHashMultimap<String, Integer>.ValueSet valueSet =
94           (LinkedHashMultimap.ValueSet) multimap.backingMap().get("a");
95       assertEquals(z, valueSet.size());
96       assertFalse(Hashing.needsResizing(valueSet.size(), valueSet.hashTable.length,
97           LinkedHashMultimap.VALUE_SET_LOAD_FACTOR));
98     }
99   }
100 
initializeMultimap5()101   private Multimap<String, Integer> initializeMultimap5() {
102     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
103     multimap.put("foo", 5);
104     multimap.put("bar", 4);
105     multimap.put("foo", 3);
106     multimap.put("cow", 2);
107     multimap.put("bar", 1);
108     return multimap;
109   }
110 
testToString()111   public void testToString() {
112     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
113     multimap.put("foo", 3);
114     multimap.put("bar", 1);
115     multimap.putAll("foo", Arrays.asList(-1, 2, 4));
116     multimap.putAll("bar", Arrays.asList(2, 3));
117     multimap.put("foo", 1);
118     assertEquals("{foo=[3, -1, 2, 4, 1], bar=[1, 2, 3]}",
119         multimap.toString());
120   }
121 
testOrderingReadOnly()122   public void testOrderingReadOnly() {
123     Multimap<String, Integer> multimap = initializeMultimap5();
124     assertOrderingReadOnly(multimap);
125   }
126 
testOrderingUnmodifiable()127   public void testOrderingUnmodifiable() {
128     Multimap<String, Integer> multimap = initializeMultimap5();
129     assertOrderingReadOnly(Multimaps.unmodifiableMultimap(multimap));
130   }
131 
testOrderingSynchronized()132   public void testOrderingSynchronized() {
133     Multimap<String, Integer> multimap = initializeMultimap5();
134     assertOrderingReadOnly(Multimaps.synchronizedMultimap(multimap));
135   }
136 
137   @GwtIncompatible("SeriazableTester")
testSerializationOrdering()138   public void testSerializationOrdering() {
139     Multimap<String, Integer> multimap = initializeMultimap5();
140     Multimap<String, Integer> copy
141         = SerializableTester.reserializeAndAssert(multimap);
142     assertOrderingReadOnly(copy);
143   }
144 
145   @GwtIncompatible("SeriazableTester")
testSerializationOrderingKeysAndEntries()146   public void testSerializationOrderingKeysAndEntries() {
147     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
148     multimap.put("a", 1);
149     multimap.put("b", 2);
150     multimap.put("a", 3);
151     multimap.put("c", 4);
152     multimap.remove("a", 1);
153     multimap = SerializableTester.reserializeAndAssert(multimap);
154     ASSERT.that(multimap.keySet()).has().exactly("a", "b", "c").inOrder();
155     ASSERT.that(multimap.entries()).has().exactly(
156         mapEntry("b", 2),
157         mapEntry("a", 3),
158         mapEntry("c", 4)).inOrder();
159     // note that the keys and entries are in different orders
160   }
161 
assertOrderingReadOnly(Multimap<String, Integer> multimap)162   private void assertOrderingReadOnly(Multimap<String, Integer> multimap) {
163     ASSERT.that(multimap.get("foo")).has().exactly(5, 3).inOrder();
164     ASSERT.that(multimap.get("bar")).has().exactly(4, 1).inOrder();
165     ASSERT.that(multimap.get("cow")).has().item(2);
166 
167     ASSERT.that(multimap.keySet()).has().exactly("foo", "bar", "cow").inOrder();
168     ASSERT.that(multimap.values()).has().exactly(5, 4, 3, 2, 1).inOrder();
169 
170     Iterator<Map.Entry<String, Integer>> entryIterator =
171         multimap.entries().iterator();
172     assertEquals(Maps.immutableEntry("foo", 5), entryIterator.next());
173     assertEquals(Maps.immutableEntry("bar", 4), entryIterator.next());
174     assertEquals(Maps.immutableEntry("foo", 3), entryIterator.next());
175     assertEquals(Maps.immutableEntry("cow", 2), entryIterator.next());
176     assertEquals(Maps.immutableEntry("bar", 1), entryIterator.next());
177 
178     Iterator<Map.Entry<String, Collection<Integer>>> collectionIterator =
179         multimap.asMap().entrySet().iterator();
180     Map.Entry<String, Collection<Integer>> entry = collectionIterator.next();
181     assertEquals("foo", entry.getKey());
182     ASSERT.that(entry.getValue()).has().exactly(5, 3).inOrder();
183     entry = collectionIterator.next();
184     assertEquals("bar", entry.getKey());
185     ASSERT.that(entry.getValue()).has().exactly(4, 1).inOrder();
186     entry = collectionIterator.next();
187     assertEquals("cow", entry.getKey());
188     ASSERT.that(entry.getValue()).has().item(2);
189   }
190 
testOrderingUpdates()191   public void testOrderingUpdates() {
192     Multimap<String, Integer> multimap = initializeMultimap5();
193 
194     ASSERT.that(multimap.replaceValues("foo", asList(6, 7))).has().exactly(5, 3).inOrder();
195     ASSERT.that(multimap.keySet()).has().exactly("foo", "bar", "cow").inOrder();
196     ASSERT.that(multimap.removeAll("foo")).has().exactly(6, 7).inOrder();
197     ASSERT.that(multimap.keySet()).has().exactly("bar", "cow").inOrder();
198     assertTrue(multimap.remove("bar", 4));
199     ASSERT.that(multimap.keySet()).has().exactly("bar", "cow").inOrder();
200     assertTrue(multimap.remove("bar", 1));
201     ASSERT.that(multimap.keySet()).has().item("cow");
202     multimap.put("bar", 9);
203     ASSERT.that(multimap.keySet()).has().exactly("cow", "bar").inOrder();
204   }
205 
testToStringNullExact()206   public void testToStringNullExact() {
207     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
208 
209     multimap.put("foo", 3);
210     multimap.put("foo", -1);
211     multimap.put(null, null);
212     multimap.put("bar", 1);
213     multimap.put("foo", 2);
214     multimap.put(null, 0);
215     multimap.put("bar", 2);
216     multimap.put("bar", null);
217     multimap.put("foo", null);
218     multimap.put("foo", 4);
219     multimap.put(null, -1);
220     multimap.put("bar", 3);
221     multimap.put("bar", 1);
222     multimap.put("foo", 1);
223 
224     assertEquals(
225         "{foo=[3, -1, 2, null, 4, 1], null=[null, 0, -1], bar=[1, 2, null, 3]}",
226         multimap.toString());
227   }
228 
testPutMultimapOrdered()229   public void testPutMultimapOrdered() {
230     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
231     multimap.putAll(initializeMultimap5());
232     assertOrderingReadOnly(multimap);
233   }
234 
testKeysToString_ordering()235   public void testKeysToString_ordering() {
236     Multimap<String, Integer> multimap = initializeMultimap5();
237     assertEquals("[foo x 2, bar x 2, cow]", multimap.keys().toString());
238   }
239 
testCreate()240   public void testCreate() {
241     LinkedHashMultimap<String, Integer> multimap = LinkedHashMultimap.create();
242     multimap.put("foo", 1);
243     multimap.put("bar", 2);
244     multimap.put("foo", 3);
245     assertEquals(ImmutableSet.of(1, 3), multimap.get("foo"));
246   }
247 
testCreateFromMultimap()248   public void testCreateFromMultimap() {
249     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
250     multimap.put("a", 1);
251     multimap.put("b", 2);
252     multimap.put("a", 3);
253     multimap.put("c", 4);
254     LinkedHashMultimap<String, Integer> copy =
255         LinkedHashMultimap.create(multimap);
256     new EqualsTester()
257         .addEqualityGroup(multimap, copy)
258         .testEquals();
259   }
260 
testCreateFromSizes()261   public void testCreateFromSizes() {
262     LinkedHashMultimap<String, Integer> multimap
263         = LinkedHashMultimap.create(20, 15);
264     multimap.put("foo", 1);
265     multimap.put("bar", 2);
266     multimap.put("foo", 3);
267     assertEquals(ImmutableSet.of(1, 3), multimap.get("foo"));
268   }
269 
testCreateFromIllegalSizes()270   public void testCreateFromIllegalSizes() {
271     try {
272       LinkedHashMultimap.create(-20, 15);
273       fail();
274     } catch (IllegalArgumentException expected) {}
275 
276     try {
277       LinkedHashMultimap.create(20, -15);
278       fail();
279     } catch (IllegalArgumentException expected) {}
280   }
281 
282   @GwtIncompatible("unreasonably slow")
testGetIteration()283   public void testGetIteration() {
284     new IteratorTester<Integer>(6, MODIFIABLE,
285         newLinkedHashSet(asList(2, 3, 4, 7, 8)),
286         IteratorTester.KnownOrder.KNOWN_ORDER) {
287       private Multimap<String, Integer> multimap;
288 
289       @Override protected Iterator<Integer> newTargetIterator() {
290         multimap = LinkedHashMultimap.create();
291         multimap.putAll("foo", asList(2, 3, 4));
292         multimap.putAll("bar", asList(5, 6));
293         multimap.putAll("foo", asList(7, 8));
294         return multimap.get("foo").iterator();
295       }
296 
297       @Override protected void verify(List<Integer> elements) {
298         assertEquals(newHashSet(elements), multimap.get("foo"));
299       }
300     }.test();
301   }
302 
303   @GwtIncompatible("unreasonably slow")
testEntriesIteration()304   public void testEntriesIteration() {
305     @SuppressWarnings("unchecked")
306     Set<Entry<String, Integer>> set = Sets.newLinkedHashSet(asList(
307         Maps.immutableEntry("foo", 2),
308         Maps.immutableEntry("foo", 3),
309         Maps.immutableEntry("bar", 4),
310         Maps.immutableEntry("bar", 5),
311         Maps.immutableEntry("foo", 6)));
312 
313     new IteratorTester<Entry<String, Integer>>(6, MODIFIABLE, set,
314         IteratorTester.KnownOrder.KNOWN_ORDER) {
315       private Multimap<String, Integer> multimap;
316 
317       @Override protected Iterator<Entry<String, Integer>> newTargetIterator() {
318         multimap = LinkedHashMultimap.create();
319         multimap.putAll("foo", asList(2, 3));
320         multimap.putAll("bar", asList(4, 5));
321         multimap.putAll("foo", asList(6));
322         return multimap.entries().iterator();
323       }
324 
325       @Override protected void verify(List<Entry<String, Integer>> elements) {
326         assertEquals(newHashSet(elements), multimap.entries());
327       }
328     }.test();
329   }
330 
331   @GwtIncompatible("unreasonably slow")
testKeysIteration()332   public void testKeysIteration() {
333     new IteratorTester<String>(6, MODIFIABLE, newArrayList("foo", "foo", "bar",
334         "bar", "foo"), IteratorTester.KnownOrder.KNOWN_ORDER) {
335       private Multimap<String, Integer> multimap;
336 
337       @Override protected Iterator<String> newTargetIterator() {
338         multimap = LinkedHashMultimap.create();
339         multimap.putAll("foo", asList(2, 3));
340         multimap.putAll("bar", asList(4, 5));
341         multimap.putAll("foo", asList(6));
342         return multimap.keys().iterator();
343       }
344 
345       @Override protected void verify(List<String> elements) {
346         assertEquals(elements, Lists.newArrayList(multimap.keys()));
347       }
348     }.test();
349   }
350 
351   @GwtIncompatible("unreasonably slow")
testValuesIteration()352   public void testValuesIteration() {
353     new IteratorTester<Integer>(6, MODIFIABLE, newArrayList(2, 3, 4, 5, 6),
354         IteratorTester.KnownOrder.KNOWN_ORDER) {
355       private Multimap<String, Integer> multimap;
356 
357       @Override protected Iterator<Integer> newTargetIterator() {
358         multimap = LinkedHashMultimap.create();
359         multimap.putAll("foo", asList(2, 3));
360         multimap.putAll("bar", asList(4, 5));
361         multimap.putAll("foo", asList(6));
362         return multimap.values().iterator();
363       }
364 
365       @Override protected void verify(List<Integer> elements) {
366         assertEquals(elements, Lists.newArrayList(multimap.values()));
367       }
368     }.test();
369   }
370 
371   @GwtIncompatible("unreasonably slow")
testKeySetIteration()372   public void testKeySetIteration() {
373     new IteratorTester<String>(6, MODIFIABLE,
374         newLinkedHashSet(asList("foo", "bar", "baz", "dog", "cat")),
375         IteratorTester.KnownOrder.KNOWN_ORDER) {
376       private Multimap<String, Integer> multimap;
377 
378       @Override protected Iterator<String> newTargetIterator() {
379         multimap = LinkedHashMultimap.create();
380         multimap.putAll("foo", asList(2, 3));
381         multimap.putAll("bar", asList(4, 5));
382         multimap.putAll("foo", asList(6));
383         multimap.putAll("baz", asList(7, 8));
384         multimap.putAll("dog", asList(9));
385         multimap.putAll("bar", asList(10, 11));
386         multimap.putAll("cat", asList(12, 13, 14));
387         return multimap.keySet().iterator();
388       }
389 
390       @Override protected void verify(List<String> elements) {
391         assertEquals(newHashSet(elements), multimap.keySet());
392       }
393     }.test();
394   }
395 
396   @GwtIncompatible("unreasonably slow")
testAsSetIteration()397   public void testAsSetIteration() {
398     @SuppressWarnings("unchecked")
399     Set<Entry<String, Collection<Integer>>> set = newLinkedHashSet(asList(
400         Maps.immutableEntry("foo",
401             (Collection<Integer>) Sets.newHashSet(2, 3, 6)),
402         Maps.immutableEntry("bar",
403             (Collection<Integer>) Sets.newHashSet(4, 5, 10, 11)),
404         Maps.immutableEntry("baz",
405             (Collection<Integer>) Sets.newHashSet(7, 8)),
406         Maps.immutableEntry("dog",
407             (Collection<Integer>) Sets.newHashSet(9)),
408         Maps.immutableEntry("cat",
409             (Collection<Integer>) Sets.newHashSet(12, 13, 14))
410     ));
411     new IteratorTester<Entry<String, Collection<Integer>>>(6, MODIFIABLE, set,
412         IteratorTester.KnownOrder.KNOWN_ORDER) {
413       private Multimap<String, Integer> multimap;
414 
415       @Override protected Iterator<Entry<String, Collection<Integer>>>
416           newTargetIterator() {
417         multimap = LinkedHashMultimap.create();
418         multimap.putAll("foo", asList(2, 3));
419         multimap.putAll("bar", asList(4, 5));
420         multimap.putAll("foo", asList(6));
421         multimap.putAll("baz", asList(7, 8));
422         multimap.putAll("dog", asList(9));
423         multimap.putAll("bar", asList(10, 11));
424         multimap.putAll("cat", asList(12, 13, 14));
425         return multimap.asMap().entrySet().iterator();
426       }
427 
428       @Override protected void verify(
429           List<Entry<String, Collection<Integer>>> elements) {
430         assertEquals(newHashSet(elements), multimap.asMap().entrySet());
431       }
432     }.test();
433   }
434 }
435