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 com.google.common.truth.Truth.assertThat;
26import static java.util.Arrays.asList;
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;
32import com.google.common.collect.testing.features.CollectionFeature;
33import com.google.common.collect.testing.features.CollectionSize;
34import com.google.common.collect.testing.features.MapFeature;
35import com.google.common.collect.testing.google.ListMultimapTestSuiteBuilder;
36import com.google.common.collect.testing.google.TestStringListMultimapGenerator;
37import com.google.common.testing.EqualsTester;
38
39import junit.framework.Test;
40import junit.framework.TestCase;
41import junit.framework.TestSuite;
42
43import java.util.Arrays;
44import java.util.Collection;
45import java.util.Collections;
46import java.util.Iterator;
47import java.util.List;
48import java.util.ListIterator;
49import java.util.Map;
50import java.util.Map.Entry;
51import java.util.RandomAccess;
52import java.util.Set;
53
54/**
55 * Tests for {@code LinkedListMultimap}.
56 *
57 * @author Mike Bostock
58 */
59@GwtCompatible(emulated = true)
60public 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