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