View Javadoc
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 }