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 org.truth0.Truth.ASSERT;
20 
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.annotations.GwtIncompatible;
23 import com.google.common.collect.testing.DerivedComparable;
24 import com.google.common.collect.testing.features.CollectionFeature;
25 import com.google.common.collect.testing.features.CollectionSize;
26 import com.google.common.collect.testing.features.MapFeature;
27 import com.google.common.collect.testing.google.SortedSetMultimapTestSuiteBuilder;
28 import com.google.common.collect.testing.google.TestStringSetMultimapGenerator;
29 import com.google.common.testing.SerializableTester;
30 
31 import junit.framework.Test;
32 import junit.framework.TestCase;
33 import junit.framework.TestSuite;
34 
35 import java.lang.reflect.Method;
36 import java.util.Arrays;
37 import java.util.Collection;
38 import java.util.Comparator;
39 import java.util.Iterator;
40 import java.util.List;
41 import java.util.Map;
42 import java.util.Map.Entry;
43 import java.util.Set;
44 import java.util.SortedMap;
45 import java.util.SortedSet;
46 
47 /**
48  * Unit tests for {@code TreeMultimap} with natural ordering.
49  *
50  * @author Jared Levy
51  */
52 @GwtCompatible(emulated = true)
53 public class TreeMultimapNaturalTest extends TestCase {
54 
55   @GwtIncompatible("suite")
suite()56   public static Test suite() {
57     TestSuite suite = new TestSuite();
58     // TODO(user): should we force TreeMultimap to be more thorough about checking nulls?
59     suite.addTest(SortedSetMultimapTestSuiteBuilder.using(new TestStringSetMultimapGenerator() {
60         @Override
61         protected SetMultimap<String, String> create(Entry<String, String>[] entries) {
62           SetMultimap<String, String> multimap = TreeMultimap.create(
63               Ordering.natural().nullsFirst(), Ordering.natural().nullsFirst());
64           for (Entry<String, String> entry : entries) {
65             multimap.put(entry.getKey(), entry.getValue());
66           }
67           return multimap;
68         }
69 
70         @Override
71         public Iterable<Entry<String, String>> order(List<Entry<String, String>> insertionOrder) {
72           return new Ordering<Entry<String, String>>() {
73             @Override
74             public int compare(Entry<String, String> left, Entry<String, String> right) {
75               return ComparisonChain.start()
76                   .compare(left.getKey(), right.getKey(), Ordering.natural().nullsFirst())
77                   .compare(left.getValue(), right.getValue(), Ordering.natural().nullsFirst())
78                   .result();
79             }
80           }.sortedCopy(insertionOrder);
81         }
82       })
83       .named("TreeMultimap nullsFirst")
84       .withFeatures(
85           MapFeature.ALLOWS_NULL_KEYS,
86           MapFeature.ALLOWS_NULL_VALUES,
87           MapFeature.ALLOWS_ANY_NULL_QUERIES,
88           MapFeature.GENERAL_PURPOSE,
89           MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION,
90           CollectionFeature.SUPPORTS_ITERATOR_REMOVE,
91           CollectionFeature.KNOWN_ORDER,
92           CollectionFeature.SERIALIZABLE,
93           CollectionSize.ANY)
94       .createTestSuite());
95     suite.addTestSuite(TreeMultimapNaturalTest.class);
96     return suite;
97   }
98 
create()99   protected SetMultimap<String, Integer> create() {
100     return TreeMultimap.create();
101   }
102 
103   /**
104    * Create and populate a {@code TreeMultimap} with the natural ordering of
105    * keys and values.
106    */
createPopulate()107   private TreeMultimap<String, Integer> createPopulate() {
108     TreeMultimap<String, Integer> multimap = TreeMultimap.create();
109     multimap.put("google", 2);
110     multimap.put("google", 6);
111     multimap.put("foo", 3);
112     multimap.put("foo", 1);
113     multimap.put("foo", 7);
114     multimap.put("tree", 4);
115     multimap.put("tree", 0);
116     return multimap;
117   }
118 
testToString()119   public void testToString() {
120     SetMultimap<String, Integer> multimap = create();
121     multimap.putAll("bar", Arrays.asList(3, 1, 2));
122     multimap.putAll("foo", Arrays.asList(2, 3, 1, -1, 4));
123     assertEquals("{bar=[1, 2, 3], foo=[-1, 1, 2, 3, 4]}",
124         multimap.toString());
125   }
126 
testOrderedGet()127   public void testOrderedGet() {
128     TreeMultimap<String, Integer> multimap = createPopulate();
129     ASSERT.that(multimap.get("foo")).has().exactly(1, 3, 7).inOrder();
130     ASSERT.that(multimap.get("google")).has().exactly(2, 6).inOrder();
131     ASSERT.that(multimap.get("tree")).has().exactly(0, 4).inOrder();
132   }
133 
testOrderedKeySet()134   public void testOrderedKeySet() {
135     TreeMultimap<String, Integer> multimap = createPopulate();
136     ASSERT.that(multimap.keySet()).has().exactly("foo", "google", "tree").inOrder();
137   }
138 
testOrderedAsMapEntries()139   public void testOrderedAsMapEntries() {
140     TreeMultimap<String, Integer> multimap = createPopulate();
141     Iterator<Map.Entry<String, Collection<Integer>>> iterator =
142         multimap.asMap().entrySet().iterator();
143     Map.Entry<String, Collection<Integer>> entry = iterator.next();
144     assertEquals("foo", entry.getKey());
145     ASSERT.that(entry.getValue()).has().exactly(1, 3, 7);
146     entry = iterator.next();
147     assertEquals("google", entry.getKey());
148     ASSERT.that(entry.getValue()).has().exactly(2, 6);
149     entry = iterator.next();
150     assertEquals("tree", entry.getKey());
151     ASSERT.that(entry.getValue()).has().exactly(0, 4);
152   }
153 
testOrderedEntries()154   public void testOrderedEntries() {
155     TreeMultimap<String, Integer> multimap = createPopulate();
156     ASSERT.that(multimap.entries()).has().exactly(
157         Maps.immutableEntry("foo", 1),
158         Maps.immutableEntry("foo", 3),
159         Maps.immutableEntry("foo", 7),
160         Maps.immutableEntry("google", 2),
161         Maps.immutableEntry("google", 6),
162         Maps.immutableEntry("tree", 0),
163         Maps.immutableEntry("tree", 4)).inOrder();
164   }
165 
testOrderedValues()166   public void testOrderedValues() {
167     TreeMultimap<String, Integer> multimap = createPopulate();
168     ASSERT.that(multimap.values()).has().exactly(
169         1, 3, 7, 2, 6, 0, 4).inOrder();
170   }
171 
testMultimapConstructor()172   public void testMultimapConstructor() {
173     SetMultimap<String, Integer> multimap = create();
174     multimap.putAll("bar", Arrays.asList(3, 1, 2));
175     multimap.putAll("foo", Arrays.asList(2, 3, 1, -1, 4));
176     TreeMultimap<String, Integer> copy = TreeMultimap.create(multimap);
177     assertEquals(multimap, copy);
178   }
179 
180   private static final Comparator<Double> KEY_COMPARATOR =
181       Ordering.natural();
182 
183   private static final Comparator<Double> VALUE_COMPARATOR =
184       Ordering.natural().reverse().nullsFirst();
185 
186   /**
187    * Test that creating one TreeMultimap from another does not copy the
188    * comparators from the source TreeMultimap.
189    */
testCreateFromTreeMultimap()190   public void testCreateFromTreeMultimap() {
191     Multimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR);
192     tree.put(1.0, 2.0);
193     tree.put(2.0, 3.0);
194     tree.put(3.0, 4.0);
195     tree.put(4.0, 5.0);
196 
197     TreeMultimap<Double, Double> copyFromTree = TreeMultimap.create(tree);
198     assertEquals(tree, copyFromTree);
199     assertSame(Ordering.natural(), copyFromTree.keyComparator());
200     assertSame(Ordering.natural(), copyFromTree.valueComparator());
201     assertSame(Ordering.natural(), copyFromTree.get(1.0).comparator());
202   }
203 
204   /**
205    * Test that creating one TreeMultimap from a non-TreeMultimap
206    * results in natural ordering.
207    */
testCreateFromHashMultimap()208   public void testCreateFromHashMultimap() {
209     Multimap<Double, Double> hash = HashMultimap.create();
210     hash.put(1.0, 2.0);
211     hash.put(2.0, 3.0);
212     hash.put(3.0, 4.0);
213     hash.put(4.0, 5.0);
214 
215     TreeMultimap<Double, Double> copyFromHash = TreeMultimap.create(hash);
216     assertEquals(hash, copyFromHash);
217     assertEquals(Ordering.natural(), copyFromHash.keyComparator());
218     assertEquals(Ordering.natural(), copyFromHash.valueComparator());
219   }
220 
221   /**
222    * Test that creating one TreeMultimap from a SortedSetMultimap uses natural
223    * ordering.
224    */
testCreateFromSortedSetMultimap()225   public void testCreateFromSortedSetMultimap() {
226     SortedSetMultimap<Double, Double> tree = TreeMultimap.create(KEY_COMPARATOR, VALUE_COMPARATOR);
227     tree.put(1.0, 2.0);
228     tree.put(2.0, 3.0);
229     tree.put(3.0, 4.0);
230     tree.put(4.0, 5.0);
231 
232     SortedSetMultimap<Double, Double> sorted = Multimaps.unmodifiableSortedSetMultimap(tree);
233     TreeMultimap<Double, Double> copyFromSorted = TreeMultimap.create(sorted);
234     assertEquals(tree, copyFromSorted);
235     assertSame(Ordering.natural(), copyFromSorted.keyComparator());
236     assertSame(Ordering.natural(), copyFromSorted.valueComparator());
237     assertSame(Ordering.natural(), copyFromSorted.get(1.0).comparator());
238   }
239 
testComparators()240   public void testComparators() {
241     TreeMultimap<String, Integer> multimap = TreeMultimap.create();
242     assertEquals(Ordering.natural(), multimap.keyComparator());
243     assertEquals(Ordering.natural(), multimap.valueComparator());
244   }
245 
246   @GwtIncompatible("SerializableTester")
testExplicitComparatorSerialization()247   public void testExplicitComparatorSerialization() {
248     TreeMultimap<String, Integer> multimap = createPopulate();
249     TreeMultimap<String, Integer> copy
250         = SerializableTester.reserializeAndAssert(multimap);
251     ASSERT.that(copy.values()).has().exactly(1, 3, 7, 2, 6, 0, 4).inOrder();
252     ASSERT.that(copy.keySet()).has().exactly("foo", "google", "tree").inOrder();
253     assertEquals(multimap.keyComparator(), copy.keyComparator());
254     assertEquals(multimap.valueComparator(), copy.valueComparator());
255   }
256 
257   @GwtIncompatible("SerializableTester")
testTreeMultimapDerived()258   public void testTreeMultimapDerived() {
259     TreeMultimap<DerivedComparable, DerivedComparable> multimap = TreeMultimap.create();
260     assertEquals(ImmutableMultimap.of(), multimap);
261     multimap.put(new DerivedComparable("foo"), new DerivedComparable("f"));
262     multimap.put(new DerivedComparable("foo"), new DerivedComparable("o"));
263     multimap.put(new DerivedComparable("foo"), new DerivedComparable("o"));
264     multimap.put(new DerivedComparable("bar"), new DerivedComparable("b"));
265     multimap.put(new DerivedComparable("bar"), new DerivedComparable("a"));
266     multimap.put(new DerivedComparable("bar"), new DerivedComparable("r"));
267     ASSERT.that(multimap.keySet()).has().exactly(
268         new DerivedComparable("bar"), new DerivedComparable("foo")).inOrder();
269     ASSERT.that(multimap.values()).has().exactly(
270         new DerivedComparable("a"), new DerivedComparable("b"), new DerivedComparable("r"),
271         new DerivedComparable("f"), new DerivedComparable("o")).inOrder();
272     assertEquals(Ordering.natural(), multimap.keyComparator());
273     assertEquals(Ordering.natural(), multimap.valueComparator());
274     SerializableTester.reserializeAndAssert(multimap);
275   }
276 
277   @GwtIncompatible("SerializableTester")
testTreeMultimapNonGeneric()278   public void testTreeMultimapNonGeneric() {
279     TreeMultimap<LegacyComparable, LegacyComparable> multimap
280         = TreeMultimap.create();
281     assertEquals(ImmutableMultimap.of(), multimap);
282     multimap.put(new LegacyComparable("foo"), new LegacyComparable("f"));
283     multimap.put(new LegacyComparable("foo"), new LegacyComparable("o"));
284     multimap.put(new LegacyComparable("foo"), new LegacyComparable("o"));
285     multimap.put(new LegacyComparable("bar"), new LegacyComparable("b"));
286     multimap.put(new LegacyComparable("bar"), new LegacyComparable("a"));
287     multimap.put(new LegacyComparable("bar"), new LegacyComparable("r"));
288     ASSERT.that(multimap.keySet()).has().exactly(
289         new LegacyComparable("bar"), new LegacyComparable("foo")).inOrder();
290     ASSERT.that(multimap.values()).has().exactly(
291         new LegacyComparable("a"),
292         new LegacyComparable("b"),
293         new LegacyComparable("r"),
294         new LegacyComparable("f"),
295         new LegacyComparable("o")).inOrder();
296     assertEquals(Ordering.natural(), multimap.keyComparator());
297     assertEquals(Ordering.natural(), multimap.valueComparator());
298     SerializableTester.reserializeAndAssert(multimap);
299   }
300 
testTreeMultimapAsMapSorted()301   public void testTreeMultimapAsMapSorted() {
302     TreeMultimap<String, Integer> multimap = createPopulate();
303     SortedMap<String, Collection<Integer>> asMap = multimap.asMap();
304     assertEquals(Ordering.natural(), asMap.comparator());
305     assertEquals("foo", asMap.firstKey());
306     assertEquals("tree", asMap.lastKey());
307     Set<Integer> fooValues = ImmutableSet.of(1, 3, 7);
308     Set<Integer> googleValues = ImmutableSet.of(2, 6);
309     Set<Integer> treeValues = ImmutableSet.of(4, 0);
310     assertEquals(ImmutableMap.of("google", googleValues, "tree", treeValues),
311         asMap.tailMap("g"));
312     assertEquals(ImmutableMap.of("google", googleValues, "foo", fooValues),
313         asMap.headMap("h"));
314     assertEquals(ImmutableMap.of("google", googleValues),
315         asMap.subMap("g", "h"));
316   }
317 
testTailSetClear()318   public void testTailSetClear() {
319     TreeMultimap<String, Integer> multimap = TreeMultimap.create();
320     multimap.put("a", 1);
321     multimap.put("a", 11);
322     multimap.put("b", 2);
323     multimap.put("c", 3);
324     multimap.put("d", 4);
325     multimap.put("e", 5);
326     multimap.put("e", 55);
327 
328     multimap.keySet().tailSet("d").clear();
329     assertEquals(ImmutableSet.of("a", "b", "c"), multimap.keySet());
330     assertEquals(4, multimap.size());
331     assertEquals(4, multimap.values().size());
332     assertEquals(4, multimap.keys().size());
333   }
334 
335   @GwtIncompatible("reflection")
testKeySetBridgeMethods()336   public void testKeySetBridgeMethods() {
337     for (Method m : TreeMultimap.class.getMethods()) {
338       if (m.getName().equals("keySet") && m.getReturnType().equals(SortedSet.class)) {
339         return;
340       }
341     }
342     fail("No bridge method found");
343   }
344 
345   @GwtIncompatible("reflection")
testAsMapBridgeMethods()346   public void testAsMapBridgeMethods() {
347     for (Method m : TreeMultimap.class.getMethods()) {
348       if (m.getName().equals("asMap") && m.getReturnType().equals(SortedMap.class)) {
349         return;
350       }
351     }
352   }
353 
354   @GwtIncompatible("reflection")
testGetBridgeMethods()355   public void testGetBridgeMethods() {
356     for (Method m : TreeMultimap.class.getMethods()) {
357       if (m.getName().equals("get") && m.getReturnType().equals(SortedSet.class)) {
358         return;
359       }
360     }
361     fail("No bridge method found");
362   }
363 }
364