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.testing.IteratorFeature.MODIFIABLE; 22 import static java.util.Arrays.asList; 23 import static org.junit.contrib.truth.Truth.ASSERT; 24 25 import com.google.common.annotations.GwtCompatible; 26 import com.google.common.annotations.GwtIncompatible; 27 import com.google.common.collect.testing.DerivedComparable; 28 import com.google.common.collect.testing.IteratorTester; 29 import com.google.common.testing.SerializableTester; 30 31 import java.util.Collection; 32 import java.util.Collections; 33 import java.util.Comparator; 34 import java.util.Iterator; 35 import java.util.List; 36 import java.util.Map; 37 import java.util.Map.Entry; 38 import java.util.NoSuchElementException; 39 import java.util.Set; 40 import java.util.SortedMap; 41 import java.util.SortedSet; 42 43 /** 44 * Unit tests for {@code TreeMultimap} with natural ordering. 45 * 46 * @author Jared Levy 47 */ 48 @GwtCompatible(emulated = true) 49 public class TreeMultimapNaturalTest<E> extends AbstractSetMultimapTest { 50 @Override protected Multimap<String, Integer> create() { 51 return TreeMultimap.create(); 52 } 53 54 /* Null keys and values aren't supported. */ 55 @Override protected String nullKey() { 56 return "null"; 57 } 58 59 @Override protected Integer nullValue() { 60 return 42; 61 } 62 63 /** 64 * Create and populate a {@code TreeMultimap} with the natural ordering of 65 * keys and values. 66 */ 67 private TreeMultimap<String, Integer> createPopulate() { 68 TreeMultimap<String, Integer> multimap = TreeMultimap.create(); 69 multimap.put("google", 2); 70 multimap.put("google", 6); 71 multimap.put("foo", 3); 72 multimap.put("foo", 1); 73 multimap.put("foo", 7); 74 multimap.put("tree", 4); 75 multimap.put("tree", 0); 76 return multimap; 77 } 78 79 public void testToString() { 80 assertEquals("{bar=[1, 2, 3], foo=[-1, 1, 2, 3, 4]}", 81 createSample().toString()); 82 } 83 84 public void testOrderedGet() { 85 TreeMultimap<String, Integer> multimap = createPopulate(); 86 ASSERT.that(multimap.get("foo")).hasContentsInOrder(1, 3, 7); 87 ASSERT.that(multimap.get("google")).hasContentsInOrder(2, 6); 88 ASSERT.that(multimap.get("tree")).hasContentsInOrder(0, 4); 89 } 90 91 public void testOrderedKeySet() { 92 TreeMultimap<String, Integer> multimap = createPopulate(); 93 ASSERT.that(multimap.keySet()).hasContentsInOrder("foo", "google", "tree"); 94 } 95 96 public void testOrderedAsMapEntries() { 97 TreeMultimap<String, Integer> multimap = createPopulate(); 98 Iterator<Map.Entry<String, Collection<Integer>>> iterator = 99 multimap.asMap().entrySet().iterator(); 100 Map.Entry<String, Collection<Integer>> entry = iterator.next(); 101 assertEquals("foo", entry.getKey()); 102 ASSERT.that(entry.getValue()).hasContentsAnyOrder(1, 3, 7); 103 entry = iterator.next(); 104 assertEquals("google", entry.getKey()); 105 ASSERT.that(entry.getValue()).hasContentsAnyOrder(2, 6); 106 entry = iterator.next(); 107 assertEquals("tree", entry.getKey()); 108 ASSERT.that(entry.getValue()).hasContentsAnyOrder(0, 4); 109 } 110 111 public void testOrderedEntries() { 112 TreeMultimap<String, Integer> multimap = createPopulate(); 113 ASSERT.that(multimap.entries()).hasContentsInOrder( 114 Maps.immutableEntry("foo", 1), 115 Maps.immutableEntry("foo", 3), 116 Maps.immutableEntry("foo", 7), 117 Maps.immutableEntry("google", 2), 118 Maps.immutableEntry("google", 6), 119 Maps.immutableEntry("tree", 0), 120 Maps.immutableEntry("tree", 4)); 121 } 122 123 public void testOrderedValues() { 124 TreeMultimap<String, Integer> multimap = createPopulate(); 125 ASSERT.that(multimap.values()).hasContentsInOrder( 126 1, 3, 7, 2, 6, 0, 4); 127 } 128 129 public void testFirst() { 130 TreeMultimap<String, Integer> multimap = createPopulate(); 131 assertEquals(Integer.valueOf(1), multimap.get("foo").first()); 132 try { 133 multimap.get("missing").first(); 134 fail("Expected NoSuchElementException"); 135 } catch (NoSuchElementException expected) {} 136 } 137 138 public void testLast() { 139 TreeMultimap<String, Integer> multimap = createPopulate(); 140 assertEquals(Integer.valueOf(7), multimap.get("foo").last()); 141 try { 142 multimap.get("missing").last(); 143 fail("Expected NoSuchElementException"); 144 } catch (NoSuchElementException expected) {} 145 } 146 147 public void testComparatorFromGet() { 148 TreeMultimap<String, Integer> multimap = createPopulate(); 149 assertSame(Ordering.natural(), multimap.get("foo").comparator()); 150 assertSame(Ordering.natural(), multimap.get("missing").comparator()); 151 } 152 153 public void testHeadSet() { 154 TreeMultimap<String, Integer> multimap = createPopulate(); 155 Set<Integer> fooSet = multimap.get("foo").headSet(4); 156 assertEquals(Sets.newHashSet(1, 3), fooSet); 157 Set<Integer> missingSet = multimap.get("missing").headSet(4); 158 assertEquals(Sets.newHashSet(), missingSet); 159 160 multimap.put("foo", 0); 161 assertEquals(Sets.newHashSet(0, 1, 3), fooSet); 162 163 missingSet.add(2); 164 assertEquals(Sets.newHashSet(2), multimap.get("missing")); 165 } 166 167 public void testTailSet() { 168 TreeMultimap<String, Integer> multimap = createPopulate(); 169 Set<Integer> fooSet = multimap.get("foo").tailSet(2); 170 assertEquals(Sets.newHashSet(3, 7), fooSet); 171 Set<Integer> missingSet = multimap.get("missing").tailSet(4); 172 assertEquals(Sets.newHashSet(), missingSet); 173 174 multimap.put("foo", 6); 175 assertEquals(Sets.newHashSet(3, 6, 7), fooSet); 176 177 missingSet.add(9); 178 assertEquals(Sets.newHashSet(9), multimap.get("missing")); 179 } 180 181 public void testSubSet() { 182 TreeMultimap<String, Integer> multimap = createPopulate(); 183 Set<Integer> fooSet = multimap.get("foo").subSet(2, 6); 184 assertEquals(Sets.newHashSet(3), fooSet); 185 186 multimap.put("foo", 5); 187 assertEquals(Sets.newHashSet(3, 5), fooSet); 188 189 fooSet.add(4); 190 assertEquals(Sets.newHashSet(1, 3, 4, 5, 7), multimap.get("foo")); 191 } 192 193 public void testMultimapConstructor() { 194 Multimap<String, Integer> multimap = createSample(); 195 TreeMultimap<String, Integer> copy = TreeMultimap.create(multimap); 196 assertEquals(multimap, copy); 197 } 198 199 private static final Comparator<Double> KEY_COMPARATOR = 200 Ordering.natural(); 201 202 private static final Comparator<Double> VALUE_COMPARATOR = 203 Ordering.natural().reverse().nullsFirst(); 204 205 /** 206 * Test that creating one TreeMultimap from another does not copy the 207 * comparators from the source TreeMultimap. 208 */ 209 public void testCreateFromTreeMultimap() { 210 Multimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR); 211 tree.put(1.0, 2.0); 212 tree.put(2.0, 3.0); 213 tree.put(3.0, 4.0); 214 tree.put(4.0, 5.0); 215 216 TreeMultimap<Double, Double> copyFromTree = TreeMultimap.create(tree); 217 assertEquals(tree, copyFromTree); 218 assertSame(Ordering.natural(), copyFromTree.keyComparator()); 219 assertSame(Ordering.natural(), copyFromTree.valueComparator()); 220 assertSame(Ordering.natural(), copyFromTree.get(1.0).comparator()); 221 } 222 223 /** 224 * Test that creating one TreeMultimap from a non-TreeMultimap 225 * results in natural ordering. 226 */ 227 public void testCreateFromHashMultimap() { 228 Multimap<Double, Double> hash = HashMultimap.create(); 229 hash.put(1.0, 2.0); 230 hash.put(2.0, 3.0); 231 hash.put(3.0, 4.0); 232 hash.put(4.0, 5.0); 233 234 TreeMultimap<Double, Double> copyFromHash = TreeMultimap.create(hash); 235 assertEquals(hash, copyFromHash); 236 assertEquals(Ordering.natural(), copyFromHash.keyComparator()); 237 assertEquals(Ordering.natural(), copyFromHash.valueComparator()); 238 } 239 240 /** 241 * Test that creating one TreeMultimap from a SortedSetMultimap uses natural 242 * ordering. 243 */ 244 public void testCreateFromSortedSetMultimap() { 245 SortedSetMultimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR); 246 tree.put(1.0, 2.0); 247 tree.put(2.0, 3.0); 248 tree.put(3.0, 4.0); 249 tree.put(4.0, 5.0); 250 251 SortedSetMultimap<Double, Double> sorted = Multimaps.unmodifiableSortedSetMultimap(tree); 252 TreeMultimap<Double, Double> copyFromSorted = TreeMultimap.create(sorted); 253 assertEquals(tree, copyFromSorted); 254 assertSame(Ordering.natural(), copyFromSorted.keyComparator()); 255 assertSame(Ordering.natural(), copyFromSorted.valueComparator()); 256 assertSame(Ordering.natural(), copyFromSorted.get(1.0).comparator()); 257 } 258 259 public void testComparators() { 260 TreeMultimap<String, Integer> multimap = TreeMultimap.create(); 261 assertEquals(Ordering.natural(), multimap.keyComparator()); 262 assertEquals(Ordering.natural(), multimap.valueComparator()); 263 } 264 265 public void testSortedKeySet() { 266 TreeMultimap<String, Integer> multimap = createPopulate(); 267 SortedSet<String> keySet = multimap.keySet(); 268 269 assertEquals("foo", keySet.first()); 270 assertEquals("tree", keySet.last()); 271 assertEquals(Ordering.natural(), keySet.comparator()); 272 assertEquals(ImmutableSet.of("foo", "google"), keySet.headSet("hi")); 273 assertEquals(ImmutableSet.of("tree"), keySet.tailSet("hi")); 274 assertEquals(ImmutableSet.of("google"), keySet.subSet("gap", "hi")); 275 } 276 277 public void testKeySetSubSet() { 278 TreeMultimap<String, Integer> multimap = createPopulate(); 279 SortedSet<String> keySet = multimap.keySet(); 280 SortedSet<String> subSet = keySet.subSet("gap", "hi"); 281 282 assertEquals(1, subSet.size()); 283 assertTrue(subSet.contains("google")); 284 assertFalse(subSet.contains("foo")); 285 assertTrue(subSet.containsAll(Collections.singleton("google"))); 286 assertFalse(subSet.containsAll(Collections.singleton("foo"))); 287 288 Iterator<String> iterator = subSet.iterator(); 289 assertTrue(iterator.hasNext()); 290 assertEquals("google", iterator.next()); 291 assertFalse(iterator.hasNext()); 292 293 assertFalse(subSet.remove("foo")); 294 assertTrue(multimap.containsKey("foo")); 295 assertEquals(7, multimap.size()); 296 assertTrue(subSet.remove("google")); 297 assertFalse(multimap.containsKey("google")); 298 assertEquals(5, multimap.size()); 299 } 300 301 @GwtIncompatible("unreasonable slow") 302 public void testGetIteration() { 303 new IteratorTester<Integer>(6, MODIFIABLE, 304 Sets.newTreeSet(asList(2, 3, 4, 7, 8)), 305 IteratorTester.KnownOrder.KNOWN_ORDER) { 306 private Multimap<String, Integer> multimap; 307 308 @Override protected Iterator<Integer> newTargetIterator() { 309 multimap = create(); 310 multimap.putAll("foo", asList(3, 8, 4)); 311 multimap.putAll("bar", asList(5, 6)); 312 multimap.putAll("foo", asList(7, 2)); 313 return multimap.get("foo").iterator(); 314 } 315 316 @Override protected void verify(List<Integer> elements) { 317 assertEquals(newHashSet(elements), multimap.get("foo")); 318 } 319 }.test(); 320 } 321 322 @SuppressWarnings("unchecked") 323 @GwtIncompatible("unreasonable slow") 324 public void testEntriesIteration() { 325 Set<Entry<String, Integer>> set = Sets.newLinkedHashSet(asList( 326 Maps.immutableEntry("bar", 4), 327 Maps.immutableEntry("bar", 5), 328 Maps.immutableEntry("foo", 2), 329 Maps.immutableEntry("foo", 3), 330 Maps.immutableEntry("foo", 6))); 331 new IteratorTester<Entry<String, Integer>>(6, MODIFIABLE, set, 332 IteratorTester.KnownOrder.KNOWN_ORDER) { 333 private Multimap<String, Integer> multimap; 334 335 @Override protected Iterator<Entry<String, Integer>> newTargetIterator() { 336 multimap = create(); 337 multimap.putAll("foo", asList(6, 3)); 338 multimap.putAll("bar", asList(4, 5)); 339 multimap.putAll("foo", asList(2)); 340 return multimap.entries().iterator(); 341 } 342 343 @Override protected void verify(List<Entry<String, Integer>> elements) { 344 assertEquals(newHashSet(elements), multimap.entries()); 345 } 346 }.test(); 347 } 348 349 @GwtIncompatible("unreasonable slow") 350 public void testKeysIteration() { 351 new IteratorTester<String>(6, MODIFIABLE, Lists.newArrayList("bar", "bar", 352 "foo", "foo", "foo"), IteratorTester.KnownOrder.KNOWN_ORDER) { 353 private Multimap<String, Integer> multimap; 354 355 @Override protected Iterator<String> newTargetIterator() { 356 multimap = create(); 357 multimap.putAll("foo", asList(2, 3)); 358 multimap.putAll("bar", asList(4, 5)); 359 multimap.putAll("foo", asList(6)); 360 return multimap.keys().iterator(); 361 } 362 363 @Override protected void verify(List<String> elements) { 364 assertEquals(elements, Lists.newArrayList(multimap.keys())); 365 } 366 }.test(); 367 } 368 369 @GwtIncompatible("unreasonable slow") 370 public void testValuesIteration() { 371 new IteratorTester<Integer>(6, MODIFIABLE, newArrayList(4, 5, 2, 3, 6), 372 IteratorTester.KnownOrder.KNOWN_ORDER) { 373 private Multimap<String, Integer> multimap; 374 375 @Override protected Iterator<Integer> newTargetIterator() { 376 multimap = create(); 377 multimap.putAll("foo", asList(2, 3)); 378 multimap.putAll("bar", asList(4, 5)); 379 multimap.putAll("foo", asList(6)); 380 return multimap.values().iterator(); 381 } 382 383 @Override protected void verify(List<Integer> elements) { 384 assertEquals(elements, Lists.newArrayList(multimap.values())); 385 } 386 }.test(); 387 } 388 389 @GwtIncompatible("unreasonable slow") 390 public void testKeySetIteration() { 391 new IteratorTester<String>(6, MODIFIABLE, 392 Sets.newTreeSet(asList("bar", "baz", "cat", "dog", "foo")), 393 IteratorTester.KnownOrder.KNOWN_ORDER) { 394 private Multimap<String, Integer> multimap; 395 396 @Override protected Iterator<String> newTargetIterator() { 397 multimap = create(); 398 multimap.putAll("foo", asList(2, 3)); 399 multimap.putAll("bar", asList(4, 5)); 400 multimap.putAll("foo", asList(6)); 401 multimap.putAll("baz", asList(7, 8)); 402 multimap.putAll("dog", asList(9)); 403 multimap.putAll("bar", asList(10, 11)); 404 multimap.putAll("cat", asList(12, 13, 14)); 405 return multimap.keySet().iterator(); 406 } 407 408 @Override protected void verify(List<String> elements) { 409 assertEquals(newHashSet(elements), multimap.keySet()); 410 } 411 }.test(); 412 } 413 414 @SuppressWarnings("unchecked") 415 @GwtIncompatible("unreasonable slow") 416 public void testAsSetIteration() { 417 Set<Entry<String, Collection<Integer>>> set = Sets.newTreeSet( 418 new Comparator<Entry<String, ?>>() { 419 @Override 420 public int compare(Entry<String, ?> o1, Entry<String, ?> o2) { 421 return o1.getKey().compareTo(o2.getKey()); 422 } 423 }); 424 Collections.addAll(set, 425 Maps.immutableEntry("bar", 426 (Collection<Integer>) Sets.newHashSet(4, 5, 10, 11)), 427 Maps.immutableEntry("baz", 428 (Collection<Integer>) Sets.newHashSet(7, 8)), 429 Maps.immutableEntry("cat", 430 (Collection<Integer>) Sets.newHashSet(12, 13, 14)), 431 Maps.immutableEntry("dog", 432 (Collection<Integer>) Sets.newHashSet(9)), 433 Maps.immutableEntry("foo", 434 (Collection<Integer>) Sets.newHashSet(2, 3, 6)) 435 ); 436 437 new IteratorTester<Entry<String, Collection<Integer>>>(6, MODIFIABLE, set, 438 IteratorTester.KnownOrder.KNOWN_ORDER) { 439 private Multimap<String, Integer> multimap; 440 441 @Override protected Iterator<Entry<String, Collection<Integer>>> 442 newTargetIterator() { 443 multimap = create(); 444 multimap.putAll("foo", asList(2, 3)); 445 multimap.putAll("bar", asList(4, 5)); 446 multimap.putAll("foo", asList(6)); 447 multimap.putAll("baz", asList(7, 8)); 448 multimap.putAll("dog", asList(9)); 449 multimap.putAll("bar", asList(10, 11)); 450 multimap.putAll("cat", asList(12, 13, 14)); 451 return multimap.asMap().entrySet().iterator(); 452 } 453 454 @Override protected void verify( 455 List<Entry<String, Collection<Integer>>> elements) { 456 assertEquals(newHashSet(elements), multimap.asMap().entrySet()); 457 } 458 }.test(); 459 } 460 461 @GwtIncompatible("SerializableTester") 462 public void testExplicitComparatorSerialization() { 463 TreeMultimap<String, Integer> multimap = createPopulate(); 464 TreeMultimap<String, Integer> copy 465 = SerializableTester.reserializeAndAssert(multimap); 466 ASSERT.that(copy.values()).hasContentsInOrder(1, 3, 7, 2, 6, 0, 4); 467 ASSERT.that(copy.keySet()).hasContentsInOrder("foo", "google", "tree"); 468 assertEquals(multimap.keyComparator(), copy.keyComparator()); 469 assertEquals(multimap.valueComparator(), copy.valueComparator()); 470 } 471 472 @GwtIncompatible("SerializableTester") 473 public void testTreeMultimapDerived() { 474 TreeMultimap<DerivedComparable, DerivedComparable> multimap = TreeMultimap.create(); 475 assertEquals(ImmutableMultimap.of(), multimap); 476 multimap.put(new DerivedComparable("foo"), new DerivedComparable("f")); 477 multimap.put(new DerivedComparable("foo"), new DerivedComparable("o")); 478 multimap.put(new DerivedComparable("foo"), new DerivedComparable("o")); 479 multimap.put(new DerivedComparable("bar"), new DerivedComparable("b")); 480 multimap.put(new DerivedComparable("bar"), new DerivedComparable("a")); 481 multimap.put(new DerivedComparable("bar"), new DerivedComparable("r")); 482 ASSERT.that(multimap.keySet()).hasContentsInOrder( 483 new DerivedComparable("bar"), new DerivedComparable("foo")); 484 ASSERT.that(multimap.values()).hasContentsInOrder( 485 new DerivedComparable("a"), new DerivedComparable("b"), new DerivedComparable("r"), 486 new DerivedComparable("f"), new DerivedComparable("o")); 487 assertEquals(Ordering.natural(), multimap.keyComparator()); 488 assertEquals(Ordering.natural(), multimap.valueComparator()); 489 SerializableTester.reserializeAndAssert(multimap); 490 } 491 492 @GwtIncompatible("SerializableTester") 493 public void testTreeMultimapNonGeneric() { 494 TreeMultimap<LegacyComparable, LegacyComparable> multimap 495 = TreeMultimap.create(); 496 assertEquals(ImmutableMultimap.of(), multimap); 497 multimap.put(new LegacyComparable("foo"), new LegacyComparable("f")); 498 multimap.put(new LegacyComparable("foo"), new LegacyComparable("o")); 499 multimap.put(new LegacyComparable("foo"), new LegacyComparable("o")); 500 multimap.put(new LegacyComparable("bar"), new LegacyComparable("b")); 501 multimap.put(new LegacyComparable("bar"), new LegacyComparable("a")); 502 multimap.put(new LegacyComparable("bar"), new LegacyComparable("r")); 503 ASSERT.that(multimap.keySet()).hasContentsInOrder( 504 new LegacyComparable("bar"), new LegacyComparable("foo")); 505 ASSERT.that(multimap.values()).hasContentsInOrder( 506 new LegacyComparable("a"), 507 new LegacyComparable("b"), 508 new LegacyComparable("r"), 509 new LegacyComparable("f"), 510 new LegacyComparable("o")); 511 assertEquals(Ordering.natural(), multimap.keyComparator()); 512 assertEquals(Ordering.natural(), multimap.valueComparator()); 513 SerializableTester.reserializeAndAssert(multimap); 514 } 515 516 public void testTreeMultimapAsMapSorted() { 517 TreeMultimap<String, Integer> multimap = createPopulate(); 518 SortedMap<String, Collection<Integer>> asMap = multimap.asMap(); 519 assertEquals(Ordering.natural(), asMap.comparator()); 520 assertEquals("foo", asMap.firstKey()); 521 assertEquals("tree", asMap.lastKey()); 522 Set<Integer> fooValues = ImmutableSet.of(1, 3, 7); 523 Set<Integer> googleValues = ImmutableSet.of(2, 6); 524 Set<Integer> treeValues = ImmutableSet.of(4, 0); 525 assertEquals(ImmutableMap.of("google", googleValues, "tree", treeValues), 526 asMap.tailMap("g")); 527 assertEquals(ImmutableMap.of("google", googleValues, "foo", fooValues), 528 asMap.headMap("h")); 529 assertEquals(ImmutableMap.of("google", googleValues), 530 asMap.subMap("g", "h")); 531 } 532 533 public void testTailSetClear() { 534 TreeMultimap<String, Integer> multimap = TreeMultimap.create(); 535 multimap.put("a", 1); 536 multimap.put("a", 11); 537 multimap.put("b", 2); 538 multimap.put("c", 3); 539 multimap.put("d", 4); 540 multimap.put("e", 5); 541 multimap.put("e", 55); 542 543 multimap.keySet().tailSet("d").clear(); 544 assertEquals(ImmutableSet.of("a", "b", "c"), multimap.keySet()); 545 assertEquals(4, multimap.size()); 546 assertEquals(4, multimap.values().size()); 547 assertEquals(4, multimap.keys().size()); 548 } 549 } 550
