• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 com.google.common.truth.Truth.assertThat;
25 import static java.util.Arrays.asList;
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 import java.util.ArrayList;
38 import java.util.Arrays;
39 import java.util.Collection;
40 import java.util.Iterator;
41 import java.util.List;
42 import java.util.Map.Entry;
43 import java.util.Set;
44 import junit.framework.Test;
45 import junit.framework.TestCase;
46 import junit.framework.TestSuite;
47 
48 /**
49  * Unit tests for {@code LinkedHashMultimap}.
50  *
51  * @author Jared Levy
52  */
53 @GwtCompatible(emulated = true)
54 public class LinkedHashMultimapTest extends TestCase {
55 
56   @GwtIncompatible // suite
suite()57   public static Test suite() {
58     TestSuite suite = new TestSuite();
59     suite.addTest(
60         SetMultimapTestSuiteBuilder.using(
61                 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(
97           Hashing.needsResizing(
98               valueSet.size(),
99               valueSet.hashTable.length,
100               LinkedHashMultimap.VALUE_SET_LOAD_FACTOR));
101     }
102   }
103 
initializeMultimap5()104   private Multimap<String, Integer> initializeMultimap5() {
105     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
106     multimap.put("foo", 5);
107     multimap.put("bar", 4);
108     multimap.put("foo", 3);
109     multimap.put("cow", 2);
110     multimap.put("bar", 1);
111     return multimap;
112   }
113 
testToString()114   public void testToString() {
115     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
116     multimap.put("foo", 3);
117     multimap.put("bar", 1);
118     multimap.putAll("foo", Arrays.asList(-1, 2, 4));
119     multimap.putAll("bar", Arrays.asList(2, 3));
120     multimap.put("foo", 1);
121     assertEquals("{foo=[3, -1, 2, 4, 1], bar=[1, 2, 3]}", multimap.toString());
122   }
123 
testOrderingReadOnly()124   public void testOrderingReadOnly() {
125     Multimap<String, Integer> multimap = initializeMultimap5();
126     assertOrderingReadOnly(multimap);
127   }
128 
testOrderingUnmodifiable()129   public void testOrderingUnmodifiable() {
130     Multimap<String, Integer> multimap = initializeMultimap5();
131     assertOrderingReadOnly(Multimaps.unmodifiableMultimap(multimap));
132   }
133 
testOrderingSynchronized()134   public void testOrderingSynchronized() {
135     Multimap<String, Integer> multimap = initializeMultimap5();
136     assertOrderingReadOnly(Multimaps.synchronizedMultimap(multimap));
137   }
138 
139   @GwtIncompatible // SeriazableTester
testSerializationOrdering()140   public void testSerializationOrdering() {
141     Multimap<String, Integer> multimap = initializeMultimap5();
142     Multimap<String, Integer> copy = SerializableTester.reserializeAndAssert(multimap);
143     assertOrderingReadOnly(copy);
144   }
145 
146   @GwtIncompatible // SeriazableTester
testSerializationOrderingKeysAndEntries()147   public void testSerializationOrderingKeysAndEntries() {
148     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
149     multimap.put("a", 1);
150     multimap.put("b", 2);
151     multimap.put("a", 3);
152     multimap.put("c", 4);
153     multimap.remove("a", 1);
154     multimap = SerializableTester.reserializeAndAssert(multimap);
155     assertThat(multimap.keySet()).containsExactly("a", "b", "c").inOrder();
156     assertThat(multimap.entries())
157         .containsExactly(mapEntry("b", 2), mapEntry("a", 3), mapEntry("c", 4))
158         .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     assertThat(multimap.get("foo")).containsExactly(5, 3).inOrder();
164     assertThat(multimap.get("bar")).containsExactly(4, 1).inOrder();
165     assertThat(multimap.get("cow")).contains(2);
166 
167     assertThat(multimap.keySet()).containsExactly("foo", "bar", "cow").inOrder();
168     assertThat(multimap.values()).containsExactly(5, 4, 3, 2, 1).inOrder();
169 
170     Iterator<Entry<String, Integer>> entryIterator = multimap.entries().iterator();
171     assertEquals(Maps.immutableEntry("foo", 5), entryIterator.next());
172     assertEquals(Maps.immutableEntry("bar", 4), entryIterator.next());
173     assertEquals(Maps.immutableEntry("foo", 3), entryIterator.next());
174     assertEquals(Maps.immutableEntry("cow", 2), entryIterator.next());
175     assertEquals(Maps.immutableEntry("bar", 1), entryIterator.next());
176 
177     Iterator<Entry<String, Collection<Integer>>> collectionIterator =
178         multimap.asMap().entrySet().iterator();
179     Entry<String, Collection<Integer>> entry = collectionIterator.next();
180     assertEquals("foo", entry.getKey());
181     assertThat(entry.getValue()).containsExactly(5, 3).inOrder();
182     entry = collectionIterator.next();
183     assertEquals("bar", entry.getKey());
184     assertThat(entry.getValue()).containsExactly(4, 1).inOrder();
185     entry = collectionIterator.next();
186     assertEquals("cow", entry.getKey());
187     assertThat(entry.getValue()).contains(2);
188   }
189 
testOrderingUpdates()190   public void testOrderingUpdates() {
191     Multimap<String, Integer> multimap = initializeMultimap5();
192 
193     assertThat(multimap.replaceValues("foo", asList(6, 7))).containsExactly(5, 3).inOrder();
194     assertThat(multimap.keySet()).containsExactly("foo", "bar", "cow").inOrder();
195     assertThat(multimap.removeAll("foo")).containsExactly(6, 7).inOrder();
196     assertThat(multimap.keySet()).containsExactly("bar", "cow").inOrder();
197     assertTrue(multimap.remove("bar", 4));
198     assertThat(multimap.keySet()).containsExactly("bar", "cow").inOrder();
199     assertTrue(multimap.remove("bar", 1));
200     assertThat(multimap.keySet()).contains("cow");
201     multimap.put("bar", 9);
202     assertThat(multimap.keySet()).containsExactly("cow", "bar").inOrder();
203   }
204 
testToStringNullExact()205   public void testToStringNullExact() {
206     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
207 
208     multimap.put("foo", 3);
209     multimap.put("foo", -1);
210     multimap.put(null, null);
211     multimap.put("bar", 1);
212     multimap.put("foo", 2);
213     multimap.put(null, 0);
214     multimap.put("bar", 2);
215     multimap.put("bar", null);
216     multimap.put("foo", null);
217     multimap.put("foo", 4);
218     multimap.put(null, -1);
219     multimap.put("bar", 3);
220     multimap.put("bar", 1);
221     multimap.put("foo", 1);
222 
223     assertEquals(
224         "{foo=[3, -1, 2, null, 4, 1], null=[null, 0, -1], bar=[1, 2, null, 3]}",
225         multimap.toString());
226   }
227 
testPutMultimapOrdered()228   public void testPutMultimapOrdered() {
229     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
230     multimap.putAll(initializeMultimap5());
231     assertOrderingReadOnly(multimap);
232   }
233 
testKeysToString_ordering()234   public void testKeysToString_ordering() {
235     Multimap<String, Integer> multimap = initializeMultimap5();
236     assertEquals("[foo x 2, bar x 2, cow]", multimap.keys().toString());
237   }
238 
testCreate()239   public void testCreate() {
240     LinkedHashMultimap<String, Integer> multimap = LinkedHashMultimap.create();
241     multimap.put("foo", 1);
242     multimap.put("bar", 2);
243     multimap.put("foo", 3);
244     assertEquals(ImmutableSet.of(1, 3), multimap.get("foo"));
245   }
246 
testCreateFromMultimap()247   public void testCreateFromMultimap() {
248     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
249     multimap.put("a", 1);
250     multimap.put("b", 2);
251     multimap.put("a", 3);
252     multimap.put("c", 4);
253     LinkedHashMultimap<String, Integer> copy = LinkedHashMultimap.create(multimap);
254     new EqualsTester().addEqualityGroup(multimap, copy).testEquals();
255   }
256 
testCreateFromSizes()257   public void testCreateFromSizes() {
258     LinkedHashMultimap<String, Integer> multimap = LinkedHashMultimap.create(20, 15);
259     multimap.put("foo", 1);
260     multimap.put("bar", 2);
261     multimap.put("foo", 3);
262     assertEquals(ImmutableSet.of(1, 3), multimap.get("foo"));
263   }
264 
testCreateFromIllegalSizes()265   public void testCreateFromIllegalSizes() {
266     try {
267       LinkedHashMultimap.create(-20, 15);
268       fail();
269     } catch (IllegalArgumentException expected) {
270     }
271 
272     try {
273       LinkedHashMultimap.create(20, -15);
274       fail();
275     } catch (IllegalArgumentException expected) {
276     }
277   }
278 
279   @GwtIncompatible // unreasonably slow
testGetIteration()280   public void testGetIteration() {
281     new IteratorTester<Integer>(
282         6,
283         MODIFIABLE,
284         newLinkedHashSet(asList(2, 3, 4, 7, 8)),
285         IteratorTester.KnownOrder.KNOWN_ORDER) {
286       private Multimap<String, Integer> multimap;
287 
288       @Override
289       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
298       protected void verify(List<Integer> elements) {
299         assertEquals(newHashSet(elements), multimap.get("foo"));
300       }
301     }.test();
302   }
303 
304   @GwtIncompatible // unreasonably slow
testEntriesIteration()305   public void testEntriesIteration() {
306     @SuppressWarnings("unchecked")
307     Set<Entry<String, Integer>> set =
308         Sets.newLinkedHashSet(
309             asList(
310                 Maps.immutableEntry("foo", 2),
311                 Maps.immutableEntry("foo", 3),
312                 Maps.immutableEntry("bar", 4),
313                 Maps.immutableEntry("bar", 5),
314                 Maps.immutableEntry("foo", 6)));
315 
316     new IteratorTester<Entry<String, Integer>>(
317         6, MODIFIABLE, set, IteratorTester.KnownOrder.KNOWN_ORDER) {
318       private Multimap<String, Integer> multimap;
319 
320       @Override
321       protected Iterator<Entry<String, Integer>> newTargetIterator() {
322         multimap = LinkedHashMultimap.create();
323         multimap.putAll("foo", asList(2, 3));
324         multimap.putAll("bar", asList(4, 5));
325         multimap.putAll("foo", asList(6));
326         return multimap.entries().iterator();
327       }
328 
329       @Override
330       protected void verify(List<Entry<String, Integer>> elements) {
331         assertEquals(newHashSet(elements), multimap.entries());
332       }
333     }.test();
334   }
335 
336   @GwtIncompatible // unreasonably slow
testKeysIteration()337   public void testKeysIteration() {
338     new IteratorTester<String>(
339         6,
340         MODIFIABLE,
341         newArrayList("foo", "foo", "bar", "bar", "foo"),
342         IteratorTester.KnownOrder.KNOWN_ORDER) {
343       private Multimap<String, Integer> multimap;
344 
345       @Override
346       protected Iterator<String> newTargetIterator() {
347         multimap = LinkedHashMultimap.create();
348         multimap.putAll("foo", asList(2, 3));
349         multimap.putAll("bar", asList(4, 5));
350         multimap.putAll("foo", asList(6));
351         return multimap.keys().iterator();
352       }
353 
354       @Override
355       protected void verify(List<String> elements) {
356         assertEquals(elements, Lists.newArrayList(multimap.keys()));
357       }
358     }.test();
359   }
360 
361   @GwtIncompatible // unreasonably slow
testValuesIteration()362   public void testValuesIteration() {
363     new IteratorTester<Integer>(
364         6, MODIFIABLE, newArrayList(2, 3, 4, 5, 6), IteratorTester.KnownOrder.KNOWN_ORDER) {
365       private Multimap<String, Integer> multimap;
366 
367       @Override
368       protected Iterator<Integer> newTargetIterator() {
369         multimap = LinkedHashMultimap.create();
370         multimap.putAll("foo", asList(2, 3));
371         multimap.putAll("bar", asList(4, 5));
372         multimap.putAll("foo", asList(6));
373         return multimap.values().iterator();
374       }
375 
376       @Override
377       protected void verify(List<Integer> elements) {
378         assertEquals(elements, Lists.newArrayList(multimap.values()));
379       }
380     }.test();
381   }
382 
383   @GwtIncompatible // unreasonably slow
testKeySetIteration()384   public void testKeySetIteration() {
385     new IteratorTester<String>(
386         6,
387         MODIFIABLE,
388         newLinkedHashSet(asList("foo", "bar", "baz", "dog", "cat")),
389         IteratorTester.KnownOrder.KNOWN_ORDER) {
390       private Multimap<String, Integer> multimap;
391 
392       @Override
393       protected Iterator<String> newTargetIterator() {
394         multimap = LinkedHashMultimap.create();
395         multimap.putAll("foo", asList(2, 3));
396         multimap.putAll("bar", asList(4, 5));
397         multimap.putAll("foo", asList(6));
398         multimap.putAll("baz", asList(7, 8));
399         multimap.putAll("dog", asList(9));
400         multimap.putAll("bar", asList(10, 11));
401         multimap.putAll("cat", asList(12, 13, 14));
402         return multimap.keySet().iterator();
403       }
404 
405       @Override
406       protected void verify(List<String> elements) {
407         assertEquals(newHashSet(elements), multimap.keySet());
408       }
409     }.test();
410   }
411 
412   @GwtIncompatible // unreasonably slow
testAsSetIteration()413   public void testAsSetIteration() {
414     @SuppressWarnings("unchecked")
415     Set<Entry<String, Collection<Integer>>> set =
416         newLinkedHashSet(
417             asList(
418                 Maps.immutableEntry("foo", (Collection<Integer>) Sets.newHashSet(2, 3, 6)),
419                 Maps.immutableEntry("bar", (Collection<Integer>) Sets.newHashSet(4, 5, 10, 11)),
420                 Maps.immutableEntry("baz", (Collection<Integer>) Sets.newHashSet(7, 8)),
421                 Maps.immutableEntry("dog", (Collection<Integer>) Sets.newHashSet(9)),
422                 Maps.immutableEntry("cat", (Collection<Integer>) Sets.newHashSet(12, 13, 14))));
423     new IteratorTester<Entry<String, Collection<Integer>>>(
424         6, MODIFIABLE, set, IteratorTester.KnownOrder.KNOWN_ORDER) {
425       private Multimap<String, Integer> multimap;
426 
427       @Override
428       protected Iterator<Entry<String, Collection<Integer>>> newTargetIterator() {
429         multimap = LinkedHashMultimap.create();
430         multimap.putAll("foo", asList(2, 3));
431         multimap.putAll("bar", asList(4, 5));
432         multimap.putAll("foo", asList(6));
433         multimap.putAll("baz", asList(7, 8));
434         multimap.putAll("dog", asList(9));
435         multimap.putAll("bar", asList(10, 11));
436         multimap.putAll("cat", asList(12, 13, 14));
437         return multimap.asMap().entrySet().iterator();
438       }
439 
440       @Override
441       protected void verify(List<Entry<String, Collection<Integer>>> elements) {
442         assertEquals(newHashSet(elements), multimap.asMap().entrySet());
443       }
444     }.test();
445   }
446 
testKeysSpliterator()447   public void testKeysSpliterator() {
448     List<Entry<String, Integer>> expectedEntries =
449         asList(
450             Maps.immutableEntry("foo", 2),
451             Maps.immutableEntry("foo", 3),
452             Maps.immutableEntry("bar", 4),
453             Maps.immutableEntry("bar", 5),
454             Maps.immutableEntry("foo", 6));
455     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
456     for (Entry<String, Integer> entry : expectedEntries) {
457       multimap.put(entry.getKey(), entry.getValue());
458     }
459     List<String> actualKeys = new ArrayList<>();
460     multimap.keys().spliterator().forEachRemaining(actualKeys::add);
461     assertThat(actualKeys)
462         .containsExactlyElementsIn(Lists.transform(expectedEntries, Entry::getKey))
463         .inOrder();
464   }
465 
testEntriesSpliterator()466   public void testEntriesSpliterator() {
467     List<Entry<String, Integer>> expectedEntries =
468         asList(
469             Maps.immutableEntry("foo", 2),
470             Maps.immutableEntry("foo", 3),
471             Maps.immutableEntry("bar", 4),
472             Maps.immutableEntry("bar", 5),
473             Maps.immutableEntry("foo", 6));
474     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
475     for (Entry<String, Integer> entry : expectedEntries) {
476       multimap.put(entry.getKey(), entry.getValue());
477     }
478     List<Entry<String, Integer>> actualEntries = new ArrayList<>();
479     multimap.entries().spliterator().forEachRemaining(actualEntries::add);
480     assertThat(actualEntries).containsExactlyElementsIn(expectedEntries).inOrder();
481   }
482 
testValuesSpliterator()483   public void testValuesSpliterator() {
484     List<Entry<String, Integer>> expectedEntries =
485         asList(
486             Maps.immutableEntry("foo", 2),
487             Maps.immutableEntry("foo", 3),
488             Maps.immutableEntry("bar", 4),
489             Maps.immutableEntry("bar", 5),
490             Maps.immutableEntry("foo", 6));
491     Multimap<String, Integer> multimap = LinkedHashMultimap.create();
492     for (Entry<String, Integer> entry : expectedEntries) {
493       multimap.put(entry.getKey(), entry.getValue());
494     }
495     List<Integer> actualValues = new ArrayList<>();
496     multimap.values().spliterator().forEachRemaining(actualValues::add);
497     assertThat(actualValues)
498         .containsExactlyElementsIn(Lists.transform(expectedEntries, Entry::getValue))
499         .inOrder();
500   }
501 }
502