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.truth.Truth.assertThat; 21 import static java.util.Collections.sort; 22 23 import com.google.common.annotations.GwtCompatible; 24 import com.google.common.annotations.GwtIncompatible; 25 import com.google.common.collect.testing.Helpers.NullsBeforeB; 26 import com.google.common.collect.testing.NavigableSetTestSuiteBuilder; 27 import com.google.common.collect.testing.TestStringSetGenerator; 28 import com.google.common.collect.testing.features.CollectionFeature; 29 import com.google.common.collect.testing.features.CollectionSize; 30 import com.google.common.collect.testing.google.MultisetFeature; 31 import com.google.common.collect.testing.google.SortedMultisetTestSuiteBuilder; 32 import com.google.common.collect.testing.google.TestStringMultisetGenerator; 33 34 import junit.framework.Test; 35 import junit.framework.TestCase; 36 import junit.framework.TestSuite; 37 38 import java.lang.reflect.Method; 39 import java.util.Arrays; 40 import java.util.Collections; 41 import java.util.Comparator; 42 import java.util.List; 43 import java.util.Set; 44 import java.util.SortedSet; 45 46 /** 47 * Unit test for {@link TreeMultiset}. 48 * 49 * @author Neal Kanodia 50 */ 51 @GwtCompatible(emulated = true) 52 public 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
