    001    /*
    002     * Copyright (C) 2008 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021
    022    import com.google.common.annotations.GwtCompatible;
    023    import com.google.common.base.Function;
    024    import com.google.common.base.Joiner;
    025    import com.google.common.base.Predicate;
    026    import com.google.common.base.Predicates;
    027    import com.google.common.primitives.Ints;
    028
    029    import java.util.AbstractCollection;
    030    import java.util.ArrayList;
    031    import java.util.Collection;
    032    import java.util.Collections;
    033    import java.util.Iterator;
    034    import java.util.List;
    035
    036    /**
    037     * Provides static methods for working with {@code Collection} instances.
    038     *
    039     * @author Chris Povirk
    040     * @author Mike Bostock
    041     * @author Jared Levy
    042     * @since 2.0 (imported from Google Collections Library)
    043     */
    044    @GwtCompatible
    045    public final class Collections2 {
    046      private Collections2() {}
    047
    048      /**
    049       * Returns the elements of {@code unfiltered} that satisfy a predicate. The
    050       * returned collection is a live view of {@code unfiltered}; changes to one
    051       * affect the other.
    052       *
    053       * <p>The resulting collection's iterator does not support {@code remove()},
    054       * but all other collection methods are supported. When given an element that
    055       * doesn't satisfy the predicate, the collection's {@code add()} and {@code
    056       * addAll()} methods throw an {@link IllegalArgumentException}. When methods
    057       * such as {@code removeAll()} and {@code clear()} are called on the filtered
    058       * collection, only elements that satisfy the filter will be removed from the
    059       * underlying collection.
    060       *
    061       * <p>The returned collection isn't threadsafe or serializable, even if
    062       * {@code unfiltered} is.
    063       *
    064       * <p>Many of the filtered collection's methods, such as {@code size()},
    065       * iterate across every element in the underlying collection and determine
    066       * which elements satisfy the filter. When a live view is <i>not</i> needed,
    067       * it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
    068       * and use the copy.
    069       *
    070       * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>,
    071       * as documented at {@link Predicate#apply}. Do not provide a predicate such
    072       * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
    073       * with equals. (See {@link Iterables#filter(Iterable, Class)} for related
    074       * functionality.)
    075       */
    076      // TODO(kevinb): how can we omit that Iterables link when building gwt
    077      // javadoc?
    078      public static <E> Collection<E> filter(
    079          Collection<E> unfiltered, Predicate<? super E> predicate) {
    080        if (unfiltered instanceof FilteredCollection) {
    081          // Support clear(), removeAll(), and retainAll() when filtering a filtered
    082          // collection.
    083          return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
    084        }
    085
    086        return new FilteredCollection<E>(
    087            checkNotNull(unfiltered), checkNotNull(predicate));
    088      }
    089
    090      /**
    091       * Delegates to {@link Collection#contains}. Returns {@code false} if the
    092       * {@code contains} method throws a {@code ClassCastException}.
    093       */
    094      static boolean safeContains(Collection<?> collection, Object object) {
    095        try {
    096          return collection.contains(object);
    097        } catch (ClassCastException e) {
    098          return false;
    099        }
    100      }
    101
    102      static class FilteredCollection<E> implements Collection<E> {
    103        final Collection<E> unfiltered;
    104        final Predicate<? super E> predicate;
    105
    106        FilteredCollection(Collection<E> unfiltered,
    107            Predicate<? super E> predicate) {
    108          this.unfiltered = unfiltered;
    109          this.predicate = predicate;
    110        }
    111
    112        FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) {
    113          return new FilteredCollection<E>(unfiltered,
    114              Predicates.<E>and(predicate, newPredicate));
    115          // .<E> above needed to compile in JDK 5
    116        }
    117
    118        @Override
    119        public boolean add(E element) {
    120          checkArgument(predicate.apply(element));
    121          return unfiltered.add(element);
    122        }
    123
    124        @Override
    125        public boolean addAll(Collection<? extends E> collection) {
    126          for (E element : collection) {
    127            checkArgument(predicate.apply(element));
    128          }
    129          return unfiltered.addAll(collection);
    130        }
    131
    132        @Override
    133        public void clear() {
    134          Iterables.removeIf(unfiltered, predicate);
    135        }
    136
    137        @Override
    138        public boolean contains(Object element) {
    139          try {
    140            // unsafe cast can result in a CCE from predicate.apply(), which we
    141            // will catch
    142            @SuppressWarnings("unchecked")
    143            E e = (E) element;
    144
    145            /*
    146             * We check whether e satisfies the predicate, when we really mean to
    147             * check whether the element contained in the set does. This is ok as
    148             * long as the predicate is consistent with equals, as required.
    149             */
    150            return predicate.apply(e) && unfiltered.contains(element);
    151          } catch (NullPointerException e) {
    152            return false;
    153          } catch (ClassCastException e) {
    154            return false;
    155          }
    156        }
    157
    158        @Override
    159        public boolean containsAll(Collection<?> collection) {
    160          for (Object element : collection) {
    161            if (!contains(element)) {
    162              return false;
    163            }
    164          }
    165          return true;
    166        }
    167
    168        @Override
    169        public boolean isEmpty() {
    170          return !Iterators.any(unfiltered.iterator(), predicate);
    171        }
    172
    173        @Override
    174        public Iterator<E> iterator() {
    175          return Iterators.filter(unfiltered.iterator(), predicate);
    176        }
    177
    178        @Override
    179        public boolean remove(Object element) {
    180          try {
    181            // unsafe cast can result in a CCE from predicate.apply(), which we
    182            // will catch
    183            @SuppressWarnings("unchecked")
    184            E e = (E) element;
    185
    186            // See comment in contains() concerning predicate.apply(e)
    187            return predicate.apply(e) && unfiltered.remove(element);
    188          } catch (NullPointerException e) {
    189            return false;
    190          } catch (ClassCastException e) {
    191            return false;
    192          }
    193        }
    194
    195        @Override
    196        public boolean removeAll(final Collection<?> collection) {
    197          checkNotNull(collection);
    198          Predicate<E> combinedPredicate = new Predicate<E>() {
    199            @Override
    200            public boolean apply(E input) {
    201              return predicate.apply(input) && collection.contains(input);
    202            }
    203          };
    204          return Iterables.removeIf(unfiltered, combinedPredicate);
    205        }
    206
    207        @Override
    208        public boolean retainAll(final Collection<?> collection) {
    209          checkNotNull(collection);
    210          Predicate<E> combinedPredicate = new Predicate<E>() {
    211            @Override
    212            public boolean apply(E input) {
    213              // See comment in contains() concerning predicate.apply(e)
    214              return predicate.apply(input) && !collection.contains(input);
    215            }
    216          };
    217          return Iterables.removeIf(unfiltered, combinedPredicate);
    218        }
    219
    220        @Override
    221        public int size() {
    222          return Iterators.size(iterator());
    223        }
    224
    225        @Override
    226        public Object[] toArray() {
    227          // creating an ArrayList so filtering happens once
    228          return Lists.newArrayList(iterator()).toArray();
    229        }
    230
    231        @Override
    232        public <T> T[] toArray(T[] array) {
    233          return Lists.newArrayList(iterator()).toArray(array);
    234        }
    235
    236        @Override public String toString() {
    237          return Iterators.toString(iterator());
    238        }
    239      }
    240
    241      /**
    242       * Returns a collection that applies {@code function} to each element of
    243       * {@code fromCollection}. The returned collection is a live view of {@code
    244       * fromCollection}; changes to one affect the other.
    245       *
    246       * <p>The returned collection's {@code add()} and {@code addAll()} methods
    247       * throw an {@link UnsupportedOperationException}. All other collection
    248       * methods are supported, as long as {@code fromCollection} supports them.
    249       *
    250       * <p>The returned collection isn't threadsafe or serializable, even if
    251       * {@code fromCollection} is.
    252       *
    253       * <p>When a live view is <i>not</i> needed, it may be faster to copy the
    254       * transformed collection and use the copy.
    255       *
    256       * <p>If the input {@code Collection} is known to be a {@code List}, consider
    257       * {@link Lists#transform}. If only an {@code Iterable} is available, use
    258       * {@link Iterables#transform}.
    259       */
    260      public static <F, T> Collection<T> transform(Collection<F> fromCollection,
    261          Function<? super F, T> function) {
    262        return new TransformedCollection<F, T>(fromCollection, function);
    263      }
    264
    265      static class TransformedCollection<F, T> extends AbstractCollection<T> {
    266        final Collection<F> fromCollection;
    267        final Function<? super F, ? extends T> function;
    268
    269        TransformedCollection(Collection<F> fromCollection,
    270            Function<? super F, ? extends T> function) {
    271          this.fromCollection = checkNotNull(fromCollection);
    272          this.function = checkNotNull(function);
    273        }
    274
    275        @Override public void clear() {
    276          fromCollection.clear();
    277        }
    278
    279        @Override public boolean isEmpty() {
    280          return fromCollection.isEmpty();
    281        }
    282
    283        @Override public Iterator<T> iterator() {
    284          return Iterators.transform(fromCollection.iterator(), function);
    285        }
    286
    287        @Override public int size() {
    288          return fromCollection.size();
    289        }
    290      }
    291
    292      /**
    293       * Returns {@code true} if the collection {@code self} contains all of the
    294       * elements in the collection {@code c}.
    295       *
    296       * <p>This method iterates over the specified collection {@code c}, checking
    297       * each element returned by the iterator in turn to see if it is contained in
    298       * the specified collection {@code self}. If all elements are so contained,
    299       * {@code true} is returned, otherwise {@code false}.
    300       *
    301       * @param self a collection which might contain all elements in {@code c}
    302       * @param c a collection whose elements might be contained by {@code self}
    303       */
    304      static boolean containsAllImpl(Collection<?> self, Collection<?> c) {
    305        checkNotNull(self);
    306        for (Object o : c) {
    307          if (!self.contains(o)) {
    308            return false;
    309          }
    310        }
    311        return true;
    312      }
    313
    314      /**
    315       * An implementation of {@link Collection#toString()}.
    316       */
    317      static String toStringImpl(final Collection<?> collection) {
    318        StringBuilder sb
    319            = newStringBuilderForCollection(collection.size()).append('[');
    320        STANDARD_JOINER.appendTo(
    321            sb, Iterables.transform(collection, new Function<Object, Object>() {
    322              @Override public Object apply(Object input) {
    323                return input == collection ? "(this Collection)" : input;
    324              }
    325            }));
    326        return sb.append(']').toString();
    327      }
    328
    329      /**
    330       * Returns best-effort-sized StringBuilder based on the given collection size.
    331       */
    332      static StringBuilder newStringBuilderForCollection(int size) {
    333        checkArgument(size >= 0, "size must be non-negative");
    334        return new StringBuilder((int) Math.min(size * 8L, Ints.MAX_POWER_OF_TWO));
    335      }
    336
    337      /**
    338       * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
    339       */
    340      static <T> Collection<T> cast(Iterable<T> iterable) {
    341        return (Collection<T>) iterable;
    342      }
    343
    344      static final Joiner STANDARD_JOINER = Joiner.on(", ");
    345
    346      // TODO(user): Maybe move the mathematical methods to a separate
    347      // package-permission class.
    348    }