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
17package com.google.common.collect;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.truth.Truth.assertThat;
21
22import com.google.common.annotations.GwtCompatible;
23import com.google.common.annotations.GwtIncompatible;
24import com.google.common.collect.testing.DerivedComparable;
25import com.google.common.collect.testing.Helpers;
26import com.google.common.collect.testing.NavigableMapTestSuiteBuilder;
27import com.google.common.collect.testing.NavigableSetTestSuiteBuilder;
28import com.google.common.collect.testing.SampleElements;
29import com.google.common.collect.testing.TestSortedMapGenerator;
30import com.google.common.collect.testing.TestStringSetGenerator;
31import com.google.common.collect.testing.TestStringSortedSetGenerator;
32import com.google.common.collect.testing.features.CollectionFeature;
33import com.google.common.collect.testing.features.CollectionSize;
34import com.google.common.collect.testing.features.MapFeature;
35import com.google.common.collect.testing.google.SortedSetMultimapTestSuiteBuilder;
36import com.google.common.collect.testing.google.TestStringSetMultimapGenerator;
37import com.google.common.testing.SerializableTester;
38
39import junit.framework.Test;
40import junit.framework.TestCase;
41import junit.framework.TestSuite;
42
43import java.lang.reflect.Method;
44import java.util.Arrays;
45import java.util.Collection;
46import java.util.Comparator;
47import java.util.Iterator;
48import java.util.List;
49import java.util.Map;
50import java.util.Map.Entry;
51import java.util.NavigableMap;
52import java.util.NavigableSet;
53import java.util.Set;
54import java.util.SortedMap;
55import java.util.SortedSet;
56
57/**
58 * Unit tests for {@code TreeMultimap} with natural ordering.
59 *
60 * @author Jared Levy
61 */
62@GwtCompatible(emulated = true)
63public 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