• 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.testing.IteratorFeature.MODIFIABLE;
20 import static java.util.Arrays.asList;
21 import static org.junit.contrib.truth.Truth.ASSERT;
22 
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.common.collect.testing.ListIteratorTester;
26 
27 import java.util.Collection;
28 import java.util.Collections;
29 import java.util.Iterator;
30 import java.util.List;
31 import java.util.ListIterator;
32 import java.util.Map;
33 
34 /**
35  * Tests for {@code ListMultimap} implementations.
36  *
37  * @author Jared Levy
38  */
39 @GwtCompatible(emulated = true)
40 public abstract class AbstractListMultimapTest extends AbstractMultimapTest {
41 
create()42   @Override protected abstract ListMultimap<String, Integer> create();
43 
44   /**
45    * Test adding duplicate key-value pairs to multimap.
46    */
testDuplicates()47   public void testDuplicates() {
48     Multimap<String, Integer> multimap = create();
49     multimap.put("foo", 1);
50     multimap.put("foo", 3);
51     multimap.put("bar", 3);
52     multimap.put("foo", 1);
53     assertEquals(4, multimap.size());
54     assertTrue(multimap.containsEntry("foo", 1));
55     multimap.remove("foo", 1);
56     assertEquals(3, multimap.size());
57     assertTrue(multimap.containsEntry("foo", 1));
58   }
59 
60   /**
61    * Test returned boolean when adding duplicate key-value pairs to multimap.
62    */
testPutReturn()63   public void testPutReturn() {
64     Multimap<String, Integer> multimap = create();
65     assertTrue(multimap.put("foo", 1));
66     assertTrue(multimap.put("foo", 1));
67     assertTrue(multimap.put("foo", 3));
68     assertTrue(multimap.put("bar", 5));
69   }
70 
testPutAllReturn_existingElements()71   public void testPutAllReturn_existingElements() {
72     Multimap<String, Integer> multimap = create();
73     assertTrue(multimap.putAll("foo", asList(1, 2, 3)));
74     assertTrue(multimap.put("foo", 1));
75     assertTrue(multimap.putAll("foo", asList(1, 2, 3)));
76     assertTrue(multimap.putAll("foo", asList(1, 3)));
77 
78     Multimap<String, Integer> other = create();
79     other.putAll("foo", asList(1, 2));
80     assertTrue(multimap.putAll(other));
81 
82     other.putAll("bar", asList(1, 2));
83     assertTrue(multimap.putAll(other));
84     assertTrue(other.putAll(multimap));
85   }
86 
87   /**
88    * Confirm that get() returns a collection equal to a List.
89    */
testGetEquals()90   public void testGetEquals() {
91     Multimap<String, Integer> multimap = create();
92     multimap.put("foo", 1);
93     multimap.put("foo", 3);
94     assertEquals(ImmutableList.of(1, 3), multimap.get("foo"));
95   }
96 
testAsMapEquals()97   public void testAsMapEquals() {
98     Multimap<String, Integer> multimap = getMultimap();
99     multimap.put("foo", 1);
100     multimap.put("foo", nullValue());
101     multimap.put(nullKey(), 3);
102     Map<String, Collection<Integer>> map = multimap.asMap();
103 
104     Map<String, Collection<Integer>> equalMap = Maps.newHashMap();
105     equalMap.put("foo", asList(1, nullValue()));
106     equalMap.put(nullKey(), asList(3));
107     assertEquals(map, equalMap);
108     assertEquals(equalMap, map);
109     assertEquals(equalMap.hashCode(), multimap.hashCode());
110 
111     Map<String, Collection<Integer>> unequalMap = Maps.newHashMap();
112     equalMap.put("foo", asList(3, nullValue()));
113     equalMap.put(nullKey(), asList(1));
114     assertFalse(map.equals(unequalMap));
115     assertFalse(unequalMap.equals(map));
116   }
117 
118   /**
119    * Confirm that asMap().entrySet() returns values equal to a List.
120    */
testAsMapEntriesEquals()121   public void testAsMapEntriesEquals() {
122     Multimap<String, Integer> multimap = create();
123     multimap.put("foo", 1);
124     multimap.put("foo", 3);
125     Iterator<Map.Entry<String, Collection<Integer>>> i =
126         multimap.asMap().entrySet().iterator();
127     Map.Entry<String, Collection<Integer>> entry = i.next();
128     assertEquals("foo", entry.getKey());
129     assertEquals(ImmutableList.of(1, 3), entry.getValue());
130     assertFalse(i.hasNext());
131   }
132 
testAsMapValuesRemove()133   public void testAsMapValuesRemove() {
134     Multimap<String, Integer> multimap = create();
135     multimap.put("foo", 1);
136     multimap.put("foo", 3);
137     multimap.put("bar", 3);
138     Collection<Collection<Integer>> asMapValues = multimap.asMap().values();
139     assertFalse(asMapValues.remove(asList(3, 1)));
140     assertEquals(3, multimap.size());
141     assertTrue(asMapValues.remove(asList(1, 3)));
142     assertEquals(1, multimap.size());
143   }
144 
145   /**
146    * Test multimap.equals() for multimaps with different insertion orderings.
147    */
testEqualsOrdering()148   public void testEqualsOrdering() {
149     Multimap<String, Integer> multimap = create();
150     multimap.put("foo", 1);
151     multimap.put("foo", 3);
152     multimap.put("bar", 3);
153     Multimap<String, Integer> multimap2 = create();
154     multimap2.put("foo", 3);
155     multimap2.put("foo", 1);
156     multimap2.put("bar", 3);
157     assertFalse(multimap.equals(multimap2));
158   }
159 
160   /**
161    * Test the ordering of the values returned by multimap.get().
162    */
testPutGetOrdering()163   public void testPutGetOrdering() {
164     Multimap<String, Integer> multimap = create();
165     multimap.put("foo", 1);
166     multimap.put("foo", 3);
167     multimap.put("bar", 3);
168     Iterator<Integer> values = multimap.get("foo").iterator();
169     assertEquals(Integer.valueOf(1), values.next());
170     assertEquals(Integer.valueOf(3), values.next());
171   }
172 
173   /**
174    * Test List-specific methods on List returned by get().
175    */
testListMethods()176   public void testListMethods() {
177     ListMultimap<String, Integer> multimap = create();
178     multimap.put("foo", 1);
179     multimap.put("foo", 3);
180     multimap.put("foo", 5);
181     List<Integer> list = multimap.get("foo");
182 
183     list.add(1, 2);
184     assertEquals(4, multimap.size());
185     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 5);
186 
187     list.addAll(3, asList(4, 8));
188     assertEquals(6, multimap.size());
189     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 8, 5);
190 
191     assertEquals(8, list.get(4).intValue());
192     assertEquals(4, list.indexOf(8));
193     assertEquals(4, list.lastIndexOf(8));
194 
195     list.remove(4);
196     assertEquals(5, multimap.size());
197     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5);
198 
199     list.set(4, 10);
200     assertEquals(5, multimap.size());
201     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 10);
202   }
203 
testListMethodsIncludingSublist()204   public void testListMethodsIncludingSublist() {
205     ListMultimap<String, Integer> multimap = create();
206     multimap.put("foo", 1);
207     multimap.put("foo", 2);
208     multimap.put("foo", 3);
209     multimap.put("foo", 4);
210     multimap.put("foo", 10);
211     List<Integer> list = multimap.get("foo");
212 
213     List<Integer> sublist = list.subList(1, 4);
214     ASSERT.that(sublist).hasContentsInOrder(2, 3, 4);
215     list.set(3, 6);
216     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 6, 10);
217   }
218 
219   /**
220    * Test sublist of List returned by get() after the original list is updated.
221    */
testSublistAfterListUpdate()222   public void testSublistAfterListUpdate() {
223     ListMultimap<String, Integer> multimap = create();
224     multimap.put("foo", 1);
225     multimap.put("foo", 2);
226     multimap.put("foo", 3);
227     multimap.put("foo", 4);
228     multimap.put("foo", 5);
229 
230     List<Integer> list = multimap.get("foo");
231     List<Integer> sublist = list.subList(1, 4);
232     ASSERT.that(sublist).hasContentsInOrder(2, 3, 4);
233     list.set(3, 6);
234     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 6, 5);
235     ASSERT.that(sublist).hasContentsInOrder(2, 3, 6);
236   }
237 
238   /**
239    * Test ListIterator methods that don't change the multimap.
240    */
testListIteratorNavigate()241   public void testListIteratorNavigate() {
242     ListMultimap<String, Integer> multimap = create();
243     multimap.put("foo", 1);
244     multimap.put("foo", 3);
245     List<Integer> list = multimap.get("foo");
246     ListIterator<Integer> iterator = list.listIterator();
247 
248     assertFalse(iterator.hasPrevious());
249     assertTrue(iterator.hasNext());
250     assertEquals(0, iterator.nextIndex());
251     assertEquals(-1, iterator.previousIndex());
252 
253     assertEquals(1, iterator.next().intValue());
254     assertEquals(3, iterator.next().intValue());
255     assertTrue(iterator.hasPrevious());
256     assertFalse(iterator.hasNext());
257 
258     assertEquals(3, iterator.previous().intValue());
259     assertEquals(1, iterator.previous().intValue());
260   }
261 
262   /**
263    * Test ListIterator methods that change the multimap.
264    */
testListIteratorUpdate()265   public void testListIteratorUpdate() {
266     ListMultimap<String, Integer> multimap = create();
267     multimap.put("foo", 1);
268     multimap.put("foo", 3);
269     multimap.put("foo", 5);
270     List<Integer> list = multimap.get("foo");
271     ListIterator<Integer> iterator = list.listIterator();
272 
273     assertEquals(1, iterator.next().intValue());
274     iterator.set(2);
275     ASSERT.that(multimap.get("foo")).hasContentsInOrder(2, 3, 5);
276 
277     assertEquals(3, iterator.next().intValue());
278     iterator.remove();
279     ASSERT.that(multimap.get("foo")).hasContentsInOrder(2, 5);
280   }
281 
282   /**
283    * Test calling toString() on the multimap, which does not have a
284    * deterministic iteration order for keys but does for values.
285    */
testToString()286   public void testToString() {
287     String s = createSample().toString();
288     assertTrue(s.equals("{foo=[3, -1, 2, 4, 1], bar=[1, 2, 3, 1]}")
289         || s.equals("{bar=[1, 2, 3, 1], foo=[3, -1, 2, 4, 1]}"));
290   }
291 
292   /**
293    * Test calling set() on a sublist.
294    */
testSublistSet()295   public void testSublistSet() {
296     ListMultimap<String, Integer> multimap = create();
297     multimap.putAll("foo", asList(1, 2, 3, 4, 5));
298     List<Integer> list = multimap.get("foo");
299     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5);
300     List<Integer> sublist = list.subList(1, 4);
301     ASSERT.that(sublist).hasContentsInOrder(2, 3, 4);
302 
303     sublist.set(1, 6);
304     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 6, 4, 5);
305   }
306 
307   /**
308    * Test removing elements from a sublist.
309    */
testSublistRemove()310   public void testSublistRemove() {
311     ListMultimap<String, Integer> multimap = create();
312     multimap.putAll("foo", asList(1, 2, 3, 4, 5));
313     List<Integer> list = multimap.get("foo");
314     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5);
315     List<Integer> sublist = list.subList(1, 4);
316     ASSERT.that(sublist).hasContentsInOrder(2, 3, 4);
317 
318     sublist.remove(1);
319     assertEquals(4, multimap.size());
320     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 4, 5);
321 
322     sublist.removeAll(Collections.singleton(4));
323     assertEquals(3, multimap.size());
324     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 5);
325 
326     sublist.remove(0);
327     assertEquals(2, multimap.size());
328     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 5);
329   }
330 
331   /**
332    * Test adding elements to a sublist.
333    */
testSublistAdd()334   public void testSublistAdd() {
335     ListMultimap<String, Integer> multimap = create();
336     multimap.putAll("foo", asList(1, 2, 3, 4, 5));
337     List<Integer> list = multimap.get("foo");
338     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5);
339     List<Integer> sublist = list.subList(1, 4);
340     ASSERT.that(sublist).hasContentsInOrder(2, 3, 4);
341 
342     sublist.add(6);
343     assertEquals(6, multimap.size());
344     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 6, 5);
345 
346     sublist.add(0, 7);
347     assertEquals(7, multimap.size());
348     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 7, 2, 3, 4, 6, 5);
349   }
350 
351   /**
352    * Test clearing a sublist.
353    */
testSublistClear()354   public void testSublistClear() {
355     ListMultimap<String, Integer> multimap = create();
356     multimap.putAll("foo", asList(1, 2, 3, 4, 5));
357     List<Integer> list = multimap.get("foo");
358     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5);
359     List<Integer> sublist = list.subList(1, 4);
360     ASSERT.that(sublist).hasContentsInOrder(2, 3, 4);
361 
362     sublist.clear();
363     assertEquals(2, multimap.size());
364     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 5);
365   }
366 
367   /**
368    * Test adding elements to an empty sublist with an empty ancestor.
369    */
testSublistAddToEmpty()370   public void testSublistAddToEmpty() {
371     ListMultimap<String, Integer> multimap = create();
372     multimap.putAll("foo", asList(1, 2, 3, 4, 5));
373     List<Integer> list = multimap.get("foo");
374     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5);
375     List<Integer> sublist = list.subList(0, 5);
376     ASSERT.that(sublist).hasContentsInOrder(1, 2, 3, 4, 5);
377 
378     sublist.retainAll(Collections.EMPTY_LIST);
379     assertTrue(multimap.isEmpty());
380 
381     sublist.add(6);
382     assertEquals(1, multimap.size());
383     assertTrue(multimap.containsEntry("foo", 6));
384   }
385 
386   /**
387    * Test updates through a list iterator retrieved by
388    * multimap.get(key).listIterator(index).
389    */
testListIteratorIndexUpdate()390   public void testListIteratorIndexUpdate() {
391     ListMultimap<String, Integer> multimap = create();
392     multimap.putAll("foo", asList(1, 2, 3, 4, 5));
393     ListIterator<Integer> iterator = multimap.get("foo").listIterator(1);
394 
395     assertEquals(2, iterator.next().intValue());
396     iterator.set(6);
397     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 6, 3, 4, 5);
398 
399     assertTrue(iterator.hasNext());
400     assertEquals(3, iterator.next().intValue());
401     iterator.remove();
402     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 6, 4, 5);
403     assertEquals(4, multimap.size());
404   }
405 
406   @GwtIncompatible("unreasonable slow")
testGetIteration()407   public void testGetIteration() {
408     List<Integer> addItems = ImmutableList.of(99, 88, 77);
409 
410     for (final int startIndex : new int[] {0, 3, 5}) {
411       new ListIteratorTester<Integer>(3, addItems, MODIFIABLE,
412           Lists.newArrayList(2, 3, 4, 7, 8), startIndex) {
413         private ListMultimap<String, Integer> multimap;
414 
415         @Override protected ListIterator<Integer> newTargetIterator() {
416           multimap = create();
417           multimap.put("bar", 1);
418           multimap.putAll("foo", asList(2, 3, 4));
419           multimap.putAll("bar", asList(5, 6));
420           multimap.putAll("foo", asList(7, 8));
421           return multimap.get("foo").listIterator(startIndex);
422         }
423 
424         @Override protected void verify(List<Integer> elements) {
425           assertEquals(elements, multimap.get("foo"));
426         }
427       }.test();
428     }
429   }
430 
testListGetSet()431   public void testListGetSet() {
432     ListMultimap<String, Integer> map = create();
433     map.put("bar", 1);
434     map.get("bar").set(0, 2);
435     assertEquals("{bar=[2]}", map.toString());
436     assertEquals("[bar=2]", map.entries().toString());
437   }
438 
testListPutAllIterable()439   public void testListPutAllIterable() {
440     Multimap<String, Integer> map = create();
441     map.putAll("foo", asList(1, 2));
442     assertEquals("{foo=[1, 2]}", map.toString());
443     assertEquals("[foo=1, foo=2]", map.entries().toString());
444   }
445 
testListRemoveAll()446   public void testListRemoveAll() {
447     Multimap<String, Integer> map = create();
448     map.put("bar", 1);
449     map.put("foo", 2);
450     map.put("bar", 3);
451     map.put("bar", 4);
452     map.removeAll("foo");
453     assertEquals("[bar=1, bar=3, bar=4]", map.entries().toString());
454     assertEquals("{bar=[1, 3, 4]}", map.toString());
455     map.removeAll("bar");
456     assertEquals("[]", map.entries().toString());
457     assertEquals("{}", map.toString());
458   }
459 
testListEquals()460   public void testListEquals() {
461     Multimap<String, Integer> map1 = create();
462     map1.put("bar", 1);
463     map1.put("foo", 2);
464     map1.put("bar", 3);
465     Multimap<String, Integer> map2 = ArrayListMultimap.create();
466     map2.putAll(map1);
467     assertTrue(map1.equals(map2));
468     assertTrue(map2.equals(map1));
469     assertFalse(map1.equals(null));
470     assertFalse(map1.equals(new Object()));
471   }
472 
testListHashCode()473   public void testListHashCode() {
474     Multimap<String, Integer> map1 = create();
475     map1.put("bar", 1);
476     map1.put("foo", 2);
477     map1.put("bar", 3);
478     Multimap<String, Integer> map2 = ArrayListMultimap.create();
479     map2.putAll(map1);
480     assertEquals(map1.hashCode(), map2.hashCode());
481   }
482 
testListAddIndex()483   public void testListAddIndex() {
484     ListMultimap<String, Integer> multimap = create();
485     multimap.put("bar", 11);
486     multimap.put("bar", 12);
487     multimap.get("bar").add(0, 13);
488     ASSERT.that(multimap.get("bar")).hasContentsInOrder(13, 11, 12);
489   }
490 
491   /**
492    * According to the AbstractCollection.retainAll() implementation,
493    * {@code A.retainAll(B)} should keep all occurrences of each object in B,
494    * so even though the collection that this test passes to retainAll() has
495    * fewer occurrences of 2 than the multimap has, all of the 2s should be
496    * retained.
497    */
testGetRetainAll()498   public void testGetRetainAll() {
499     // TODO: test this logic in ListRetainAllTester
500     ListMultimap<String, Integer> multimap = create();
501     multimap.putAll("foo", asList(1, 2, 2, 3, 3, 3));
502 
503     multimap.get("foo").retainAll(asList(1, 2, 4));
504     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 2);
505   }
506 
507   /**
508    * According to the AbstractCollection.removeAll() implementation,
509    * {@code A.removeAll(B)} should remove all occurrences of each object in B,
510    * so even though the collection that this test passes to removeAll() has
511    * fewer occurrences of 2 and 3 than the multimap has, there should be no
512    * 2s or 3s remaining in the collection.
513    */
testGetRemoveAll_someValuesRemain()514   public void testGetRemoveAll_someValuesRemain() {
515     // TODO: test this logic in ListRemoveAllTester
516     ListMultimap<String, Integer> multimap = create();
517     multimap.putAll("foo", asList(1, 2, 2, 3, 3, 3));
518 
519     multimap.get("foo").removeAll(asList(2, 3, 3, 4));
520     ASSERT.that(multimap.get("foo")).hasContentsInOrder(1);
521   }
522 }
523