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
17package com.google.common.collect;
18
19import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE;
20import static java.util.Arrays.asList;
21import static org.junit.contrib.truth.Truth.ASSERT;
22
23import com.google.common.annotations.GwtCompatible;
24import com.google.common.annotations.GwtIncompatible;
25import com.google.common.collect.testing.ListIteratorTester;
26
27import java.util.Collection;
28import java.util.Collections;
29import java.util.Iterator;
30import java.util.List;
31import java.util.ListIterator;
32import java.util.Map;
33
34/**
35 * Tests for {@code ListMultimap} implementations.
36 *
37 * @author Jared Levy
38 */
39@GwtCompatible(emulated = true)
40public abstract class AbstractListMultimapTest extends AbstractMultimapTest {
41
42  @Override protected abstract ListMultimap<String, Integer> create();
43
44  /**
45   * Test adding duplicate key-value pairs to multimap.
46   */
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   */
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
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   */
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
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   */
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
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   */
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   */
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   */
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
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   */
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   */
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   */
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   */
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   */
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   */
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   */
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   */
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   */
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   */
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")
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
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
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
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
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
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
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   */
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   */
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