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    }