1 /* 2 * Copyright (C) 2008 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.testing.google; 18 19 import static com.google.common.base.Preconditions.checkNotNull; 20 import static com.google.common.collect.Lists.newArrayList; 21 import static com.google.common.collect.Sets.newTreeSet; 22 import static com.google.common.collect.testing.SampleElements.Strings.AFTER_LAST; 23 import static com.google.common.collect.testing.SampleElements.Strings.AFTER_LAST_2; 24 import static com.google.common.collect.testing.SampleElements.Strings.BEFORE_FIRST; 25 import static com.google.common.collect.testing.SampleElements.Strings.BEFORE_FIRST_2; 26 import static junit.framework.Assert.assertEquals; 27 28 import com.google.common.annotations.GwtCompatible; 29 import com.google.common.annotations.GwtIncompatible; 30 import com.google.common.collect.ContiguousSet; 31 import com.google.common.collect.DiscreteDomain; 32 import com.google.common.collect.ImmutableSet; 33 import com.google.common.collect.ImmutableSortedSet; 34 import com.google.common.collect.Lists; 35 import com.google.common.collect.Ordering; 36 import com.google.common.collect.Range; 37 import com.google.common.collect.Sets; 38 import com.google.common.collect.testing.TestCollectionGenerator; 39 import com.google.common.collect.testing.TestCollidingSetGenerator; 40 import com.google.common.collect.testing.TestIntegerSortedSetGenerator; 41 import com.google.common.collect.testing.TestSetGenerator; 42 import com.google.common.collect.testing.TestStringListGenerator; 43 import com.google.common.collect.testing.TestStringSetGenerator; 44 import com.google.common.collect.testing.TestStringSortedSetGenerator; 45 import com.google.common.collect.testing.TestUnhashableCollectionGenerator; 46 import com.google.common.collect.testing.UnhashableObject; 47 48 import java.util.Arrays; 49 import java.util.Collections; 50 import java.util.Comparator; 51 import java.util.List; 52 import java.util.Set; 53 import java.util.SortedSet; 54 55 /** 56 * Generators of different types of sets and derived collections from sets. 57 * 58 * @author Kevin Bourrillion 59 * @author Jared Levy 60 * @author Hayward Chan 61 */ 62 @GwtCompatible(emulated = true) 63 public class SetGenerators { 64 65 public static class ImmutableSetCopyOfGenerator extends TestStringSetGenerator { 66 @Override protected Set<String> create(String[] elements) { 67 return ImmutableSet.copyOf(elements); 68 } 69 } 70 71 public static class ImmutableSetWithBadHashesGenerator 72 extends TestCollidingSetGenerator 73 // Work around a GWT compiler bug. Not explicitly listing this will 74 // cause the createArray() method missing in the generated javascript. 75 // TODO: Remove this once the GWT bug is fixed. 76 implements TestCollectionGenerator<Object> { 77 @Override 78 public Set<Object> create(Object... elements) { 79 return ImmutableSet.copyOf(elements); 80 } 81 } 82 83 public static class DegeneratedImmutableSetGenerator 84 extends TestStringSetGenerator { 85 // Make sure we get what we think we're getting, or else this test 86 // is pointless 87 @SuppressWarnings("cast") 88 @Override protected Set<String> create(String[] elements) { 89 return (ImmutableSet<String>) 90 ImmutableSet.of(elements[0], elements[0]); 91 } 92 } 93 94 public static class ImmutableSortedSetCopyOfGenerator 95 extends TestStringSortedSetGenerator { 96 @Override protected SortedSet<String> create(String[] elements) { 97 return ImmutableSortedSet.copyOf(elements); 98 } 99 } 100 101 public static class ImmutableSortedSetHeadsetGenerator 102 extends TestStringSortedSetGenerator { 103 @Override protected SortedSet<String> create(String[] elements) { 104 List<String> list = Lists.newArrayList(elements); 105 list.add("zzz"); 106 return ImmutableSortedSet.copyOf(list) 107 .headSet("zzy"); 108 } 109 } 110 111 public static class ImmutableSortedSetTailsetGenerator 112 extends TestStringSortedSetGenerator { 113 @Override protected SortedSet<String> create(String[] elements) { 114 List<String> list = Lists.newArrayList(elements); 115 list.add("\0"); 116 return ImmutableSortedSet.copyOf(list) 117 .tailSet("\0\0"); 118 } 119 } 120 121 public static class ImmutableSortedSetSubsetGenerator 122 extends TestStringSortedSetGenerator { 123 @Override protected SortedSet<String> create(String[] elements) { 124 List<String> list = Lists.newArrayList(elements); 125 list.add("\0"); 126 list.add("zzz"); 127 return ImmutableSortedSet.copyOf(list) 128 .subSet("\0\0", "zzy"); 129 } 130 } 131 132 @GwtIncompatible("NavigableSet") 133 public static class ImmutableSortedSetDescendingGenerator 134 extends TestStringSortedSetGenerator { 135 @Override protected SortedSet<String> create(String[] elements) { 136 return ImmutableSortedSet 137 .<String>reverseOrder() 138 .add(elements) 139 .build() 140 .descendingSet(); 141 } 142 } 143 144 public static class ImmutableSortedSetExplicitComparator 145 extends TestStringSetGenerator { 146 147 private static final Comparator<String> STRING_REVERSED 148 = Collections.reverseOrder(); 149 150 @Override protected SortedSet<String> create(String[] elements) { 151 return ImmutableSortedSet.orderedBy(STRING_REVERSED) 152 .add(elements) 153 .build(); 154 } 155 156 @Override public List<String> order(List<String> insertionOrder) { 157 Collections.sort(insertionOrder, Collections.reverseOrder()); 158 return insertionOrder; 159 } 160 } 161 162 public static class ImmutableSortedSetExplicitSuperclassComparatorGenerator 163 extends TestStringSetGenerator { 164 165 private static final Comparator<Comparable<?>> COMPARABLE_REVERSED 166 = Collections.reverseOrder(); 167 168 @Override protected SortedSet<String> create(String[] elements) { 169 return new ImmutableSortedSet.Builder<String>(COMPARABLE_REVERSED) 170 .add(elements) 171 .build(); 172 } 173 174 @Override public List<String> order(List<String> insertionOrder) { 175 Collections.sort(insertionOrder, Collections.reverseOrder()); 176 return insertionOrder; 177 } 178 } 179 180 public static class ImmutableSortedSetReversedOrderGenerator 181 extends TestStringSetGenerator { 182 183 @Override protected SortedSet<String> create(String[] elements) { 184 return ImmutableSortedSet.<String>reverseOrder() 185 .addAll(Arrays.asList(elements).iterator()) 186 .build(); 187 } 188 189 @Override public List<String> order(List<String> insertionOrder) { 190 Collections.sort(insertionOrder, Collections.reverseOrder()); 191 return insertionOrder; 192 } 193 } 194 195 public static class ImmutableSortedSetUnhashableGenerator 196 extends TestUnhashableSetGenerator { 197 @Override public Set<UnhashableObject> create( 198 UnhashableObject[] elements) { 199 return ImmutableSortedSet.copyOf(elements); 200 } 201 } 202 203 public static class ImmutableSetAsListGenerator 204 extends TestStringListGenerator { 205 @Override protected List<String> create(String[] elements) { 206 return ImmutableSet.copyOf(elements).asList(); 207 } 208 } 209 210 public static class ImmutableSortedSetAsListGenerator 211 extends TestStringListGenerator { 212 @Override protected List<String> create(String[] elements) { 213 Comparator<String> comparator = createExplicitComparator(elements); 214 ImmutableSet<String> set = ImmutableSortedSet.copyOf( 215 comparator, Arrays.asList(elements)); 216 return set.asList(); 217 } 218 } 219 220 public static class ImmutableSortedSetSubsetAsListGenerator 221 extends TestStringListGenerator { 222 @Override protected List<String> create(String[] elements) { 223 Comparator<String> comparator = createExplicitComparator(elements); 224 ImmutableSortedSet.Builder<String> builder 225 = ImmutableSortedSet.orderedBy(comparator); 226 builder.add(BEFORE_FIRST); 227 builder.add(elements); 228 builder.add(AFTER_LAST); 229 return builder.build().subSet(BEFORE_FIRST_2, 230 AFTER_LAST).asList(); 231 } 232 } 233 234 @GwtIncompatible("NavigableSet") 235 public static class ImmutableSortedSetDescendingAsListGenerator 236 extends TestStringListGenerator { 237 @Override protected List<String> create(String[] elements) { 238 Comparator<String> comparator = createExplicitComparator(elements).reverse(); 239 return ImmutableSortedSet 240 .orderedBy(comparator) 241 .add(elements) 242 .build() 243 .descendingSet() 244 .asList(); 245 } 246 } 247 248 public static class ImmutableSortedSetAsListSubListGenerator 249 extends TestStringListGenerator { 250 @Override protected List<String> create(String[] elements) { 251 Comparator<String> comparator = createExplicitComparator(elements); 252 ImmutableSortedSet.Builder<String> builder 253 = ImmutableSortedSet.orderedBy(comparator); 254 builder.add(BEFORE_FIRST); 255 builder.add(elements); 256 builder.add(AFTER_LAST); 257 return builder.build().asList().subList(1, elements.length + 1); 258 } 259 } 260 261 public static class ImmutableSortedSetSubsetAsListSubListGenerator 262 extends TestStringListGenerator { 263 @Override protected List<String> create(String[] elements) { 264 Comparator<String> comparator = createExplicitComparator(elements); 265 ImmutableSortedSet.Builder<String> builder 266 = ImmutableSortedSet.orderedBy(comparator); 267 builder.add(BEFORE_FIRST); 268 builder.add(BEFORE_FIRST_2); 269 builder.add(elements); 270 builder.add(AFTER_LAST); 271 builder.add(AFTER_LAST_2); 272 return builder.build().subSet(BEFORE_FIRST_2, 273 AFTER_LAST_2) 274 .asList().subList(1, elements.length + 1); 275 } 276 } 277 278 public abstract static class TestUnhashableSetGenerator 279 extends TestUnhashableCollectionGenerator<Set<UnhashableObject>> 280 implements TestSetGenerator<UnhashableObject> { 281 } 282 283 private static Ordering<String> createExplicitComparator( 284 String[] elements) { 285 // Collapse equal elements, which Ordering.explicit() doesn't support, while 286 // maintaining the ordering by first occurrence. 287 Set<String> elementsPlus = Sets.newLinkedHashSet(); 288 elementsPlus.add(BEFORE_FIRST); 289 elementsPlus.add(BEFORE_FIRST_2); 290 elementsPlus.addAll(Arrays.asList(elements)); 291 elementsPlus.add(AFTER_LAST); 292 elementsPlus.add(AFTER_LAST_2); 293 return Ordering.explicit(Lists.newArrayList(elementsPlus)); 294 } 295 296 /* 297 * All the ContiguousSet generators below manually reject nulls here. In principle, we'd like to 298 * defer that to Range, since it's ContiguousSet.create() that's used to create the sets. However, 299 * that gets messy here, and we already have null tests for Range. 300 */ 301 302 /* 303 * These generators also rely on consecutive integer inputs (not necessarily in order, but no 304 * holes). 305 */ 306 307 // SetCreationTester has some tests that pass in duplicates. Dedup them. 308 private static <E extends Comparable<? super E>> SortedSet<E> nullCheckedTreeSet(E[] elements) { 309 SortedSet<E> set = newTreeSet(); 310 for (E element : elements) { 311 // Explicit null check because TreeSet wrongly accepts add(null) when empty. 312 set.add(checkNotNull(element)); 313 } 314 return set; 315 } 316 317 public static class ContiguousSetGenerator extends AbstractContiguousSetGenerator { 318 @Override protected SortedSet<Integer> create(Integer[] elements) { 319 return checkedCreate(nullCheckedTreeSet(elements)); 320 } 321 } 322 323 public static class ContiguousSetHeadsetGenerator extends AbstractContiguousSetGenerator { 324 @Override protected SortedSet<Integer> create(Integer[] elements) { 325 SortedSet<Integer> set = nullCheckedTreeSet(elements); 326 int tooHigh = (set.isEmpty()) ? 0 : set.last() + 1; 327 set.add(tooHigh); 328 return checkedCreate(set).headSet(tooHigh); 329 } 330 } 331 332 public static class ContiguousSetTailsetGenerator extends AbstractContiguousSetGenerator { 333 @Override protected SortedSet<Integer> create(Integer[] elements) { 334 SortedSet<Integer> set = nullCheckedTreeSet(elements); 335 int tooLow = (set.isEmpty()) ? 0 : set.first() - 1; 336 set.add(tooLow); 337 return checkedCreate(set).tailSet(tooLow + 1); 338 } 339 } 340 341 public static class ContiguousSetSubsetGenerator extends AbstractContiguousSetGenerator { 342 @Override protected SortedSet<Integer> create(Integer[] elements) { 343 SortedSet<Integer> set = nullCheckedTreeSet(elements); 344 if (set.isEmpty()) { 345 /* 346 * The (tooLow + 1, tooHigh) arguments below would be invalid because tooLow would be 347 * greater than tooHigh. 348 */ 349 return ContiguousSet.create(Range.openClosed(0, 1), DiscreteDomain.integers()).subSet(0, 1); 350 } 351 int tooHigh = set.last() + 1; 352 int tooLow = set.first() - 1; 353 set.add(tooHigh); 354 set.add(tooLow); 355 return checkedCreate(set).subSet(tooLow + 1, tooHigh); 356 } 357 } 358 359 @GwtIncompatible("NavigableSet") 360 public static class ContiguousSetDescendingGenerator extends AbstractContiguousSetGenerator { 361 @Override protected SortedSet<Integer> create(Integer[] elements) { 362 return checkedCreate(nullCheckedTreeSet(elements)).descendingSet(); 363 } 364 365 /** Sorts the elements in reverse natural order. */ 366 @Override public List<Integer> order(List<Integer> insertionOrder) { 367 Collections.sort(insertionOrder, Ordering.natural().reverse()); 368 return insertionOrder; 369 } 370 } 371 372 private abstract static class AbstractContiguousSetGenerator 373 extends TestIntegerSortedSetGenerator { 374 protected final ContiguousSet<Integer> checkedCreate(SortedSet<Integer> elementsSet) { 375 List<Integer> elements = newArrayList(elementsSet); 376 /* 377 * A ContiguousSet can't have holes. If a test demands a hole, it should be changed so that it 378 * doesn't need one, or it should be suppressed for ContiguousSet. 379 */ 380 for (int i = 0; i < elements.size() - 1; i++) { 381 assertEquals(elements.get(i) + 1, (int) elements.get(i + 1)); 382 } 383 Range<Integer> range = 384 (elements.isEmpty()) ? Range.closedOpen(0, 0) : Range.encloseAll(elements); 385 return ContiguousSet.create(range, DiscreteDomain.integers()); 386 } 387 } 388 } 389