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