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