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