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.collect.Lists.newArrayList;
21import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE;
22import static org.junit.contrib.truth.Truth.ASSERT;
23
24import java.util.Arrays;
25import java.util.Collections;
26import java.util.Comparator;
27import java.util.Iterator;
28import java.util.List;
29import java.util.Set;
30import java.util.SortedSet;
31
32import com.google.common.annotations.GwtCompatible;
33import com.google.common.annotations.GwtIncompatible;
34import com.google.common.collect.testing.IteratorTester;
35
36/**
37 * Unit test for {@link TreeMultiset}.
38 *
39 * @author Neal Kanodia
40 */
41@GwtCompatible(emulated = true)
42public class TreeMultisetTest extends AbstractMultisetTest {
43  @SuppressWarnings("unchecked")
44  @Override protected <E> Multiset<E> create() {
45    return (Multiset) TreeMultiset.create();
46  }
47
48  public void testCreate() {
49    TreeMultiset<String> multiset = TreeMultiset.create();
50    multiset.add("foo", 2);
51    multiset.add("bar");
52    assertEquals(3, multiset.size());
53    assertEquals(2, multiset.count("foo"));
54    assertEquals(Ordering.natural(), multiset.comparator());
55    assertEquals("[bar, foo x 2]", multiset.toString());
56  }
57
58  public void testCreateWithComparator() {
59    Multiset<String> multiset = TreeMultiset.create(Collections.reverseOrder());
60    multiset.add("foo", 2);
61    multiset.add("bar");
62    assertEquals(3, multiset.size());
63    assertEquals(2, multiset.count("foo"));
64    assertEquals("[foo x 2, bar]", multiset.toString());
65  }
66
67  public void testCreateFromIterable() {
68    Multiset<String> multiset
69        = TreeMultiset.create(Arrays.asList("foo", "bar", "foo"));
70    assertEquals(3, multiset.size());
71    assertEquals(2, multiset.count("foo"));
72    assertEquals("[bar, foo x 2]", multiset.toString());
73  }
74
75  public void testToString() {
76    ms.add("a", 3);
77    ms.add("c", 1);
78    ms.add("b", 2);
79
80    assertEquals("[a x 3, b x 2, c]", ms.toString());
81  }
82
83  @GwtIncompatible("unreasonable slow")
84  public void testIteratorBashing() {
85    IteratorTester<String> tester =
86        new IteratorTester<String>(createSample().size() + 2, MODIFIABLE,
87            newArrayList(createSample()),
88            IteratorTester.KnownOrder.KNOWN_ORDER) {
89          private Multiset<String> targetMultiset;
90
91          @Override protected Iterator<String> newTargetIterator() {
92            targetMultiset = createSample();
93            return targetMultiset.iterator();
94          }
95
96          @Override protected void verify(List<String> elements) {
97            assertEquals(elements, Lists.newArrayList(targetMultiset));
98          }
99        };
100
101    /* This next line added as a stopgap until JDK6 bug is fixed. */
102    tester.ignoreSunJavaBug6529795();
103
104    tester.test();
105  }
106
107  @GwtIncompatible("slow (~30s)")
108  public void testElementSetIteratorBashing() {
109    IteratorTester<String> tester = new IteratorTester<String>(5, MODIFIABLE,
110        newArrayList("a", "b", "c"), IteratorTester.KnownOrder.KNOWN_ORDER) {
111      private Set<String> targetSet;
112      @Override protected Iterator<String> newTargetIterator() {
113        Multiset<String> multiset = create();
114        multiset.add("a", 3);
115        multiset.add("c", 1);
116        multiset.add("b", 2);
117        targetSet = multiset.elementSet();
118        return targetSet.iterator();
119      }
120      @Override protected void verify(List<String> elements) {
121        assertEquals(elements, Lists.newArrayList(targetSet));
122      }
123    };
124
125    /* This next line added as a stopgap until JDK6 bug is fixed. */
126    tester.ignoreSunJavaBug6529795();
127
128    tester.test();
129  }
130
131  public void testElementSetSortedSetMethods() {
132    TreeMultiset<String> ms = TreeMultiset.create();
133    ms.add("c", 1);
134    ms.add("a", 3);
135    ms.add("b", 2);
136    SortedSet<String> elementSet = ms.elementSet();
137
138    assertEquals("a", elementSet.first());
139    assertEquals("c", elementSet.last());
140    assertEquals(Ordering.natural(), elementSet.comparator());
141
142    ASSERT.that(elementSet.headSet("b")).hasContentsInOrder("a");
143    ASSERT.that(elementSet.tailSet("b")).hasContentsInOrder("b", "c");
144    ASSERT.that(elementSet.subSet("a", "c")).hasContentsInOrder("a", "b");
145  }
146
147  public void testElementSetSubsetRemove() {
148    TreeMultiset<String> ms = TreeMultiset.create();
149    ms.add("a", 1);
150    ms.add("b", 3);
151    ms.add("c", 2);
152    ms.add("d", 1);
153    ms.add("e", 3);
154    ms.add("f", 2);
155
156    SortedSet<String> elementSet = ms.elementSet();
157    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "c", "d", "e", "f");
158    SortedSet<String> subset = elementSet.subSet("b", "f");
159    ASSERT.that(subset).hasContentsInOrder("b", "c", "d", "e");
160
161    assertTrue(subset.remove("c"));
162    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "d", "e", "f");
163    ASSERT.that(subset).hasContentsInOrder("b", "d", "e");
164    assertEquals(10, ms.size());
165
166    assertFalse(subset.remove("a"));
167    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "d", "e", "f");
168    ASSERT.that(subset).hasContentsInOrder("b", "d", "e");
169    assertEquals(10, ms.size());
170  }
171
172  public void testElementSetSubsetRemoveAll() {
173    TreeMultiset<String> ms = TreeMultiset.create();
174    ms.add("a", 1);
175    ms.add("b", 3);
176    ms.add("c", 2);
177    ms.add("d", 1);
178    ms.add("e", 3);
179    ms.add("f", 2);
180
181    SortedSet<String> elementSet = ms.elementSet();
182    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "c", "d", "e", "f");
183    SortedSet<String> subset = elementSet.subSet("b", "f");
184    ASSERT.that(subset).hasContentsInOrder("b", "c", "d", "e");
185
186    assertTrue(subset.removeAll(Arrays.asList("a", "c")));
187    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "d", "e", "f");
188    ASSERT.that(subset).hasContentsInOrder("b", "d", "e");
189    assertEquals(10, ms.size());
190  }
191
192  public void testElementSetSubsetRetainAll() {
193    TreeMultiset<String> ms = TreeMultiset.create();
194    ms.add("a", 1);
195    ms.add("b", 3);
196    ms.add("c", 2);
197    ms.add("d", 1);
198    ms.add("e", 3);
199    ms.add("f", 2);
200
201    SortedSet<String> elementSet = ms.elementSet();
202    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "c", "d", "e", "f");
203    SortedSet<String> subset = elementSet.subSet("b", "f");
204    ASSERT.that(subset).hasContentsInOrder("b", "c", "d", "e");
205
206    assertTrue(subset.retainAll(Arrays.asList("a", "c")));
207    ASSERT.that(elementSet).hasContentsInOrder("a", "c", "f");
208    ASSERT.that(subset).hasContentsInOrder("c");
209    assertEquals(5, ms.size());
210  }
211
212  public void testElementSetSubsetClear() {
213    TreeMultiset<String> ms = TreeMultiset.create();
214    ms.add("a", 1);
215    ms.add("b", 3);
216    ms.add("c", 2);
217    ms.add("d", 1);
218    ms.add("e", 3);
219    ms.add("f", 2);
220
221    SortedSet<String> elementSet = ms.elementSet();
222    ASSERT.that(elementSet).hasContentsInOrder("a", "b", "c", "d", "e", "f");
223    SortedSet<String> subset = elementSet.subSet("b", "f");
224    ASSERT.that(subset).hasContentsInOrder("b", "c", "d", "e");
225
226    subset.clear();
227    ASSERT.that(elementSet).hasContentsInOrder("a", "f");
228    ASSERT.that(subset).hasContentsInOrder();
229    assertEquals(3, ms.size());
230  }
231
232  public void testCustomComparator() throws Exception {
233    Comparator<String> comparator = new Comparator<String>() {
234      @Override
235      public int compare(String o1, String o2) {
236        return o2.compareTo(o1);
237      }
238    };
239    TreeMultiset<String> ms = TreeMultiset.create(comparator);
240
241    ms.add("b");
242    ms.add("c");
243    ms.add("a");
244    ms.add("b");
245    ms.add("d");
246
247    ASSERT.that(ms).hasContentsInOrder("d", "c", "b", "b", "a");
248
249    SortedSet<String> elementSet = ms.elementSet();
250    assertEquals("d", elementSet.first());
251    assertEquals("a", elementSet.last());
252    assertEquals(comparator, elementSet.comparator());
253  }
254
255  public void testNullAcceptingComparator() throws Exception {
256    Comparator<String> comparator = Ordering.<String>natural().nullsFirst();
257    TreeMultiset<String> ms = TreeMultiset.create(comparator);
258
259    ms.add("b");
260    ms.add(null);
261    ms.add("a");
262    ms.add("b");
263    ms.add(null, 2);
264
265    ASSERT.that(ms).hasContentsInOrder(null, null, null, "a", "b", "b");
266    assertEquals(3, ms.count(null));
267
268    SortedSet<String> elementSet = ms.elementSet();
269    assertEquals(null, elementSet.first());
270    assertEquals("b", elementSet.last());
271    assertEquals(comparator, elementSet.comparator());
272  }
273
274  private static final Comparator<String> DEGENERATE_COMPARATOR =
275      new Comparator<String>() {
276        @Override
277        public int compare(String o1, String o2) {
278          return o1.length() - o2.length();
279        }
280      };
281
282  /**
283   * Test a TreeMultiset with a comparator that can return 0 when comparing
284   * unequal values.
285   */
286  public void testDegenerateComparator() throws Exception {
287    TreeMultiset<String> ms = TreeMultiset.create(DEGENERATE_COMPARATOR);
288
289    ms.add("foo");
290    ms.add("a");
291    ms.add("bar");
292    ms.add("b");
293    ms.add("c");
294
295    assertEquals(2, ms.count("bar"));
296    assertEquals(3, ms.count("b"));
297
298    Multiset<String> ms2 = TreeMultiset.create(DEGENERATE_COMPARATOR);
299
300    ms2.add("cat", 2);
301    ms2.add("x", 3);
302
303    assertEquals(ms, ms2);
304    assertEquals(ms2, ms);
305
306    SortedSet<String> elementSet = ms.elementSet();
307    assertEquals("a", elementSet.first());
308    assertEquals("foo", elementSet.last());
309    assertEquals(DEGENERATE_COMPARATOR, elementSet.comparator());
310  }
311
312  public void testSubMultisetSize() {
313    TreeMultiset<String> ms = TreeMultiset.create();
314    ms.add("a", Integer.MAX_VALUE);
315    ms.add("b", Integer.MAX_VALUE);
316    ms.add("c", 3);
317
318    assertEquals(Integer.MAX_VALUE, ms.count("a"));
319    assertEquals(Integer.MAX_VALUE, ms.count("b"));
320    assertEquals(3, ms.count("c"));
321
322    assertEquals(Integer.MAX_VALUE, ms.headMultiset("c", CLOSED).size());
323    assertEquals(Integer.MAX_VALUE, ms.headMultiset("b", CLOSED).size());
324    assertEquals(Integer.MAX_VALUE, ms.headMultiset("a", CLOSED).size());
325
326    assertEquals(3, ms.tailMultiset("c", CLOSED).size());
327    assertEquals(Integer.MAX_VALUE, ms.tailMultiset("b", CLOSED).size());
328    assertEquals(Integer.MAX_VALUE, ms.tailMultiset("a", CLOSED).size());
329  }
330
331  @Override public void testToStringNull() {
332    c = ms = TreeMultiset.create(Ordering.natural().nullsFirst());
333    super.testToStringNull();
334  }
335}
336
337