1 /* 2 * Copyright (C) 2012 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 21 import com.google.common.base.Predicate; 22 import com.google.common.base.Predicates; 23 import com.google.common.testing.EqualsTester; 24 25 import junit.framework.TestCase; 26 27 import java.util.Collection; 28 import java.util.Iterator; 29 import java.util.List; 30 import java.util.NavigableSet; 31 import java.util.NoSuchElementException; 32 import java.util.Set; 33 import java.util.SortedSet; 34 import java.util.TreeSet; 35 36 /** 37 * Tests for filtered collection views. 38 * 39 * @author Louis Wasserman 40 */ 41 public class FilteredCollectionsTest extends TestCase { 42 private static final Predicate<Integer> EVEN = new Predicate<Integer>() { 43 @Override 44 public boolean apply(Integer input) { 45 return input % 2 == 0; 46 } 47 }; 48 49 private static final Predicate<Integer> PRIME_DIGIT = 50 Predicates.in(ImmutableSet.of(2, 3, 5, 7)); 51 52 private static final ImmutableList<? extends List<Integer>> SAMPLE_INPUTS = 53 ImmutableList.of(ImmutableList.<Integer>of(), 54 ImmutableList.of(1), 55 ImmutableList.of(2), 56 ImmutableList.of(2, 3), 57 ImmutableList.of(1, 2), 58 ImmutableList.of(3, 5), 59 ImmutableList.of(2, 4), 60 ImmutableList.of(1, 2, 3, 5, 6, 8, 9)); 61 62 /* 63 * We have a whole series of abstract test classes that "stack", so e.g. the tests for filtered 64 * NavigableSets inherit the tests for filtered Iterables, Collections, Sets, and SortedSets. The 65 * actual implementation tests are further down. 66 */ 67 68 public static abstract class AbstractFilteredIterableTest<C extends Iterable<Integer>> 69 extends TestCase { 70 abstract C createUnfiltered(Iterable<Integer> contents); 71 72 abstract C filter(C elements, Predicate<? super Integer> predicate); 73 74 public void testIterationOrderPreserved() { 75 for (List<Integer> contents : SAMPLE_INPUTS) { 76 C unfiltered = createUnfiltered(contents); 77 C filtered = filter(unfiltered, EVEN); 78 79 Iterator<Integer> filteredItr = filtered.iterator(); 80 for (Integer i : unfiltered) { 81 if (EVEN.apply(i)) { 82 assertTrue(filteredItr.hasNext()); 83 assertEquals(i, filteredItr.next()); 84 } 85 } 86 assertFalse(filteredItr.hasNext()); 87 } 88 } 89 } 90 91 public static abstract class AbstractFilteredCollectionTest<C extends Collection<Integer>> 92 extends AbstractFilteredIterableTest<C> { 93 94 public void testReadsThroughAdd() { 95 for (List<Integer> contents : SAMPLE_INPUTS) { 96 C unfiltered = createUnfiltered(contents); 97 C filterThenAdd = filter(unfiltered, EVEN); 98 unfiltered.add(4); 99 100 List<Integer> target = Lists.newArrayList(contents); 101 target.add(4); 102 C addThenFilter = filter(createUnfiltered(target), EVEN); 103 104 assertThat(filterThenAdd).has().exactlyAs(addThenFilter); 105 } 106 } 107 108 public void testAdd() { 109 for (List<Integer> contents : SAMPLE_INPUTS) { 110 for (int toAdd = 0; toAdd < 10; toAdd++) { 111 boolean expectedResult = createUnfiltered(contents).add(toAdd); 112 113 C filtered = filter(createUnfiltered(contents), EVEN); 114 try { 115 assertEquals(expectedResult, filtered.add(toAdd)); 116 assertTrue(EVEN.apply(toAdd)); 117 } catch (IllegalArgumentException e) { 118 assertFalse(EVEN.apply(toAdd)); 119 } 120 } 121 } 122 } 123 124 public void testRemove() { 125 for (List<Integer> contents : SAMPLE_INPUTS) { 126 for (int toRemove = 0; toRemove < 10; toRemove++) { 127 assertEquals(contents.contains(toRemove) && EVEN.apply(toRemove), 128 filter(createUnfiltered(contents), EVEN).remove(toRemove)); 129 } 130 } 131 } 132 133 public void testContains() { 134 for (List<Integer> contents : SAMPLE_INPUTS) { 135 for (int i = 0; i < 10; i++) { 136 assertEquals(EVEN.apply(i) && contents.contains(i), 137 filter(createUnfiltered(contents), EVEN).contains(i)); 138 } 139 } 140 } 141 142 public void testContainsOnDifferentType() { 143 for (List<Integer> contents : SAMPLE_INPUTS) { 144 assertFalse(filter(createUnfiltered(contents), EVEN).contains(new Object())); 145 } 146 } 147 148 public void testAddAllFailsAtomically() { 149 ImmutableList<Integer> toAdd = ImmutableList.of(2, 4, 3); 150 for (List<Integer> contents : SAMPLE_INPUTS) { 151 C filtered = filter(createUnfiltered(contents), EVEN); 152 C filteredToModify = filter(createUnfiltered(contents), EVEN); 153 154 try { 155 filteredToModify.addAll(toAdd); 156 fail("Expected IllegalArgumentException"); 157 } catch (IllegalArgumentException expected) { 158 } 159 160 assertThat(filteredToModify).has().exactlyAs(filtered); 161 } 162 } 163 164 public void testAddToFilterFiltered() { 165 for (List<Integer> contents : SAMPLE_INPUTS) { 166 C unfiltered = createUnfiltered(contents); 167 C filtered1 = filter(unfiltered, EVEN); 168 C filtered2 = filter(filtered1, PRIME_DIGIT); 169 170 try { 171 filtered2.add(4); 172 fail("Expected IllegalArgumentException"); 173 } catch (IllegalArgumentException expected) {} 174 175 try { 176 filtered2.add(3); 177 fail("Expected IllegalArgumentException"); 178 } catch (IllegalArgumentException expected) {} 179 180 filtered2.add(2); 181 } 182 } 183 184 public void testClearFilterFiltered() { 185 for (List<Integer> contents : SAMPLE_INPUTS) { 186 C unfiltered = createUnfiltered(contents); 187 C filtered1 = filter(unfiltered, EVEN); 188 C filtered2 = filter(filtered1, PRIME_DIGIT); 189 190 C inverseFiltered = filter(createUnfiltered(contents), 191 Predicates.not(Predicates.and(EVEN, PRIME_DIGIT))); 192 193 filtered2.clear(); 194 assertThat(unfiltered).has().exactlyAs(inverseFiltered); 195 } 196 } 197 } 198 199 public static abstract class AbstractFilteredSetTest<C extends Set<Integer>> 200 extends AbstractFilteredCollectionTest<C> { 201 public void testEqualsAndHashCode() { 202 for (List<Integer> contents : SAMPLE_INPUTS) { 203 Set<Integer> expected = Sets.newHashSet(); 204 for (Integer i : contents) { 205 if (EVEN.apply(i)) { 206 expected.add(i); 207 } 208 } 209 new EqualsTester().addEqualityGroup(expected, filter(createUnfiltered(contents), EVEN)) 210 .testEquals(); 211 } 212 } 213 } 214 215 public static abstract class AbstractFilteredSortedSetTest<C extends SortedSet<Integer>> 216 extends AbstractFilteredSetTest<C> { 217 public void testFirst() { 218 for (List<Integer> contents : SAMPLE_INPUTS) { 219 C filtered = filter(createUnfiltered(contents), EVEN); 220 221 try { 222 Integer first = filtered.first(); 223 assertFalse(filtered.isEmpty()); 224 assertEquals(Ordering.natural().min(filtered), first); 225 } catch (NoSuchElementException e) { 226 assertTrue(filtered.isEmpty()); 227 } 228 } 229 } 230 231 public void testLast() { 232 for (List<Integer> contents : SAMPLE_INPUTS) { 233 C filtered = filter(createUnfiltered(contents), EVEN); 234 235 try { 236 Integer first = filtered.last(); 237 assertFalse(filtered.isEmpty()); 238 assertEquals(Ordering.natural().max(filtered), first); 239 } catch (NoSuchElementException e) { 240 assertTrue(filtered.isEmpty()); 241 } 242 } 243 } 244 245 @SuppressWarnings("unchecked") 246 public void testHeadSet() { 247 for (List<Integer> contents : SAMPLE_INPUTS) { 248 for (int i = 0; i < 10; i++) { 249 assertEquals( 250 filter((C) createUnfiltered(contents).headSet(i), EVEN), 251 filter(createUnfiltered(contents), EVEN).headSet(i)); 252 } 253 } 254 } 255 256 @SuppressWarnings("unchecked") 257 public void testTailSet() { 258 for (List<Integer> contents : SAMPLE_INPUTS) { 259 for (int i = 0; i < 10; i++) { 260 assertEquals( 261 filter((C) createUnfiltered(contents).tailSet(i), EVEN), 262 filter(createUnfiltered(contents), EVEN).tailSet(i)); 263 } 264 } 265 } 266 267 @SuppressWarnings("unchecked") 268 public void testSubSet() { 269 for (List<Integer> contents : SAMPLE_INPUTS) { 270 for (int i = 0; i < 10; i++) { 271 for (int j = i; j < 10; j++) { 272 assertEquals( 273 filter((C) createUnfiltered(contents).subSet(i, j), EVEN), 274 filter(createUnfiltered(contents), EVEN).subSet(i, j)); 275 } 276 } 277 } 278 } 279 } 280 281 public static abstract class AbstractFilteredNavigableSetTest 282 extends AbstractFilteredSortedSetTest<NavigableSet<Integer>> { 283 284 public void testNavigableHeadSet() { 285 for (List<Integer> contents : SAMPLE_INPUTS) { 286 for (int i = 0; i < 10; i++) { 287 for (boolean inclusive : ImmutableList.of(true, false)) { 288 assertEquals( 289 filter(createUnfiltered(contents).headSet(i, inclusive), EVEN), 290 filter(createUnfiltered(contents), EVEN).headSet(i, inclusive)); 291 } 292 } 293 } 294 } 295 296 public void testNavigableTailSet() { 297 for (List<Integer> contents : SAMPLE_INPUTS) { 298 for (int i = 0; i < 10; i++) { 299 for (boolean inclusive : ImmutableList.of(true, false)) { 300 assertEquals( 301 filter(createUnfiltered(contents).tailSet(i, inclusive), EVEN), 302 filter(createUnfiltered(contents), EVEN).tailSet(i, inclusive)); 303 } 304 } 305 } 306 } 307 308 public void testNavigableSubSet() { 309 for (List<Integer> contents : SAMPLE_INPUTS) { 310 for (int i = 0; i < 10; i++) { 311 for (int j = i + 1; j < 10; j++) { 312 for (boolean fromInclusive : ImmutableList.of(true, false)) { 313 for (boolean toInclusive : ImmutableList.of(true, false)) { 314 NavigableSet<Integer> filterSubset = filter( 315 createUnfiltered(contents).subSet(i, fromInclusive, j, toInclusive), EVEN); 316 NavigableSet<Integer> subsetFilter = filter(createUnfiltered(contents), EVEN) 317 .subSet(i, fromInclusive, j, toInclusive); 318 assertEquals(filterSubset, subsetFilter); 319 } 320 } 321 } 322 } 323 } 324 } 325 326 public void testDescendingSet() { 327 for (List<Integer> contents : SAMPLE_INPUTS) { 328 NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN); 329 NavigableSet<Integer> unfiltered = createUnfiltered(filtered); 330 331 assertThat(filtered.descendingSet()).has().exactlyAs(unfiltered.descendingSet()).inOrder(); 332 } 333 } 334 335 public void testPollFirst() { 336 for (List<Integer> contents : SAMPLE_INPUTS) { 337 NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN); 338 NavigableSet<Integer> unfiltered = createUnfiltered(filtered); 339 340 assertEquals(unfiltered.pollFirst(), filtered.pollFirst()); 341 assertEquals(unfiltered, filtered); 342 } 343 } 344 345 public void testPollLast() { 346 for (List<Integer> contents : SAMPLE_INPUTS) { 347 NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN); 348 NavigableSet<Integer> unfiltered = createUnfiltered(filtered); 349 350 assertEquals(unfiltered.pollLast(), filtered.pollLast()); 351 assertEquals(unfiltered, filtered); 352 } 353 } 354 355 public void testNavigation() { 356 for (List<Integer> contents : SAMPLE_INPUTS) { 357 NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN); 358 NavigableSet<Integer> unfiltered = createUnfiltered(filtered); 359 for (int i = 0; i < 10; i++) { 360 assertEquals(unfiltered.lower(i), filtered.lower(i)); 361 assertEquals(unfiltered.floor(i), filtered.floor(i)); 362 assertEquals(unfiltered.ceiling(i), filtered.ceiling(i)); 363 assertEquals(unfiltered.higher(i), filtered.higher(i)); 364 } 365 } 366 } 367 } 368 369 // implementation tests 370 371 public static final class IterablesFilterArrayListTest 372 extends AbstractFilteredIterableTest<Iterable<Integer>> { 373 @Override 374 Iterable<Integer> createUnfiltered(Iterable<Integer> contents) { 375 return Lists.newArrayList(contents); 376 } 377 378 @Override 379 Iterable<Integer> filter(Iterable<Integer> elements, Predicate<? super Integer> predicate) { 380 return Iterables.filter(elements, predicate); 381 } 382 } 383 384 public static final class Collections2FilterArrayListTest 385 extends AbstractFilteredCollectionTest<Collection<Integer>> { 386 @Override 387 Collection<Integer> createUnfiltered(Iterable<Integer> contents) { 388 return Lists.newArrayList(contents); 389 } 390 391 @Override 392 Collection<Integer> filter(Collection<Integer> elements, Predicate<? super Integer> predicate) { 393 return Collections2.filter(elements, predicate); 394 } 395 } 396 397 public static final class SetsFilterHashSetTest 398 extends AbstractFilteredSetTest<Set<Integer>> { 399 @Override 400 Set<Integer> createUnfiltered(Iterable<Integer> contents) { 401 return Sets.newHashSet(contents); 402 } 403 404 @Override 405 Set<Integer> filter(Set<Integer> elements, Predicate<? super Integer> predicate) { 406 return Sets.filter(elements, predicate); 407 } 408 } 409 410 public static final class SetsFilterSortedSetTest 411 extends AbstractFilteredSortedSetTest<SortedSet<Integer>> { 412 @Override 413 SortedSet<Integer> createUnfiltered(Iterable<Integer> contents) { 414 final TreeSet<Integer> result = Sets.newTreeSet(contents); 415 // we have to make the result not Navigable 416 return new ForwardingSortedSet<Integer>() { 417 @Override 418 protected SortedSet<Integer> delegate() { 419 return result; 420 } 421 }; 422 } 423 424 @Override 425 SortedSet<Integer> filter(SortedSet<Integer> elements, Predicate<? super Integer> predicate) { 426 return Sets.filter(elements, predicate); 427 } 428 } 429 430 public static final class SetsFilterNavigableSetTest extends AbstractFilteredNavigableSetTest { 431 @Override 432 NavigableSet<Integer> createUnfiltered(Iterable<Integer> contents) { 433 return Sets.newTreeSet(contents); 434 } 435 436 @Override 437 NavigableSet<Integer> filter( 438 NavigableSet<Integer> elements, Predicate<? super Integer> predicate) { 439 return Sets.filter(elements, predicate); 440 } 441 } 442 443 /** No-op test so that the class has at least one method, making Maven's test runner happy. */ 444 public void testNoop() { 445 } 446 } 447