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