| /* |
| * Copyright (C) 2007 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.collect; |
| |
| import static com.google.common.base.Preconditions.checkArgument; |
| import static com.google.common.truth.Truth.assertThat; |
| |
| import com.google.common.annotations.GwtCompatible; |
| import com.google.common.annotations.GwtIncompatible; |
| import com.google.common.collect.testing.DerivedComparable; |
| import com.google.common.collect.testing.Helpers; |
| import com.google.common.collect.testing.NavigableMapTestSuiteBuilder; |
| import com.google.common.collect.testing.NavigableSetTestSuiteBuilder; |
| import com.google.common.collect.testing.SampleElements; |
| import com.google.common.collect.testing.TestSortedMapGenerator; |
| import com.google.common.collect.testing.TestStringSetGenerator; |
| import com.google.common.collect.testing.TestStringSortedSetGenerator; |
| import com.google.common.collect.testing.features.CollectionFeature; |
| import com.google.common.collect.testing.features.CollectionSize; |
| import com.google.common.collect.testing.features.MapFeature; |
| import com.google.common.collect.testing.google.SortedSetMultimapTestSuiteBuilder; |
| import com.google.common.collect.testing.google.TestStringSetMultimapGenerator; |
| import com.google.common.testing.SerializableTester; |
| import java.lang.reflect.Method; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map.Entry; |
| import java.util.NavigableMap; |
| import java.util.NavigableSet; |
| import java.util.Set; |
| import java.util.SortedMap; |
| import java.util.SortedSet; |
| import junit.framework.Test; |
| import junit.framework.TestCase; |
| import junit.framework.TestSuite; |
| |
| /** |
| * Unit tests for {@code TreeMultimap} with natural ordering. |
| * |
| * @author Jared Levy |
| */ |
| @GwtCompatible(emulated = true) |
| public class TreeMultimapNaturalTest extends TestCase { |
| |
| @GwtIncompatible // suite |
| public static Test suite() { |
| TestSuite suite = new TestSuite(); |
| // TODO(lowasser): should we force TreeMultimap to be more thorough about checking nulls? |
| suite.addTest( |
| SortedSetMultimapTestSuiteBuilder.using( |
| new TestStringSetMultimapGenerator() { |
| @Override |
| protected SetMultimap<String, String> create(Entry<String, String>[] entries) { |
| SetMultimap<String, String> multimap = |
| TreeMultimap.create( |
| Ordering.natural().nullsFirst(), Ordering.natural().nullsFirst()); |
| for (Entry<String, String> entry : entries) { |
| multimap.put(entry.getKey(), entry.getValue()); |
| } |
| return multimap; |
| } |
| |
| @Override |
| public Iterable<Entry<String, String>> order( |
| List<Entry<String, String>> insertionOrder) { |
| return new Ordering<Entry<String, String>>() { |
| @Override |
| public int compare(Entry<String, String> left, Entry<String, String> right) { |
| return ComparisonChain.start() |
| .compare(left.getKey(), right.getKey(), Ordering.natural().nullsFirst()) |
| .compare( |
| left.getValue(), right.getValue(), Ordering.natural().nullsFirst()) |
| .result(); |
| } |
| }.sortedCopy(insertionOrder); |
| } |
| }) |
| .named("TreeMultimap nullsFirst") |
| .withFeatures( |
| MapFeature.ALLOWS_NULL_KEYS, |
| MapFeature.ALLOWS_NULL_VALUES, |
| MapFeature.ALLOWS_ANY_NULL_QUERIES, |
| MapFeature.GENERAL_PURPOSE, |
| MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION, |
| CollectionFeature.SUPPORTS_ITERATOR_REMOVE, |
| CollectionFeature.KNOWN_ORDER, |
| CollectionFeature.SERIALIZABLE, |
| CollectionSize.ANY) |
| .createTestSuite()); |
| suite.addTest( |
| NavigableSetTestSuiteBuilder.using( |
| new TestStringSortedSetGenerator() { |
| @Override |
| protected NavigableSet<String> create(String[] elements) { |
| TreeMultimap<String, Integer> multimap = |
| TreeMultimap.create(Ordering.natural().nullsFirst(), Ordering.natural()); |
| for (int i = 0; i < elements.length; i++) { |
| multimap.put(elements[i], i); |
| } |
| return multimap.keySet(); |
| } |
| |
| @Override |
| public List<String> order(List<String> insertionOrder) { |
| return Ordering.natural().nullsFirst().sortedCopy(insertionOrder); |
| } |
| }) |
| .named("TreeMultimap.keySet") |
| .withFeatures( |
| CollectionFeature.ALLOWS_NULL_VALUES, |
| CollectionFeature.REMOVE_OPERATIONS, |
| CollectionFeature.KNOWN_ORDER, |
| CollectionSize.ANY) |
| .createTestSuite()); |
| suite.addTest( |
| NavigableMapTestSuiteBuilder.using( |
| new TestSortedMapGenerator<String, Collection<String>>() { |
| |
| @Override |
| public String[] createKeyArray(int length) { |
| return new String[length]; |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public Collection<String>[] createValueArray(int length) { |
| return new Collection[length]; |
| } |
| |
| @Override |
| public SampleElements<Entry<String, Collection<String>>> samples() { |
| return new SampleElements<>( |
| Helpers.mapEntry("a", (Collection<String>) ImmutableSortedSet.of("alex")), |
| Helpers.mapEntry( |
| "b", (Collection<String>) ImmutableSortedSet.of("bob", "bagel")), |
| Helpers.mapEntry( |
| "c", (Collection<String>) ImmutableSortedSet.of("carl", "carol")), |
| Helpers.mapEntry( |
| "d", (Collection<String>) ImmutableSortedSet.of("david", "dead")), |
| Helpers.mapEntry( |
| "e", (Collection<String>) ImmutableSortedSet.of("eric", "elaine"))); |
| } |
| |
| @SuppressWarnings("unchecked") |
| @Override |
| public Entry<String, Collection<String>>[] createArray(int length) { |
| return new Entry[length]; |
| } |
| |
| @Override |
| public Iterable<Entry<String, Collection<String>>> order( |
| List<Entry<String, Collection<String>>> insertionOrder) { |
| return new Ordering<Entry<String, ?>>() { |
| @Override |
| public int compare(Entry<String, ?> left, Entry<String, ?> right) { |
| return left.getKey().compareTo(right.getKey()); |
| } |
| }.sortedCopy(insertionOrder); |
| } |
| |
| @Override |
| public NavigableMap<String, Collection<String>> create(Object... elements) { |
| TreeMultimap<String, String> multimap = TreeMultimap.create(); |
| for (Object o : elements) { |
| @SuppressWarnings("unchecked") |
| Entry<String, Collection<String>> entry = |
| (Entry<String, Collection<String>>) o; |
| checkArgument(!multimap.containsKey(entry.getKey())); |
| multimap.putAll(entry.getKey(), entry.getValue()); |
| } |
| return multimap.asMap(); |
| } |
| |
| @Override |
| public Entry<String, Collection<String>> belowSamplesLesser() { |
| return Helpers.mapEntry( |
| "-- a", (Collection<String>) ImmutableSortedSet.of("--below")); |
| } |
| |
| @Override |
| public Entry<String, Collection<String>> belowSamplesGreater() { |
| return Helpers.mapEntry( |
| "-- b", (Collection<String>) ImmutableSortedSet.of("--below")); |
| } |
| |
| @Override |
| public Entry<String, Collection<String>> aboveSamplesLesser() { |
| return Helpers.mapEntry( |
| "~~ b", (Collection<String>) ImmutableSortedSet.of("~above")); |
| } |
| |
| @Override |
| public Entry<String, Collection<String>> aboveSamplesGreater() { |
| return Helpers.mapEntry( |
| "~~ c", (Collection<String>) ImmutableSortedSet.of("~above")); |
| } |
| }) |
| .named("TreeMultimap.asMap") |
| .withFeatures( |
| MapFeature.SUPPORTS_REMOVE, |
| MapFeature.REJECTS_DUPLICATES_AT_CREATION, |
| CollectionFeature.SUPPORTS_ITERATOR_REMOVE, |
| CollectionFeature.KNOWN_ORDER, |
| CollectionSize.ANY) |
| .createTestSuite()); |
| suite.addTest( |
| NavigableSetTestSuiteBuilder.using( |
| new TestStringSetGenerator() { |
| @Override |
| protected Set<String> create(String[] elements) { |
| TreeMultimap<Integer, String> multimap = |
| TreeMultimap.create(Ordering.natural(), Ordering.natural().nullsFirst()); |
| multimap.putAll(1, Arrays.asList(elements)); |
| return multimap.get(1); |
| } |
| |
| @Override |
| public List<String> order(List<String> insertionOrder) { |
| return Ordering.natural().nullsFirst().sortedCopy(insertionOrder); |
| } |
| }) |
| .named("TreeMultimap.get") |
| .withFeatures( |
| CollectionFeature.ALLOWS_NULL_VALUES, |
| CollectionFeature.GENERAL_PURPOSE, |
| CollectionFeature.KNOWN_ORDER, |
| CollectionSize.ANY) |
| .createTestSuite()); |
| suite.addTest( |
| NavigableSetTestSuiteBuilder.using( |
| new TestStringSetGenerator() { |
| @Override |
| protected Set<String> create(String[] elements) { |
| TreeMultimap<Integer, String> multimap = |
| TreeMultimap.create(Ordering.natural(), Ordering.natural().nullsFirst()); |
| multimap.putAll(1, Arrays.asList(elements)); |
| return (Set<String>) multimap.asMap().entrySet().iterator().next().getValue(); |
| } |
| |
| @Override |
| public List<String> order(List<String> insertionOrder) { |
| return Ordering.natural().nullsFirst().sortedCopy(insertionOrder); |
| } |
| }) |
| .named("TreeMultimap.asMap.entrySet collection") |
| .withFeatures( |
| CollectionFeature.ALLOWS_NULL_VALUES, |
| CollectionFeature.GENERAL_PURPOSE, |
| CollectionFeature.KNOWN_ORDER, |
| CollectionSize.ONE, |
| CollectionSize.SEVERAL) |
| .createTestSuite()); |
| suite.addTestSuite(TreeMultimapNaturalTest.class); |
| return suite; |
| } |
| |
| protected SetMultimap<String, Integer> create() { |
| return TreeMultimap.create(); |
| } |
| |
| /** Create and populate a {@code TreeMultimap} with the natural ordering of keys and values. */ |
| private TreeMultimap<String, Integer> createPopulate() { |
| TreeMultimap<String, Integer> multimap = TreeMultimap.create(); |
| multimap.put("google", 2); |
| multimap.put("google", 6); |
| multimap.put("foo", 3); |
| multimap.put("foo", 1); |
| multimap.put("foo", 7); |
| multimap.put("tree", 4); |
| multimap.put("tree", 0); |
| return multimap; |
| } |
| |
| public void testToString() { |
| SetMultimap<String, Integer> multimap = create(); |
| multimap.putAll("bar", Arrays.asList(3, 1, 2)); |
| multimap.putAll("foo", Arrays.asList(2, 3, 1, -1, 4)); |
| assertEquals("{bar=[1, 2, 3], foo=[-1, 1, 2, 3, 4]}", multimap.toString()); |
| } |
| |
| public void testOrderedGet() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| assertThat(multimap.get("foo")).containsExactly(1, 3, 7).inOrder(); |
| assertThat(multimap.get("google")).containsExactly(2, 6).inOrder(); |
| assertThat(multimap.get("tree")).containsExactly(0, 4).inOrder(); |
| } |
| |
| public void testOrderedKeySet() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| assertThat(multimap.keySet()).containsExactly("foo", "google", "tree").inOrder(); |
| } |
| |
| public void testOrderedAsMapEntries() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| Iterator<Entry<String, Collection<Integer>>> iterator = multimap.asMap().entrySet().iterator(); |
| Entry<String, Collection<Integer>> entry = iterator.next(); |
| assertEquals("foo", entry.getKey()); |
| assertThat(entry.getValue()).containsExactly(1, 3, 7); |
| entry = iterator.next(); |
| assertEquals("google", entry.getKey()); |
| assertThat(entry.getValue()).containsExactly(2, 6); |
| entry = iterator.next(); |
| assertEquals("tree", entry.getKey()); |
| assertThat(entry.getValue()).containsExactly(0, 4); |
| } |
| |
| public void testOrderedEntries() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| assertThat(multimap.entries()) |
| .containsExactly( |
| Maps.immutableEntry("foo", 1), |
| Maps.immutableEntry("foo", 3), |
| Maps.immutableEntry("foo", 7), |
| Maps.immutableEntry("google", 2), |
| Maps.immutableEntry("google", 6), |
| Maps.immutableEntry("tree", 0), |
| Maps.immutableEntry("tree", 4)) |
| .inOrder(); |
| } |
| |
| public void testOrderedValues() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| assertThat(multimap.values()).containsExactly(1, 3, 7, 2, 6, 0, 4).inOrder(); |
| } |
| |
| public void testMultimapConstructor() { |
| SetMultimap<String, Integer> multimap = create(); |
| multimap.putAll("bar", Arrays.asList(3, 1, 2)); |
| multimap.putAll("foo", Arrays.asList(2, 3, 1, -1, 4)); |
| TreeMultimap<String, Integer> copy = TreeMultimap.create(multimap); |
| assertEquals(multimap, copy); |
| } |
| |
| private static final Comparator<Double> KEY_COMPARATOR = Ordering.natural(); |
| |
| private static final Comparator<Double> VALUE_COMPARATOR = |
| Ordering.natural().reverse().nullsFirst(); |
| |
| /** |
| * Test that creating one TreeMultimap from another does not copy the comparators from the source |
| * TreeMultimap. |
| */ |
| public void testCreateFromTreeMultimap() { |
| Multimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR); |
| tree.put(1.0, 2.0); |
| tree.put(2.0, 3.0); |
| tree.put(3.0, 4.0); |
| tree.put(4.0, 5.0); |
| |
| TreeMultimap<Double, Double> copyFromTree = TreeMultimap.create(tree); |
| assertEquals(tree, copyFromTree); |
| assertSame(Ordering.natural(), copyFromTree.keyComparator()); |
| assertSame(Ordering.natural(), copyFromTree.valueComparator()); |
| assertSame(Ordering.natural(), copyFromTree.get(1.0).comparator()); |
| } |
| |
| /** Test that creating one TreeMultimap from a non-TreeMultimap results in natural ordering. */ |
| public void testCreateFromHashMultimap() { |
| Multimap<Double, Double> hash = HashMultimap.create(); |
| hash.put(1.0, 2.0); |
| hash.put(2.0, 3.0); |
| hash.put(3.0, 4.0); |
| hash.put(4.0, 5.0); |
| |
| TreeMultimap<Double, Double> copyFromHash = TreeMultimap.create(hash); |
| assertEquals(hash, copyFromHash); |
| assertEquals(Ordering.natural(), copyFromHash.keyComparator()); |
| assertEquals(Ordering.natural(), copyFromHash.valueComparator()); |
| } |
| |
| /** Test that creating one TreeMultimap from a SortedSetMultimap uses natural ordering. */ |
| public void testCreateFromSortedSetMultimap() { |
| SortedSetMultimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR); |
| tree.put(1.0, 2.0); |
| tree.put(2.0, 3.0); |
| tree.put(3.0, 4.0); |
| tree.put(4.0, 5.0); |
| |
| SortedSetMultimap<Double, Double> sorted = Multimaps.unmodifiableSortedSetMultimap(tree); |
| TreeMultimap<Double, Double> copyFromSorted = TreeMultimap.create(sorted); |
| assertEquals(tree, copyFromSorted); |
| assertSame(Ordering.natural(), copyFromSorted.keyComparator()); |
| assertSame(Ordering.natural(), copyFromSorted.valueComparator()); |
| assertSame(Ordering.natural(), copyFromSorted.get(1.0).comparator()); |
| } |
| |
| public void testComparators() { |
| TreeMultimap<String, Integer> multimap = TreeMultimap.create(); |
| assertEquals(Ordering.natural(), multimap.keyComparator()); |
| assertEquals(Ordering.natural(), multimap.valueComparator()); |
| } |
| |
| @GwtIncompatible // SerializableTester |
| public void testExplicitComparatorSerialization() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| TreeMultimap<String, Integer> copy = SerializableTester.reserializeAndAssert(multimap); |
| assertThat(copy.values()).containsExactly(1, 3, 7, 2, 6, 0, 4).inOrder(); |
| assertThat(copy.keySet()).containsExactly("foo", "google", "tree").inOrder(); |
| assertEquals(multimap.keyComparator(), copy.keyComparator()); |
| assertEquals(multimap.valueComparator(), copy.valueComparator()); |
| } |
| |
| @GwtIncompatible // SerializableTester |
| public void testTreeMultimapDerived() { |
| TreeMultimap<DerivedComparable, DerivedComparable> multimap = TreeMultimap.create(); |
| assertEquals(ImmutableMultimap.of(), multimap); |
| multimap.put(new DerivedComparable("foo"), new DerivedComparable("f")); |
| multimap.put(new DerivedComparable("foo"), new DerivedComparable("o")); |
| multimap.put(new DerivedComparable("foo"), new DerivedComparable("o")); |
| multimap.put(new DerivedComparable("bar"), new DerivedComparable("b")); |
| multimap.put(new DerivedComparable("bar"), new DerivedComparable("a")); |
| multimap.put(new DerivedComparable("bar"), new DerivedComparable("r")); |
| assertThat(multimap.keySet()) |
| .containsExactly(new DerivedComparable("bar"), new DerivedComparable("foo")) |
| .inOrder(); |
| assertThat(multimap.values()) |
| .containsExactly( |
| new DerivedComparable("a"), |
| new DerivedComparable("b"), |
| new DerivedComparable("r"), |
| new DerivedComparable("f"), |
| new DerivedComparable("o")) |
| .inOrder(); |
| assertEquals(Ordering.natural(), multimap.keyComparator()); |
| assertEquals(Ordering.natural(), multimap.valueComparator()); |
| SerializableTester.reserializeAndAssert(multimap); |
| } |
| |
| @GwtIncompatible // SerializableTester |
| public void testTreeMultimapNonGeneric() { |
| TreeMultimap<LegacyComparable, LegacyComparable> multimap = TreeMultimap.create(); |
| assertEquals(ImmutableMultimap.of(), multimap); |
| multimap.put(new LegacyComparable("foo"), new LegacyComparable("f")); |
| multimap.put(new LegacyComparable("foo"), new LegacyComparable("o")); |
| multimap.put(new LegacyComparable("foo"), new LegacyComparable("o")); |
| multimap.put(new LegacyComparable("bar"), new LegacyComparable("b")); |
| multimap.put(new LegacyComparable("bar"), new LegacyComparable("a")); |
| multimap.put(new LegacyComparable("bar"), new LegacyComparable("r")); |
| assertThat(multimap.keySet()) |
| .containsExactly(new LegacyComparable("bar"), new LegacyComparable("foo")) |
| .inOrder(); |
| assertThat(multimap.values()) |
| .containsExactly( |
| new LegacyComparable("a"), |
| new LegacyComparable("b"), |
| new LegacyComparable("r"), |
| new LegacyComparable("f"), |
| new LegacyComparable("o")) |
| .inOrder(); |
| assertEquals(Ordering.natural(), multimap.keyComparator()); |
| assertEquals(Ordering.natural(), multimap.valueComparator()); |
| SerializableTester.reserializeAndAssert(multimap); |
| } |
| |
| public void testTreeMultimapAsMapSorted() { |
| TreeMultimap<String, Integer> multimap = createPopulate(); |
| SortedMap<String, Collection<Integer>> asMap = multimap.asMap(); |
| assertEquals(Ordering.natural(), asMap.comparator()); |
| assertEquals("foo", asMap.firstKey()); |
| assertEquals("tree", asMap.lastKey()); |
| Set<Integer> fooValues = ImmutableSet.of(1, 3, 7); |
| Set<Integer> googleValues = ImmutableSet.of(2, 6); |
| Set<Integer> treeValues = ImmutableSet.of(4, 0); |
| assertEquals(ImmutableMap.of("google", googleValues, "tree", treeValues), asMap.tailMap("g")); |
| assertEquals(ImmutableMap.of("google", googleValues, "foo", fooValues), asMap.headMap("h")); |
| assertEquals(ImmutableMap.of("google", googleValues), asMap.subMap("g", "h")); |
| } |
| |
| public void testTailSetClear() { |
| TreeMultimap<String, Integer> multimap = TreeMultimap.create(); |
| multimap.put("a", 1); |
| multimap.put("a", 11); |
| multimap.put("b", 2); |
| multimap.put("c", 3); |
| multimap.put("d", 4); |
| multimap.put("e", 5); |
| multimap.put("e", 55); |
| |
| multimap.keySet().tailSet("d").clear(); |
| assertEquals(ImmutableSet.of("a", "b", "c"), multimap.keySet()); |
| assertEquals(4, multimap.size()); |
| assertEquals(4, multimap.values().size()); |
| assertEquals(4, multimap.keys().size()); |
| } |
| |
| @GwtIncompatible // reflection |
| public void testKeySetBridgeMethods() { |
| for (Method m : TreeMultimap.class.getMethods()) { |
| if (m.getName().equals("keySet") && m.getReturnType().equals(SortedSet.class)) { |
| return; |
| } |
| } |
| fail("No bridge method found"); |
| } |
| |
| @GwtIncompatible // reflection |
| public void testAsMapBridgeMethods() { |
| for (Method m : TreeMultimap.class.getMethods()) { |
| if (m.getName().equals("asMap") && m.getReturnType().equals(SortedMap.class)) { |
| return; |
| } |
| } |
| } |
| |
| @GwtIncompatible // reflection |
| public void testGetBridgeMethods() { |
| for (Method m : TreeMultimap.class.getMethods()) { |
| if (m.getName().equals("get") && m.getReturnType().equals(SortedSet.class)) { |
| return; |
| } |
| } |
| fail("No bridge method found"); |
| } |
| } |
