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 com.google.common.collect.BoundType.CLOSED; 20 import static com.google.common.collect.Lists.newArrayList; 21 import static com.google.common.collect.testing.IteratorFeature.MODIFIABLE; 22 import static org.junit.contrib.truth.Truth.ASSERT; 23 24 import java.util.Arrays; 25 import java.util.Collections; 26 import java.util.Comparator; 27 import java.util.Iterator; 28 import java.util.List; 29 import java.util.Set; 30 import java.util.SortedSet; 31 32 import com.google.common.annotations.GwtCompatible; 33 import com.google.common.annotations.GwtIncompatible; 34 import com.google.common.collect.testing.IteratorTester; 35 36 /** 37 * Unit test for {@link TreeMultiset}. 38 * 39 * @author Neal Kanodia 40 */ 41 @GwtCompatible(emulated = true) 42 public 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
