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.truth.Truth.assertThat; 20 import static org.junit.Assert.assertThrows; 21 22 import com.google.common.annotations.GwtCompatible; 23 import com.google.common.annotations.GwtIncompatible; 24 import com.google.common.annotations.J2ktIncompatible; 25 import com.google.common.collect.ImmutableSet.Builder; 26 import com.google.common.collect.testing.ListTestSuiteBuilder; 27 import com.google.common.collect.testing.SetTestSuiteBuilder; 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.SetGenerators.DegeneratedImmutableSetGenerator; 31 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetAsListGenerator; 32 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetCopyOfGenerator; 33 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetSizedBuilderGenerator; 34 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetTooBigBuilderGenerator; 35 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetTooSmallBuilderGenerator; 36 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetUnsizedBuilderGenerator; 37 import com.google.common.collect.testing.google.SetGenerators.ImmutableSetWithBadHashesGenerator; 38 import com.google.common.testing.EqualsTester; 39 import java.util.Collection; 40 import java.util.Collections; 41 import java.util.Iterator; 42 import java.util.Set; 43 import junit.framework.Test; 44 import junit.framework.TestSuite; 45 46 /** 47 * Unit test for {@link ImmutableSet}. 48 * 49 * @author Kevin Bourrillion 50 * @author Jared Levy 51 * @author Nick Kralevich 52 */ 53 @GwtCompatible(emulated = true) 54 @ElementTypesAreNonnullByDefault 55 public class ImmutableSetTest extends AbstractImmutableSetTest { 56 57 @J2ktIncompatible 58 @GwtIncompatible // suite suite()59 public static Test suite() { 60 TestSuite suite = new TestSuite(); 61 62 suite.addTest( 63 SetTestSuiteBuilder.using(new ImmutableSetCopyOfGenerator()) 64 .named(ImmutableSetTest.class.getName()) 65 .withFeatures( 66 CollectionSize.ANY, 67 CollectionFeature.KNOWN_ORDER, 68 CollectionFeature.SERIALIZABLE, 69 CollectionFeature.ALLOWS_NULL_QUERIES) 70 .createTestSuite()); 71 72 suite.addTest( 73 SetTestSuiteBuilder.using(new ImmutableSetUnsizedBuilderGenerator()) 74 .named(ImmutableSetTest.class.getName() + ", with unsized builder") 75 .withFeatures( 76 CollectionSize.ANY, 77 CollectionFeature.KNOWN_ORDER, 78 CollectionFeature.SERIALIZABLE, 79 CollectionFeature.ALLOWS_NULL_QUERIES) 80 .createTestSuite()); 81 82 suite.addTest( 83 SetTestSuiteBuilder.using(new ImmutableSetSizedBuilderGenerator()) 84 .named(ImmutableSetTest.class.getName() + ", with exactly sized builder") 85 .withFeatures( 86 CollectionSize.ANY, 87 CollectionFeature.KNOWN_ORDER, 88 CollectionFeature.SERIALIZABLE, 89 CollectionFeature.ALLOWS_NULL_QUERIES) 90 .createTestSuite()); 91 92 suite.addTest( 93 SetTestSuiteBuilder.using(new ImmutableSetTooBigBuilderGenerator()) 94 .named(ImmutableSetTest.class.getName() + ", with oversized builder") 95 .withFeatures( 96 CollectionSize.ANY, 97 CollectionFeature.KNOWN_ORDER, 98 CollectionFeature.SERIALIZABLE, 99 CollectionFeature.ALLOWS_NULL_QUERIES) 100 .createTestSuite()); 101 102 suite.addTest( 103 SetTestSuiteBuilder.using(new ImmutableSetTooSmallBuilderGenerator()) 104 .named(ImmutableSetTest.class.getName() + ", with undersized builder") 105 .withFeatures( 106 CollectionSize.ANY, 107 CollectionFeature.KNOWN_ORDER, 108 CollectionFeature.SERIALIZABLE, 109 CollectionFeature.ALLOWS_NULL_QUERIES) 110 .createTestSuite()); 111 112 suite.addTest( 113 SetTestSuiteBuilder.using(new ImmutableSetWithBadHashesGenerator()) 114 .named(ImmutableSetTest.class.getName() + ", with bad hashes") 115 .withFeatures( 116 CollectionSize.ANY, 117 CollectionFeature.KNOWN_ORDER, 118 CollectionFeature.ALLOWS_NULL_QUERIES) 119 .createTestSuite()); 120 121 suite.addTest( 122 SetTestSuiteBuilder.using(new DegeneratedImmutableSetGenerator()) 123 .named(ImmutableSetTest.class.getName() + ", degenerate") 124 .withFeatures( 125 CollectionSize.ONE, 126 CollectionFeature.KNOWN_ORDER, 127 CollectionFeature.ALLOWS_NULL_QUERIES) 128 .createTestSuite()); 129 130 suite.addTest( 131 ListTestSuiteBuilder.using(new ImmutableSetAsListGenerator()) 132 .named("ImmutableSet.asList") 133 .withFeatures( 134 CollectionSize.ANY, 135 CollectionFeature.REJECTS_DUPLICATES_AT_CREATION, 136 CollectionFeature.SERIALIZABLE, 137 CollectionFeature.ALLOWS_NULL_QUERIES) 138 .createTestSuite()); 139 140 suite.addTestSuite(ImmutableSetTest.class); 141 142 return suite; 143 } 144 145 @Override of()146 protected <E extends Comparable<? super E>> Set<E> of() { 147 return ImmutableSet.of(); 148 } 149 150 @Override of(E e)151 protected <E extends Comparable<? super E>> Set<E> of(E e) { 152 return ImmutableSet.of(e); 153 } 154 155 @Override of(E e1, E e2)156 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2) { 157 return ImmutableSet.of(e1, e2); 158 } 159 160 @Override of(E e1, E e2, E e3)161 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3) { 162 return ImmutableSet.of(e1, e2, e3); 163 } 164 165 @Override of(E e1, E e2, E e3, E e4)166 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3, E e4) { 167 return ImmutableSet.of(e1, e2, e3, e4); 168 } 169 170 @Override of(E e1, E e2, E e3, E e4, E e5)171 protected <E extends Comparable<? super E>> Set<E> of(E e1, E e2, E e3, E e4, E e5) { 172 return ImmutableSet.of(e1, e2, e3, e4, e5); 173 } 174 175 @Override of( E e1, E e2, E e3, E e4, E e5, E e6, E... rest)176 protected <E extends Comparable<? super E>> Set<E> of( 177 E e1, E e2, E e3, E e4, E e5, E e6, E... rest) { 178 return ImmutableSet.of(e1, e2, e3, e4, e5, e6, rest); 179 } 180 181 @Override copyOf(E[] elements)182 protected <E extends Comparable<? super E>> Set<E> copyOf(E[] elements) { 183 return ImmutableSet.copyOf(elements); 184 } 185 186 @Override copyOf(Collection<? extends E> elements)187 protected <E extends Comparable<? super E>> Set<E> copyOf(Collection<? extends E> elements) { 188 return ImmutableSet.copyOf(elements); 189 } 190 191 @Override copyOf(Iterable<? extends E> elements)192 protected <E extends Comparable<? super E>> Set<E> copyOf(Iterable<? extends E> elements) { 193 return ImmutableSet.copyOf(elements); 194 } 195 196 @Override copyOf(Iterator<? extends E> elements)197 protected <E extends Comparable<? super E>> Set<E> copyOf(Iterator<? extends E> elements) { 198 return ImmutableSet.copyOf(elements); 199 } 200 testCreation_allDuplicates()201 public void testCreation_allDuplicates() { 202 ImmutableSet<String> set = ImmutableSet.copyOf(Lists.newArrayList("a", "a")); 203 assertTrue(set instanceof SingletonImmutableSet); 204 assertEquals(Lists.newArrayList("a"), Lists.newArrayList(set)); 205 } 206 testCreation_oneDuplicate()207 public void testCreation_oneDuplicate() { 208 // now we'll get the varargs overload 209 ImmutableSet<String> set = 210 ImmutableSet.of("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "a"); 211 assertEquals( 212 Lists.newArrayList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m"), 213 Lists.newArrayList(set)); 214 } 215 testCreation_manyDuplicates()216 public void testCreation_manyDuplicates() { 217 // now we'll get the varargs overload 218 ImmutableSet<String> set = 219 ImmutableSet.of("a", "b", "c", "c", "c", "c", "b", "b", "a", "a", "c", "c", "c", "a"); 220 assertThat(set).containsExactly("a", "b", "c").inOrder(); 221 } 222 223 @GwtIncompatible("Builder impl") testBuilderForceCopy()224 public void testBuilderForceCopy() { 225 ImmutableSet.Builder<Integer> builder = ImmutableSet.builder(); 226 builder.add(-1); 227 Object[] prevArray = null; 228 for (int i = 0; i < 10; i++) { 229 builder.add(i); 230 assertNotSame(builder.contents, prevArray); 231 prevArray = builder.contents; 232 ImmutableSet<Integer> unused = builder.build(); 233 } 234 } 235 236 @GwtIncompatible("Builder impl") testPresizedBuilderDedups()237 public void testPresizedBuilderDedups() { 238 ImmutableSet.Builder<String> builder = ImmutableSet.builderWithExpectedSize(4); 239 builder.add("a"); 240 assertEquals(1, builder.size); 241 builder.add("a"); 242 assertEquals(1, builder.size); 243 builder.add("b", "c", "d"); 244 assertEquals(4, builder.size); 245 Object[] table = builder.hashTable; 246 assertNotNull(table); 247 assertSame(table, ((RegularImmutableSet<String>) builder.build()).table); 248 } 249 250 @GwtIncompatible("Builder impl") testPresizedBuilderForceCopy()251 public void testPresizedBuilderForceCopy() { 252 for (int expectedSize = 1; expectedSize < 4; expectedSize++) { 253 ImmutableSet.Builder<Integer> builder = ImmutableSet.builderWithExpectedSize(expectedSize); 254 builder.add(-1); 255 Object[] prevArray = null; 256 for (int i = 0; i < 10; i++) { 257 ImmutableSet<Integer> prevBuilt = builder.build(); 258 builder.add(i); 259 assertFalse(prevBuilt.contains(i)); 260 assertNotSame(builder.contents, prevArray); 261 prevArray = builder.contents; 262 } 263 } 264 } 265 testCreation_arrayOfArray()266 public void testCreation_arrayOfArray() { 267 String[] array = new String[] {"a"}; 268 Set<String[]> set = ImmutableSet.<String[]>of(array); 269 assertEquals(Collections.singleton(array), set); 270 } 271 272 @GwtIncompatible // ImmutableSet.chooseTableSize testChooseTableSize()273 public void testChooseTableSize() { 274 assertEquals(8, ImmutableSet.chooseTableSize(3)); 275 assertEquals(8, ImmutableSet.chooseTableSize(4)); 276 277 assertEquals(1 << 29, ImmutableSet.chooseTableSize(1 << 28)); 278 assertEquals(1 << 29, ImmutableSet.chooseTableSize((1 << 29) * 3 / 5)); 279 280 // Now we hit the cap 281 assertEquals(1 << 30, ImmutableSet.chooseTableSize(1 << 29)); 282 assertEquals(1 << 30, ImmutableSet.chooseTableSize((1 << 30) - 1)); 283 284 // Now we've gone too far 285 assertThrows(IllegalArgumentException.class, () -> ImmutableSet.chooseTableSize(1 << 30)); 286 } 287 288 @GwtIncompatible // RegularImmutableSet.table not in emulation testResizeTable()289 public void testResizeTable() { 290 verifyTableSize(100, 2, 4); 291 verifyTableSize(100, 5, 8); 292 verifyTableSize(100, 33, 64); 293 verifyTableSize(60, 60, 128); 294 verifyTableSize(120, 60, 256); 295 // if the table is only double the necessary size, we don't bother resizing it 296 verifyTableSize(180, 60, 128); 297 // but if it's even bigger than double, we rebuild the table 298 verifyTableSize(17, 17, 32); 299 verifyTableSize(17, 16, 32); 300 verifyTableSize(17, 15, 32); 301 } 302 303 @GwtIncompatible // RegularImmutableSet.table not in emulation verifyTableSize(int inputSize, int setSize, int tableSize)304 private void verifyTableSize(int inputSize, int setSize, int tableSize) { 305 Builder<Integer> builder = ImmutableSet.builder(); 306 for (int i = 0; i < inputSize; i++) { 307 builder.add(i % setSize); 308 } 309 ImmutableSet<Integer> set = builder.build(); 310 assertTrue(set instanceof RegularImmutableSet); 311 assertEquals( 312 "Input size " + inputSize + " and set size " + setSize, 313 tableSize, 314 ((RegularImmutableSet<Integer>) set).table.length); 315 } 316 testCopyOf_copiesImmutableSortedSet()317 public void testCopyOf_copiesImmutableSortedSet() { 318 ImmutableSortedSet<String> sortedSet = ImmutableSortedSet.of("a"); 319 ImmutableSet<String> copy = ImmutableSet.copyOf(sortedSet); 320 assertNotSame(sortedSet, copy); 321 } 322 323 // TODO(b/172823566): Use mainline testToImmutableSet once CollectorTester is usable to java7. testToImmutableSet_java7()324 public void testToImmutableSet_java7() { 325 ImmutableSet.Builder<String> zis = ImmutableSet.<String>builder().add("a", "b", "a"); 326 ImmutableSet.Builder<String> zat = ImmutableSet.<String>builder().add("c", "b", "d", "c"); 327 ImmutableSet<String> set = zis.combine(zat).build(); 328 assertThat(set).containsExactly("a", "b", "c", "d").inOrder(); 329 } 330 331 @Override builder()332 <E extends Comparable<E>> Builder<E> builder() { 333 return ImmutableSet.builder(); 334 } 335 336 @Override getComplexBuilderSetLastElement()337 int getComplexBuilderSetLastElement() { 338 return LAST_COLOR_ADDED; 339 } 340 testEquals()341 public void testEquals() { 342 new EqualsTester() 343 .addEqualityGroup(ImmutableSet.of(), ImmutableSet.of()) 344 .addEqualityGroup(ImmutableSet.of(1), ImmutableSet.of(1), ImmutableSet.of(1, 1)) 345 .addEqualityGroup(ImmutableSet.of(1, 2, 1), ImmutableSet.of(2, 1, 1)) 346 .testEquals(); 347 } 348 349 @GwtIncompatible("internals") testControlsArraySize()350 public void testControlsArraySize() { 351 ImmutableSet.Builder<String> builder = new ImmutableSet.Builder<String>(); 352 for (int i = 0; i < 10; i++) { 353 builder.add("foo"); 354 } 355 builder.add("bar"); 356 RegularImmutableSet<String> set = (RegularImmutableSet<String>) builder.build(); 357 assertTrue(set.elements.length <= 2 * set.size()); 358 } 359 360 @GwtIncompatible("internals") testReusedBuilder()361 public void testReusedBuilder() { 362 ImmutableSet.Builder<String> builder = new ImmutableSet.Builder<String>(); 363 for (int i = 0; i < 10; i++) { 364 builder.add("foo"); 365 } 366 builder.add("bar"); 367 RegularImmutableSet<String> set = (RegularImmutableSet<String>) builder.build(); 368 builder.add("baz"); 369 assertTrue(set.elements != builder.contents); 370 } 371 testReuseBuilderReducingHashTableSizeWithPowerOfTwoTotalElements()372 public void testReuseBuilderReducingHashTableSizeWithPowerOfTwoTotalElements() { 373 ImmutableSet.Builder<Object> builder = ImmutableSet.builderWithExpectedSize(6); 374 builder.add(0); 375 ImmutableSet<Object> unused = builder.build(); 376 ImmutableSet<Object> subject = builder.add(1).add(2).add(3).build(); 377 assertFalse(subject.contains(4)); 378 } 379 } 380