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.base.Preconditions.checkArgument; 20 import static com.google.common.truth.Truth.assertThat; 21 22 import com.google.common.annotations.GwtCompatible; 23 import com.google.common.annotations.GwtIncompatible; 24 import com.google.common.collect.testing.DerivedComparable; 25 import com.google.common.collect.testing.Helpers; 26 import com.google.common.collect.testing.NavigableMapTestSuiteBuilder; 27 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder; 28 import com.google.common.collect.testing.SampleElements; 29 import com.google.common.collect.testing.TestSortedMapGenerator; 30 import com.google.common.collect.testing.TestStringSetGenerator; 31 import com.google.common.collect.testing.TestStringSortedSetGenerator; 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.SortedSetMultimapTestSuiteBuilder; 36 import com.google.common.collect.testing.google.TestStringSetMultimapGenerator; 37 import com.google.common.testing.SerializableTester; 38 import java.lang.reflect.Method; 39 import java.util.Arrays; 40 import java.util.Collection; 41 import java.util.Comparator; 42 import java.util.Iterator; 43 import java.util.List; 44 import java.util.Map.Entry; 45 import java.util.NavigableMap; 46 import java.util.NavigableSet; 47 import java.util.Set; 48 import java.util.SortedMap; 49 import java.util.SortedSet; 50 import junit.framework.Test; 51 import junit.framework.TestCase; 52 import junit.framework.TestSuite; 53 54 /** 55 * Unit tests for {@code TreeMultimap} with natural ordering. 56 * 57 * @author Jared Levy 58 */ 59 @GwtCompatible(emulated = true) 60 public class TreeMultimapNaturalTest extends TestCase { 61 62 @GwtIncompatible // suite suite()63 public static Test suite() { 64 TestSuite suite = new TestSuite(); 65 // TODO(lowasser): should we force TreeMultimap to be more thorough about checking nulls? 66 suite.addTest( 67 SortedSetMultimapTestSuiteBuilder.using( 68 new TestStringSetMultimapGenerator() { 69 @Override 70 protected SetMultimap<String, String> create(Entry<String, String>[] entries) { 71 SetMultimap<String, String> multimap = 72 TreeMultimap.create( 73 Ordering.natural().nullsFirst(), Ordering.natural().nullsFirst()); 74 for (Entry<String, String> entry : entries) { 75 multimap.put(entry.getKey(), entry.getValue()); 76 } 77 return multimap; 78 } 79 80 @Override 81 public Iterable<Entry<String, String>> order( 82 List<Entry<String, String>> insertionOrder) { 83 return new Ordering<Entry<String, String>>() { 84 @Override 85 public int compare(Entry<String, String> left, Entry<String, String> right) { 86 return ComparisonChain.start() 87 .compare(left.getKey(), right.getKey(), Ordering.natural().nullsFirst()) 88 .compare( 89 left.getValue(), right.getValue(), Ordering.natural().nullsFirst()) 90 .result(); 91 } 92 }.sortedCopy(insertionOrder); 93 } 94 }) 95 .named("TreeMultimap nullsFirst") 96 .withFeatures( 97 MapFeature.ALLOWS_NULL_KEYS, 98 MapFeature.ALLOWS_NULL_VALUES, 99 MapFeature.ALLOWS_ANY_NULL_QUERIES, 100 MapFeature.GENERAL_PURPOSE, 101 MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION, 102 CollectionFeature.SUPPORTS_ITERATOR_REMOVE, 103 CollectionFeature.KNOWN_ORDER, 104 CollectionFeature.SERIALIZABLE, 105 CollectionSize.ANY) 106 .createTestSuite()); 107 suite.addTest( 108 NavigableSetTestSuiteBuilder.using( 109 new TestStringSortedSetGenerator() { 110 @Override 111 protected NavigableSet<String> create(String[] elements) { 112 TreeMultimap<String, Integer> multimap = 113 TreeMultimap.create(Ordering.natural().nullsFirst(), Ordering.natural()); 114 for (int i = 0; i < elements.length; i++) { 115 multimap.put(elements[i], i); 116 } 117 return multimap.keySet(); 118 } 119 120 @Override 121 public List<String> order(List<String> insertionOrder) { 122 return Ordering.natural().nullsFirst().sortedCopy(insertionOrder); 123 } 124 }) 125 .named("TreeMultimap.keySet") 126 .withFeatures( 127 CollectionFeature.ALLOWS_NULL_VALUES, 128 CollectionFeature.REMOVE_OPERATIONS, 129 CollectionFeature.KNOWN_ORDER, 130 CollectionSize.ANY) 131 .createTestSuite()); 132 suite.addTest( 133 NavigableMapTestSuiteBuilder.using( 134 new TestSortedMapGenerator<String, Collection<String>>() { 135 136 @Override 137 public String[] createKeyArray(int length) { 138 return new String[length]; 139 } 140 141 @SuppressWarnings("unchecked") 142 @Override 143 public Collection<String>[] createValueArray(int length) { 144 return new Collection[length]; 145 } 146 147 @Override 148 public SampleElements<Entry<String, Collection<String>>> samples() { 149 return new SampleElements<>( 150 Helpers.mapEntry("a", (Collection<String>) ImmutableSortedSet.of("alex")), 151 Helpers.mapEntry( 152 "b", (Collection<String>) ImmutableSortedSet.of("bob", "bagel")), 153 Helpers.mapEntry( 154 "c", (Collection<String>) ImmutableSortedSet.of("carl", "carol")), 155 Helpers.mapEntry( 156 "d", (Collection<String>) ImmutableSortedSet.of("david", "dead")), 157 Helpers.mapEntry( 158 "e", (Collection<String>) ImmutableSortedSet.of("eric", "elaine"))); 159 } 160 161 @SuppressWarnings("unchecked") 162 @Override 163 public Entry<String, Collection<String>>[] createArray(int length) { 164 return new Entry[length]; 165 } 166 167 @Override 168 public Iterable<Entry<String, Collection<String>>> order( 169 List<Entry<String, Collection<String>>> insertionOrder) { 170 return new Ordering<Entry<String, ?>>() { 171 @Override 172 public int compare(Entry<String, ?> left, Entry<String, ?> right) { 173 return left.getKey().compareTo(right.getKey()); 174 } 175 }.sortedCopy(insertionOrder); 176 } 177 178 @Override 179 public NavigableMap<String, Collection<String>> create(Object... elements) { 180 TreeMultimap<String, String> multimap = TreeMultimap.create(); 181 for (Object o : elements) { 182 @SuppressWarnings("unchecked") 183 Entry<String, Collection<String>> entry = 184 (Entry<String, Collection<String>>) o; 185 checkArgument(!multimap.containsKey(entry.getKey())); 186 multimap.putAll(entry.getKey(), entry.getValue()); 187 } 188 return multimap.asMap(); 189 } 190 191 @Override 192 public Entry<String, Collection<String>> belowSamplesLesser() { 193 return Helpers.mapEntry( 194 "-- a", (Collection<String>) ImmutableSortedSet.of("--below")); 195 } 196 197 @Override 198 public Entry<String, Collection<String>> belowSamplesGreater() { 199 return Helpers.mapEntry( 200 "-- b", (Collection<String>) ImmutableSortedSet.of("--below")); 201 } 202 203 @Override 204 public Entry<String, Collection<String>> aboveSamplesLesser() { 205 return Helpers.mapEntry( 206 "~~ b", (Collection<String>) ImmutableSortedSet.of("~above")); 207 } 208 209 @Override 210 public Entry<String, Collection<String>> aboveSamplesGreater() { 211 return Helpers.mapEntry( 212 "~~ c", (Collection<String>) ImmutableSortedSet.of("~above")); 213 } 214 }) 215 .named("TreeMultimap.asMap") 216 .withFeatures( 217 MapFeature.SUPPORTS_REMOVE, 218 MapFeature.REJECTS_DUPLICATES_AT_CREATION, 219 CollectionFeature.SUPPORTS_ITERATOR_REMOVE, 220 CollectionFeature.KNOWN_ORDER, 221 CollectionSize.ANY) 222 .createTestSuite()); 223 suite.addTest( 224 NavigableSetTestSuiteBuilder.using( 225 new TestStringSetGenerator() { 226 @Override 227 protected Set<String> create(String[] elements) { 228 TreeMultimap<Integer, String> multimap = 229 TreeMultimap.create(Ordering.natural(), Ordering.natural().nullsFirst()); 230 multimap.putAll(1, Arrays.asList(elements)); 231 return multimap.get(1); 232 } 233 234 @Override 235 public List<String> order(List<String> insertionOrder) { 236 return Ordering.natural().nullsFirst().sortedCopy(insertionOrder); 237 } 238 }) 239 .named("TreeMultimap.get") 240 .withFeatures( 241 CollectionFeature.ALLOWS_NULL_VALUES, 242 CollectionFeature.GENERAL_PURPOSE, 243 CollectionFeature.KNOWN_ORDER, 244 CollectionSize.ANY) 245 .createTestSuite()); 246 suite.addTest( 247 NavigableSetTestSuiteBuilder.using( 248 new TestStringSetGenerator() { 249 @Override 250 protected Set<String> create(String[] elements) { 251 TreeMultimap<Integer, String> multimap = 252 TreeMultimap.create(Ordering.natural(), Ordering.natural().nullsFirst()); 253 multimap.putAll(1, Arrays.asList(elements)); 254 return (Set<String>) multimap.asMap().entrySet().iterator().next().getValue(); 255 } 256 257 @Override 258 public List<String> order(List<String> insertionOrder) { 259 return Ordering.natural().nullsFirst().sortedCopy(insertionOrder); 260 } 261 }) 262 .named("TreeMultimap.asMap.entrySet collection") 263 .withFeatures( 264 CollectionFeature.ALLOWS_NULL_VALUES, 265 CollectionFeature.GENERAL_PURPOSE, 266 CollectionFeature.KNOWN_ORDER, 267 CollectionSize.ONE, 268 CollectionSize.SEVERAL) 269 .createTestSuite()); 270 suite.addTestSuite(TreeMultimapNaturalTest.class); 271 return suite; 272 } 273 create()274 protected SetMultimap<String, Integer> create() { 275 return TreeMultimap.create(); 276 } 277 278 /** Create and populate a {@code TreeMultimap} with the natural ordering of keys and values. */ createPopulate()279 private TreeMultimap<String, Integer> createPopulate() { 280 TreeMultimap<String, Integer> multimap = TreeMultimap.create(); 281 multimap.put("google", 2); 282 multimap.put("google", 6); 283 multimap.put("foo", 3); 284 multimap.put("foo", 1); 285 multimap.put("foo", 7); 286 multimap.put("tree", 4); 287 multimap.put("tree", 0); 288 return multimap; 289 } 290 testToString()291 public void testToString() { 292 SetMultimap<String, Integer> multimap = create(); 293 multimap.putAll("bar", Arrays.asList(3, 1, 2)); 294 multimap.putAll("foo", Arrays.asList(2, 3, 1, -1, 4)); 295 assertEquals("{bar=[1, 2, 3], foo=[-1, 1, 2, 3, 4]}", multimap.toString()); 296 } 297 testOrderedGet()298 public void testOrderedGet() { 299 TreeMultimap<String, Integer> multimap = createPopulate(); 300 assertThat(multimap.get("foo")).containsExactly(1, 3, 7).inOrder(); 301 assertThat(multimap.get("google")).containsExactly(2, 6).inOrder(); 302 assertThat(multimap.get("tree")).containsExactly(0, 4).inOrder(); 303 } 304 testOrderedKeySet()305 public void testOrderedKeySet() { 306 TreeMultimap<String, Integer> multimap = createPopulate(); 307 assertThat(multimap.keySet()).containsExactly("foo", "google", "tree").inOrder(); 308 } 309 testOrderedAsMapEntries()310 public void testOrderedAsMapEntries() { 311 TreeMultimap<String, Integer> multimap = createPopulate(); 312 Iterator<Entry<String, Collection<Integer>>> iterator = multimap.asMap().entrySet().iterator(); 313 Entry<String, Collection<Integer>> entry = iterator.next(); 314 assertEquals("foo", entry.getKey()); 315 assertThat(entry.getValue()).containsExactly(1, 3, 7); 316 entry = iterator.next(); 317 assertEquals("google", entry.getKey()); 318 assertThat(entry.getValue()).containsExactly(2, 6); 319 entry = iterator.next(); 320 assertEquals("tree", entry.getKey()); 321 assertThat(entry.getValue()).containsExactly(0, 4); 322 } 323 testOrderedEntries()324 public void testOrderedEntries() { 325 TreeMultimap<String, Integer> multimap = createPopulate(); 326 assertThat(multimap.entries()) 327 .containsExactly( 328 Maps.immutableEntry("foo", 1), 329 Maps.immutableEntry("foo", 3), 330 Maps.immutableEntry("foo", 7), 331 Maps.immutableEntry("google", 2), 332 Maps.immutableEntry("google", 6), 333 Maps.immutableEntry("tree", 0), 334 Maps.immutableEntry("tree", 4)) 335 .inOrder(); 336 } 337 testOrderedValues()338 public void testOrderedValues() { 339 TreeMultimap<String, Integer> multimap = createPopulate(); 340 assertThat(multimap.values()).containsExactly(1, 3, 7, 2, 6, 0, 4).inOrder(); 341 } 342 testMultimapConstructor()343 public void testMultimapConstructor() { 344 SetMultimap<String, Integer> multimap = create(); 345 multimap.putAll("bar", Arrays.asList(3, 1, 2)); 346 multimap.putAll("foo", Arrays.asList(2, 3, 1, -1, 4)); 347 TreeMultimap<String, Integer> copy = TreeMultimap.create(multimap); 348 assertEquals(multimap, copy); 349 } 350 351 private static final Comparator<Double> KEY_COMPARATOR = Ordering.natural(); 352 353 private static final Comparator<Double> VALUE_COMPARATOR = 354 Ordering.natural().reverse().nullsFirst(); 355 356 /** 357 * Test that creating one TreeMultimap from another does not copy the comparators from the source 358 * TreeMultimap. 359 */ testCreateFromTreeMultimap()360 public void testCreateFromTreeMultimap() { 361 Multimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR); 362 tree.put(1.0, 2.0); 363 tree.put(2.0, 3.0); 364 tree.put(3.0, 4.0); 365 tree.put(4.0, 5.0); 366 367 TreeMultimap<Double, Double> copyFromTree = TreeMultimap.create(tree); 368 assertEquals(tree, copyFromTree); 369 assertSame(Ordering.natural(), copyFromTree.keyComparator()); 370 assertSame(Ordering.natural(), copyFromTree.valueComparator()); 371 assertSame(Ordering.natural(), copyFromTree.get(1.0).comparator()); 372 } 373 374 /** Test that creating one TreeMultimap from a non-TreeMultimap results in natural ordering. */ testCreateFromHashMultimap()375 public void testCreateFromHashMultimap() { 376 Multimap<Double, Double> hash = HashMultimap.create(); 377 hash.put(1.0, 2.0); 378 hash.put(2.0, 3.0); 379 hash.put(3.0, 4.0); 380 hash.put(4.0, 5.0); 381 382 TreeMultimap<Double, Double> copyFromHash = TreeMultimap.create(hash); 383 assertEquals(hash, copyFromHash); 384 assertEquals(Ordering.natural(), copyFromHash.keyComparator()); 385 assertEquals(Ordering.natural(), copyFromHash.valueComparator()); 386 } 387 388 /** Test that creating one TreeMultimap from a SortedSetMultimap uses natural ordering. */ testCreateFromSortedSetMultimap()389 public void testCreateFromSortedSetMultimap() { 390 SortedSetMultimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR); 391 tree.put(1.0, 2.0); 392 tree.put(2.0, 3.0); 393 tree.put(3.0, 4.0); 394 tree.put(4.0, 5.0); 395 396 SortedSetMultimap<Double, Double> sorted = Multimaps.unmodifiableSortedSetMultimap(tree); 397 TreeMultimap<Double, Double> copyFromSorted = TreeMultimap.create(sorted); 398 assertEquals(tree, copyFromSorted); 399 assertSame(Ordering.natural(), copyFromSorted.keyComparator()); 400 assertSame(Ordering.natural(), copyFromSorted.valueComparator()); 401 assertSame(Ordering.natural(), copyFromSorted.get(1.0).comparator()); 402 } 403 testComparators()404 public void testComparators() { 405 TreeMultimap<String, Integer> multimap = TreeMultimap.create(); 406 assertEquals(Ordering.natural(), multimap.keyComparator()); 407 assertEquals(Ordering.natural(), multimap.valueComparator()); 408 } 409 410 @GwtIncompatible // SerializableTester testExplicitComparatorSerialization()411 public void testExplicitComparatorSerialization() { 412 TreeMultimap<String, Integer> multimap = createPopulate(); 413 TreeMultimap<String, Integer> copy = SerializableTester.reserializeAndAssert(multimap); 414 assertThat(copy.values()).containsExactly(1, 3, 7, 2, 6, 0, 4).inOrder(); 415 assertThat(copy.keySet()).containsExactly("foo", "google", "tree").inOrder(); 416 assertEquals(multimap.keyComparator(), copy.keyComparator()); 417 assertEquals(multimap.valueComparator(), copy.valueComparator()); 418 } 419 420 @GwtIncompatible // SerializableTester testTreeMultimapDerived()421 public void testTreeMultimapDerived() { 422 TreeMultimap<DerivedComparable, DerivedComparable> multimap = TreeMultimap.create(); 423 assertEquals(ImmutableMultimap.of(), multimap); 424 multimap.put(new DerivedComparable("foo"), new DerivedComparable("f")); 425 multimap.put(new DerivedComparable("foo"), new DerivedComparable("o")); 426 multimap.put(new DerivedComparable("foo"), new DerivedComparable("o")); 427 multimap.put(new DerivedComparable("bar"), new DerivedComparable("b")); 428 multimap.put(new DerivedComparable("bar"), new DerivedComparable("a")); 429 multimap.put(new DerivedComparable("bar"), new DerivedComparable("r")); 430 assertThat(multimap.keySet()) 431 .containsExactly(new DerivedComparable("bar"), new DerivedComparable("foo")) 432 .inOrder(); 433 assertThat(multimap.values()) 434 .containsExactly( 435 new DerivedComparable("a"), 436 new DerivedComparable("b"), 437 new DerivedComparable("r"), 438 new DerivedComparable("f"), 439 new DerivedComparable("o")) 440 .inOrder(); 441 assertEquals(Ordering.natural(), multimap.keyComparator()); 442 assertEquals(Ordering.natural(), multimap.valueComparator()); 443 SerializableTester.reserializeAndAssert(multimap); 444 } 445 446 @GwtIncompatible // SerializableTester testTreeMultimapNonGeneric()447 public void testTreeMultimapNonGeneric() { 448 TreeMultimap<LegacyComparable, LegacyComparable> multimap = TreeMultimap.create(); 449 assertEquals(ImmutableMultimap.of(), multimap); 450 multimap.put(new LegacyComparable("foo"), new LegacyComparable("f")); 451 multimap.put(new LegacyComparable("foo"), new LegacyComparable("o")); 452 multimap.put(new LegacyComparable("foo"), new LegacyComparable("o")); 453 multimap.put(new LegacyComparable("bar"), new LegacyComparable("b")); 454 multimap.put(new LegacyComparable("bar"), new LegacyComparable("a")); 455 multimap.put(new LegacyComparable("bar"), new LegacyComparable("r")); 456 assertThat(multimap.keySet()) 457 .containsExactly(new LegacyComparable("bar"), new LegacyComparable("foo")) 458 .inOrder(); 459 assertThat(multimap.values()) 460 .containsExactly( 461 new LegacyComparable("a"), 462 new LegacyComparable("b"), 463 new LegacyComparable("r"), 464 new LegacyComparable("f"), 465 new LegacyComparable("o")) 466 .inOrder(); 467 assertEquals(Ordering.natural(), multimap.keyComparator()); 468 assertEquals(Ordering.natural(), multimap.valueComparator()); 469 SerializableTester.reserializeAndAssert(multimap); 470 } 471 testTreeMultimapAsMapSorted()472 public void testTreeMultimapAsMapSorted() { 473 TreeMultimap<String, Integer> multimap = createPopulate(); 474 SortedMap<String, Collection<Integer>> asMap = multimap.asMap(); 475 assertEquals(Ordering.natural(), asMap.comparator()); 476 assertEquals("foo", asMap.firstKey()); 477 assertEquals("tree", asMap.lastKey()); 478 Set<Integer> fooValues = ImmutableSet.of(1, 3, 7); 479 Set<Integer> googleValues = ImmutableSet.of(2, 6); 480 Set<Integer> treeValues = ImmutableSet.of(4, 0); 481 assertEquals(ImmutableMap.of("google", googleValues, "tree", treeValues), asMap.tailMap("g")); 482 assertEquals(ImmutableMap.of("google", googleValues, "foo", fooValues), asMap.headMap("h")); 483 assertEquals(ImmutableMap.of("google", googleValues), asMap.subMap("g", "h")); 484 } 485 testTailSetClear()486 public void testTailSetClear() { 487 TreeMultimap<String, Integer> multimap = TreeMultimap.create(); 488 multimap.put("a", 1); 489 multimap.put("a", 11); 490 multimap.put("b", 2); 491 multimap.put("c", 3); 492 multimap.put("d", 4); 493 multimap.put("e", 5); 494 multimap.put("e", 55); 495 496 multimap.keySet().tailSet("d").clear(); 497 assertEquals(ImmutableSet.of("a", "b", "c"), multimap.keySet()); 498 assertEquals(4, multimap.size()); 499 assertEquals(4, multimap.values().size()); 500 assertEquals(4, multimap.keys().size()); 501 } 502 503 @GwtIncompatible // reflection testKeySetBridgeMethods()504 public void testKeySetBridgeMethods() { 505 for (Method m : TreeMultimap.class.getMethods()) { 506 if (m.getName().equals("keySet") && m.getReturnType().equals(SortedSet.class)) { 507 return; 508 } 509 } 510 fail("No bridge method found"); 511 } 512 513 @GwtIncompatible // reflection testAsMapBridgeMethods()514 public void testAsMapBridgeMethods() { 515 for (Method m : TreeMultimap.class.getMethods()) { 516 if (m.getName().equals("asMap") && m.getReturnType().equals(SortedMap.class)) { 517 return; 518 } 519 } 520 } 521 522 @GwtIncompatible // reflection testGetBridgeMethods()523 public void testGetBridgeMethods() { 524 for (Method m : TreeMultimap.class.getMethods()) { 525 if (m.getName().equals("get") && m.getReturnType().equals(SortedSet.class)) { 526 return; 527 } 528 } 529 fail("No bridge method found"); 530 } 531 } 532