TreeMultimapNaturalTest.java revision 1d580d0f6ee4f21eb309ba7b509d2c6d671c4044 
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.collect.Lists.newArrayList;
20import static com.google.common.collect.Sets.newHashSet;
21import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE;
22import static java.util.Arrays.asList;
23import static org.junit.contrib.truth.Truth.ASSERT;
24
25import com.google.common.annotations.GwtCompatible;
26import com.google.common.annotations.GwtIncompatible;
27import com.google.common.collect.testing.DerivedComparable;
28import com.google.common.collect.testing.IteratorTester;
29import com.google.common.testing.SerializableTester;
30
31import java.util.Collection;
32import java.util.Collections;
33import java.util.Comparator;
34import java.util.Iterator;
35import java.util.List;
36import java.util.Map;
37import java.util.Map.Entry;
38import java.util.NoSuchElementException;
39import java.util.Set;
40import java.util.SortedMap;
41import java.util.SortedSet;
42
43/**
44 * Unit tests for {@code TreeMultimap} with natural ordering.
45 *
46 * @author Jared Levy
47 */
48@GwtCompatible(emulated = true)
49public 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