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