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.Helpers.mapEntry;
23import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE;
24import static com.google.common.truth.Truth.assertThat;
25import static java.util.Arrays.asList;
26
27import com.google.common.annotations.GwtCompatible;
28import com.google.common.annotations.GwtIncompatible;
29import com.google.common.collect.testing.IteratorTester;
30import com.google.common.collect.testing.features.CollectionFeature;
31import com.google.common.collect.testing.features.CollectionSize;
32import com.google.common.collect.testing.features.MapFeature;
33import com.google.common.collect.testing.google.SetMultimapTestSuiteBuilder;
34import com.google.common.collect.testing.google.TestStringSetMultimapGenerator;
35import com.google.common.testing.EqualsTester;
36import com.google.common.testing.SerializableTester;
37
38import junit.framework.Test;
39import junit.framework.TestCase;
40import junit.framework.TestSuite;
41
42import java.util.Arrays;
43import java.util.Collection;
44import java.util.Iterator;
45import java.util.List;
46import java.util.Map;
47import java.util.Map.Entry;
48import java.util.Set;
49
50/**
51 * Unit tests for {@code LinkedHashMultimap}.
52 *
53 * @author Jared Levy
54 */
55@GwtCompatible(emulated = true)
56public class LinkedHashMultimapTest extends TestCase {
57
58  @GwtIncompatible("suite")
59  public static Test suite() {
60    TestSuite suite = new TestSuite();
61    suite.addTest(SetMultimapTestSuiteBuilder.using(new TestStringSetMultimapGenerator() {
62        @Override
63        protected SetMultimap<String, String> create(Entry<String, String>[] entries) {
64          SetMultimap<String, String> multimap = LinkedHashMultimap.create();
65          for (Entry<String, String> entry : entries) {
66            multimap.put(entry.getKey(), entry.getValue());
67          }
68          return multimap;
69        }
70      })
71      .named("LinkedHashMultimap")
72      .withFeatures(
73          MapFeature.ALLOWS_NULL_KEYS,
74          MapFeature.ALLOWS_NULL_VALUES,
75          MapFeature.ALLOWS_ANY_NULL_QUERIES,
76          MapFeature.GENERAL_PURPOSE,
77          MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION,
78          CollectionFeature.SUPPORTS_ITERATOR_REMOVE,
79          CollectionFeature.KNOWN_ORDER,
80          CollectionFeature.SERIALIZABLE,
81          CollectionSize.ANY)
82      .createTestSuite());
83    suite.addTestSuite(LinkedHashMultimapTest.class);
84    return suite;
85  }
86
87  public void testValueSetHashTableExpansion() {
88    LinkedHashMultimap<String, Integer> multimap = LinkedHashMultimap.create();
89    for (int z = 1; z <= 100; z++) {
90      multimap.put("a", z);
91      // The Eclipse compiler (and hence GWT) rejects a parameterized cast.
92      @SuppressWarnings("unchecked")
93      LinkedHashMultimap<String, Integer>.ValueSet valueSet =
94          (LinkedHashMultimap.ValueSet) multimap.backingMap().get("a");
95      assertEquals(z, valueSet.size());
96      assertFalse(Hashing.needsResizing(valueSet.size(), valueSet.hashTable.length,
97          LinkedHashMultimap.VALUE_SET_LOAD_FACTOR));
98    }
99  }
100
101  private Multimap<String, Integer> initializeMultimap5() {
102    Multimap<String, Integer> multimap = LinkedHashMultimap.create();
103    multimap.put("foo", 5);
104    multimap.put("bar", 4);
105    multimap.put("foo", 3);
106    multimap.put("cow", 2);
107    multimap.put("bar", 1);
108    return multimap;
109  }
110
111  public void testToString() {
112    Multimap<String, Integer> multimap = LinkedHashMultimap.create();
113    multimap.put("foo", 3);
114    multimap.put("bar", 1);
115    multimap.putAll("foo", Arrays.asList(-1, 2, 4));
116    multimap.putAll("bar", Arrays.asList(2, 3));
117    multimap.put("foo", 1);
118    assertEquals("{foo=[3, -1, 2, 4, 1], bar=[1, 2, 3]}",
119        multimap.toString());
120  }
121
122  public void testOrderingReadOnly() {
123    Multimap<String, Integer> multimap = initializeMultimap5();
124    assertOrderingReadOnly(multimap);
125  }
126
127  public void testOrderingUnmodifiable() {
128    Multimap<String, Integer> multimap = initializeMultimap5();
129    assertOrderingReadOnly(Multimaps.unmodifiableMultimap(multimap));
130  }
131
132  public void testOrderingSynchronized() {
133    Multimap<String, Integer> multimap = initializeMultimap5();
134    assertOrderingReadOnly(Multimaps.synchronizedMultimap(multimap));
135  }
136
137  @GwtIncompatible("SeriazableTester")
138  public void testSerializationOrdering() {
139    Multimap<String, Integer> multimap = initializeMultimap5();
140    Multimap<String, Integer> copy
141        = SerializableTester.reserializeAndAssert(multimap);
142    assertOrderingReadOnly(copy);
143  }
144
145  @GwtIncompatible("SeriazableTester")
146  public void testSerializationOrderingKeysAndEntries() {
147    Multimap<String, Integer> multimap = LinkedHashMultimap.create();
148    multimap.put("a", 1);
149    multimap.put("b", 2);
150    multimap.put("a", 3);
151    multimap.put("c", 4);
152    multimap.remove("a", 1);
153    multimap = SerializableTester.reserializeAndAssert(multimap);
154    assertThat(multimap.keySet()).has().exactly("a", "b", "c").inOrder();
155    assertThat(multimap.entries()).has().exactly(
156        mapEntry("b", 2),
157        mapEntry("a", 3),
158        mapEntry("c", 4)).inOrder();
159    // note that the keys and entries are in different orders
160  }
161
162  private void assertOrderingReadOnly(Multimap<String, Integer> multimap) {
163    assertThat(multimap.get("foo")).has().exactly(5, 3).inOrder();
164    assertThat(multimap.get("bar")).has().exactly(4, 1).inOrder();
165    assertThat(multimap.get("cow")).has().item(2);
166
167    assertThat(multimap.keySet()).has().exactly("foo", "bar", "cow").inOrder();
168    assertThat(multimap.values()).has().exactly(5, 4, 3, 2, 1).inOrder();
169
170    Iterator<Map.Entry<String, Integer>> entryIterator =
171        multimap.entries().iterator();
172    assertEquals(Maps.immutableEntry("foo", 5), entryIterator.next());
173    assertEquals(Maps.immutableEntry("bar", 4), entryIterator.next());
174    assertEquals(Maps.immutableEntry("foo", 3), entryIterator.next());
175    assertEquals(Maps.immutableEntry("cow", 2), entryIterator.next());
176    assertEquals(Maps.immutableEntry("bar", 1), entryIterator.next());
177
178    Iterator<Map.Entry<String, Collection<Integer>>> collectionIterator =
179        multimap.asMap().entrySet().iterator();
180    Map.Entry<String, Collection<Integer>> entry = collectionIterator.next();
181    assertEquals("foo", entry.getKey());
182    assertThat(entry.getValue()).has().exactly(5, 3).inOrder();
183    entry = collectionIterator.next();
184    assertEquals("bar", entry.getKey());
185    assertThat(entry.getValue()).has().exactly(4, 1).inOrder();
186    entry = collectionIterator.next();
187    assertEquals("cow", entry.getKey());
188    assertThat(entry.getValue()).has().item(2);
189  }
190
191  public void testOrderingUpdates() {
192    Multimap<String, Integer> multimap = initializeMultimap5();
193
194    assertThat(multimap.replaceValues("foo", asList(6, 7))).has().exactly(5, 3).inOrder();
195    assertThat(multimap.keySet()).has().exactly("foo", "bar", "cow").inOrder();
196    assertThat(multimap.removeAll("foo")).has().exactly(6, 7).inOrder();
197    assertThat(multimap.keySet()).has().exactly("bar", "cow").inOrder();
198    assertTrue(multimap.remove("bar", 4));
199    assertThat(multimap.keySet()).has().exactly("bar", "cow").inOrder();
200    assertTrue(multimap.remove("bar", 1));
201    assertThat(multimap.keySet()).has().item("cow");
202    multimap.put("bar", 9);
203    assertThat(multimap.keySet()).has().exactly("cow", "bar").inOrder();
204  }
205
206  public void testToStringNullExact() {
207    Multimap<String, Integer> multimap = LinkedHashMultimap.create();
208
209    multimap.put("foo", 3);
210    multimap.put("foo", -1);
211    multimap.put(null, null);
212    multimap.put("bar", 1);
213    multimap.put("foo", 2);
214    multimap.put(null, 0);
215    multimap.put("bar", 2);
216    multimap.put("bar", null);
217    multimap.put("foo", null);
218    multimap.put("foo", 4);
219    multimap.put(null, -1);
220    multimap.put("bar", 3);
221    multimap.put("bar", 1);
222    multimap.put("foo", 1);
223
224    assertEquals(
225        "{foo=[3, -1, 2, null, 4, 1], null=[null, 0, -1], bar=[1, 2, null, 3]}",
226        multimap.toString());
227  }
228
229  public void testPutMultimapOrdered() {
230    Multimap<String, Integer> multimap = LinkedHashMultimap.create();
231    multimap.putAll(initializeMultimap5());
232    assertOrderingReadOnly(multimap);
233  }
234
235  public void testKeysToString_ordering() {
236    Multimap<String, Integer> multimap = initializeMultimap5();
237    assertEquals("[foo x 2, bar x 2, cow]", multimap.keys().toString());
238  }
239
240  public void testCreate() {
241    LinkedHashMultimap<String, Integer> multimap = LinkedHashMultimap.create();
242    multimap.put("foo", 1);
243    multimap.put("bar", 2);
244    multimap.put("foo", 3);
245    assertEquals(ImmutableSet.of(1, 3), multimap.get("foo"));
246  }
247
248  public void testCreateFromMultimap() {
249    Multimap<String, Integer> multimap = LinkedHashMultimap.create();
250    multimap.put("a", 1);
251    multimap.put("b", 2);
252    multimap.put("a", 3);
253    multimap.put("c", 4);
254    LinkedHashMultimap<String, Integer> copy =
255        LinkedHashMultimap.create(multimap);
256    new EqualsTester()
257        .addEqualityGroup(multimap, copy)
258        .testEquals();
259  }
260
261  public void testCreateFromSizes() {
262    LinkedHashMultimap<String, Integer> multimap
263        = LinkedHashMultimap.create(20, 15);
264    multimap.put("foo", 1);
265    multimap.put("bar", 2);
266    multimap.put("foo", 3);
267    assertEquals(ImmutableSet.of(1, 3), multimap.get("foo"));
268  }
269
270  public void testCreateFromIllegalSizes() {
271    try {
272      LinkedHashMultimap.create(-20, 15);
273      fail();
274    } catch (IllegalArgumentException expected) {}
275
276    try {
277      LinkedHashMultimap.create(20, -15);
278      fail();
279    } catch (IllegalArgumentException expected) {}
280  }
281
282  @GwtIncompatible("unreasonably slow")
283  public void testGetIteration() {
284    new IteratorTester<Integer>(6, MODIFIABLE,
285        newLinkedHashSet(asList(2, 3, 4, 7, 8)),
286        IteratorTester.KnownOrder.KNOWN_ORDER) {
287      private Multimap<String, Integer> multimap;
288
289      @Override protected Iterator<Integer> newTargetIterator() {
290        multimap = LinkedHashMultimap.create();
291        multimap.putAll("foo", asList(2, 3, 4));
292        multimap.putAll("bar", asList(5, 6));
293        multimap.putAll("foo", asList(7, 8));
294        return multimap.get("foo").iterator();
295      }
296
297      @Override protected void verify(List<Integer> elements) {
298        assertEquals(newHashSet(elements), multimap.get("foo"));
299      }
300    }.test();
301  }
302
303  @GwtIncompatible("unreasonably slow")
304  public void testEntriesIteration() {
305    @SuppressWarnings("unchecked")
306    Set<Entry<String, Integer>> set = Sets.newLinkedHashSet(asList(
307        Maps.immutableEntry("foo", 2),
308        Maps.immutableEntry("foo", 3),
309        Maps.immutableEntry("bar", 4),
310        Maps.immutableEntry("bar", 5),
311        Maps.immutableEntry("foo", 6)));
312
313    new IteratorTester<Entry<String, Integer>>(6, MODIFIABLE, set,
314        IteratorTester.KnownOrder.KNOWN_ORDER) {
315      private Multimap<String, Integer> multimap;
316
317      @Override protected Iterator<Entry<String, Integer>> newTargetIterator() {
318        multimap = LinkedHashMultimap.create();
319        multimap.putAll("foo", asList(2, 3));
320        multimap.putAll("bar", asList(4, 5));
321        multimap.putAll("foo", asList(6));
322        return multimap.entries().iterator();
323      }
324
325      @Override protected void verify(List<Entry<String, Integer>> elements) {
326        assertEquals(newHashSet(elements), multimap.entries());
327      }
328    }.test();
329  }
330
331  @GwtIncompatible("unreasonably slow")
332  public void testKeysIteration() {
333    new IteratorTester<String>(6, MODIFIABLE, newArrayList("foo", "foo", "bar",
334        "bar", "foo"), IteratorTester.KnownOrder.KNOWN_ORDER) {
335      private Multimap<String, Integer> multimap;
336
337      @Override protected Iterator<String> newTargetIterator() {
338        multimap = LinkedHashMultimap.create();
339        multimap.putAll("foo", asList(2, 3));
340        multimap.putAll("bar", asList(4, 5));
341        multimap.putAll("foo", asList(6));
342        return multimap.keys().iterator();
343      }
344
345      @Override protected void verify(List<String> elements) {
346        assertEquals(elements, Lists.newArrayList(multimap.keys()));
347      }
348    }.test();
349  }
350
351  @GwtIncompatible("unreasonably slow")
352  public void testValuesIteration() {
353    new IteratorTester<Integer>(6, MODIFIABLE, newArrayList(2, 3, 4, 5, 6),
354        IteratorTester.KnownOrder.KNOWN_ORDER) {
355      private Multimap<String, Integer> multimap;
356
357      @Override protected Iterator<Integer> newTargetIterator() {
358        multimap = LinkedHashMultimap.create();
359        multimap.putAll("foo", asList(2, 3));
360        multimap.putAll("bar", asList(4, 5));
361        multimap.putAll("foo", asList(6));
362        return multimap.values().iterator();
363      }
364
365      @Override protected void verify(List<Integer> elements) {
366        assertEquals(elements, Lists.newArrayList(multimap.values()));
367      }
368    }.test();
369  }
370
371  @GwtIncompatible("unreasonably slow")
372  public void testKeySetIteration() {
373    new IteratorTester<String>(6, MODIFIABLE,
374        newLinkedHashSet(asList("foo", "bar", "baz", "dog", "cat")),
375        IteratorTester.KnownOrder.KNOWN_ORDER) {
376      private Multimap<String, Integer> multimap;
377
378      @Override protected Iterator<String> newTargetIterator() {
379        multimap = LinkedHashMultimap.create();
380        multimap.putAll("foo", asList(2, 3));
381        multimap.putAll("bar", asList(4, 5));
382        multimap.putAll("foo", asList(6));
383        multimap.putAll("baz", asList(7, 8));
384        multimap.putAll("dog", asList(9));
385        multimap.putAll("bar", asList(10, 11));
386        multimap.putAll("cat", asList(12, 13, 14));
387        return multimap.keySet().iterator();
388      }
389
390      @Override protected void verify(List<String> elements) {
391        assertEquals(newHashSet(elements), multimap.keySet());
392      }
393    }.test();
394  }
395
396  @GwtIncompatible("unreasonably slow")
397  public void testAsSetIteration() {
398    @SuppressWarnings("unchecked")
399    Set<Entry<String, Collection<Integer>>> set = newLinkedHashSet(asList(
400        Maps.immutableEntry("foo",
401            (Collection<Integer>) Sets.newHashSet(2, 3, 6)),
402        Maps.immutableEntry("bar",
403            (Collection<Integer>) Sets.newHashSet(4, 5, 10, 11)),
404        Maps.immutableEntry("baz",
405            (Collection<Integer>) Sets.newHashSet(7, 8)),
406        Maps.immutableEntry("dog",
407            (Collection<Integer>) Sets.newHashSet(9)),
408        Maps.immutableEntry("cat",
409            (Collection<Integer>) Sets.newHashSet(12, 13, 14))
410    ));
411    new IteratorTester<Entry<String, Collection<Integer>>>(6, MODIFIABLE, set,
412        IteratorTester.KnownOrder.KNOWN_ORDER) {
413      private Multimap<String, Integer> multimap;
414
415      @Override protected Iterator<Entry<String, Collection<Integer>>>
416          newTargetIterator() {
417        multimap = LinkedHashMultimap.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.asMap().entrySet().iterator();
426      }
427
428      @Override protected void verify(
429          List<Entry<String, Collection<Integer>>> elements) {
430        assertEquals(newHashSet(elements), multimap.asMap().entrySet());
431      }
432    }.test();
433  }
434}
435