001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections;
018
019 import java.util.ArrayList;
020 import java.util.Collection;
021 import java.util.Collections;
022 import java.util.Iterator;
023 import java.util.List;
024
025 import org.apache.commons.collections.list.FixedSizeList;
026 import org.apache.commons.collections.list.LazyList;
027 import org.apache.commons.collections.list.PredicatedList;
028 import org.apache.commons.collections.list.SynchronizedList;
029 import org.apache.commons.collections.list.TransformedList;
030 import org.apache.commons.collections.list.TypedList;
031 import org.apache.commons.collections.list.UnmodifiableList;
032
033 /**
034 * Provides utility methods and decorators for {@link List} instances.
035 *
036 * @since Commons Collections 1.0
037 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
038 *
039 * @author Federico Barbieri
040 * @author Peter Donald
041 * @author Paul Jack
042 * @author Stephen Colebourne
043 * @author Neil O'Toole
044 * @author Matthew Hawthorne
045 */
046 public class ListUtils {
047
048 /**
049 * An empty unmodifiable list.
050 * This uses the {@link Collections Collections} implementation
051 * and is provided for completeness.
052 */
053 public static final List EMPTY_LIST = Collections.EMPTY_LIST;
054
055 /**
056 * <code>ListUtils</code> should not normally be instantiated.
057 */
058 public ListUtils() {
059 }
060
061 //-----------------------------------------------------------------------
062 /**
063 * Returns a new list containing all elements that are contained in
064 * both given lists.
065 *
066 * @param list1 the first list
067 * @param list2 the second list
068 * @return the intersection of those two lists
069 * @throws NullPointerException if either list is null
070 */
071 public static List intersection(final List list1, final List list2) {
072 final ArrayList result = new ArrayList();
073 final Iterator iterator = list2.iterator();
074
075 while (iterator.hasNext()) {
076 final Object o = iterator.next();
077
078 if (list1.contains(o)) {
079 result.add(o);
080 }
081 }
082
083 return result;
084 }
085
086 /**
087 * Subtracts all elements in the second list from the first list,
088 * placing the results in a new list.
089 * <p>
090 * This differs from {@link List#removeAll(Collection)} in that
091 * cardinality is respected; if <Code>list1</Code> contains two
092 * occurrences of <Code>null</Code> and <Code>list2</Code> only
093 * contains one occurrence, then the returned list will still contain
094 * one occurrence.
095 *
096 * @param list1 the list to subtract from
097 * @param list2 the list to subtract
098 * @return a new list containing the results
099 * @throws NullPointerException if either list is null
100 */
101 public static List subtract(final List list1, final List list2) {
102 final ArrayList result = new ArrayList(list1);
103 final Iterator iterator = list2.iterator();
104
105 while (iterator.hasNext()) {
106 result.remove(iterator.next());
107 }
108
109 return result;
110 }
111
112 /**
113 * Returns the sum of the given lists. This is their intersection
114 * subtracted from their union.
115 *
116 * @param list1 the first list
117 * @param list2 the second list
118 * @return a new list containing the sum of those lists
119 * @throws NullPointerException if either list is null
120 */
121 public static List sum(final List list1, final List list2) {
122 return subtract(union(list1, list2), intersection(list1, list2));
123 }
124
125 /**
126 * Returns a new list containing the second list appended to the
127 * first list. The {@link List#addAll(Collection)} operation is
128 * used to append the two given lists into a new list.
129 *
130 * @param list1 the first list
131 * @param list2 the second list
132 * @return a new list containing the union of those lists
133 * @throws NullPointerException if either list is null
134 */
135 public static List union(final List list1, final List list2) {
136 final ArrayList result = new ArrayList(list1);
137 result.addAll(list2);
138 return result;
139 }
140
141 /**
142 * Tests two lists for value-equality as per the equality contract in
143 * {@link java.util.List#equals(java.lang.Object)}.
144 * <p>
145 * This method is useful for implementing <code>List</code> when you cannot
146 * extend AbstractList. The method takes Collection instances to enable other
147 * collection types to use the List implementation algorithm.
148 * <p>
149 * The relevant text (slightly paraphrased as this is a static method) is:
150 * <blockquote>
151 * Compares the two list objects for equality. Returns
152 * <tt>true</tt> if and only if both
153 * lists have the same size, and all corresponding pairs of elements in
154 * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
155 * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
156 * e1.equals(e2))</tt>.) In other words, two lists are defined to be
157 * equal if they contain the same elements in the same order. This
158 * definition ensures that the equals method works properly across
159 * different implementations of the <tt>List</tt> interface.
160 * </blockquote>
161 *
162 * <b>Note:</b> The behaviour of this method is undefined if the lists are
163 * modified during the equals comparison.
164 *
165 * @see java.util.List
166 * @param list1 the first list, may be null
167 * @param list2 the second list, may be null
168 * @return whether the lists are equal by value comparison
169 */
170 public static boolean isEqualList(final Collection list1, final Collection list2) {
171 if (list1 == list2) {
172 return true;
173 }
174 if (list1 == null || list2 == null || list1.size() != list2.size()) {
175 return false;
176 }
177
178 Iterator it1 = list1.iterator();
179 Iterator it2 = list2.iterator();
180 Object obj1 = null;
181 Object obj2 = null;
182
183 while (it1.hasNext() && it2.hasNext()) {
184 obj1 = it1.next();
185 obj2 = it2.next();
186
187 if (!(obj1 == null ? obj2 == null : obj1.equals(obj2))) {
188 return false;
189 }
190 }
191
192 return !(it1.hasNext() || it2.hasNext());
193 }
194
195 /**
196 * Generates a hash code using the algorithm specified in
197 * {@link java.util.List#hashCode()}.
198 * <p>
199 * This method is useful for implementing <code>List</code> when you cannot
200 * extend AbstractList. The method takes Collection instances to enable other
201 * collection types to use the List implementation algorithm.
202 *
203 * @see java.util.List#hashCode()
204 * @param list the list to generate the hashCode for, may be null
205 * @return the hash code
206 */
207 public static int hashCodeForList(final Collection list) {
208 if (list == null) {
209 return 0;
210 }
211 int hashCode = 1;
212 Iterator it = list.iterator();
213 Object obj = null;
214
215 while (it.hasNext()) {
216 obj = it.next();
217 hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
218 }
219 return hashCode;
220 }
221
222 //-----------------------------------------------------------------------
223 /**
224 * Returns a List containing all the elements in <code>collection</code>
225 * that are also in <code>retain</code>. The cardinality of an element <code>e</code>
226 * in the returned list is the same as the cardinality of <code>e</code>
227 * in <code>collection</code> unless <code>retain</code> does not contain <code>e</code>, in which
228 * case the cardinality is zero. This method is useful if you do not wish to modify
229 * the collection <code>c</code> and thus cannot call <code>collection.retainAll(retain);</code>.
230 *
231 * @param collection the collection whose contents are the target of the #retailAll operation
232 * @param retain the collection containing the elements to be retained in the returned collection
233 * @return a <code>List</code> containing all the elements of <code>c</code>
234 * that occur at least once in <code>retain</code>.
235 * @throws NullPointerException if either parameter is null
236 * @since Commons Collections 3.2
237 */
238 public static List retainAll(Collection collection, Collection retain) {
239 List list = new ArrayList(Math.min(collection.size(), retain.size()));
240
241 for (Iterator iter = collection.iterator(); iter.hasNext();) {
242 Object obj = iter.next();
243 if (retain.contains(obj)) {
244 list.add(obj);
245 }
246 }
247 return list;
248 }
249
250 /**
251 * Removes the elements in <code>remove</code> from <code>collection</code>. That is, this
252 * method returns a list containing all the elements in <code>c</code>
253 * that are not in <code>remove</code>. The cardinality of an element <code>e</code>
254 * in the returned collection is the same as the cardinality of <code>e</code>
255 * in <code>collection</code> unless <code>remove</code> contains <code>e</code>, in which
256 * case the cardinality is zero. This method is useful if you do not wish to modify
257 * <code>collection</code> and thus cannot call <code>collection.removeAll(remove);</code>.
258 *
259 * @param collection the collection from which items are removed (in the returned collection)
260 * @param remove the items to be removed from the returned <code>collection</code>
261 * @return a <code>List</code> containing all the elements of <code>c</code> except
262 * any elements that also occur in <code>remove</code>.
263 * @throws NullPointerException if either parameter is null
264 * @since Commons Collections 3.2
265 */
266 public static List removeAll(Collection collection, Collection remove) {
267 List list = new ArrayList();
268 for (Iterator iter = collection.iterator(); iter.hasNext();) {
269 Object obj = iter.next();
270 if (remove.contains(obj) == false) {
271 list.add(obj);
272 }
273 }
274 return list;
275 }
276
277 //-----------------------------------------------------------------------
278 /**
279 * Returns a synchronized list backed by the given list.
280 * <p>
281 * You must manually synchronize on the returned buffer's iterator to
282 * avoid non-deterministic behavior:
283 *
284 * <pre>
285 * List list = ListUtils.synchronizedList(myList);
286 * synchronized (list) {
287 * Iterator i = list.iterator();
288 * while (i.hasNext()) {
289 * process (i.next());
290 * }
291 * }
292 * </pre>
293 *
294 * This method uses the implementation in the decorators subpackage.
295 *
296 * @param list the list to synchronize, must not be null
297 * @return a synchronized list backed by the given list
298 * @throws IllegalArgumentException if the list is null
299 */
300 public static List synchronizedList(List list) {
301 return SynchronizedList.decorate(list);
302 }
303
304 /**
305 * Returns an unmodifiable list backed by the given list.
306 * <p>
307 * This method uses the implementation in the decorators subpackage.
308 *
309 * @param list the list to make unmodifiable, must not be null
310 * @return an unmodifiable list backed by the given list
311 * @throws IllegalArgumentException if the list is null
312 */
313 public static List unmodifiableList(List list) {
314 return UnmodifiableList.decorate(list);
315 }
316
317 /**
318 * Returns a predicated (validating) list backed by the given list.
319 * <p>
320 * Only objects that pass the test in the given predicate can be added to the list.
321 * Trying to add an invalid object results in an IllegalArgumentException.
322 * It is important not to use the original list after invoking this method,
323 * as it is a backdoor for adding invalid objects.
324 *
325 * @param list the list to predicate, must not be null
326 * @param predicate the predicate for the list, must not be null
327 * @return a predicated list backed by the given list
328 * @throws IllegalArgumentException if the List or Predicate is null
329 */
330 public static List predicatedList(List list, Predicate predicate) {
331 return PredicatedList.decorate(list, predicate);
332 }
333
334 /**
335 * Returns a typed list backed by the given list.
336 * <p>
337 * Only objects of the specified type can be added to the list.
338 *
339 * @param list the list to limit to a specific type, must not be null
340 * @param type the type of objects which may be added to the list
341 * @return a typed list backed by the specified list
342 */
343 public static List typedList(List list, Class type) {
344 return TypedList.decorate(list, type);
345 }
346
347 /**
348 * Returns a transformed list backed by the given list.
349 * <p>
350 * Each object is passed through the transformer as it is added to the
351 * List. It is important not to use the original list after invoking this
352 * method, as it is a backdoor for adding untransformed objects.
353 *
354 * @param list the list to predicate, must not be null
355 * @param transformer the transformer for the list, must not be null
356 * @return a transformed list backed by the given list
357 * @throws IllegalArgumentException if the List or Transformer is null
358 */
359 public static List transformedList(List list, Transformer transformer) {
360 return TransformedList.decorate(list, transformer);
361 }
362
363 /**
364 * Returns a "lazy" list whose elements will be created on demand.
365 * <p>
366 * When the index passed to the returned list's {@link List#get(int) get}
367 * method is greater than the list's size, then the factory will be used
368 * to create a new object and that object will be inserted at that index.
369 * <p>
370 * For instance:
371 *
372 * <pre>
373 * Factory factory = new Factory() {
374 * public Object create() {
375 * return new Date();
376 * }
377 * }
378 * List lazy = ListUtils.lazyList(new ArrayList(), factory);
379 * Object obj = lazy.get(3);
380 * </pre>
381 *
382 * After the above code is executed, <code>obj</code> will contain
383 * a new <code>Date</code> instance. Furthermore, that <code>Date</code>
384 * instance is the fourth element in the list. The first, second,
385 * and third element are all set to <code>null</code>.
386 *
387 * @param list the list to make lazy, must not be null
388 * @param factory the factory for creating new objects, must not be null
389 * @return a lazy list backed by the given list
390 * @throws IllegalArgumentException if the List or Factory is null
391 */
392 public static List lazyList(List list, Factory factory) {
393 return LazyList.decorate(list, factory);
394 }
395
396 /**
397 * Returns a fixed-sized list backed by the given list.
398 * Elements may not be added or removed from the returned list, but
399 * existing elements can be changed (for instance, via the
400 * {@link List#set(int,Object)} method).
401 *
402 * @param list the list whose size to fix, must not be null
403 * @return a fixed-size list backed by that list
404 * @throws IllegalArgumentException if the List is null
405 */
406 public static List fixedSizeList(List list) {
407 return FixedSizeList.decorate(list);
408 }
409
410 }