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