1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkArgument; 18import static com.google.common.truth.Truth.assertThat; 19import static java.util.Arrays.asList; 20 21import com.google.common.base.Function; 22import com.google.common.collect.Multiset.Entry; 23import com.google.common.collect.testing.ListTestSuiteBuilder; 24import com.google.common.collect.testing.MinimalCollection; 25import com.google.common.collect.testing.TestStringListGenerator; 26import com.google.common.collect.testing.features.CollectionFeature; 27import com.google.common.collect.testing.features.CollectionSize; 28import com.google.common.collect.testing.google.SortedMultisetTestSuiteBuilder; 29import com.google.common.collect.testing.google.TestStringMultisetGenerator; 30import com.google.common.collect.testing.google.UnmodifiableCollectionTests; 31import com.google.common.testing.NullPointerTester; 32import com.google.common.testing.SerializableTester; 33 34import junit.framework.Test; 35import junit.framework.TestCase; 36import junit.framework.TestSuite; 37 38import org.easymock.EasyMock; 39 40import java.util.ArrayList; 41import java.util.Arrays; 42import java.util.Collection; 43import java.util.Comparator; 44import java.util.HashSet; 45import java.util.Iterator; 46import java.util.List; 47import java.util.Set; 48 49/** 50 * Tests for {@link ImmutableSortedMultiset}. 51 * 52 * @author Louis Wasserman 53 */ 54public class ImmutableSortedMultisetTest extends TestCase { 55 public static Test suite() { 56 TestSuite suite = new TestSuite(); 57 suite.addTestSuite(ImmutableSortedMultisetTest.class); 58 59 suite.addTest(SortedMultisetTestSuiteBuilder.using(new TestStringMultisetGenerator() { 60 @Override 61 protected Multiset<String> create(String[] elements) { 62 return ImmutableSortedMultiset.copyOf(elements); 63 } 64 65 @Override 66 public List<String> order(List<String> insertionOrder) { 67 return Ordering.natural().sortedCopy(insertionOrder); 68 } 69 }) 70 .named("ImmutableSortedMultiset") 71 .withFeatures(CollectionSize.ANY, 72 CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS, 73 CollectionFeature.ALLOWS_NULL_QUERIES) 74 .createTestSuite()); 75 76 suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() { 77 @Override 78 protected List<String> create(String[] elements) { 79 return ImmutableSortedMultiset.copyOf(elements).asList(); 80 } 81 82 @Override 83 public List<String> order(List<String> insertionOrder) { 84 return Ordering.natural().sortedCopy(insertionOrder); 85 } 86 }) 87 .named("ImmutableSortedMultiset.asList") 88 .withFeatures(CollectionSize.ANY, 89 CollectionFeature.SERIALIZABLE, 90 CollectionFeature.ALLOWS_NULL_QUERIES) 91 .createTestSuite()); 92 93 suite.addTest(ListTestSuiteBuilder.using(new TestStringListGenerator() { 94 @Override 95 protected List<String> create(String[] elements) { 96 Set<String> set = Sets.newHashSet(); 97 ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder(); 98 for (String s : elements) { 99 checkArgument(set.add(s)); 100 builder.addCopies(s, 2); 101 } 102 return builder.build().elementSet().asList(); 103 } 104 105 @Override 106 public List<String> order(List<String> insertionOrder) { 107 return Ordering.natural().sortedCopy(insertionOrder); 108 } 109 }) 110 .named("ImmutableSortedMultiset.elementSet.asList") 111 .withFeatures(CollectionSize.ANY, 112 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, 113 CollectionFeature.SERIALIZABLE, 114 CollectionFeature.ALLOWS_NULL_QUERIES) 115 .createTestSuite()); 116 117 return suite; 118 } 119 120 public void testCreation_noArgs() { 121 Multiset<String> multiset = ImmutableSortedMultiset.of(); 122 assertTrue(multiset.isEmpty()); 123 } 124 125 public void testCreation_oneElement() { 126 Multiset<String> multiset = ImmutableSortedMultiset.of("a"); 127 assertEquals(HashMultiset.create(asList("a")), multiset); 128 } 129 130 public void testCreation_twoElements() { 131 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b"); 132 assertEquals(HashMultiset.create(asList("a", "b")), multiset); 133 } 134 135 public void testCreation_threeElements() { 136 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c"); 137 assertEquals(HashMultiset.create(asList("a", "b", "c")), multiset); 138 } 139 140 public void testCreation_fourElements() { 141 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d"); 142 assertEquals(HashMultiset.create(asList("a", "b", "c", "d")), multiset); 143 } 144 145 public void testCreation_fiveElements() { 146 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d", "e"); 147 assertEquals(HashMultiset.create(asList("a", "b", "c", "d", "e")), multiset); 148 } 149 150 public void testCreation_sixElements() { 151 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d", "e", "f"); 152 assertEquals(HashMultiset.create(asList("a", "b", "c", "d", "e", "f")), multiset); 153 } 154 155 public void testCreation_sevenElements() { 156 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "c", "d", "e", "f", "g"); 157 assertEquals(HashMultiset.create(asList("a", "b", "c", "d", "e", "f", "g")), multiset); 158 } 159 160 public void testCreation_emptyArray() { 161 String[] array = new String[0]; 162 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(array); 163 assertTrue(multiset.isEmpty()); 164 } 165 166 public void testCreation_arrayOfOneElement() { 167 String[] array = new String[] {"a"}; 168 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(array); 169 assertEquals(HashMultiset.create(asList("a")), multiset); 170 } 171 172 public void testCreation_arrayOfArray() { 173 Comparator<String[]> comparator = 174 Ordering.natural().lexicographical() 175 .onResultOf(new Function<String[], Iterable<Comparable>>() { 176 @Override 177 public Iterable<Comparable> apply(String[] input) { 178 return Arrays.<Comparable>asList(input); 179 } 180 }); 181 String[] array = new String[] {"a"}; 182 Multiset<String[]> multiset = ImmutableSortedMultiset.orderedBy(comparator).add(array).build(); 183 Multiset<String[]> expected = HashMultiset.create(); 184 expected.add(array); 185 assertEquals(expected, multiset); 186 } 187 188 public void testCreation_arrayContainingOnlyNull() { 189 String[] array = new String[] {null}; 190 try { 191 ImmutableSortedMultiset.copyOf(array); 192 fail(); 193 } catch (NullPointerException expected) {} 194 } 195 196 public void testCopyOf_collection_empty() { 197 // "<String>" is required to work around a javac 1.5 bug. 198 Collection<String> c = MinimalCollection.<String>of(); 199 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c); 200 assertTrue(multiset.isEmpty()); 201 } 202 203 public void testCopyOf_collection_oneElement() { 204 Collection<String> c = MinimalCollection.of("a"); 205 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c); 206 assertEquals(HashMultiset.create(asList("a")), multiset); 207 } 208 209 public void testCopyOf_collection_general() { 210 Collection<String> c = MinimalCollection.of("a", "b", "a"); 211 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c); 212 assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset); 213 } 214 215 public void testCopyOf_collectionContainingNull() { 216 Collection<String> c = MinimalCollection.of("a", null, "b"); 217 try { 218 ImmutableSortedMultiset.copyOf(c); 219 fail(); 220 } catch (NullPointerException expected) {} 221 } 222 223 public void testCopyOf_multiset_empty() { 224 Multiset<String> c = HashMultiset.create(); 225 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c); 226 assertTrue(multiset.isEmpty()); 227 } 228 229 public void testCopyOf_multiset_oneElement() { 230 Multiset<String> c = HashMultiset.create(asList("a")); 231 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c); 232 assertEquals(HashMultiset.create(asList("a")), multiset); 233 } 234 235 public void testCopyOf_multiset_general() { 236 Multiset<String> c = HashMultiset.create(asList("a", "b", "a")); 237 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(c); 238 assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset); 239 } 240 241 public void testCopyOf_multisetContainingNull() { 242 Multiset<String> c = HashMultiset.create(asList("a", null, "b")); 243 try { 244 ImmutableSortedMultiset.copyOf(c); 245 fail(); 246 } catch (NullPointerException expected) {} 247 } 248 249 public void testCopyOf_iterator_empty() { 250 Iterator<String> iterator = Iterators.emptyIterator(); 251 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterator); 252 assertTrue(multiset.isEmpty()); 253 } 254 255 public void testCopyOf_iterator_oneElement() { 256 Iterator<String> iterator = Iterators.singletonIterator("a"); 257 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterator); 258 assertEquals(HashMultiset.create(asList("a")), multiset); 259 } 260 261 public void testCopyOf_iterator_general() { 262 Iterator<String> iterator = asList("a", "b", "a").iterator(); 263 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterator); 264 assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset); 265 } 266 267 public void testCopyOf_iteratorContainingNull() { 268 Iterator<String> iterator = asList("a", null, "b").iterator(); 269 try { 270 ImmutableSortedMultiset.copyOf(iterator); 271 fail(); 272 } catch (NullPointerException expected) {} 273 } 274 275 private static class CountingIterable implements Iterable<String> { 276 int count = 0; 277 278 @Override 279 public Iterator<String> iterator() { 280 count++; 281 return asList("a", "b", "a").iterator(); 282 } 283 } 284 285 public void testCopyOf_plainIterable() { 286 CountingIterable iterable = new CountingIterable(); 287 Multiset<String> multiset = ImmutableSortedMultiset.copyOf(iterable); 288 assertEquals(HashMultiset.create(asList("a", "b", "a")), multiset); 289 assertEquals(1, iterable.count); 290 } 291 292 public void testCopyOf_shortcut_empty() { 293 Collection<String> c = ImmutableSortedMultiset.of(); 294 assertSame(c, ImmutableSortedMultiset.copyOf(c)); 295 } 296 297 public void testCopyOf_shortcut_singleton() { 298 Collection<String> c = ImmutableSortedMultiset.of("a"); 299 assertSame(c, ImmutableSortedMultiset.copyOf(c)); 300 } 301 302 public void testCopyOf_shortcut_immutableMultiset() { 303 Collection<String> c = ImmutableSortedMultiset.of("a", "b", "c"); 304 assertSame(c, ImmutableSortedMultiset.copyOf(c)); 305 } 306 307 public void testBuilderAdd() { 308 ImmutableSortedMultiset<String> multiset = 309 ImmutableSortedMultiset.<String>naturalOrder().add("a").add("b").add("a").add("c").build(); 310 assertEquals(HashMultiset.create(asList("a", "b", "a", "c")), multiset); 311 } 312 313 public void testBuilderAddAll() { 314 List<String> a = asList("a", "b"); 315 List<String> b = asList("c", "d"); 316 ImmutableSortedMultiset<String> multiset = 317 ImmutableSortedMultiset.<String>naturalOrder().addAll(a).addAll(b).build(); 318 assertEquals(HashMultiset.create(asList("a", "b", "c", "d")), multiset); 319 } 320 321 public void testBuilderAddAllMultiset() { 322 Multiset<String> a = HashMultiset.create(asList("a", "b", "b")); 323 Multiset<String> b = HashMultiset.create(asList("c", "b")); 324 ImmutableSortedMultiset<String> multiset = 325 ImmutableSortedMultiset.<String>naturalOrder().addAll(a).addAll(b).build(); 326 assertEquals(HashMultiset.create(asList("a", "b", "b", "b", "c")), multiset); 327 } 328 329 public void testBuilderAddAllIterator() { 330 Iterator<String> iterator = asList("a", "b", "a", "c").iterator(); 331 ImmutableSortedMultiset<String> multiset = 332 ImmutableSortedMultiset.<String>naturalOrder().addAll(iterator).build(); 333 assertEquals(HashMultiset.create(asList("a", "b", "a", "c")), multiset); 334 } 335 336 public void testBuilderAddCopies() { 337 ImmutableSortedMultiset<String> multiset = 338 ImmutableSortedMultiset.<String>naturalOrder().addCopies("a", 2).addCopies("b", 3) 339 .addCopies("c", 0).build(); 340 assertEquals(HashMultiset.create(asList("a", "a", "b", "b", "b")), multiset); 341 } 342 343 public void testBuilderSetCount() { 344 ImmutableSortedMultiset<String> multiset = 345 ImmutableSortedMultiset.<String>naturalOrder().add("a").setCount("a", 2).setCount("b", 3) 346 .build(); 347 assertEquals(HashMultiset.create(asList("a", "a", "b", "b", "b")), multiset); 348 } 349 350 public void testBuilderAddHandlesNullsCorrectly() { 351 ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder(); 352 try { 353 builder.add((String) null); 354 fail("expected NullPointerException"); 355 } catch (NullPointerException expected) {} 356 } 357 358 public void testBuilderAddAllHandlesNullsCorrectly() { 359 ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder(); 360 try { 361 builder.addAll((Collection<String>) null); 362 fail("expected NullPointerException"); 363 } catch (NullPointerException expected) {} 364 365 builder = ImmutableSortedMultiset.naturalOrder(); 366 List<String> listWithNulls = asList("a", null, "b"); 367 try { 368 builder.addAll(listWithNulls); 369 fail("expected NullPointerException"); 370 } catch (NullPointerException expected) {} 371 372 builder = ImmutableSortedMultiset.naturalOrder(); 373 Multiset<String> multisetWithNull = LinkedHashMultiset.create(asList("a", null, "b")); 374 try { 375 builder.addAll(multisetWithNull); 376 fail("expected NullPointerException"); 377 } catch (NullPointerException expected) {} 378 } 379 380 public void testBuilderAddCopiesHandlesNullsCorrectly() { 381 ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder(); 382 try { 383 builder.addCopies(null, 2); 384 fail("expected NullPointerException"); 385 } catch (NullPointerException expected) {} 386 } 387 388 public void testBuilderAddCopiesIllegal() { 389 ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder(); 390 try { 391 builder.addCopies("a", -2); 392 fail("expected IllegalArgumentException"); 393 } catch (IllegalArgumentException expected) {} 394 } 395 396 public void testBuilderSetCountHandlesNullsCorrectly() { 397 ImmutableSortedMultiset.Builder<String> builder = 398 new ImmutableSortedMultiset.Builder<String>(Ordering.natural().nullsFirst()); 399 try { 400 builder.setCount(null, 2); 401 fail("expected NullPointerException"); 402 } catch (NullPointerException expected) {} 403 } 404 405 public void testBuilderSetCountIllegal() { 406 ImmutableSortedMultiset.Builder<String> builder = ImmutableSortedMultiset.naturalOrder(); 407 try { 408 builder.setCount("a", -2); 409 fail("expected IllegalArgumentException"); 410 } catch (IllegalArgumentException expected) {} 411 } 412 413 public void testNullPointers() { 414 new NullPointerTester().testAllPublicStaticMethods(ImmutableSortedMultiset.class); 415 } 416 417 public void testSerialization_empty() { 418 Collection<String> c = ImmutableSortedMultiset.of(); 419 assertSame(c, SerializableTester.reserialize(c)); 420 } 421 422 public void testSerialization_multiple() { 423 Collection<String> c = ImmutableSortedMultiset.of("a", "b", "a"); 424 Collection<String> copy = SerializableTester.reserializeAndAssert(c); 425 assertThat(copy).has().exactly("a", "a", "b").inOrder(); 426 } 427 428 public void testSerialization_elementSet() { 429 Multiset<String> c = ImmutableSortedMultiset.of("a", "b", "a"); 430 Collection<String> copy = SerializableTester.reserializeAndAssert(c.elementSet()); 431 assertThat(copy).has().exactly("a", "b").inOrder(); 432 } 433 434 public void testSerialization_entrySet() { 435 Multiset<String> c = ImmutableSortedMultiset.of("a", "b", "c"); 436 SerializableTester.reserializeAndAssert(c.entrySet()); 437 } 438 439 public void testEquals_immutableMultiset() { 440 Collection<String> c = ImmutableSortedMultiset.of("a", "b", "a"); 441 assertEquals(c, ImmutableSortedMultiset.of("a", "b", "a")); 442 assertEquals(c, ImmutableSortedMultiset.of("a", "a", "b")); 443 assertThat(c).isNotEqualTo(ImmutableSortedMultiset.of("a", "b")); 444 assertThat(c).isNotEqualTo(ImmutableSortedMultiset.of("a", "b", "c", "d")); 445 } 446 447 public void testIterationOrder() { 448 Collection<String> c = ImmutableSortedMultiset.of("a", "b", "a"); 449 assertThat(c).has().exactly("a", "a", "b").inOrder(); 450 } 451 452 public void testMultisetWrites() { 453 Multiset<String> multiset = ImmutableSortedMultiset.of("a", "b", "a"); 454 UnmodifiableCollectionTests.assertMultisetIsUnmodifiable(multiset, "test"); 455 } 456 457 public void testAsList() { 458 ImmutableSortedMultiset<String> multiset = ImmutableSortedMultiset.of("a", "a", "b", "b", "b"); 459 ImmutableList<String> list = multiset.asList(); 460 assertEquals(ImmutableList.of("a", "a", "b", "b", "b"), list); 461 assertTrue(list instanceof ImmutableAsList); 462 ImmutableList<String> copy = SerializableTester.reserializeAndAssert(list); 463 assertTrue(copy instanceof ImmutableAsList); 464 assertEquals(2, list.indexOf("b")); 465 assertEquals(4, list.lastIndexOf("b")); 466 } 467 468 public void testCopyOfDefensiveCopy() { 469 // Depending on JDK version, either toArray() or toArray(T[]) may be called... use this class 470 // rather than mocking to ensure that one of those methods is called. 471 class TestArrayList<E> extends ArrayList<E> { 472 boolean toArrayCalled = false; 473 474 @Override 475 public Object[] toArray() { 476 toArrayCalled = true; 477 return super.toArray(); 478 } 479 480 @Override 481 public <T> T[] toArray(T[] a) { 482 toArrayCalled = true; 483 return super.toArray(a); 484 } 485 } 486 487 // Test that toArray() is used to make a defensive copy in copyOf(), so concurrently modified 488 // synchronized collections can be safely copied. 489 TestArrayList<String> toCopy = new TestArrayList<String>(); 490 ImmutableSortedMultiset<String> multiset = 491 ImmutableSortedMultiset.copyOf(Ordering.natural(), toCopy); 492 assertTrue(toCopy.toArrayCalled); 493 } 494 495 @SuppressWarnings("unchecked") 496 public void testCopyOfSortedDefensiveCopy() { 497 // Depending on JDK version, either toArray() or toArray(T[]) may be called... use this class 498 // rather than mocking to ensure that one of those methods is called. 499 class TestHashSet<E> extends HashSet<E> { 500 boolean toArrayCalled = false; 501 502 @Override 503 public Object[] toArray() { 504 toArrayCalled = true; 505 return super.toArray(); 506 } 507 508 @Override 509 public <T> T[] toArray(T[] a) { 510 toArrayCalled = true; 511 return super.toArray(a); 512 } 513 } 514 515 // Test that toArray() is used to make a defensive copy in copyOf(), so concurrently modified 516 // synchronized collections can be safely copied. 517 SortedMultiset<String> toCopy = EasyMock.createMock(SortedMultiset.class); 518 TestHashSet<Entry<String>> entrySet = new TestHashSet<Entry<String>>(); 519 EasyMock.expect((Comparator<Comparable>) toCopy.comparator()) 520 .andReturn(Ordering.natural()); 521 EasyMock.expect(toCopy.entrySet()).andReturn(entrySet); 522 EasyMock.replay(toCopy); 523 ImmutableSortedMultiset<String> multiset = 524 ImmutableSortedMultiset.copyOfSorted(toCopy); 525 EasyMock.verify(toCopy); 526 assertTrue(entrySet.toArrayCalled); 527 } 528 529 private static class IntegerDiv10 implements Comparable<IntegerDiv10> { 530 final int value; 531 532 IntegerDiv10(int value) { 533 this.value = value; 534 } 535 536 @Override 537 public int compareTo(IntegerDiv10 o) { 538 return value / 10 - o.value / 10; 539 } 540 541 @Override public String toString() { 542 return Integer.toString(value); 543 } 544 } 545 546 public void testCopyOfDuplicateInconsistentWithEquals() { 547 IntegerDiv10 three = new IntegerDiv10(3); 548 IntegerDiv10 eleven = new IntegerDiv10(11); 549 IntegerDiv10 twelve = new IntegerDiv10(12); 550 IntegerDiv10 twenty = new IntegerDiv10(20); 551 552 List<IntegerDiv10> original = ImmutableList.of(three, eleven, twelve, twenty); 553 554 Multiset<IntegerDiv10> copy = ImmutableSortedMultiset.copyOf(original); 555 assertTrue(copy.contains(eleven)); 556 assertTrue(copy.contains(twelve)); 557 } 558} 559