common/collect/FilteredCollectionsTest.java

/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.truth.Truth.assertThat;

import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.testing.EqualsTester;

import junit.framework.TestCase;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.NavigableSet;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * Tests for filtered collection views.
 *
 * @author Louis Wasserman
 */
public class FilteredCollectionsTest extends TestCase {
  private static final Predicate<Integer> EVEN = new Predicate<Integer>() {
    @Override
    public boolean apply(Integer input) {
      return input % 2 == 0;
    }
  };

  private static final Predicate<Integer> PRIME_DIGIT =
      Predicates.in(ImmutableSet.of(2, 3, 5, 7));

  private static final ImmutableList<? extends List<Integer>> SAMPLE_INPUTS =
      ImmutableList.of(ImmutableList.<Integer>of(),
          ImmutableList.of(1),
          ImmutableList.of(2),
          ImmutableList.of(2, 3),
          ImmutableList.of(1, 2),
          ImmutableList.of(3, 5),
          ImmutableList.of(2, 4),
          ImmutableList.of(1, 2, 3, 5, 6, 8, 9));

  /*
   * We have a whole series of abstract test classes that "stack", so e.g. the tests for filtered
   * NavigableSets inherit the tests for filtered Iterables, Collections, Sets, and SortedSets. The
   * actual implementation tests are further down.
   */

