1/*
2 * Copyright (C) 2008 Google Inc.
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;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.base.Function;
21import com.google.common.base.Joiner;
22import com.google.common.base.Predicate;
23import com.google.common.base.Predicates;
24
25import java.util.AbstractCollection;
26import java.util.Collection;
27import java.util.Iterator;
28import java.util.Set;
29
30import javax.annotation.Nullable;
31
32import static com.google.common.base.Preconditions.checkArgument;
33import static com.google.common.base.Preconditions.checkNotNull;
34
35/**
36 * Provides static methods for working with {@code Collection} instances.
37 *
38 * @author Chris Povirk
39 * @author Mike Bostock
40 * @author Jared Levy
41 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library)
42 */
43@GwtCompatible
44public final class Collections2 {
45  private Collections2() {}
46
47  /**
48   * Returns {@code true} if the collection {@code self} contains all of the
49   * elements in the collection {@code c}.
50   *
51   * <p>This method iterates over the specified collection {@code c}, checking
52   * each element returned by the iterator in turn to see if it is contained in
53   * the specified collection {@code self}. If all elements are so contained,
54   * {@code true} is returned, otherwise {@code false}.
55   *
56   * @param self a collection which might contain all elements in {@code c}
57   * @param c a collection whose elements might be contained by {@code self}
58   */
59  // TODO: Make public?
60  static boolean containsAll(Collection<?> self, Collection<?> c) {
61    checkNotNull(self);
62    for (Object o : c) {
63      if (!self.contains(o)) {
64        return false;
65      }
66    }
67    return true;
68  }
69
70  /**
71   * Converts an iterable into a collection. If the iterable is already a
72   * collection, it is returned. Otherwise, an {@link java.util.ArrayList} is
73   * created with the contents of the iterable in the same iteration order.
74   */
75  static <E> Collection<E> toCollection(Iterable<E> iterable) {
76    return (iterable instanceof Collection)
77        ? (Collection<E>) iterable : Lists.newArrayList(iterable);
78  }
79
80  /**
81   * Returns the elements of {@code unfiltered} that satisfy a predicate. The
82   * returned collection is a live view of {@code unfiltered}; changes to one
83   * affect the other.
84   *
85   * <p>The resulting collection's iterator does not support {@code remove()},
86   * but all other collection methods are supported. The collection's
87   * {@code add()} and {@code addAll()} methods throw an
88   * {@link IllegalArgumentException} if an element that doesn't satisfy the
89   * predicate is provided. When methods such as {@code removeAll()} and
90   * {@code clear()} are called on the filtered collection, only elements that
91   * satisfy the filter will be removed from the underlying collection.
92   *
93   * <p>The returned collection isn't threadsafe or serializable, even if
94   * {@code unfiltered} is.
95   *
96   * <p>Many of the filtered collection's methods, such as {@code size()},
97   * iterate across every element in the underlying collection and determine
98   * which elements satisfy the filter. When a live view is <i>not</i> needed,
99   * it may be faster to copy {@code Iterables.filter(unfiltered, predicate)}
100   * and use the copy.
101   */
102  public static <E> Collection<E> filter(
103      Collection<E> unfiltered, Predicate<? super E> predicate) {
104    if (unfiltered instanceof FilteredCollection) {
105      // Support clear(), removeAll(), and retainAll() when filtering a filtered
106      // collection.
107      return ((FilteredCollection<E>) unfiltered).createCombined(predicate);
108    }
109
110    return new FilteredCollection<E>(
111        checkNotNull(unfiltered), checkNotNull(predicate));
112  }
113
114  /**
115   * Delegates to {@link Collection#contains}.  Returns {@code false} on {@code
116   * ClassCastException}
117   */
118  static boolean safeContains(Collection<?> collection, Object object) {
119    try {
120      return collection.contains(object);
121    } catch (ClassCastException e) {
122      return false;
123    }
124  }
125
126  static class FilteredCollection<E> implements Collection<E> {
127    final Collection<E> unfiltered;
128    final Predicate<? super E> predicate;
129
130    FilteredCollection(Collection<E> unfiltered,
131        Predicate<? super E> predicate) {
132      this.unfiltered = unfiltered;
133      this.predicate = predicate;
134    }
135
136    FilteredCollection<E> createCombined(Predicate<? super E> newPredicate) {
137      return new FilteredCollection<E>(unfiltered,
138          Predicates.<E>and(predicate, newPredicate));
139      // .<E> above needed to compile in JDK 5
140    }
141
142    public boolean add(E element) {
143      checkArgument(predicate.apply(element));
144      return unfiltered.add(element);
145    }
146
147    public boolean addAll(Collection<? extends E> collection) {
148      for (E element : collection) {
149        checkArgument(predicate.apply(element));
150      }
151      return unfiltered.addAll(collection);
152    }
153
154    public void clear() {
155      Iterables.removeIf(unfiltered, predicate);
156    }
157
158    public boolean contains(Object element) {
159      try {
160        // unsafe cast can result in a CCE from predicate.apply(), which we
161        // will catch
162        @SuppressWarnings("unchecked")
163        E e = (E) element;
164        return predicate.apply(e) && unfiltered.contains(element);
165      } catch (NullPointerException e) {
166        return false;
167      } catch (ClassCastException e) {
168        return false;
169      }
170    }
171
172    public boolean containsAll(Collection<?> collection) {
173      for (Object element : collection) {
174        if (!contains(element)) {
175          return false;
176        }
177      }
178      return true;
179    }
180
181    public boolean isEmpty() {
182      return !Iterators.any(unfiltered.iterator(), predicate);
183    }
184
185    public Iterator<E> iterator() {
186      return Iterators.filter(unfiltered.iterator(), predicate);
187    }
188
189    public boolean remove(Object element) {
190      try {
191        // unsafe cast can result in a CCE from predicate.apply(), which we
192        // will catch
193        @SuppressWarnings("unchecked")
194        E e = (E) element;
195        return predicate.apply(e) && unfiltered.remove(element);
196      } catch (NullPointerException e) {
197        return false;
198      } catch (ClassCastException e) {
199        return false;
200      }
201    }
202
203    public boolean removeAll(final Collection<?> collection) {
204      checkNotNull(collection);
205      Predicate<E> combinedPredicate = new Predicate<E>() {
206        public boolean apply(E input) {
207          return predicate.apply(input) && collection.contains(input);
208        }
209      };
210      return Iterables.removeIf(unfiltered, combinedPredicate);
211    }
212
213    public boolean retainAll(final Collection<?> collection) {
214      checkNotNull(collection);
215      Predicate<E> combinedPredicate = new Predicate<E>() {
216        public boolean apply(E input) {
217          return predicate.apply(input) && !collection.contains(input);
218        }
219      };
220      return Iterables.removeIf(unfiltered, combinedPredicate);
221    }
222
223    public int size() {
224      return Iterators.size(iterator());
225    }
226
227    public Object[] toArray() {
228      // creating an ArrayList so filtering happens once
229      return Lists.newArrayList(iterator()).toArray();
230    }
231
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  public static <F, T> Collection<T> transform(Collection<F> fromCollection,
257      Function<? super F, T> function) {
258    return new TransformedCollection<F, T>(fromCollection, function);
259  }
260
261  static class TransformedCollection<F, T> extends AbstractCollection<T> {
262    final Collection<F> fromCollection;
263    final Function<? super F, ? extends T> function;
264
265    TransformedCollection(Collection<F> fromCollection,
266        Function<? super F, ? extends T> function) {
267      this.fromCollection = checkNotNull(fromCollection);
268      this.function = checkNotNull(function);
269    }
270
271    @Override public void clear() {
272      fromCollection.clear();
273    }
274
275    @Override public boolean isEmpty() {
276      return fromCollection.isEmpty();
277    }
278
279    @Override public Iterator<T> iterator() {
280      return Iterators.transform(fromCollection.iterator(), function);
281    }
282
283    @Override public int size() {
284      return fromCollection.size();
285    }
286  }
287
288  static boolean setEquals(Set<?> thisSet, @Nullable Object object) {
289    if (object == thisSet) {
290      return true;
291    }
292    if (object instanceof Set) {
293      Set<?> thatSet = (Set<?>) object;
294      return thisSet.size() == thatSet.size()
295          && thisSet.containsAll(thatSet);
296    }
297    return false;
298  }
299
300  static final Joiner standardJoiner = Joiner.on(", ");
301}
302