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