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