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 }