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.BoundType.CLOSED;
20import static com.google.common.truth.Truth.assertThat;
21import static java.util.Collections.sort;
22
23import com.google.common.annotations.GwtCompatible;
24import com.google.common.annotations.GwtIncompatible;
25import com.google.common.collect.testing.Helpers.NullsBeforeB;
26import com.google.common.collect.testing.NavigableSetTestSuiteBuilder;
27import com.google.common.collect.testing.TestStringSetGenerator;
28import com.google.common.collect.testing.features.CollectionFeature;
29import com.google.common.collect.testing.features.CollectionSize;
30import com.google.common.collect.testing.google.MultisetFeature;
31import com.google.common.collect.testing.google.SortedMultisetTestSuiteBuilder;
32import com.google.common.collect.testing.google.TestStringMultisetGenerator;
33
34import junit.framework.Test;
35import junit.framework.TestCase;
36import junit.framework.TestSuite;
37
38import java.lang.reflect.Method;
39import java.util.Arrays;
40import java.util.Collections;
41import java.util.Comparator;
42import java.util.List;
43import java.util.Set;
44import java.util.SortedSet;
45
46/**
47 * Unit test for {@link TreeMultiset}.
48 *
49 * @author Neal Kanodia
50 */
51@GwtCompatible(emulated = true)
52public class TreeMultisetTest extends TestCase {
53
54  @GwtIncompatible("suite")
55  public static Test suite() {
56    TestSuite suite = new TestSuite();
57    suite.addTest(SortedMultisetTestSuiteBuilder
58        .using(new TestStringMultisetGenerator() {
59          @Override
60          protected Multiset<String> create(String[] elements) {
61            return TreeMultiset.create(Arrays.asList(elements));
62          }
63
64          @Override
65          public List<String> order(List<String> insertionOrder) {
66            return Ordering.natural().sortedCopy(insertionOrder);
67          }
68        })
69        .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER,
70            CollectionFeature.GENERAL_PURPOSE,
71            CollectionFeature.SERIALIZABLE,
72            CollectionFeature.ALLOWS_NULL_QUERIES,
73            MultisetFeature.ENTRIES_ARE_VIEWS)
74        .named("TreeMultiset, Ordering.natural")
75        .createTestSuite());
76    suite.addTest(SortedMultisetTestSuiteBuilder
77        .using(new TestStringMultisetGenerator() {
78          @Override
79          protected Multiset<String> create(String[] elements) {
80            Multiset<String> result = TreeMultiset.create(NullsBeforeB.INSTANCE);
81            Collections.addAll(result, elements);
82            return result;
83          }
84
85          @Override
86          public List<String> order(List<String> insertionOrder) {
87            sort(insertionOrder, NullsBeforeB.INSTANCE);
88            return insertionOrder;
89          }
90        })
91        .withFeatures(CollectionSize.ANY, CollectionFeature.KNOWN_ORDER,
92            CollectionFeature.GENERAL_PURPOSE,
93            CollectionFeature.SERIALIZABLE,
94            CollectionFeature.ALLOWS_NULL_VALUES,
95            MultisetFeature.ENTRIES_ARE_VIEWS)
96        .named("TreeMultiset, NullsBeforeB")
97        .createTestSuite());
98    suite.addTest(NavigableSetTestSuiteBuilder.using(new TestStringSetGenerator() {
99        @Override
100        protected Set<String> create(String[] elements) {
101          return TreeMultiset.create(Arrays.asList(elements)).elementSet();
102        }
103
104        @Override
105        public List<String> order(List<String> insertionOrder) {
106          return Lists.newArrayList(Sets.newTreeSet(insertionOrder));
107        }
108      })
109      .named("TreeMultiset[Ordering.natural].elementSet")
110      .withFeatures(
111          CollectionSize.ANY,
112          CollectionFeature.REMOVE_OPERATIONS,
113          CollectionFeature.ALLOWS_NULL_QUERIES)
114      .createTestSuite());
115    suite.addTestSuite(TreeMultisetTest.class);
116    return suite;
117  }
118
119  public void testCreate() {
120    TreeMultiset<String> multiset = TreeMultiset.create();
121    multiset.add("foo", 2);
122    multiset.add("bar");
123    assertEquals(3, multiset.size());
124    assertEquals(2, multiset.count("foo"));
125    assertEquals(Ordering.natural(), multiset.comparator());
126    assertEquals("[bar, foo x 2]", multiset.toString());
127  }
128
129  public void testCreateWithComparator() {
130    Multiset<String> multiset = TreeMultiset.create(Collections.reverseOrder());
131    multiset.add("foo", 2);
132    multiset.add("bar");
133    assertEquals(3, multiset.size());
134    assertEquals(2, multiset.count("foo"));
135    assertEquals("[foo x 2, bar]", multiset.toString());
136  }
137
138  public void testCreateFromIterable() {
139    Multiset<String> multiset
140        = TreeMultiset.create(Arrays.asList("foo", "bar", "foo"));
141    assertEquals(3, multiset.size());
142    assertEquals(2, multiset.count("foo"));
143    assertEquals("[bar, foo x 2]", multiset.toString());
144  }
145
146  public void testToString() {
147    Multiset<String> ms = TreeMultiset.create();
148    ms.add("a", 3);
149    ms.add("c", 1);
150    ms.add("b", 2);
151
152    assertEquals("[a x 3, b x 2, c]", ms.toString());
153  }
154
155  public void testElementSetSortedSetMethods() {
156    TreeMultiset<String> ms = TreeMultiset.create();
157    ms.add("c", 1);
158    ms.add("a", 3);
159    ms.add("b", 2);
160    SortedSet<String> elementSet = ms.elementSet();
161
162    assertEquals("a", elementSet.first());
163    assertEquals("c", elementSet.last());
164    assertEquals(Ordering.natural(), elementSet.comparator());
165
166    assertThat(elementSet.headSet("b")).has().exactly("a").inOrder();
167    assertThat(elementSet.tailSet("b")).has().exactly("b", "c").inOrder();
168    assertThat(elementSet.subSet("a", "c")).has().exactly("a", "b").inOrder();
169  }
170
171  public void testElementSetSubsetRemove() {
172    TreeMultiset<String> ms = TreeMultiset.create();
173    ms.add("a", 1);
174    ms.add("b", 3);
175    ms.add("c", 2);
176    ms.add("d", 1);
177    ms.add("e", 3);
178    ms.add("f", 2);
179
180    SortedSet<String> elementSet = ms.elementSet();
181    assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
182    SortedSet<String> subset = elementSet.subSet("b", "f");
183    assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
184
185    assertTrue(subset.remove("c"));
186    assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder();
187    assertThat(subset).has().exactly("b", "d", "e").inOrder();
188    assertEquals(10, ms.size());
189
190    assertFalse(subset.remove("a"));
191    assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder();
192    assertThat(subset).has().exactly("b", "d", "e").inOrder();
193    assertEquals(10, ms.size());
194  }
195
196  public void testElementSetSubsetRemoveAll() {
197    TreeMultiset<String> ms = TreeMultiset.create();
198    ms.add("a", 1);
199    ms.add("b", 3);
200    ms.add("c", 2);
201    ms.add("d", 1);
202    ms.add("e", 3);
203    ms.add("f", 2);
204
205    SortedSet<String> elementSet = ms.elementSet();
206    assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
207    SortedSet<String> subset = elementSet.subSet("b", "f");
208    assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
209
210    assertTrue(subset.removeAll(Arrays.asList("a", "c")));
211    assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder();
212    assertThat(subset).has().exactly("b", "d", "e").inOrder();
213    assertEquals(10, ms.size());
214  }
215
216  public void testElementSetSubsetRetainAll() {
217    TreeMultiset<String> ms = TreeMultiset.create();
218    ms.add("a", 1);
219    ms.add("b", 3);
220    ms.add("c", 2);
221    ms.add("d", 1);
222    ms.add("e", 3);
223    ms.add("f", 2);
224
225    SortedSet<String> elementSet = ms.elementSet();
226    assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
227    SortedSet<String> subset = elementSet.subSet("b", "f");
228    assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
229
230    assertTrue(subset.retainAll(Arrays.asList("a", "c")));
231    assertThat(elementSet).has().exactly("a", "c", "f").inOrder();
232    assertThat(subset).has().exactly("c").inOrder();
233    assertEquals(5, ms.size());
234  }
235
236  public void testElementSetSubsetClear() {
237    TreeMultiset<String> ms = TreeMultiset.create();
238    ms.add("a", 1);
239    ms.add("b", 3);
240    ms.add("c", 2);
241    ms.add("d", 1);
242    ms.add("e", 3);
243    ms.add("f", 2);
244
245    SortedSet<String> elementSet = ms.elementSet();
246    assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder();
247    SortedSet<String> subset = elementSet.subSet("b", "f");
248    assertThat(subset).has().exactly("b", "c", "d", "e").inOrder();
249
250    subset.clear();
251    assertThat(elementSet).has().exactly("a", "f").inOrder();
252    assertThat(subset).isEmpty();
253    assertEquals(3, ms.size());
254  }
255
256  public void testCustomComparator() throws Exception {
257    Comparator<String> comparator = new Comparator<String>() {
258      @Override
259      public int compare(String o1, String o2) {
260        return o2.compareTo(o1);
261      }
262    };
263    TreeMultiset<String> ms = TreeMultiset.create(comparator);
264
265    ms.add("b");
266    ms.add("c");
267    ms.add("a");
268    ms.add("b");
269    ms.add("d");
270
271    assertThat(ms).has().exactly("d", "c", "b", "b", "a").inOrder();
272
273    SortedSet<String> elementSet = ms.elementSet();
274    assertEquals("d", elementSet.first());
275    assertEquals("a", elementSet.last());
276    assertEquals(comparator, elementSet.comparator());
277  }
278
279  public void testNullAcceptingComparator() throws Exception {
280    Comparator<String> comparator = Ordering.<String>natural().nullsFirst();
281    TreeMultiset<String> ms = TreeMultiset.create(comparator);
282
283    ms.add("b");
284    ms.add(null);
285    ms.add("a");
286    ms.add("b");
287    ms.add(null, 2);
288
289    assertThat(ms).has().exactly(null, null, null, "a", "b", "b").inOrder();
290    assertEquals(3, ms.count(null));
291
292    SortedSet<String> elementSet = ms.elementSet();
293    assertEquals(null, elementSet.first());
294    assertEquals("b", elementSet.last());
295    assertEquals(comparator, elementSet.comparator());
296  }
297
298  private static final Comparator<String> DEGENERATE_COMPARATOR =
299      new Comparator<String>() {
300        @Override
301        public int compare(String o1, String o2) {
302          return o1.length() - o2.length();
303        }
304      };
305
306  /**
307   * Test a TreeMultiset with a comparator that can return 0 when comparing
308   * unequal values.
309   */
310  public void testDegenerateComparator() throws Exception {
311    TreeMultiset<String> ms = TreeMultiset.create(DEGENERATE_COMPARATOR);
312
313    ms.add("foo");
314    ms.add("a");
315    ms.add("bar");
316    ms.add("b");
317    ms.add("c");
318
319    assertEquals(2, ms.count("bar"));
320    assertEquals(3, ms.count("b"));
321
322    Multiset<String> ms2 = TreeMultiset.create(DEGENERATE_COMPARATOR);
323
324    ms2.add("cat", 2);
325    ms2.add("x", 3);
326
327    assertEquals(ms, ms2);
328    assertEquals(ms2, ms);
329
330    SortedSet<String> elementSet = ms.elementSet();
331    assertEquals("a", elementSet.first());
332    assertEquals("foo", elementSet.last());
333    assertEquals(DEGENERATE_COMPARATOR, elementSet.comparator());
334  }
335
336  public void testSubMultisetSize() {
337    TreeMultiset<String> ms = TreeMultiset.create();
338    ms.add("a", Integer.MAX_VALUE);
339    ms.add("b", Integer.MAX_VALUE);
340    ms.add("c", 3);
341
342    assertEquals(Integer.MAX_VALUE, ms.count("a"));
343    assertEquals(Integer.MAX_VALUE, ms.count("b"));
344    assertEquals(3, ms.count("c"));
345
346    assertEquals(Integer.MAX_VALUE, ms.headMultiset("c", CLOSED).size());
347    assertEquals(Integer.MAX_VALUE, ms.headMultiset("b", CLOSED).size());
348    assertEquals(Integer.MAX_VALUE, ms.headMultiset("a", CLOSED).size());
349
350    assertEquals(3, ms.tailMultiset("c", CLOSED).size());
351    assertEquals(Integer.MAX_VALUE, ms.tailMultiset("b", CLOSED).size());
352    assertEquals(Integer.MAX_VALUE, ms.tailMultiset("a", CLOSED).size());
353  }
354
355  @GwtIncompatible("reflection")
356  public void testElementSetBridgeMethods() {
357    for (Method m : TreeMultiset.class.getMethods()) {
358      if (m.getName().equals("elementSet") && m.getReturnType().equals(SortedSet.class)) {
359        return;
360      }
361    }
362    fail("No bridge method found");
363  }
364}
365