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 39 import junit.framework.Test; 40 import junit.framework.TestCase; 41 import junit.framework.TestSuite; 42 43 import java.util.Arrays; 44 import java.util.Collection; 45 import java.util.Collections; 46 import java.util.Iterator; 47 import java.util.List; 48 import java.util.ListIterator; 49 import java.util.Map; 50 import java.util.Map.Entry; 51 import java.util.RandomAccess; 52 import java.util.Set; 53 54 /** 55 * Tests for {@code LinkedListMultimap}. 56 * 57 * @author Mike Bostock 58 */ 59 @GwtCompatible(emulated = true) 60 public 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
