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.testing.IteratorFeature.MODIFIABLE; 20 import static java.util.Arrays.asList; 21 import static org.junit.contrib.truth.Truth.ASSERT; 22 23 import com.google.common.annotations.GwtCompatible; 24 import com.google.common.annotations.GwtIncompatible; 25 import com.google.common.collect.testing.ListIteratorTester; 26 27 import java.util.Collection; 28 import java.util.Collections; 29 import java.util.Iterator; 30 import java.util.List; 31 import java.util.ListIterator; 32 import java.util.Map; 33 34 /** 35 * Tests for {@code ListMultimap} implementations. 36 * 37 * @author Jared Levy 38 */ 39 @GwtCompatible(emulated = true) 40 public abstract class AbstractListMultimapTest extends AbstractMultimapTest { 41 42 @Override protected abstract ListMultimap<String, Integer> create(); 43 44 /** 45 * Test adding duplicate key-value pairs to multimap. 46 */ 47 public void testDuplicates() { 48 Multimap<String, Integer> multimap = create(); 49 multimap.put("foo", 1); 50 multimap.put("foo", 3); 51 multimap.put("bar", 3); 52 multimap.put("foo", 1); 53 assertEquals(4, multimap.size()); 54 assertTrue(multimap.containsEntry("foo", 1)); 55 multimap.remove("foo", 1); 56 assertEquals(3, multimap.size()); 57 assertTrue(multimap.containsEntry("foo", 1)); 58 } 59 60 /** 61 * Test returned boolean when adding duplicate key-value pairs to multimap. 62 */ 63 public void testPutReturn() { 64 Multimap<String, Integer> multimap = create(); 65 assertTrue(multimap.put("foo", 1)); 66 assertTrue(multimap.put("foo", 1)); 67 assertTrue(multimap.put("foo", 3)); 68 assertTrue(multimap.put("bar", 5)); 69 } 70 71 public void testPutAllReturn_existingElements() { 72 Multimap<String, Integer> multimap = create(); 73 assertTrue(multimap.putAll("foo", asList(1, 2, 3))); 74 assertTrue(multimap.put("foo", 1)); 75 assertTrue(multimap.putAll("foo", asList(1, 2, 3))); 76 assertTrue(multimap.putAll("foo", asList(1, 3))); 77 78 Multimap<String, Integer> other = create(); 79 other.putAll("foo", asList(1, 2)); 80 assertTrue(multimap.putAll(other)); 81 82 other.putAll("bar", asList(1, 2)); 83 assertTrue(multimap.putAll(other)); 84 assertTrue(other.putAll(multimap)); 85 } 86 87 /** 88 * Confirm that get() returns a collection equal to a List. 89 */ 90 public void testGetEquals() { 91 Multimap<String, Integer> multimap = create(); 92 multimap.put("foo", 1); 93 multimap.put("foo", 3); 94 assertEquals(ImmutableList.of(1, 3), multimap.get("foo")); 95 } 96 97 public void testAsMapEquals() { 98 Multimap<String, Integer> multimap = getMultimap(); 99 multimap.put("foo", 1); 100 multimap.put("foo", nullValue()); 101 multimap.put(nullKey(), 3); 102 Map<String, Collection<Integer>> map = multimap.asMap(); 103 104 Map<String, Collection<Integer>> equalMap = Maps.newHashMap(); 105 equalMap.put("foo", asList(1, nullValue())); 106 equalMap.put(nullKey(), asList(3)); 107 assertEquals(map, equalMap); 108 assertEquals(equalMap, map); 109 assertEquals(equalMap.hashCode(), multimap.hashCode()); 110 111 Map<String, Collection<Integer>> unequalMap = Maps.newHashMap(); 112 equalMap.put("foo", asList(3, nullValue())); 113 equalMap.put(nullKey(), asList(1)); 114 assertFalse(map.equals(unequalMap)); 115 assertFalse(unequalMap.equals(map)); 116 } 117 118 /** 119 * Confirm that asMap().entrySet() returns values equal to a List. 120 */ 121 public void testAsMapEntriesEquals() { 122 Multimap<String, Integer> multimap = create(); 123 multimap.put("foo", 1); 124 multimap.put("foo", 3); 125 Iterator<Map.Entry<String, Collection<Integer>>> i = 126 multimap.asMap().entrySet().iterator(); 127 Map.Entry<String, Collection<Integer>> entry = i.next(); 128 assertEquals("foo", entry.getKey()); 129 assertEquals(ImmutableList.of(1, 3), entry.getValue()); 130 assertFalse(i.hasNext()); 131 } 132 133 public void testAsMapValuesRemove() { 134 Multimap<String, Integer> multimap = create(); 135 multimap.put("foo", 1); 136 multimap.put("foo", 3); 137 multimap.put("bar", 3); 138 Collection<Collection<Integer>> asMapValues = multimap.asMap().values(); 139 assertFalse(asMapValues.remove(asList(3, 1))); 140 assertEquals(3, multimap.size()); 141 assertTrue(asMapValues.remove(asList(1, 3))); 142 assertEquals(1, multimap.size()); 143 } 144 145 /** 146 * Test multimap.equals() for multimaps with different insertion orderings. 147 */ 148 public void testEqualsOrdering() { 149 Multimap<String, Integer> multimap = create(); 150 multimap.put("foo", 1); 151 multimap.put("foo", 3); 152 multimap.put("bar", 3); 153 Multimap<String, Integer> multimap2 = create(); 154 multimap2.put("foo", 3); 155 multimap2.put("foo", 1); 156 multimap2.put("bar", 3); 157 assertFalse(multimap.equals(multimap2)); 158 } 159 160 /** 161 * Test the ordering of the values returned by multimap.get(). 162 */ 163 public void testPutGetOrdering() { 164 Multimap<String, Integer> multimap = create(); 165 multimap.put("foo", 1); 166 multimap.put("foo", 3); 167 multimap.put("bar", 3); 168 Iterator<Integer> values = multimap.get("foo").iterator(); 169 assertEquals(Integer.valueOf(1), values.next()); 170 assertEquals(Integer.valueOf(3), values.next()); 171 } 172 173 /** 174 * Test List-specific methods on List returned by get(). 175 */ 176 public void testListMethods() { 177 ListMultimap<String, Integer> multimap = create(); 178 multimap.put("foo", 1); 179 multimap.put("foo", 3); 180 multimap.put("foo", 5); 181 List<Integer> list = multimap.get("foo"); 182 183 list.add(1, 2); 184 assertEquals(4, multimap.size()); 185 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 5); 186 187 list.addAll(3, asList(4, 8)); 188 assertEquals(6, multimap.size()); 189 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 8, 5); 190 191 assertEquals(8, list.get(4).intValue()); 192 assertEquals(4, list.indexOf(8)); 193 assertEquals(4, list.lastIndexOf(8)); 194 195 list.remove(4); 196 assertEquals(5, multimap.size()); 197 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5); 198 199 list.set(4, 10); 200 assertEquals(5, multimap.size()); 201 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 10); 202 } 203 204 public void testListMethodsIncludingSublist() { 205 ListMultimap<String, Integer> multimap = create(); 206 multimap.put("foo", 1); 207 multimap.put("foo", 2); 208 multimap.put("foo", 3); 209 multimap.put("foo", 4); 210 multimap.put("foo", 10); 211 List<Integer> list = multimap.get("foo"); 212 213 List<Integer> sublist = list.subList(1, 4); 214 ASSERT.that(sublist).hasContentsInOrder(2, 3, 4); 215 list.set(3, 6); 216 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 6, 10); 217 } 218 219 /** 220 * Test sublist of List returned by get() after the original list is updated. 221 */ 222 public void testSublistAfterListUpdate() { 223 ListMultimap<String, Integer> multimap = create(); 224 multimap.put("foo", 1); 225 multimap.put("foo", 2); 226 multimap.put("foo", 3); 227 multimap.put("foo", 4); 228 multimap.put("foo", 5); 229 230 List<Integer> list = multimap.get("foo"); 231 List<Integer> sublist = list.subList(1, 4); 232 ASSERT.that(sublist).hasContentsInOrder(2, 3, 4); 233 list.set(3, 6); 234 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 6, 5); 235 ASSERT.that(sublist).hasContentsInOrder(2, 3, 6); 236 } 237 238 /** 239 * Test ListIterator methods that don't change the multimap. 240 */ 241 public void testListIteratorNavigate() { 242 ListMultimap<String, Integer> multimap = create(); 243 multimap.put("foo", 1); 244 multimap.put("foo", 3); 245 List<Integer> list = multimap.get("foo"); 246 ListIterator<Integer> iterator = list.listIterator(); 247 248 assertFalse(iterator.hasPrevious()); 249 assertTrue(iterator.hasNext()); 250 assertEquals(0, iterator.nextIndex()); 251 assertEquals(-1, iterator.previousIndex()); 252 253 assertEquals(1, iterator.next().intValue()); 254 assertEquals(3, iterator.next().intValue()); 255 assertTrue(iterator.hasPrevious()); 256 assertFalse(iterator.hasNext()); 257 258 assertEquals(3, iterator.previous().intValue()); 259 assertEquals(1, iterator.previous().intValue()); 260 } 261 262 /** 263 * Test ListIterator methods that change the multimap. 264 */ 265 public void testListIteratorUpdate() { 266 ListMultimap<String, Integer> multimap = create(); 267 multimap.put("foo", 1); 268 multimap.put("foo", 3); 269 multimap.put("foo", 5); 270 List<Integer> list = multimap.get("foo"); 271 ListIterator<Integer> iterator = list.listIterator(); 272 273 assertEquals(1, iterator.next().intValue()); 274 iterator.set(2); 275 ASSERT.that(multimap.get("foo")).hasContentsInOrder(2, 3, 5); 276 277 assertEquals(3, iterator.next().intValue()); 278 iterator.remove(); 279 ASSERT.that(multimap.get("foo")).hasContentsInOrder(2, 5); 280 } 281 282 /** 283 * Test calling toString() on the multimap, which does not have a 284 * deterministic iteration order for keys but does for values. 285 */ 286 public void testToString() { 287 String s = createSample().toString(); 288 assertTrue(s.equals("{foo=[3, -1, 2, 4, 1], bar=[1, 2, 3, 1]}") 289 || s.equals("{bar=[1, 2, 3, 1], foo=[3, -1, 2, 4, 1]}")); 290 } 291 292 /** 293 * Test calling set() on a sublist. 294 */ 295 public void testSublistSet() { 296 ListMultimap<String, Integer> multimap = create(); 297 multimap.putAll("foo", asList(1, 2, 3, 4, 5)); 298 List<Integer> list = multimap.get("foo"); 299 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5); 300 List<Integer> sublist = list.subList(1, 4); 301 ASSERT.that(sublist).hasContentsInOrder(2, 3, 4); 302 303 sublist.set(1, 6); 304 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 6, 4, 5); 305 } 306 307 /** 308 * Test removing elements from a sublist. 309 */ 310 public void testSublistRemove() { 311 ListMultimap<String, Integer> multimap = create(); 312 multimap.putAll("foo", asList(1, 2, 3, 4, 5)); 313 List<Integer> list = multimap.get("foo"); 314 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5); 315 List<Integer> sublist = list.subList(1, 4); 316 ASSERT.that(sublist).hasContentsInOrder(2, 3, 4); 317 318 sublist.remove(1); 319 assertEquals(4, multimap.size()); 320 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 4, 5); 321 322 sublist.removeAll(Collections.singleton(4)); 323 assertEquals(3, multimap.size()); 324 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 5); 325 326 sublist.remove(0); 327 assertEquals(2, multimap.size()); 328 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 5); 329 } 330 331 /** 332 * Test adding elements to a sublist. 333 */ 334 public void testSublistAdd() { 335 ListMultimap<String, Integer> multimap = create(); 336 multimap.putAll("foo", asList(1, 2, 3, 4, 5)); 337 List<Integer> list = multimap.get("foo"); 338 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5); 339 List<Integer> sublist = list.subList(1, 4); 340 ASSERT.that(sublist).hasContentsInOrder(2, 3, 4); 341 342 sublist.add(6); 343 assertEquals(6, multimap.size()); 344 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 6, 5); 345 346 sublist.add(0, 7); 347 assertEquals(7, multimap.size()); 348 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 7, 2, 3, 4, 6, 5); 349 } 350 351 /** 352 * Test clearing a sublist. 353 */ 354 public void testSublistClear() { 355 ListMultimap<String, Integer> multimap = create(); 356 multimap.putAll("foo", asList(1, 2, 3, 4, 5)); 357 List<Integer> list = multimap.get("foo"); 358 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5); 359 List<Integer> sublist = list.subList(1, 4); 360 ASSERT.that(sublist).hasContentsInOrder(2, 3, 4); 361 362 sublist.clear(); 363 assertEquals(2, multimap.size()); 364 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 5); 365 } 366 367 /** 368 * Test adding elements to an empty sublist with an empty ancestor. 369 */ 370 public void testSublistAddToEmpty() { 371 ListMultimap<String, Integer> multimap = create(); 372 multimap.putAll("foo", asList(1, 2, 3, 4, 5)); 373 List<Integer> list = multimap.get("foo"); 374 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 3, 4, 5); 375 List<Integer> sublist = list.subList(0, 5); 376 ASSERT.that(sublist).hasContentsInOrder(1, 2, 3, 4, 5); 377 378 sublist.retainAll(Collections.EMPTY_LIST); 379 assertTrue(multimap.isEmpty()); 380 381 sublist.add(6); 382 assertEquals(1, multimap.size()); 383 assertTrue(multimap.containsEntry("foo", 6)); 384 } 385 386 /** 387 * Test updates through a list iterator retrieved by 388 * multimap.get(key).listIterator(index). 389 */ 390 public void testListIteratorIndexUpdate() { 391 ListMultimap<String, Integer> multimap = create(); 392 multimap.putAll("foo", asList(1, 2, 3, 4, 5)); 393 ListIterator<Integer> iterator = multimap.get("foo").listIterator(1); 394 395 assertEquals(2, iterator.next().intValue()); 396 iterator.set(6); 397 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 6, 3, 4, 5); 398 399 assertTrue(iterator.hasNext()); 400 assertEquals(3, iterator.next().intValue()); 401 iterator.remove(); 402 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 6, 4, 5); 403 assertEquals(4, multimap.size()); 404 } 405 406 @GwtIncompatible("unreasonable slow") 407 public void testGetIteration() { 408 List<Integer> addItems = ImmutableList.of(99, 88, 77); 409 410 for (final int startIndex : new int[] {0, 3, 5}) { 411 new ListIteratorTester<Integer>(3, addItems, MODIFIABLE, 412 Lists.newArrayList(2, 3, 4, 7, 8), startIndex) { 413 private ListMultimap<String, Integer> multimap; 414 415 @Override protected ListIterator<Integer> newTargetIterator() { 416 multimap = create(); 417 multimap.put("bar", 1); 418 multimap.putAll("foo", asList(2, 3, 4)); 419 multimap.putAll("bar", asList(5, 6)); 420 multimap.putAll("foo", asList(7, 8)); 421 return multimap.get("foo").listIterator(startIndex); 422 } 423 424 @Override protected void verify(List<Integer> elements) { 425 assertEquals(elements, multimap.get("foo")); 426 } 427 }.test(); 428 } 429 } 430 431 public void testListGetSet() { 432 ListMultimap<String, Integer> map = create(); 433 map.put("bar", 1); 434 map.get("bar").set(0, 2); 435 assertEquals("{bar=[2]}", map.toString()); 436 assertEquals("[bar=2]", map.entries().toString()); 437 } 438 439 public void testListPutAllIterable() { 440 Multimap<String, Integer> map = create(); 441 map.putAll("foo", asList(1, 2)); 442 assertEquals("{foo=[1, 2]}", map.toString()); 443 assertEquals("[foo=1, foo=2]", map.entries().toString()); 444 } 445 446 public void testListRemoveAll() { 447 Multimap<String, Integer> map = create(); 448 map.put("bar", 1); 449 map.put("foo", 2); 450 map.put("bar", 3); 451 map.put("bar", 4); 452 map.removeAll("foo"); 453 assertEquals("[bar=1, bar=3, bar=4]", map.entries().toString()); 454 assertEquals("{bar=[1, 3, 4]}", map.toString()); 455 map.removeAll("bar"); 456 assertEquals("[]", map.entries().toString()); 457 assertEquals("{}", map.toString()); 458 } 459 460 public void testListEquals() { 461 Multimap<String, Integer> map1 = create(); 462 map1.put("bar", 1); 463 map1.put("foo", 2); 464 map1.put("bar", 3); 465 Multimap<String, Integer> map2 = ArrayListMultimap.create(); 466 map2.putAll(map1); 467 assertTrue(map1.equals(map2)); 468 assertTrue(map2.equals(map1)); 469 assertFalse(map1.equals(null)); 470 assertFalse(map1.equals(new Object())); 471 } 472 473 public void testListHashCode() { 474 Multimap<String, Integer> map1 = create(); 475 map1.put("bar", 1); 476 map1.put("foo", 2); 477 map1.put("bar", 3); 478 Multimap<String, Integer> map2 = ArrayListMultimap.create(); 479 map2.putAll(map1); 480 assertEquals(map1.hashCode(), map2.hashCode()); 481 } 482 483 public void testListAddIndex() { 484 ListMultimap<String, Integer> multimap = create(); 485 multimap.put("bar", 11); 486 multimap.put("bar", 12); 487 multimap.get("bar").add(0, 13); 488 ASSERT.that(multimap.get("bar")).hasContentsInOrder(13, 11, 12); 489 } 490 491 /** 492 * According to the AbstractCollection.retainAll() implementation, 493 * {@code A.retainAll(B)} should keep all occurrences of each object in B, 494 * so even though the collection that this test passes to retainAll() has 495 * fewer occurrences of 2 than the multimap has, all of the 2s should be 496 * retained. 497 */ 498 public void testGetRetainAll() { 499 // TODO: test this logic in ListRetainAllTester 500 ListMultimap<String, Integer> multimap = create(); 501 multimap.putAll("foo", asList(1, 2, 2, 3, 3, 3)); 502 503 multimap.get("foo").retainAll(asList(1, 2, 4)); 504 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 2, 2); 505 } 506 507 /** 508 * According to the AbstractCollection.removeAll() implementation, 509 * {@code A.removeAll(B)} should remove all occurrences of each object in B, 510 * so even though the collection that this test passes to removeAll() has 511 * fewer occurrences of 2 and 3 than the multimap has, there should be no 512 * 2s or 3s remaining in the collection. 513 */ 514 public void testGetRemoveAll_someValuesRemain() { 515 // TODO: test this logic in ListRemoveAllTester 516 ListMultimap<String, Integer> multimap = create(); 517 multimap.putAll("foo", asList(1, 2, 2, 3, 3, 3)); 518 519 multimap.get("foo").removeAll(asList(2, 3, 3, 4)); 520 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1); 521 } 522 } 523
