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 22 import com.google.common.annotations.GwtCompatible; 23 24 import junit.framework.TestCase; 25 26 import java.util.Arrays; 27 import java.util.Collections; 28 import java.util.Comparator; 29 import java.util.SortedSet; 30 31 /** 32 * Unit test for {@link TreeMultiset}. 33 * 34 * @author Neal Kanodia 35 */ 36 @GwtCompatible(emulated = true) 37 public class TreeMultisetTest extends TestCase { 38 39 public void testCreate() { 40 TreeMultiset<String> multiset = TreeMultiset.create(); 41 multiset.add("foo", 2); 42 multiset.add("bar"); 43 assertEquals(3, multiset.size()); 44 assertEquals(2, multiset.count("foo")); 45 assertEquals(Ordering.natural(), multiset.comparator()); 46 assertEquals("[bar, foo x 2]", multiset.toString()); 47 } 48 49 public void testCreateWithComparator() { 50 Multiset<String> multiset = TreeMultiset.create(Collections.reverseOrder()); 51 multiset.add("foo", 2); 52 multiset.add("bar"); 53 assertEquals(3, multiset.size()); 54 assertEquals(2, multiset.count("foo")); 55 assertEquals("[foo x 2, bar]", multiset.toString()); 56 } 57 58 public void testCreateFromIterable() { 59 Multiset<String> multiset 60 = TreeMultiset.create(Arrays.asList("foo", "bar", "foo")); 61 assertEquals(3, multiset.size()); 62 assertEquals(2, multiset.count("foo")); 63 assertEquals("[bar, foo x 2]", multiset.toString()); 64 } 65 66 public void testToString() { 67 Multiset<String> ms = TreeMultiset.create(); 68 ms.add("a", 3); 69 ms.add("c", 1); 70 ms.add("b", 2); 71 72 assertEquals("[a x 3, b x 2, c]", ms.toString()); 73 } 74 75 public void testElementSetSortedSetMethods() { 76 TreeMultiset<String> ms = TreeMultiset.create(); 77 ms.add("c", 1); 78 ms.add("a", 3); 79 ms.add("b", 2); 80 SortedSet<String> elementSet = ms.elementSet(); 81 82 assertEquals("a", elementSet.first()); 83 assertEquals("c", elementSet.last()); 84 assertEquals(Ordering.natural(), elementSet.comparator()); 85 86 assertThat(elementSet.headSet("b")).has().exactly("a").inOrder(); 87 assertThat(elementSet.tailSet("b")).has().exactly("b", "c").inOrder(); 88 assertThat(elementSet.subSet("a", "c")).has().exactly("a", "b").inOrder(); 89 } 90 91 public void testElementSetSubsetRemove() { 92 TreeMultiset<String> ms = TreeMultiset.create(); 93 ms.add("a", 1); 94 ms.add("b", 3); 95 ms.add("c", 2); 96 ms.add("d", 1); 97 ms.add("e", 3); 98 ms.add("f", 2); 99 100 SortedSet<String> elementSet = ms.elementSet(); 101 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder(); 102 SortedSet<String> subset = elementSet.subSet("b", "f"); 103 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder(); 104 105 assertTrue(subset.remove("c")); 106 assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder(); 107 assertThat(subset).has().exactly("b", "d", "e").inOrder(); 108 assertEquals(10, ms.size()); 109 110 assertFalse(subset.remove("a")); 111 assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder(); 112 assertThat(subset).has().exactly("b", "d", "e").inOrder(); 113 assertEquals(10, ms.size()); 114 } 115 116 public void testElementSetSubsetRemoveAll() { 117 TreeMultiset<String> ms = TreeMultiset.create(); 118 ms.add("a", 1); 119 ms.add("b", 3); 120 ms.add("c", 2); 121 ms.add("d", 1); 122 ms.add("e", 3); 123 ms.add("f", 2); 124 125 SortedSet<String> elementSet = ms.elementSet(); 126 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder(); 127 SortedSet<String> subset = elementSet.subSet("b", "f"); 128 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder(); 129 130 assertTrue(subset.removeAll(Arrays.asList("a", "c"))); 131 assertThat(elementSet).has().exactly("a", "b", "d", "e", "f").inOrder(); 132 assertThat(subset).has().exactly("b", "d", "e").inOrder(); 133 assertEquals(10, ms.size()); 134 } 135 136 public void testElementSetSubsetRetainAll() { 137 TreeMultiset<String> ms = TreeMultiset.create(); 138 ms.add("a", 1); 139 ms.add("b", 3); 140 ms.add("c", 2); 141 ms.add("d", 1); 142 ms.add("e", 3); 143 ms.add("f", 2); 144 145 SortedSet<String> elementSet = ms.elementSet(); 146 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder(); 147 SortedSet<String> subset = elementSet.subSet("b", "f"); 148 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder(); 149 150 assertTrue(subset.retainAll(Arrays.asList("a", "c"))); 151 assertThat(elementSet).has().exactly("a", "c", "f").inOrder(); 152 assertThat(subset).has().exactly("c").inOrder(); 153 assertEquals(5, ms.size()); 154 } 155 156 public void testElementSetSubsetClear() { 157 TreeMultiset<String> ms = TreeMultiset.create(); 158 ms.add("a", 1); 159 ms.add("b", 3); 160 ms.add("c", 2); 161 ms.add("d", 1); 162 ms.add("e", 3); 163 ms.add("f", 2); 164 165 SortedSet<String> elementSet = ms.elementSet(); 166 assertThat(elementSet).has().exactly("a", "b", "c", "d", "e", "f").inOrder(); 167 SortedSet<String> subset = elementSet.subSet("b", "f"); 168 assertThat(subset).has().exactly("b", "c", "d", "e").inOrder(); 169 170 subset.clear(); 171 assertThat(elementSet).has().exactly("a", "f").inOrder(); 172 assertThat(subset).isEmpty(); 173 assertEquals(3, ms.size()); 174 } 175 176 public void testCustomComparator() throws Exception { 177 Comparator<String> comparator = new Comparator<String>() { 178 @Override 179 public int compare(String o1, String o2) { 180 return o2.compareTo(o1); 181 } 182 }; 183 TreeMultiset<String> ms = TreeMultiset.create(comparator); 184 185 ms.add("b"); 186 ms.add("c"); 187 ms.add("a"); 188 ms.add("b"); 189 ms.add("d"); 190 191 assertThat(ms).has().exactly("d", "c", "b", "b", "a").inOrder(); 192 193 SortedSet<String> elementSet = ms.elementSet(); 194 assertEquals("d", elementSet.first()); 195 assertEquals("a", elementSet.last()); 196 assertEquals(comparator, elementSet.comparator()); 197 } 198 199 public void testNullAcceptingComparator() throws Exception { 200 Comparator<String> comparator = Ordering.<String>natural().nullsFirst(); 201 TreeMultiset<String> ms = TreeMultiset.create(comparator); 202 203 ms.add("b"); 204 ms.add(null); 205 ms.add("a"); 206 ms.add("b"); 207 ms.add(null, 2); 208 209 assertThat(ms).has().exactly(null, null, null, "a", "b", "b").inOrder(); 210 assertEquals(3, ms.count(null)); 211 212 SortedSet<String> elementSet = ms.elementSet(); 213 assertEquals(null, elementSet.first()); 214 assertEquals("b", elementSet.last()); 215 assertEquals(comparator, elementSet.comparator()); 216 } 217 218 private static final Comparator<String> DEGENERATE_COMPARATOR = 219 new Comparator<String>() { 220 @Override 221 public int compare(String o1, String o2) { 222 return o1.length() - o2.length(); 223 } 224 }; 225 226 /** 227 * Test a TreeMultiset with a comparator that can return 0 when comparing 228 * unequal values. 229 */ 230 public void testDegenerateComparator() throws Exception { 231 TreeMultiset<String> ms = TreeMultiset.create(DEGENERATE_COMPARATOR); 232 233 ms.add("foo"); 234 ms.add("a"); 235 ms.add("bar"); 236 ms.add("b"); 237 ms.add("c"); 238 239 assertEquals(2, ms.count("bar")); 240 assertEquals(3, ms.count("b")); 241 242 Multiset<String> ms2 = TreeMultiset.create(DEGENERATE_COMPARATOR); 243 244 ms2.add("cat", 2); 245 ms2.add("x", 3); 246 247 assertEquals(ms, ms2); 248 assertEquals(ms2, ms); 249 250 SortedSet<String> elementSet = ms.elementSet(); 251 assertEquals("a", elementSet.first()); 252 assertEquals("foo", elementSet.last()); 253 assertEquals(DEGENERATE_COMPARATOR, elementSet.comparator()); 254 } 255 256 public void testSubMultisetSize() { 257 TreeMultiset<String> ms = TreeMultiset.create(); 258 ms.add("a", Integer.MAX_VALUE); 259 ms.add("b", Integer.MAX_VALUE); 260 ms.add("c", 3); 261 262 assertEquals(Integer.MAX_VALUE, ms.count("a")); 263 assertEquals(Integer.MAX_VALUE, ms.count("b")); 264 assertEquals(3, ms.count("c")); 265 266 assertEquals(Integer.MAX_VALUE, ms.headMultiset("c", CLOSED).size()); 267 assertEquals(Integer.MAX_VALUE, ms.headMultiset("b", CLOSED).size()); 268 assertEquals(Integer.MAX_VALUE, ms.headMultiset("a", CLOSED).size()); 269 270 assertEquals(3, ms.tailMultiset("c", CLOSED).size()); 271 assertEquals(Integer.MAX_VALUE, ms.tailMultiset("b", CLOSED).size()); 272 assertEquals(Integer.MAX_VALUE, ms.tailMultiset("a", CLOSED).size()); 273 } 274 } 275 276