| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.collections4; |
| |
| import java.util.AbstractList; |
| import java.util.ArrayList; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.List; |
| |
| import org.apache.commons.collections4.bag.HashBag; |
| import org.apache.commons.collections4.functors.DefaultEquator; |
| import org.apache.commons.collections4.list.FixedSizeList; |
| import org.apache.commons.collections4.list.LazyList; |
| import org.apache.commons.collections4.list.PredicatedList; |
| import org.apache.commons.collections4.list.TransformedList; |
| import org.apache.commons.collections4.list.UnmodifiableList; |
| import org.apache.commons.collections4.sequence.CommandVisitor; |
| import org.apache.commons.collections4.sequence.EditScript; |
| import org.apache.commons.collections4.sequence.SequencesComparator; |
| |
| /** |
| * Provides utility methods and decorators for {@link List} instances. |
| * |
| * @since 1.0 |
| * @version $Id$ |
| */ |
| public class ListUtils { |
| |
| /** |
| * <code>ListUtils</code> should not normally be instantiated. |
| */ |
| private ListUtils() {} |
| |
| //----------------------------------------------------------------------- |
| |
| /** |
| * Returns an immutable empty list if the argument is <code>null</code>, |
| * or the argument itself otherwise. |
| * |
| * @param <T> the element type |
| * @param list the list, possibly <code>null</code> |
| * @return an empty list if the argument is <code>null</code> |
| */ |
| public static <T> List<T> emptyIfNull(final List<T> list) { |
| return list == null ? Collections.<T>emptyList() : list; |
| } |
| |
| /** |
| * Returns either the passed in list, or if the list is {@code null}, |
| * the value of {@code defaultList}. |
| * |
| * @param <T> the element type |
| * @param list the list, possibly {@code null} |
| * @param defaultList the returned values if list is {@code null} |
| * @return an empty list if the argument is <code>null</code> |
| * @since 4.0 |
| */ |
| public static <T> List<T> defaultIfNull(final List<T> list, final List<T> defaultList) { |
| return list == null ? defaultList : list; |
| } |
| |
| /** |
| * Returns a new list containing all elements that are contained in |
| * both given lists. |
| * |
| * @param <E> the element type |
| * @param list1 the first list |
| * @param list2 the second list |
| * @return the intersection of those two lists |
| * @throws NullPointerException if either list is null |
| */ |
| public static <E> List<E> intersection(final List<? extends E> list1, final List<? extends E> list2) { |
| final List<E> result = new ArrayList<E>(); |
| |
| List<? extends E> smaller = list1; |
| List<? extends E> larger = list2; |
| if (list1.size() > list2.size()) { |
| smaller = list2; |
| larger = list1; |
| } |
| |
| final HashSet<E> hashSet = new HashSet<E>(smaller); |
| |
| for (final E e : larger) { |
| if (hashSet.contains(e)) { |
| result.add(e); |
| hashSet.remove(e); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Subtracts all elements in the second list from the first list, |
| * placing the results in a new list. |
| * <p> |
| * This differs from {@link List#removeAll(Collection)} in that |
| * cardinality is respected; if <Code>list1</Code> contains two |
| * occurrences of <Code>null</Code> and <Code>list2</Code> only |
| * contains one occurrence, then the returned list will still contain |
| * one occurrence. |
| * |
| * @param <E> the element type |
| * @param list1 the list to subtract from |
| * @param list2 the list to subtract |
| * @return a new list containing the results |
| * @throws NullPointerException if either list is null |
| */ |
| public static <E> List<E> subtract(final List<E> list1, final List<? extends E> list2) { |
| final ArrayList<E> result = new ArrayList<E>(); |
| final HashBag<E> bag = new HashBag<E>(list2); |
| for (final E e : list1) { |
| if (!bag.remove(e, 1)) { |
| result.add(e); |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Returns the sum of the given lists. This is their intersection |
| * subtracted from their union. |
| * |
| * @param <E> the element type |
| * @param list1 the first list |
| * @param list2 the second list |
| * @return a new list containing the sum of those lists |
| * @throws NullPointerException if either list is null |
| */ |
| public static <E> List<E> sum(final List<? extends E> list1, final List<? extends E> list2) { |
| return subtract(union(list1, list2), intersection(list1, list2)); |
| } |
| |
| /** |
| * Returns a new list containing the second list appended to the |
| * first list. The {@link List#addAll(Collection)} operation is |
| * used to append the two given lists into a new list. |
| * |
| * @param <E> the element type |
| * @param list1 the first list |
| * @param list2 the second list |
| * @return a new list containing the union of those lists |
| * @throws NullPointerException if either list is null |
| */ |
| public static <E> List<E> union(final List<? extends E> list1, final List<? extends E> list2) { |
| final ArrayList<E> result = new ArrayList<E>(list1); |
| result.addAll(list2); |
| return result; |
| } |
| |
| /** |
| * Selects all elements from input collection which match the given |
| * predicate into an output list. |
| * <p> |
| * A <code>null</code> predicate matches no elements. |
| * |
| * @param <E> the element type |
| * @param inputCollection the collection to get the input from, may not be null |
| * @param predicate the predicate to use, may be null |
| * @return the elements matching the predicate (new list) |
| * @throws NullPointerException if the input list is null |
| * |
| * @since 4.0 |
| * @see CollectionUtils#select(Iterable, Predicate) |
| */ |
| public static <E> List<E> select(final Collection<? extends E> inputCollection, |
| final Predicate<? super E> predicate) { |
| return CollectionUtils.select(inputCollection, predicate, new ArrayList<E>(inputCollection.size())); |
| } |
| |
| /** |
| * Selects all elements from inputCollection which don't match the given |
| * predicate into an output collection. |
| * <p> |
| * If the input predicate is <code>null</code>, the result is an empty list. |
| * |
| * @param <E> the element type |
| * @param inputCollection the collection to get the input from, may not be null |
| * @param predicate the predicate to use, may be null |
| * @return the elements <b>not</b> matching the predicate (new list) |
| * @throws NullPointerException if the input collection is null |
| * |
| * @since 4.0 |
| * @see CollectionUtils#selectRejected(Iterable, Predicate) |
| */ |
| public static <E> List<E> selectRejected(final Collection<? extends E> inputCollection, |
| final Predicate<? super E> predicate) { |
| return CollectionUtils.selectRejected(inputCollection, predicate, new ArrayList<E>(inputCollection.size())); |
| } |
| |
| /** |
| * Tests two lists for value-equality as per the equality contract in |
| * {@link java.util.List#equals(java.lang.Object)}. |
| * <p> |
| * This method is useful for implementing <code>List</code> when you cannot |
| * extend AbstractList. The method takes Collection instances to enable other |
| * collection types to use the List implementation algorithm. |
| * <p> |
| * The relevant text (slightly paraphrased as this is a static method) is: |
| * <blockquote> |
| * Compares the two list objects for equality. Returns |
| * {@code true} if and only if both |
| * lists have the same size, and all corresponding pairs of elements in |
| * the two lists are <i>equal</i>. (Two elements {@code e1} and |
| * {@code e2} are <i>equal</i> if <tt>(e1==null ? e2==null : |
| * e1.equals(e2))</tt>.) In other words, two lists are defined to be |
| * equal if they contain the same elements in the same order. This |
| * definition ensures that the equals method works properly across |
| * different implementations of the {@code List} interface. |
| * </blockquote> |
| * |
| * <b>Note:</b> The behaviour of this method is undefined if the lists are |
| * modified during the equals comparison. |
| * |
| * @see java.util.List |
| * @param list1 the first list, may be null |
| * @param list2 the second list, may be null |
| * @return whether the lists are equal by value comparison |
| */ |
| public static boolean isEqualList(final Collection<?> list1, final Collection<?> list2) { |
| if (list1 == list2) { |
| return true; |
| } |
| if (list1 == null || list2 == null || list1.size() != list2.size()) { |
| return false; |
| } |
| |
| final Iterator<?> it1 = list1.iterator(); |
| final Iterator<?> it2 = list2.iterator(); |
| Object obj1 = null; |
| Object obj2 = null; |
| |
| while (it1.hasNext() && it2.hasNext()) { |
| obj1 = it1.next(); |
| obj2 = it2.next(); |
| |
| if (!(obj1 == null ? obj2 == null : obj1.equals(obj2))) { |
| return false; |
| } |
| } |
| |
| return !(it1.hasNext() || it2.hasNext()); |
| } |
| |
| /** |
| * Generates a hash code using the algorithm specified in |
| * {@link java.util.List#hashCode()}. |
| * <p> |
| * This method is useful for implementing <code>List</code> when you cannot |
| * extend AbstractList. The method takes Collection instances to enable other |
| * collection types to use the List implementation algorithm. |
| * |
| * @see java.util.List#hashCode() |
| * @param list the list to generate the hashCode for, may be null |
| * @return the hash code |
| */ |
| public static int hashCodeForList(final Collection<?> list) { |
| if (list == null) { |
| return 0; |
| } |
| int hashCode = 1; |
| final Iterator<?> it = list.iterator(); |
| |
| while (it.hasNext()) { |
| final Object obj = it.next(); |
| hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); |
| } |
| return hashCode; |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Returns a List containing all the elements in <code>collection</code> |
| * that are also in <code>retain</code>. The cardinality of an element <code>e</code> |
| * in the returned list is the same as the cardinality of <code>e</code> |
| * in <code>collection</code> unless <code>retain</code> does not contain <code>e</code>, in which |
| * case the cardinality is zero. This method is useful if you do not wish to modify |
| * the collection <code>c</code> and thus cannot call <code>collection.retainAll(retain);</code>. |
| * <p> |
| * This implementation iterates over <code>collection</code>, checking each element in |
| * turn to see if it's contained in <code>retain</code>. If it's contained, it's added |
| * to the returned list. As a consequence, it is advised to use a collection type for |
| * <code>retain</code> that provides a fast (e.g. O(1)) implementation of |
| * {@link Collection#contains(Object)}. |
| * |
| * @param <E> the element type |
| * @param collection the collection whose contents are the target of the #retailAll operation |
| * @param retain the collection containing the elements to be retained in the returned collection |
| * @return a <code>List</code> containing all the elements of <code>c</code> |
| * that occur at least once in <code>retain</code>. |
| * @throws NullPointerException if either parameter is null |
| * @since 3.2 |
| */ |
| public static <E> List<E> retainAll(final Collection<E> collection, final Collection<?> retain) { |
| final List<E> list = new ArrayList<E>(Math.min(collection.size(), retain.size())); |
| |
| for (final E obj : collection) { |
| if (retain.contains(obj)) { |
| list.add(obj); |
| } |
| } |
| return list; |
| } |
| |
| /** |
| * Removes the elements in <code>remove</code> from <code>collection</code>. That is, this |
| * method returns a list containing all the elements in <code>collection</code> |
| * that are not in <code>remove</code>. The cardinality of an element <code>e</code> |
| * in the returned collection is the same as the cardinality of <code>e</code> |
| * in <code>collection</code> unless <code>remove</code> contains <code>e</code>, in which |
| * case the cardinality is zero. This method is useful if you do not wish to modify |
| * <code>collection</code> and thus cannot call <code>collection.removeAll(remove);</code>. |
| * <p> |
| * This implementation iterates over <code>collection</code>, checking each element in |
| * turn to see if it's contained in <code>remove</code>. If it's not contained, it's added |
| * to the returned list. As a consequence, it is advised to use a collection type for |
| * <code>remove</code> that provides a fast (e.g. O(1)) implementation of |
| * {@link Collection#contains(Object)}. |
| * |
| * @param <E> the element type |
| * @param collection the collection from which items are removed (in the returned collection) |
| * @param remove the items to be removed from the returned <code>collection</code> |
| * @return a <code>List</code> containing all the elements of <code>c</code> except |
| * any elements that also occur in <code>remove</code>. |
| * @throws NullPointerException if either parameter is null |
| * @since 3.2 |
| */ |
| public static <E> List<E> removeAll(final Collection<E> collection, final Collection<?> remove) { |
| final List<E> list = new ArrayList<E>(); |
| for (final E obj : collection) { |
| if (!remove.contains(obj)) { |
| list.add(obj); |
| } |
| } |
| return list; |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Returns a synchronized list backed by the given list. |
| * <p> |
| * You must manually synchronize on the returned list's iterator to |
| * avoid non-deterministic behavior: |
| * |
| * <pre> |
| * List list = ListUtils.synchronizedList(myList); |
| * synchronized (list) { |
| * Iterator i = list.iterator(); |
| * while (i.hasNext()) { |
| * process (i.next()); |
| * } |
| * } |
| * </pre> |
| * |
| * This method is just a wrapper for {@link Collections#synchronizedList(List)}. |
| * |
| * @param <E> the element type |
| * @param list the list to synchronize, must not be null |
| * @return a synchronized list backed by the given list |
| * @throws NullPointerException if the list is null |
| */ |
| public static <E> List<E> synchronizedList(final List<E> list) { |
| return Collections.synchronizedList(list); |
| } |
| |
| /** |
| * Returns an unmodifiable list backed by the given list. |
| * <p> |
| * This method uses the implementation in the decorators subpackage. |
| * |
| * @param <E> the element type |
| * @param list the list to make unmodifiable, must not be null |
| * @return an unmodifiable list backed by the given list |
| * @throws NullPointerException if the list is null |
| */ |
| public static <E> List<E> unmodifiableList(final List<? extends E> list) { |
| return UnmodifiableList.unmodifiableList(list); |
| } |
| |
| /** |
| * Returns a predicated (validating) list backed by the given list. |
| * <p> |
| * Only objects that pass the test in the given predicate can be added to the list. |
| * Trying to add an invalid object results in an IllegalArgumentException. |
| * It is important not to use the original list after invoking this method, |
| * as it is a backdoor for adding invalid objects. |
| * |
| * @param <E> the element type |
| * @param list the list to predicate, must not be null |
| * @param predicate the predicate for the list, must not be null |
| * @return a predicated list backed by the given list |
| * @throws NullPointerException if the List or Predicate is null |
| */ |
| public static <E> List<E> predicatedList(final List<E> list, final Predicate<E> predicate) { |
| return PredicatedList.predicatedList(list, predicate); |
| } |
| |
| /** |
| * Returns a transformed list backed by the given list. |
| * <p> |
| * This method returns a new list (decorating the specified list) that |
| * will transform any new entries added to it. |
| * Existing entries in the specified list will not be transformed. |
| * <p> |
| * Each object is passed through the transformer as it is added to the |
| * List. It is important not to use the original list after invoking this |
| * method, as it is a backdoor for adding untransformed objects. |
| * <p> |
| * Existing entries in the specified list will not be transformed. |
| * If you want that behaviour, see {@link TransformedList#transformedList}. |
| * |
| * @param <E> the element type |
| * @param list the list to predicate, must not be null |
| * @param transformer the transformer for the list, must not be null |
| * @return a transformed list backed by the given list |
| * @throws NullPointerException if the List or Transformer is null |
| */ |
| public static <E> List<E> transformedList(final List<E> list, |
| final Transformer<? super E, ? extends E> transformer) { |
| return TransformedList.transformingList(list, transformer); |
| } |
| |
| /** |
| * Returns a "lazy" list whose elements will be created on demand. |
| * <p> |
| * When the index passed to the returned list's {@link List#get(int) get} |
| * method is greater than the list's size, then the factory will be used |
| * to create a new object and that object will be inserted at that index. |
| * <p> |
| * For instance: |
| * |
| * <pre> |
| * Factory<Date> factory = new Factory<Date>() { |
| * public Date create() { |
| * return new Date(); |
| * } |
| * } |
| * List<Date> lazy = ListUtils.lazyList(new ArrayList<Date>(), factory); |
| * Date date = lazy.get(3); |
| * </pre> |
| * |
| * After the above code is executed, <code>date</code> will refer to |
| * a new <code>Date</code> instance. Furthermore, that <code>Date</code> |
| * instance is the fourth element in the list. The first, second, |
| * and third element are all set to <code>null</code>. |
| * |
| * @param <E> the element type |
| * @param list the list to make lazy, must not be null |
| * @param factory the factory for creating new objects, must not be null |
| * @return a lazy list backed by the given list |
| * @throws NullPointerException if the List or Factory is null |
| */ |
| public static <E> List<E> lazyList(final List<E> list, final Factory<? extends E> factory) { |
| return LazyList.lazyList(list, factory); |
| } |
| |
| /** |
| * Returns a fixed-sized list backed by the given list. |
| * Elements may not be added or removed from the returned list, but |
| * existing elements can be changed (for instance, via the |
| * {@link List#set(int, Object)} method). |
| * |
| * @param <E> the element type |
| * @param list the list whose size to fix, must not be null |
| * @return a fixed-size list backed by that list |
| * @throws NullPointerException if the List is null |
| */ |
| public static <E> List<E> fixedSizeList(final List<E> list) { |
| return FixedSizeList.fixedSizeList(list); |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Finds the first index in the given List which matches the given predicate. |
| * <p> |
| * If the input List or predicate is null, or no element of the List |
| * matches the predicate, -1 is returned. |
| * |
| * @param <E> the element type |
| * @param list the List to search, may be null |
| * @param predicate the predicate to use, may be null |
| * @return the first index of an Object in the List which matches the predicate or -1 if none could be found |
| */ |
| public static <E> int indexOf(final List<E> list, final Predicate<E> predicate) { |
| if (list != null && predicate != null) { |
| for (int i = 0; i < list.size(); i++) { |
| final E item = list.get(i); |
| if (predicate.evaluate(item)) { |
| return i; |
| } |
| } |
| } |
| return -1; |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Returns the longest common subsequence (LCS) of two sequences (lists). |
| * |
| * @param <E> the element type |
| * @param a the first list |
| * @param b the second list |
| * @return the longest common subsequence |
| * @throws NullPointerException if either list is {@code null} |
| * @since 4.0 |
| */ |
| public static <E> List<E> longestCommonSubsequence(final List<E> a, final List<E> b) { |
| return longestCommonSubsequence( a, b, DefaultEquator.defaultEquator() ); |
| } |
| |
| /** |
| * Returns the longest common subsequence (LCS) of two sequences (lists). |
| * |
| * @param <E> the element type |
| * @param a the first list |
| * @param b the second list |
| * @param equator the equator used to test object equality |
| * @return the longest common subsequence |
| * @throws NullPointerException if either list or the equator is {@code null} |
| * @since 4.0 |
| */ |
| public static <E> List<E> longestCommonSubsequence(final List<E> a, final List<E> b, |
| final Equator<? super E> equator) { |
| if (a == null || b == null) { |
| throw new NullPointerException("List must not be null"); |
| } |
| if (equator == null) { |
| throw new NullPointerException("Equator must not be null"); |
| } |
| |
| final SequencesComparator<E> comparator = new SequencesComparator<E>(a, b, equator); |
| final EditScript<E> script = comparator.getScript(); |
| final LcsVisitor<E> visitor = new LcsVisitor<E>(); |
| script.visit(visitor); |
| return visitor.getSubSequence(); |
| } |
| |
| /** |
| * Returns the longest common subsequence (LCS) of two {@link CharSequence} objects. |
| * <p> |
| * This is a convenience method for using {@link #longestCommonSubsequence(List, List)} |
| * with {@link CharSequence} instances. |
| * |
| * @param a the first sequence |
| * @param b the second sequence |
| * @return the longest common subsequence as {@link String} |
| * @throws NullPointerException if either sequence is {@code null} |
| * @since 4.0 |
| */ |
| public static String longestCommonSubsequence(final CharSequence a, final CharSequence b) { |
| if (a == null || b == null) { |
| throw new NullPointerException("CharSequence must not be null"); |
| } |
| final List<Character> lcs = longestCommonSubsequence(new CharSequenceAsList( a ), new CharSequenceAsList( b )); |
| final StringBuilder sb = new StringBuilder(); |
| for ( Character ch : lcs ) { |
| sb.append(ch); |
| } |
| return sb.toString(); |
| } |
| |
| /** |
| * A helper class used to construct the longest common subsequence. |
| */ |
| private static final class LcsVisitor<E> implements CommandVisitor<E> { |
| private ArrayList<E> sequence; |
| |
| public LcsVisitor() { |
| sequence = new ArrayList<E>(); |
| } |
| |
| public void visitInsertCommand(final E object) {} |
| |
| public void visitDeleteCommand(final E object) {} |
| |
| public void visitKeepCommand(final E object) { |
| sequence.add(object); |
| } |
| |
| public List<E> getSubSequence() { |
| return sequence; |
| } |
| } |
| |
| /** |
| * A simple wrapper to use a CharSequence as List. |
| */ |
| private static final class CharSequenceAsList extends AbstractList<Character> { |
| |
| private final CharSequence sequence; |
| |
| public CharSequenceAsList(final CharSequence sequence) { |
| this.sequence = sequence; |
| } |
| |
| @Override |
| public Character get( int index ) { |
| return Character.valueOf(sequence.charAt( index )); |
| } |
| |
| @Override |
| public int size() { |
| return sequence.length(); |
| } |
| |
| } |
| |
| //----------------------------------------------------------------------- |
| /** |
| * Returns consecutive {@link List#subList(int, int) sublists} of a |
| * list, each of the same size (the final list may be smaller). For example, |
| * partitioning a list containing {@code [a, b, c, d, e]} with a partition |
| * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing |
| * two inner lists of three and two elements, all in the original order. |
| * <p> |
| * The outer list is unmodifiable, but reflects the latest state of the |
| * source list. The inner lists are sublist views of the original list, |
| * produced on demand using {@link List#subList(int, int)}, and are subject |
| * to all the usual caveats about modification as explained in that API. |
| * <p> |
| * Adapted from http://code.google.com/p/guava-libraries/ |
| * |
| * @param <T> the element type |
| * @param list the list to return consecutive sublists of |
| * @param size the desired size of each sublist (the last may be smaller) |
| * @return a list of consecutive sublists |
| * @throws NullPointerException if list is null |
| * @throws IllegalArgumentException if size is not strictly positive |
| * @since 4.0 |
| */ |
| public static <T> List<List<T>> partition(final List<T> list, final int size) { |
| if (list == null) { |
| throw new NullPointerException("List must not be null"); |
| } |
| if (size <= 0) { |
| throw new IllegalArgumentException("Size must be greater than 0"); |
| } |
| return new Partition<T>(list, size); |
| } |
| |
| /** |
| * Provides a partition view on a {@link List}. |
| * @since 4.0 |
| */ |
| private static class Partition<T> extends AbstractList<List<T>> { |
| private final List<T> list; |
| private final int size; |
| |
| private Partition(final List<T> list, final int size) { |
| this.list = list; |
| this.size = size; |
| } |
| |
| @Override |
| public List<T> get(final int index) { |
| final int listSize = size(); |
| if (listSize < 0) { |
| throw new IllegalArgumentException("negative size: " + listSize); |
| } |
| if (index < 0) { |
| throw new IndexOutOfBoundsException("Index " + index + " must not be negative"); |
| } |
| if (index >= listSize) { |
| throw new IndexOutOfBoundsException("Index " + index + " must be less than size " + |
| listSize); |
| } |
| final int start = index * size; |
| final int end = Math.min(start + size, list.size()); |
| return list.subList(start, end); |
| } |
| |
| @Override |
| public int size() { |
| return (list.size() + size - 1) / size; |
| } |
| |
| @Override |
| public boolean isEmpty() { |
| return list.isEmpty(); |
| } |
| } |
| } |
