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
028 import java.util.AbstractCollection;
029 import java.util.ArrayList;
030 import java.util.Collection;
031 import java.util.Collections;
032 import 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
043 public 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 }