  public static abstract class AbstractFilteredIterableTest<C extends Iterable<Integer>>
      extends TestCase {
    abstract C createUnfiltered(Iterable<Integer> contents);

    abstract C filter(C elements, Predicate<? super Integer> predicate);

    public void testIterationOrderPreserved() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C unfiltered = createUnfiltered(contents);
        C filtered = filter(unfiltered, EVEN);

        Iterator<Integer> filteredItr = filtered.iterator();
        for (Integer i : unfiltered) {
          if (EVEN.apply(i)) {
            assertTrue(filteredItr.hasNext());
            assertEquals(i, filteredItr.next());
          }
        }
        assertFalse(filteredItr.hasNext());
      }
    }
  }

  public static abstract class AbstractFilteredCollectionTest<C extends Collection<Integer>>
      extends AbstractFilteredIterableTest<C> {

    public void testReadsThroughAdd() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C unfiltered  = createUnfiltered(contents);
        C filterThenAdd = filter(unfiltered, EVEN);
        unfiltered.add(4);

        List<Integer> target = Lists.newArrayList(contents);
        target.add(4);
        C addThenFilter = filter(createUnfiltered(target), EVEN);

        assertThat(filterThenAdd).has().exactlyAs(addThenFilter);
      }
    }

    public void testAdd() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int toAdd = 0; toAdd < 10; toAdd++) {
          boolean expectedResult = createUnfiltered(contents).add(toAdd);

          C filtered = filter(createUnfiltered(contents), EVEN);
          try {
            assertEquals(expectedResult, filtered.add(toAdd));
            assertTrue(EVEN.apply(toAdd));
          } catch (IllegalArgumentException e) {
            assertFalse(EVEN.apply(toAdd));
          }
        }
      }
    }

    public void testRemove() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int toRemove = 0; toRemove < 10; toRemove++) {
          assertEquals(contents.contains(toRemove) && EVEN.apply(toRemove),
              filter(createUnfiltered(contents), EVEN).remove(toRemove));
        }
      }
    }

    public void testContains() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
          assertEquals(EVEN.apply(i) && contents.contains(i),
              filter(createUnfiltered(contents), EVEN).contains(i));
        }
      }
    }

    public void testContainsOnDifferentType() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        assertFalse(filter(createUnfiltered(contents), EVEN).contains(new Object()));
      }
    }

    public void testAddAllFailsAtomically() {
      ImmutableList<Integer> toAdd = ImmutableList.of(2, 4, 3);
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C filtered = filter(createUnfiltered(contents), EVEN);
        C filteredToModify = filter(createUnfiltered(contents), EVEN);

        try {
          filteredToModify.addAll(toAdd);
          fail("Expected IllegalArgumentException");
        } catch (IllegalArgumentException expected) {
        }

        assertThat(filteredToModify).has().exactlyAs(filtered);
      }
    }

    public void testAddToFilterFiltered() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C unfiltered = createUnfiltered(contents);
        C filtered1 = filter(unfiltered, EVEN);
        C filtered2 = filter(filtered1, PRIME_DIGIT);

        try {
          filtered2.add(4);
          fail("Expected IllegalArgumentException");
        } catch (IllegalArgumentException expected) {}

        try {
          filtered2.add(3);
          fail("Expected IllegalArgumentException");
        } catch (IllegalArgumentException expected) {}

        filtered2.add(2);
      }
    }

    public void testClearFilterFiltered() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C unfiltered = createUnfiltered(contents);
        C filtered1 = filter(unfiltered, EVEN);
        C filtered2 = filter(filtered1, PRIME_DIGIT);

        C inverseFiltered = filter(createUnfiltered(contents),
            Predicates.not(Predicates.and(EVEN, PRIME_DIGIT)));

        filtered2.clear();
        assertThat(unfiltered).has().exactlyAs(inverseFiltered);
      }
    }
  }

  public static abstract class AbstractFilteredSetTest<C extends Set<Integer>>
      extends AbstractFilteredCollectionTest<C> {
    public void testEqualsAndHashCode() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        Set<Integer> expected = Sets.newHashSet();
        for (Integer i : contents) {
          if (EVEN.apply(i)) {
            expected.add(i);
          }
        }
        new EqualsTester().addEqualityGroup(expected, filter(createUnfiltered(contents), EVEN))
            .testEquals();
      }
    }
  }

  public static abstract class AbstractFilteredSortedSetTest<C extends SortedSet<Integer>>
      extends AbstractFilteredSetTest<C> {
    public void testFirst() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C filtered = filter(createUnfiltered(contents), EVEN);

        try {
          Integer first = filtered.first();
          assertFalse(filtered.isEmpty());
          assertEquals(Ordering.natural().min(filtered), first);
        } catch (NoSuchElementException e) {
          assertTrue(filtered.isEmpty());
        }
      }
    }

    public void testLast() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        C filtered = filter(createUnfiltered(contents), EVEN);

        try {
          Integer first = filtered.last();
          assertFalse(filtered.isEmpty());
          assertEquals(Ordering.natural().max(filtered), first);
        } catch (NoSuchElementException e) {
          assertTrue(filtered.isEmpty());
        }
      }
    }

    @SuppressWarnings("unchecked")
    public void testHeadSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
            assertEquals(
                filter((C) createUnfiltered(contents).headSet(i), EVEN),
                filter(createUnfiltered(contents), EVEN).headSet(i));
        }
      }
    }

    @SuppressWarnings("unchecked")
    public void testTailSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
          assertEquals(
              filter((C) createUnfiltered(contents).tailSet(i), EVEN),
              filter(createUnfiltered(contents), EVEN).tailSet(i));
        }
      }
    }

    @SuppressWarnings("unchecked")
    public void testSubSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
          for (int j = i; j < 10; j++) {
          assertEquals(
              filter((C) createUnfiltered(contents).subSet(i, j), EVEN),
              filter(createUnfiltered(contents), EVEN).subSet(i, j));
          }
        }
      }
    }
  }

  public static abstract class AbstractFilteredNavigableSetTest
      extends AbstractFilteredSortedSetTest<NavigableSet<Integer>> {

    public void testNavigableHeadSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
          for (boolean inclusive : ImmutableList.of(true, false)) {
            assertEquals(
                filter(createUnfiltered(contents).headSet(i, inclusive), EVEN),
                filter(createUnfiltered(contents), EVEN).headSet(i, inclusive));
          }
        }
      }
    }

    public void testNavigableTailSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
          for (boolean inclusive : ImmutableList.of(true, false)) {
            assertEquals(
                filter(createUnfiltered(contents).tailSet(i, inclusive), EVEN),
                filter(createUnfiltered(contents), EVEN).tailSet(i, inclusive));
          }
        }
      }
    }

    public void testNavigableSubSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        for (int i = 0; i < 10; i++) {
          for (int j = i + 1; j < 10; j++) {
            for (boolean fromInclusive : ImmutableList.of(true, false)) {
              for (boolean toInclusive : ImmutableList.of(true, false)) {
                NavigableSet<Integer> filterSubset = filter(
                    createUnfiltered(contents).subSet(i, fromInclusive, j, toInclusive), EVEN);
                NavigableSet<Integer> subsetFilter = filter(createUnfiltered(contents), EVEN)
                    .subSet(i, fromInclusive, j, toInclusive);
                assertEquals(filterSubset, subsetFilter);
              }
            }
          }
        }
      }
    }

    public void testDescendingSet() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN);
        NavigableSet<Integer> unfiltered = createUnfiltered(filtered);

        assertThat(filtered.descendingSet()).has().exactlyAs(unfiltered.descendingSet()).inOrder();
      }
    }

    public void testPollFirst() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN);
        NavigableSet<Integer> unfiltered = createUnfiltered(filtered);

        assertEquals(unfiltered.pollFirst(), filtered.pollFirst());
        assertEquals(unfiltered, filtered);
      }
    }

    public void testPollLast() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN);
        NavigableSet<Integer> unfiltered = createUnfiltered(filtered);

        assertEquals(unfiltered.pollLast(), filtered.pollLast());
        assertEquals(unfiltered, filtered);
      }
    }

    public void testNavigation() {
      for (List<Integer> contents : SAMPLE_INPUTS) {
        NavigableSet<Integer> filtered = filter(createUnfiltered(contents), EVEN);
        NavigableSet<Integer> unfiltered = createUnfiltered(filtered);
        for (int i = 0; i < 10; i++) {
          assertEquals(unfiltered.lower(i), filtered.lower(i));
          assertEquals(unfiltered.floor(i), filtered.floor(i));
          assertEquals(unfiltered.ceiling(i), filtered.ceiling(i));
          assertEquals(unfiltered.higher(i), filtered.higher(i));
        }
      }
    }
  }

  // implementation tests

  public static final class IterablesFilterArrayListTest
      extends AbstractFilteredIterableTest<Iterable<Integer>> {
    @Override
    Iterable<Integer> createUnfiltered(Iterable<Integer> contents) {
      return Lists.newArrayList(contents);
    }

    @Override
    Iterable<Integer> filter(Iterable<Integer> elements, Predicate<? super Integer> predicate) {
      return Iterables.filter(elements, predicate);
    }
  }

  public static final class Collections2FilterArrayListTest
      extends AbstractFilteredCollectionTest<Collection<Integer>> {
    @Override
    Collection<Integer> createUnfiltered(Iterable<Integer> contents) {
      return Lists.newArrayList(contents);
    }

    @Override
    Collection<Integer> filter(Collection<Integer> elements, Predicate<? super Integer> predicate) {
      return Collections2.filter(elements, predicate);
    }
  }

  public static final class SetsFilterHashSetTest
      extends AbstractFilteredSetTest<Set<Integer>> {
    @Override
    Set<Integer> createUnfiltered(Iterable<Integer> contents) {
      return Sets.newHashSet(contents);
    }

    @Override
    Set<Integer> filter(Set<Integer> elements, Predicate<? super Integer> predicate) {
      return Sets.filter(elements, predicate);
    }
  }

  public static final class SetsFilterSortedSetTest
      extends AbstractFilteredSortedSetTest<SortedSet<Integer>> {
    @Override
    SortedSet<Integer> createUnfiltered(Iterable<Integer> contents) {
      final TreeSet<Integer> result = Sets.newTreeSet(contents);
      // we have to make the result not Navigable
      return new ForwardingSortedSet<Integer>() {
        @Override
        protected SortedSet<Integer> delegate() {
          return result;
        }
      };
    }

    @Override
    SortedSet<Integer> filter(SortedSet<Integer> elements, Predicate<? super Integer> predicate) {
      return Sets.filter(elements, predicate);
    }
  }

  public static final class SetsFilterNavigableSetTest extends AbstractFilteredNavigableSetTest {
    @Override
    NavigableSet<Integer> createUnfiltered(Iterable<Integer> contents) {
      return Sets.newTreeSet(contents);
    }

    @Override
    NavigableSet<Integer> filter(
        NavigableSet<Integer> elements, Predicate<? super Integer> predicate) {
      return Sets.filter(elements, predicate);
    }
  }

  /** No-op test so that the class has at least one method, making Maven's test runner happy. */
  public void testNoop() {
  }
}