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.IteratorFeature.MODIFIABLE;
23 import static com.google.common.collect.testing.IteratorFeature.SUPPORTS_REMOVE;
24 import static com.google.common.collect.testing.IteratorFeature.SUPPORTS_SET;
25 import static com.google.common.truth.Truth.assertThat;
26 import static java.util.Arrays.asList;
27 
28 import com.google.common.annotations.GwtCompatible;
29 import com.google.common.annotations.GwtIncompatible;
30 import com.google.common.collect.testing.IteratorTester;
31 import com.google.common.collect.testing.ListIteratorTester;
32 import com.google.common.collect.testing.features.CollectionFeature;
33 import com.google.common.collect.testing.features.CollectionSize;
34 import com.google.common.collect.testing.features.MapFeature;
35 import com.google.common.collect.testing.google.ListMultimapTestSuiteBuilder;
36 import com.google.common.collect.testing.google.TestStringListMultimapGenerator;
37 import com.google.common.testing.EqualsTester;
38 
39 import junit.framework.Test;
40 import junit.framework.TestCase;
41 import junit.framework.TestSuite;
42 
43 import java.util.Arrays;
44 import java.util.Collection;
45 import java.util.Collections;
46 import java.util.Iterator;
47 import java.util.List;
48 import java.util.ListIterator;
49 import java.util.Map;
50 import java.util.Map.Entry;
51 import java.util.RandomAccess;
52 import java.util.Set;
53 
54 /**
55  * Tests for {@code LinkedListMultimap}.
56  *
57  * @author Mike Bostock
58  */
59 @GwtCompatible(emulated = true)
60 public class LinkedListMultimapTest extends TestCase {
61 
62   @GwtIncompatible("suite")
63   public static Test suite() {
64     TestSuite suite = new TestSuite();
65     suite.addTest(ListMultimapTestSuiteBuilder.using(new TestStringListMultimapGenerator() {
66         @Override
67         protected ListMultimap<String, String> create(Entry<String, String>[] entries) {
68           ListMultimap<String, String> multimap = LinkedListMultimap.create();
69           for (Entry<String, String> entry : entries) {
70             multimap.put(entry.getKey(), entry.getValue());
71           }
72           return multimap;
73         }
74       })
75       .named("LinkedListMultimap")
76       .withFeatures(
77           MapFeature.ALLOWS_NULL_KEYS,
78           MapFeature.ALLOWS_NULL_VALUES,
79           MapFeature.ALLOWS_ANY_NULL_QUERIES,
80           MapFeature.GENERAL_PURPOSE,
81           CollectionFeature.SUPPORTS_ITERATOR_REMOVE,
82           CollectionFeature.SERIALIZABLE,
83           CollectionFeature.KNOWN_ORDER,
84           CollectionSize.ANY)
85       .createTestSuite());
86     suite.addTestSuite(LinkedListMultimapTest.class);
87     return suite;
88   }
89 
90   protected LinkedListMultimap<String, Integer> create() {
91     return LinkedListMultimap.create();
92   }
93 
94   /**
95    * Confirm that get() returns a List that doesn't implement RandomAccess.
96    */
97   public void testGetRandomAccess() {
98     Multimap<String, Integer> multimap = create();
99     multimap.put("foo", 1);
100     multimap.put("foo", 3);
101     assertFalse(multimap.get("foo") instanceof RandomAccess);
102     assertFalse(multimap.get("bar") instanceof RandomAccess);
103   }
104 
105   /**
106    * Confirm that removeAll() returns a List that implements RandomAccess, even
107    * though get() doesn't.
108    */
109   public void testRemoveAllRandomAccess() {
110     Multimap<String, Integer> multimap = create();
111     multimap.put("foo", 1);
112     multimap.put("foo", 3);
113     assertTrue(multimap.removeAll("foo") instanceof RandomAccess);
114     assertTrue(multimap.removeAll("bar") instanceof RandomAccess);
115   }
116 
117   /**
118    * Confirm that replaceValues() returns a List that implements RandomAccess,
119    * even though get() doesn't.
120    */
121   public void testReplaceValuesRandomAccess() {
122     Multimap<String, Integer> multimap = create();
123     multimap.put("foo", 1);
124     multimap.put("foo", 3);
125     assertTrue(multimap.replaceValues("foo", Arrays.asList(2, 4))
126         instanceof RandomAccess);
127     assertTrue(multimap.replaceValues("bar", Arrays.asList(2, 4))
128         instanceof RandomAccess);
129   }
130 
131   public void testCreateFromMultimap() {
132     Multimap<String, Integer> multimap = LinkedListMultimap.create();
133     multimap.put("foo", 1);
134     multimap.put("bar", 3);
135     multimap.put("foo", 2);
136     LinkedListMultimap<String, Integer> copy =
137         LinkedListMultimap.create(multimap);
138     assertEquals(multimap, copy);
139     assertThat(copy.entries()).has().exactlyAs(multimap.entries()).inOrder();
140   }
141 
142   public void testCreateFromSize() {
143     LinkedListMultimap<String, Integer> multimap
144         = LinkedListMultimap.create(20);
145     multimap.put("foo", 1);
146     multimap.put("bar", 2);
147     multimap.put("foo", 3);
148     assertEquals(ImmutableList.of(1, 3), multimap.get("foo"));
149   }
150 
151   public void testCreateFromIllegalSize() {
152     try {
153       LinkedListMultimap.create(-20);
154       fail();
155     } catch (IllegalArgumentException expected) {}
156   }
157 
158   public void testLinkedGetAdd() {
159     LinkedListMultimap<String, Integer> map = create();
160     map.put("bar", 1);
161     Collection<Integer> foos = map.get("foo");
162     foos.add(2);
163     foos.add(3);
164     map.put("bar", 4);
165     map.put("foo", 5);
166     assertEquals("{bar=[1, 4], foo=[2, 3, 5]}", map.toString());
167     assertEquals("[bar=1, foo=2, foo=3, bar=4, foo=5]",
168         map.entries().toString());
169   }
170 
171   public void testLinkedGetInsert() {
172     ListMultimap<String, Integer> map = create();
173     map.put("bar", 1);
174     List<Integer> foos = map.get("foo");
175     foos.add(2);
176     foos.add(0, 3);
177     map.put("bar", 4);
178     map.put("foo", 5);
179     assertEquals("{bar=[1, 4], foo=[3, 2, 5]}", map.toString());
180     assertEquals("[bar=1, foo=3, foo=2, bar=4, foo=5]",
181         map.entries().toString());
182   }
183 
184   public void testLinkedPutInOrder() {
185     Multimap<String, Integer> map = create();
186     map.put("foo", 1);
187     map.put("bar", 2);
188     map.put("bar", 3);
189     assertEquals("{foo=[1], bar=[2, 3]}", map.toString());
190     assertEquals("[foo=1, bar=2, bar=3]", map.entries().toString());
191   }
192 
193   public void testLinkedPutOutOfOrder() {
194     Multimap<String, Integer> map = create();
195     map.put("bar", 1);
196     map.put("foo", 2);
197     map.put("bar", 3);
198     assertEquals("{bar=[1, 3], foo=[2]}", map.toString());
199     assertEquals("[bar=1, foo=2, bar=3]", map.entries().toString());
200   }
201 
202   public void testLinkedPutAllMultimap() {
203     Multimap<String, Integer> src = create();
204     src.put("bar", 1);
205     src.put("foo", 2);
206     src.put("bar", 3);
207     Multimap<String, Integer> dst = create();
208     dst.putAll(src);
209     assertEquals("{bar=[1, 3], foo=[2]}", dst.toString());
210     assertEquals("[bar=1, foo=2, bar=3]", src.entries().toString());
211   }
212 
213   public void testLinkedReplaceValues() {
214     Multimap<String, Integer> map = create();
215     map.put("bar", 1);
216     map.put("foo", 2);
217     map.put("bar", 3);
218     map.put("bar", 4);
219     assertEquals("{bar=[1, 3, 4], foo=[2]}", map.toString());
220     map.replaceValues("bar", asList(1, 2));
221     assertEquals("[bar=1, foo=2, bar=2]", map.entries().toString());
222     assertEquals("{bar=[1, 2], foo=[2]}", map.toString());
223   }
224 
225   public void testLinkedClear() {
226     ListMultimap<String, Integer> map = create();
227     map.put("foo", 1);
228     map.put("foo", 2);
229     map.put("bar", 3);
230     List<Integer> foos = map.get("foo");
231     Collection<Integer> values = map.values();
232     assertEquals(asList(1, 2), foos);
233     assertThat(values).has().exactly(1, 2, 3).inOrder();
234     map.clear();
235     assertEquals(Collections.emptyList(), foos);
236     assertThat(values).isEmpty();
237     assertEquals("[]", map.entries().toString());
238     assertEquals("{}", map.toString());
239   }
240 
241   public void testLinkedKeySet() {
242     Multimap<String, Integer> map = create();
243     map.put("bar", 1);
244     map.put("foo", 2);
245     map.put("bar", 3);
246     map.put("bar", 4);
247     assertEquals("[bar, foo]", map.keySet().toString());
248     map.keySet().remove("bar");
249     assertEquals("{foo=[2]}", map.toString());
250   }
251 
252   public void testLinkedKeys() {
253     Multimap<String, Integer> map = create();
254     map.put("bar", 1);
255     map.put("foo", 2);
256     map.put("bar", 3);
257     map.put("bar", 4);
258     assertEquals("[bar=1, foo=2, bar=3, bar=4]",
259         map.entries().toString());
260     assertThat(map.keys()).has().exactly("bar", "foo", "bar", "bar").inOrder();
261     map.keys().remove("bar"); // bar is no longer the first key!
262     assertEquals("{foo=[2], bar=[3, 4]}", map.toString());
263   }
264 
265   public void testLinkedValues() {
266     Multimap<String, Integer> map = create();
267     map.put("bar", 1);
268     map.put("foo", 2);
269     map.put("bar", 3);
270     map.put("bar", 4);
271     assertEquals("[1, 2, 3, 4]", map.values().toString());
272     map.values().remove(2);
273     assertEquals("{bar=[1, 3, 4]}", map.toString());
274   }
275 
276   public void testLinkedEntries() {
277     Multimap<String, Integer> map = create();
278     map.put("bar", 1);
279     map.put("foo", 2);
280     map.put("bar", 3);
281     Iterator<Map.Entry<String, Integer>> entries = map.entries().iterator();
282     Map.Entry<String, Integer> entry = entries.next();
283     assertEquals("bar", entry.getKey());
284     assertEquals(1, (int) entry.getValue());
285     entry = entries.next();
286     assertEquals("foo", entry.getKey());
287     assertEquals(2, (int) entry.getValue());
288     entry.setValue(4);
289     entry = entries.next();
290     assertEquals("bar", entry.getKey());
291     assertEquals(3, (int) entry.getValue());
292     assertFalse(entries.hasNext());
293     entries.remove();
294     assertEquals("{bar=[1], foo=[4]}", map.toString());
295   }
296 
297   public void testLinkedAsMapEntries() {
298     Multimap<String, Integer> map = create();
299     map.put("bar", 1);
300     map.put("foo", 2);
301     map.put("bar", 3);
302     Iterator<Map.Entry<String, Collection<Integer>>> entries
303         = map.asMap().entrySet().iterator();
304     Map.Entry<String, Collection<Integer>> entry = entries.next();
305     assertEquals("bar", entry.getKey());
306     assertThat(entry.getValue()).has().exactly(1, 3).inOrder();
307     try {
308       entry.setValue(Arrays.<Integer>asList());
309       fail("UnsupportedOperationException expected");
310     } catch (UnsupportedOperationException expected) {}
311     entries.remove(); // clear
312     entry = entries.next();
313     assertEquals("foo", entry.getKey());
314     assertThat(entry.getValue()).has().item(2);
315     assertFalse(entries.hasNext());
316     assertEquals("{foo=[2]}", map.toString());
317   }
318 
319   public void testEntriesAfterMultimapUpdate() {
320     ListMultimap<String, Integer> multimap = create();
321     multimap.put("foo", 2);
322     multimap.put("bar", 3);
323     Collection<Map.Entry<String, Integer>> entries = multimap.entries();
324     Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
325     Map.Entry<String, Integer> entrya = iterator.next();
326     Map.Entry<String, Integer> entryb = iterator.next();
327 
328     assertEquals(2, (int) multimap.get("foo").set(0, 4));
329     assertFalse(multimap.containsEntry("foo", 2));
330     assertTrue(multimap.containsEntry("foo", 4));
331     assertTrue(multimap.containsEntry("bar", 3));
332     assertEquals(4, (int) entrya.getValue());
333     assertEquals(3, (int) entryb.getValue());
334 
335     assertTrue(multimap.put("foo", 5));
336     assertTrue(multimap.containsEntry("foo", 5));
337     assertTrue(multimap.containsEntry("foo", 4));
338     assertTrue(multimap.containsEntry("bar", 3));
339     assertEquals(4, (int) entrya.getValue());
340     assertEquals(3, (int) entryb.getValue());
341   }
342 
343   @SuppressWarnings("unchecked")
344   @GwtIncompatible("unreasonably slow")
345   public void testEntriesIteration() {
346     List<Entry<String, Integer>> addItems = ImmutableList.of(
347         Maps.immutableEntry("foo", 99),
348         Maps.immutableEntry("foo", 88),
349         Maps.immutableEntry("bar", 77));
350 
351     for (final int startIndex : new int[] {0, 3, 5}) {
352       List<Entry<String, Integer>> list = Lists.newArrayList(
353           Maps.immutableEntry("foo", 2),
354           Maps.immutableEntry("foo", 3),
355           Maps.immutableEntry("bar", 4),
356           Maps.immutableEntry("bar", 5),
357           Maps.immutableEntry("foo", 6));
358       new ListIteratorTester<Entry<String, Integer>>(3, addItems,
359           ImmutableList.of(SUPPORTS_REMOVE), list, startIndex) {
360         private LinkedListMultimap<String, Integer> multimap;
361 
362         @Override protected ListIterator<Entry<String, Integer>> newTargetIterator() {
363           multimap = create();
364           multimap.putAll("foo", asList(2, 3));
365           multimap.putAll("bar", asList(4, 5));
366           multimap.put("foo", 6);
367           return multimap.entries().listIterator(startIndex);
368         }
369 
370         @Override protected void verify(List<Entry<String, Integer>> elements) {
371           assertEquals(elements, multimap.entries());
372         }
373       }.test();
374     }
375   }
376 
377   @GwtIncompatible("unreasonably slow")
378   public void testKeysIteration() {
379     new IteratorTester<String>(6, MODIFIABLE, newArrayList("foo", "foo", "bar",
380         "bar", "foo"), IteratorTester.KnownOrder.KNOWN_ORDER) {
381       private Multimap<String, Integer> multimap;
382 
383       @Override protected Iterator<String> newTargetIterator() {
384         multimap = create();
385         multimap.putAll("foo", asList(2, 3));
386         multimap.putAll("bar", asList(4, 5));
387         multimap.putAll("foo", asList(6));
388         return multimap.keys().iterator();
389       }
390 
391       @Override protected void verify(List<String> elements) {
392         assertEquals(elements, Lists.newArrayList(multimap.keys()));
393       }
394     }.test();
395   }
396 
397   @GwtIncompatible("unreasonably slow")
398   public void testValuesIteration() {
399     List<Integer> addItems = ImmutableList.of(99, 88, 77);
400 
401     for (final int startIndex : new int[] {0, 3, 5}) {
402       new ListIteratorTester<Integer>(3, addItems,
403           ImmutableList.of(SUPPORTS_REMOVE, SUPPORTS_SET),
404           Lists.newArrayList(2, 3, 4, 5, 6), startIndex) {
405         private LinkedListMultimap<String, Integer> multimap;
406 
407         @Override protected ListIterator<Integer> newTargetIterator() {
408           multimap = create();
409           multimap.put("bar", 2);
410           multimap.putAll("foo", Arrays.asList(3, 4));
411           multimap.put("bar", 5);
412           multimap.put("foo", 6);
413           return multimap.values().listIterator(startIndex);
414         }
415 
416         @Override protected void verify(List<Integer> elements) {
417           assertEquals(elements, multimap.values());
418         }
419       }.test();
420     }
421   }
422 
423   @GwtIncompatible("unreasonably slow")
424   public void testKeySetIteration() {
425     new IteratorTester<String>(6, MODIFIABLE, newLinkedHashSet(asList(
426         "foo", "bar", "baz", "dog", "cat")),
427         IteratorTester.KnownOrder.KNOWN_ORDER) {
428       private Multimap<String, Integer> multimap;
429 
430       @Override protected Iterator<String> newTargetIterator() {
431         multimap = create();
432         multimap.putAll("foo", asList(2, 3));
433         multimap.putAll("bar", asList(4, 5));
434         multimap.putAll("foo", asList(6));
435         multimap.putAll("baz", asList(7, 8));
436         multimap.putAll("dog", asList(9));
437         multimap.putAll("bar", asList(10, 11));
438         multimap.putAll("cat", asList(12, 13, 14));
439         return multimap.keySet().iterator();
440       }
441 
442       @Override protected void verify(List<String> elements) {
443         assertEquals(newHashSet(elements), multimap.keySet());
444       }
445     }.test();
446   }
447 
448   @SuppressWarnings("unchecked")
449   @GwtIncompatible("unreasonably slow")
450   public void testAsSetIteration() {
451     Set<Entry<String, Collection<Integer>>> set = Sets.newLinkedHashSet(asList(
452         Maps.immutableEntry("foo",
453             (Collection<Integer>) asList(2, 3, 6)),
454         Maps.immutableEntry("bar",
455             (Collection<Integer>) asList(4, 5, 10, 11)),
456         Maps.immutableEntry("baz",
457             (Collection<Integer>) asList(7, 8)),
458         Maps.immutableEntry("dog",
459             (Collection<Integer>) asList(9)),
460         Maps.immutableEntry("cat",
461             (Collection<Integer>) asList(12, 13, 14))
462     ));
463 
464     new IteratorTester<Entry<String, Collection<Integer>>>(6, MODIFIABLE, set,
465         IteratorTester.KnownOrder.KNOWN_ORDER) {
466       private Multimap<String, Integer> multimap;
467 
468       @Override protected Iterator<Entry<String, Collection<Integer>>>
469           newTargetIterator() {
470         multimap = create();
471         multimap.putAll("foo", asList(2, 3));
472         multimap.putAll("bar", asList(4, 5));
473         multimap.putAll("foo", asList(6));
474         multimap.putAll("baz", asList(7, 8));
475         multimap.putAll("dog", asList(9));
476         multimap.putAll("bar", asList(10, 11));
477         multimap.putAll("cat", asList(12, 13, 14));
478         return multimap.asMap().entrySet().iterator();
479       }
480 
481       @Override protected void verify(
482           List<Entry<String, Collection<Integer>>> elements) {
483         assertEquals(newHashSet(elements), multimap.asMap().entrySet());
484       }
485     }.test();
486   }
487 
488   public void testEquals() {
489     new EqualsTester()
490         .addEqualityGroup(
491             LinkedListMultimap.create(),
492             LinkedListMultimap.create(),
493             LinkedListMultimap.create(1))
494         .testEquals();
495   }
496 }
497