LinkedListMultimapTest.java revision 3c77433663281544363151bf284b0240dfd22a42
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.truth0.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;
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.TestSuite;
41
42import java.util.Arrays;
43import java.util.Collection;
44import java.util.Collections;
45import java.util.Iterator;
46import java.util.List;
47import java.util.ListIterator;
48import java.util.Map;
49import java.util.Map.Entry;
50import java.util.RandomAccess;
51import java.util.Set;
52
53/**
54 * Tests for {@code LinkedListMultimap}.
55 *
56 * @author Mike Bostock
57 */
58@GwtCompatible(emulated = true)
59public class LinkedListMultimapTest extends AbstractListMultimapTest {
60
61  @GwtIncompatible("suite")
62  public static Test suite() {
63    TestSuite suite = new TestSuite();
64    suite.addTest(ListMultimapTestSuiteBuilder.using(new TestStringListMultimapGenerator() {
65        @Override
66        protected ListMultimap<String, String> create(Entry<String, String>[] entries) {
67          ListMultimap<String, String> multimap = LinkedListMultimap.create();
68          for (Entry<String, String> entry : entries) {
69            multimap.put(entry.getKey(), entry.getValue());
70          }
71          return multimap;
72        }
73      })
74      .named("LinkedListMultimap")
75      .withFeatures(
76          MapFeature.ALLOWS_NULL_KEYS,
77          MapFeature.ALLOWS_NULL_VALUES,
78          MapFeature.GENERAL_PURPOSE,
79          CollectionFeature.SERIALIZABLE,
80          CollectionFeature.KNOWN_ORDER,
81          CollectionSize.ANY)
82      .createTestSuite());
83    suite.addTestSuite(LinkedListMultimapTest.class);
84    return suite;
85  }
86
87  @Override protected LinkedListMultimap<String, Integer> create() {
88    return LinkedListMultimap.create();
89  }
90
91  /**
92   * Confirm that get() returns a List that doesn't implement RandomAccess.
93   */
94  public void testGetRandomAccess() {
95    Multimap<String, Integer> multimap = create();
96    multimap.put("foo", 1);
97    multimap.put("foo", 3);
98    assertFalse(multimap.get("foo") instanceof RandomAccess);
99    assertFalse(multimap.get("bar") instanceof RandomAccess);
100  }
101
102  /**
103   * Confirm that removeAll() returns a List that implements RandomAccess, even
104   * though get() doesn't.
105   */
106  public void testRemoveAllRandomAccess() {
107    Multimap<String, Integer> multimap = create();
108    multimap.put("foo", 1);
109    multimap.put("foo", 3);
110    assertTrue(multimap.removeAll("foo") instanceof RandomAccess);
111    assertTrue(multimap.removeAll("bar") instanceof RandomAccess);
112  }
113
114  /**
115   * Confirm that replaceValues() returns a List that implements RandomAccess,
116   * even though get() doesn't.
117   */
118  public void testReplaceValuesRandomAccess() {
119    Multimap<String, Integer> multimap = create();
120    multimap.put("foo", 1);
121    multimap.put("foo", 3);
122    assertTrue(multimap.replaceValues("foo", Arrays.asList(2, 4))
123        instanceof RandomAccess);
124    assertTrue(multimap.replaceValues("bar", Arrays.asList(2, 4))
125        instanceof RandomAccess);
126  }
127
128  public void testCreateFromMultimap() {
129    Multimap<String, Integer> multimap = createSample();
130    LinkedListMultimap<String, Integer> copy =
131        LinkedListMultimap.create(multimap);
132    assertEquals(multimap, copy);
133  }
134
135  public void testCreateFromSize() {
136    LinkedListMultimap<String, Integer> multimap
137        = LinkedListMultimap.create(20);
138    multimap.put("foo", 1);
139    multimap.put("bar", 2);
140    multimap.put("foo", 3);
141    assertEquals(ImmutableList.of(1, 3), multimap.get("foo"));
142  }
143
144  public void testCreateFromIllegalSize() {
145    try {
146      LinkedListMultimap.create(-20);
147      fail();
148    } catch (IllegalArgumentException expected) {}
149  }
150
151  /* "Linked" prefix avoids collision with AbstractMultimapTest. */
152
153  public void testLinkedToString() {
154    assertEquals("{foo=[3, -1, 2, 4, 1], bar=[1, 2, 3, 1]}",
155        createSample().toString());
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    ASSERT.that(values).has().allOf(1, 2, 3).inOrder();
234    map.clear();
235    assertEquals(Collections.emptyList(), foos);
236    ASSERT.that(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    ASSERT.that(map.keys()).has().allOf("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    ASSERT.that(entry.getValue()).has().allOf(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    ASSERT.that(entry.getValue()).has().item(2);
315    assertFalse(entries.hasNext());
316    assertEquals("{foo=[2]}", map.toString());
317  }
318
319  /**
320   * Test calling setValue() on an entry returned by multimap.entries().
321   */
322  @Override public void testEntrySetValue() {
323    ListMultimap<String, Integer> multimap = create();
324    multimap.put("foo", 1);
325    multimap.put("bar", 3);
326    Collection<Map.Entry<String, Integer>> entries = multimap.entries();
327    Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
328    Map.Entry<String, Integer> entrya = iterator.next();
329    Map.Entry<String, Integer> entryb = iterator.next();
330
331    int oldValue = entrya.setValue(2);
332    assertEquals(1, oldValue);
333    assertFalse(multimap.containsEntry("foo", 1));
334    assertTrue(multimap.containsEntry("foo", 2));
335    assertTrue(multimap.containsEntry("bar", 3));
336    assertEquals(2, (int) entrya.getValue());
337    assertEquals(3, (int) entryb.getValue());
338  }
339
340  public void testEntriesAfterMultimapUpdate() {
341    ListMultimap<String, Integer> multimap = create();
342    multimap.put("foo", 2);
343    multimap.put("bar", 3);
344    Collection<Map.Entry<String, Integer>> entries = multimap.entries();
345    Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
346    Map.Entry<String, Integer> entrya = iterator.next();
347    Map.Entry<String, Integer> entryb = iterator.next();
348
349    assertEquals(2, (int) multimap.get("foo").set(0, 4));
350    assertFalse(multimap.containsEntry("foo", 2));
351    assertTrue(multimap.containsEntry("foo", 4));
352    assertTrue(multimap.containsEntry("bar", 3));
353    assertEquals(4, (int) entrya.getValue());
354    assertEquals(3, (int) entryb.getValue());
355
356    assertTrue(multimap.put("foo", 5));
357    assertTrue(multimap.containsEntry("foo", 5));
358    assertTrue(multimap.containsEntry("foo", 4));
359    assertTrue(multimap.containsEntry("bar", 3));
360    assertEquals(4, (int) entrya.getValue());
361    assertEquals(3, (int) entryb.getValue());
362  }
363
364  @SuppressWarnings("unchecked")
365  @GwtIncompatible("unreasonable slow")
366  public void testEntriesIteration() {
367    List<Entry<String, Integer>> addItems = ImmutableList.of(
368        Maps.immutableEntry("foo", 99),
369        Maps.immutableEntry("foo", 88),
370        Maps.immutableEntry("bar", 77));
371
372    for (final int startIndex : new int[] {0, 3, 5}) {
373      List<Entry<String, Integer>> list = Lists.newArrayList(
374          Maps.immutableEntry("foo", 2),
375          Maps.immutableEntry("foo", 3),
376          Maps.immutableEntry("bar", 4),
377          Maps.immutableEntry("bar", 5),
378          Maps.immutableEntry("foo", 6));
379      new ListIteratorTester<Entry<String, Integer>>(3, addItems,
380          ImmutableList.of(SUPPORTS_REMOVE), list, startIndex) {
381        private LinkedListMultimap<String, Integer> multimap;
382
383        @Override protected ListIterator<Entry<String, Integer>> newTargetIterator() {
384          multimap = create();
385          multimap.putAll("foo", asList(2, 3));
386          multimap.putAll("bar", asList(4, 5));
387          multimap.put("foo", 6);
388          return multimap.entries().listIterator(startIndex);
389        }
390
391        @Override protected void verify(List<Entry<String, Integer>> elements) {
392          assertEquals(elements, multimap.entries());
393        }
394      }.test();
395    }
396  }
397
398  @GwtIncompatible("unreasonable slow")
399  public void testKeysIteration() {
400    new IteratorTester<String>(6, MODIFIABLE, newArrayList("foo", "foo", "bar",
401        "bar", "foo"), IteratorTester.KnownOrder.KNOWN_ORDER) {
402      private Multimap<String, Integer> multimap;
403
404      @Override protected Iterator<String> newTargetIterator() {
405        multimap = create();
406        multimap.putAll("foo", asList(2, 3));
407        multimap.putAll("bar", asList(4, 5));
408        multimap.putAll("foo", asList(6));
409        return multimap.keys().iterator();
410      }
411
412      @Override protected void verify(List<String> elements) {
413        assertEquals(elements, Lists.newArrayList(multimap.keys()));
414      }
415    }.test();
416  }
417
418  @GwtIncompatible("unreasonable slow")
419  public void testValuesIteration() {
420    List<Integer> addItems = ImmutableList.of(99, 88, 77);
421
422    for (final int startIndex : new int[] {0, 3, 5}) {
423      new ListIteratorTester<Integer>(3, addItems,
424          ImmutableList.of(SUPPORTS_REMOVE, SUPPORTS_SET),
425          Lists.newArrayList(2, 3, 4, 5, 6), startIndex) {
426        private LinkedListMultimap<String, Integer> multimap;
427
428        @Override protected ListIterator<Integer> newTargetIterator() {
429          multimap = create();
430          multimap.put("bar", 2);
431          multimap.putAll("foo", Arrays.asList(3, 4));
432          multimap.put("bar", 5);
433          multimap.put("foo", 6);
434          return multimap.values().listIterator(startIndex);
435        }
436
437        @Override protected void verify(List<Integer> elements) {
438          assertEquals(elements, multimap.values());
439        }
440      }.test();
441    }
442  }
443
444  @GwtIncompatible("unreasonable slow")
445  public void testKeySetIteration() {
446    new IteratorTester<String>(6, MODIFIABLE, newLinkedHashSet(asList(
447        "foo", "bar", "baz", "dog", "cat")),
448        IteratorTester.KnownOrder.KNOWN_ORDER) {
449      private Multimap<String, Integer> multimap;
450
451      @Override protected Iterator<String> newTargetIterator() {
452        multimap = create();
453        multimap.putAll("foo", asList(2, 3));
454        multimap.putAll("bar", asList(4, 5));
455        multimap.putAll("foo", asList(6));
456        multimap.putAll("baz", asList(7, 8));
457        multimap.putAll("dog", asList(9));
458        multimap.putAll("bar", asList(10, 11));
459        multimap.putAll("cat", asList(12, 13, 14));
460        return multimap.keySet().iterator();
461      }
462
463      @Override protected void verify(List<String> elements) {
464        assertEquals(newHashSet(elements), multimap.keySet());
465      }
466    }.test();
467  }
468
469  @SuppressWarnings("unchecked")
470  @GwtIncompatible("unreasonable slow")
471  public void testAsSetIteration() {
472    Set<Entry<String, Collection<Integer>>> set = Sets.newLinkedHashSet(asList(
473        Maps.immutableEntry("foo",
474            (Collection<Integer>) asList(2, 3, 6)),
475        Maps.immutableEntry("bar",
476            (Collection<Integer>) asList(4, 5, 10, 11)),
477        Maps.immutableEntry("baz",
478            (Collection<Integer>) asList(7, 8)),
479        Maps.immutableEntry("dog",
480            (Collection<Integer>) asList(9)),
481        Maps.immutableEntry("cat",
482            (Collection<Integer>) asList(12, 13, 14))
483    ));
484
485    new IteratorTester<Entry<String, Collection<Integer>>>(6, MODIFIABLE, set,
486        IteratorTester.KnownOrder.KNOWN_ORDER) {
487      private Multimap<String, Integer> multimap;
488
489      @Override protected Iterator<Entry<String, Collection<Integer>>>
490          newTargetIterator() {
491        multimap = create();
492        multimap.putAll("foo", asList(2, 3));
493        multimap.putAll("bar", asList(4, 5));
494        multimap.putAll("foo", asList(6));
495        multimap.putAll("baz", asList(7, 8));
496        multimap.putAll("dog", asList(9));
497        multimap.putAll("bar", asList(10, 11));
498        multimap.putAll("cat", asList(12, 13, 14));
499        return multimap.asMap().entrySet().iterator();
500      }
501
502      @Override protected void verify(
503          List<Entry<String, Collection<Integer>>> elements) {
504        assertEquals(newHashSet(elements), multimap.asMap().entrySet());
505      }
506    }.test();
507  }
508
509  public void testEquals() {
510    new EqualsTester()
511        .addEqualityGroup(
512            LinkedListMultimap.create(),
513            LinkedListMultimap.create(),
514            LinkedListMultimap.create(1))
515        .testEquals();
516  }
517}
518