    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 */
    017package org.apache.commons.collections4;
    018
    019import java.util.AbstractList;
    020import java.util.ArrayList;
    021import java.util.Collection;
    022import java.util.Collections;
    023import java.util.HashSet;
    024import java.util.Iterator;
    025import java.util.List;
    026import java.util.Objects;
    027
    028import org.apache.commons.collections4.bag.HashBag;
    029import org.apache.commons.collections4.functors.DefaultEquator;
    030import org.apache.commons.collections4.list.FixedSizeList;
    031import org.apache.commons.collections4.list.LazyList;
    032import org.apache.commons.collections4.list.PredicatedList;
    033import org.apache.commons.collections4.list.TransformedList;
    034import org.apache.commons.collections4.list.UnmodifiableList;
    035import org.apache.commons.collections4.sequence.CommandVisitor;
    036import org.apache.commons.collections4.sequence.EditScript;
    037import org.apache.commons.collections4.sequence.SequencesComparator;
    038
    039/**
    040 * Provides utility methods and decorators for {@link List} instances.
    041 *
    042 * @since 1.0
    043 */
    044public class ListUtils {
    045
    046    /**
    047     * A simple wrapper to use a CharSequence as List.
    048     */
    049    private static final class CharSequenceAsList extends AbstractList<Character> {
    050        private final CharSequence sequence;
    051
    052        CharSequenceAsList(final CharSequence sequence) {
    053            this.sequence = sequence;
    054        }
    055
    056        @Override
    057        public Character get(final int index) {
    058            return Character.valueOf(sequence.charAt(index));
    059        }
    060
    061        @Override
    062        public int size() {
    063            return sequence.length();
    064        }
    065    }
    066
    067    /**
    068     * A helper class used to construct the longest common subsequence.
    069     */
    070    private static final class LcsVisitor<E> implements CommandVisitor<E> {
    071        private final ArrayList<E> sequence;
    072
    073        LcsVisitor() {
    074            sequence = new ArrayList<>();
    075        }
    076
    077        public List<E> getSubSequence() {
    078            return sequence;
    079        }
    080
    081        @Override
    082        public void visitDeleteCommand(final E object) {
    083            // noop
    084        }
    085
    086        @Override
    087        public void visitInsertCommand(final E object) {
    088            // noop
    089        }
    090
    091        @Override
    092        public void visitKeepCommand(final E object) {
    093            sequence.add(object);
    094        }
    095    }
    096
    097    /**
    098     * Provides a partition view on a {@link List}.
    099     * @since 4.0
    100     */
    101    private static final class Partition<T> extends AbstractList<List<T>> {
    102        private final List<T> list;
    103        private final int size;
    104
    105        private Partition(final List<T> list, final int size) {
    106            this.list = list;
    107            this.size = size;
    108        }
    109
    110        @Override
    111        public List<T> get(final int index) {
    112            final int listSize = size();
    113            if (index < 0) {
    114                throw new IndexOutOfBoundsException("Index " + index + " must not be negative");
    115            }
    116            if (index >= listSize) {
    117                throw new IndexOutOfBoundsException("Index " + index + " must be less than size " +
    118                                                    listSize);
    119            }
    120            final int start = index * size;
    121            final int end = Math.min(start + size, list.size());
    122            return list.subList(start, end);
    123        }
    124
    125        @Override
    126        public boolean isEmpty() {
    127            return list.isEmpty();
    128        }
    129
    130        @Override
    131        public int size() {
    132            return (int) Math.ceil((double) list.size() / (double) size);
    133        }
    134    }
    135
    136    /**
    137     * Returns either the passed in list, or if the list is {@code null},
    138     * the value of {@code defaultList}.
    139     *
    140     * @param <T> the element type
    141     * @param list  the list, possibly {@code null}
    142     * @param defaultList  the returned values if list is {@code null}
    143     * @return an empty list if the argument is {@code null}
    144     * @since 4.0
    145     */
    146    public static <T> List<T> defaultIfNull(final List<T> list, final List<T> defaultList) {
    147        return list == null ? defaultList : list;
    148    }
    149
    150    /**
    151     * Returns an immutable empty list if the argument is {@code null},
    152     * or the argument itself otherwise.
    153     *
    154     * @param <T> the element type
    155     * @param list the list, possibly {@code null}
    156     * @return an empty list if the argument is {@code null}
    157     */
    158    public static <T> List<T> emptyIfNull(final List<T> list) {
    159        return list == null ? Collections.<T>emptyList() : list;
    160    }
    161
    162    /**
    163     * Returns a fixed-sized list backed by the given list.
    164     * Elements may not be added or removed from the returned list, but
    165     * existing elements can be changed (for instance, via the
    166     * {@link List#set(int, Object)} method).
    167     *
    168     * @param <E>  the element type
    169     * @param list  the list whose size to fix, must not be null
    170     * @return a fixed-size list backed by that list
    171     * @throws NullPointerException  if the List is null
    172     */
    173    public static <E> List<E> fixedSizeList(final List<E> list) {
    174        return FixedSizeList.fixedSizeList(list);
    175    }
    176
    177    /**
    178     * Gets the first element of a list.
    179     * <p>
    180     * Shorthand for {@code list.get(0)}
    181     * </p>
    182     *
    183     * @param <T> The list type.
    184     * @param list The list.
    185     * @return the first element of a list.
    186     * @see List#get(int)
    187     * @since 4.5.0-M1
    188     */
    189    public static <T> T getFirst(final List<T> list) {
    190        return Objects.requireNonNull(list, "list").get(0);
    191    }
    192
    193    /**
    194     * Gets the last element of a list.
    195     * <p>
    196     * Shorthand for {@code list.get(list.size() - 1)}
    197     * </p>
    198     *
    199     * @param <T> The list type.
    200     * @param list The list.
    201     * @return the last element of a list.
    202     * @see List#get(int)
    203     * @since 4.5.0-M1
    204     */
    205    public static <T> T getLast(final List<T> list) {
    206        return Objects.requireNonNull(list, "list").get(list.size() - 1);
    207    }
    208
    209    /**
    210     * Generates a hash code using the algorithm specified in
    211     * {@link java.util.List#hashCode()}.
    212     * <p>
    213     * This method is useful for implementing {@code List} when you cannot
    214     * extend AbstractList. The method takes Collection instances to enable other
    215     * collection types to use the List implementation algorithm.
    216     * </p>
    217     *
    218     * @see java.util.List#hashCode()
    219     * @param list  the list to generate the hashCode for, may be null
    220     * @return the hash code
    221     */
    222    public static int hashCodeForList(final Collection<?> list) {
    223        if (list == null) {
    224            return 0;
    225        }
    226        int hashCode = 1;
    227
    228        for (final Object obj : list) {
    229            hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
    230        }
    231        return hashCode;
    232    }
    233
    234    /**
    235     * Finds the first index in the given List which matches the given predicate.
    236     * <p>
    237     * If the input List or predicate is null, or no element of the List
    238     * matches the predicate, -1 is returned.
    239     * </p>
    240     *
    241     * @param <E>  the element type
    242     * @param list the List to search, may be null
    243     * @param predicate  the predicate to use, may be null
    244     * @return the first index of an Object in the List which matches the predicate or -1 if none could be found
    245     */
    246    public static <E> int indexOf(final List<E> list, final Predicate<E> predicate) {
    247        if (list != null && predicate != null) {
    248            for (int i = 0; i < list.size(); i++) {
    249                final E item = list.get(i);
    250                if (predicate.test(item)) {
    251                    return i;
    252                }
    253            }
    254        }
    255        return CollectionUtils.INDEX_NOT_FOUND;
    256    }
    257
    258    /**
    259     * Returns a new list containing all elements that are contained in
    260     * both given lists.
    261     *
    262     * @param <E> the element type
    263     * @param list1  the first list
    264     * @param list2  the second list
    265     * @return  the intersection of those two lists
    266     * @throws NullPointerException if either list is null
    267     */
    268    public static <E> List<E> intersection(final List<? extends E> list1, final List<? extends E> list2) {
    269        final List<E> result = new ArrayList<>();
    270
    271        List<? extends E> smaller = list1;
    272        List<? extends E> larger = list2;
    273        if (list1.size() > list2.size()) {
    274            smaller = list2;
    275            larger = list1;
    276        }
    277
    278        final HashSet<E> hashSet = new HashSet<>(smaller);
    279
    280        for (final E e : larger) {
    281            if (hashSet.contains(e)) {
    282                result.add(e);
    283                hashSet.remove(e);
    284            }
    285        }
    286        return result;
    287    }
    288
    289    /**
    290     * Tests two lists for value-equality as per the equality contract in
    291     * {@link java.util.List#equals(Object)}.
    292     * <p>
    293     * This method is useful for implementing {@code List} when you cannot
    294     * extend AbstractList. The method takes Collection instances to enable other
    295     * collection types to use the List implementation algorithm.
    296     * </p>
    297     * <p>
    298     * The relevant text (slightly paraphrased as this is a static method) is:
    299     * </p>
    300     * <blockquote>
    301     * Compares the two list objects for equality.  Returns
    302     * {@code true} if and only if both
    303     * lists have the same size, and all corresponding pairs of elements in
    304     * the two lists are <em>equal</em>.  (Two elements {@code e1} and
    305     * {@code e2} are <em>equal</em> if {@code (e1==null ? e2==null :
    306     * e1.equals(e2))}.)  In other words, two lists are defined to be
    307     * equal if they contain the same elements in the same order.  This
    308     * definition ensures that the equals method works properly across
    309     * different implementations of the {@code List} interface.
    310     * </blockquote>
    311     * <p>
    312     * <strong>Note:</strong> The behavior of this method is undefined if the lists are
    313     * modified during the equals comparison.
    314     * </p>
    315     *
    316     * @see java.util.List
    317     * @param list1  the first list, may be null
    318     * @param list2  the second list, may be null
    319     * @return whether the lists are equal by value comparison
    320     */
    321    public static boolean isEqualList(final Collection<?> list1, final Collection<?> list2) {
    322        if (list1 == list2) {
    323            return true;
    324        }
    325        if (list1 == null || list2 == null || list1.size() != list2.size()) {
    326            return false;
    327        }
    328
    329        final Iterator<?> it1 = list1.iterator();
    330        final Iterator<?> it2 = list2.iterator();
    331
    332        while (it1.hasNext() && it2.hasNext()) {
    333            final Object obj1 = it1.next();
    334            final Object obj2 = it2.next();
    335
    336            if (!Objects.equals(obj1, obj2)) {
    337                return false;
    338            }
    339        }
    340
    341        return !(it1.hasNext() || it2.hasNext());
    342    }
    343
    344    /**
    345     * Returns a "lazy" list whose elements will be created on demand.
    346     * <p>
    347     * When the index passed to the returned list's {@link List#get(int) get}
    348     * method is greater than the list's size, then the factory will be used
    349     * to create a new object and that object will be inserted at that index.
    350     * </p>
    351     * <p>
    352     * For instance:
    353     * </p>
    354     * <pre>
    355     * Factory&lt;Date&gt; factory = new Factory&lt;Date&gt;() {
    356     *     public Date create() {
    357     *         return new Date();
    358     *     }
    359     * }
    360     * List&lt;Date&gt; lazy = ListUtils.lazyList(new ArrayList&lt;Date&gt;(), factory);
    361     * Date date = lazy.get(3);
    362     * </pre>
    363     * <p>
    364     * After the above code is executed, {@code date} will refer to
    365     * a new {@code Date} instance. Furthermore, that {@code Date}
    366     * instance is the fourth element in the list.  The first, second,
    367     * and third element are all set to {@code null}.
    368     * </p>
    369     *
    370     * @param <E> the element type
    371     * @param list  the list to make lazy, must not be null
    372     * @param factory  the factory for creating new objects, must not be null
    373     * @return a lazy list backed by the given list
    374     * @throws NullPointerException if the List or Factory is null
    375     */
    376    public static <E> List<E> lazyList(final List<E> list, final Factory<? extends E> factory) {
    377        return LazyList.lazyList(list, factory);
    378    }
    379
    380    /**
    381     * Returns a "lazy" list whose elements will be created on demand.
    382     * <p>
    383     * When the index passed to the returned list's {@link List#get(int) get}
    384     * method is greater than the list's size, then the transformer will be used
    385     * to create a new object and that object will be inserted at that index.
    386     * </p>
    387     * <p>
    388     * For instance:
    389     * </p>
    390     * <pre>
    391     * List&lt;Integer&gt; hours = Arrays.asList(7, 5, 8, 2);
    392     * Transformer&lt;Integer,Date&gt; transformer = input -&gt; LocalDateTime.now().withHour(hours.get(input));
    393     * List&lt;LocalDateTime&gt; lazy = ListUtils.lazyList(new ArrayList&lt;LocalDateTime&gt;(), transformer);
    394     * Date date = lazy.get(3);
    395     * </pre>
    396     * <p>
    397     * After the above code is executed, {@code date} will refer to
    398     * a new {@code Date} instance. Furthermore, that {@code Date}
    399     * instance is the fourth element in the list.  The first, second,
    400     * and third element are all set to {@code null}.
    401     * </p>
    402     *
    403     * @param <E> the element type
    404     * @param list  the list to make lazy, must not be null
    405     * @param transformer  the transformer for creating new objects, must not be null
    406     * @return a lazy list backed by the given list
    407     * @throws NullPointerException if the List or Transformer is null
    408     */
    409    public static <E> List<E> lazyList(final List<E> list, final Transformer<Integer, ? extends E> transformer) {
    410        return LazyList.lazyList(list, transformer);
    411    }
    412
    413    /**
    414     * Returns the longest common subsequence (LCS) of two {@link CharSequence} objects.
    415     * <p>
    416     * This is a convenience method for using {@link #longestCommonSubsequence(List, List)}
    417     * with {@link CharSequence} instances.
    418     * </p>
    419     *
    420     * @param charSequenceA  the first sequence
    421     * @param charSequenceB  the second sequence
    422     * @return the longest common subsequence as {@link String}
    423     * @throws NullPointerException if either sequence is {@code null}
    424     * @since 4.0
    425     */
    426    public static String longestCommonSubsequence(final CharSequence charSequenceA, final CharSequence charSequenceB) {
    427        Objects.requireNonNull(charSequenceA, "charSequenceA");
    428        Objects.requireNonNull(charSequenceB, "charSequenceB");
    429        final List<Character> lcs = longestCommonSubsequence(new CharSequenceAsList(charSequenceA),
    430                new CharSequenceAsList(charSequenceB));
    431        final StringBuilder sb = new StringBuilder();
    432        for (final Character ch : lcs) {
    433            sb.append(ch);
    434        }
    435        return sb.toString();
    436    }
    437
    438    /**
    439     * Returns the longest common subsequence (LCS) of two sequences (lists).
    440     *
    441     * @param <E>  the element type
    442     * @param a  the first list
    443     * @param b  the second list
    444     * @return the longest common subsequence
    445     * @throws NullPointerException if either list is {@code null}
    446     * @since 4.0
    447     */
    448    public static <E> List<E> longestCommonSubsequence(final List<E> a, final List<E> b) {
    449        return longestCommonSubsequence(a, b, DefaultEquator.defaultEquator());
    450    }
    451
    452    /**
    453     * Returns the longest common subsequence (LCS) of two sequences (lists).
    454     *
    455     * @param <E>  the element type
    456     * @param listA  the first list
    457     * @param listB  the second list
    458     * @param equator  the equator used to test object equality
    459     * @return the longest common subsequence
    460     * @throws NullPointerException if either list or the equator is {@code null}
    461     * @since 4.0
    462     */
    463    public static <E> List<E> longestCommonSubsequence(final List<E> listA, final List<E> listB,
    464                                                       final Equator<? super E> equator) {
    465        Objects.requireNonNull(listA, "listA");
    466        Objects.requireNonNull(listB, "listB");
    467        Objects.requireNonNull(equator, "equator");
    468
    469        final SequencesComparator<E> comparator = new SequencesComparator<>(listA, listB, equator);
    470        final EditScript<E> script = comparator.getScript();
    471        final LcsVisitor<E> visitor = new LcsVisitor<>();
    472        script.visit(visitor);
    473        return visitor.getSubSequence();
    474    }
    475
    476    /**
    477     * Returns consecutive {@link List#subList(int, int) sublists} of a
    478     * list, each of the same size (the final list may be smaller). For example,
    479     * partitioning a list containing {@code [a, b, c, d, e]} with a partition
    480     * size of 3 yields {@code [[a, b, c], [d, e]]} -- an outer list containing
    481     * two inner lists of three and two elements, all in the original order.
    482     * <p>
    483     * The outer list is unmodifiable, but reflects the latest state of the
    484     * source list. The inner lists are sublist views of the original list,
    485     * produced on demand using {@link List#subList(int, int)}, and are subject
    486     * to all the usual caveats about modification as explained in that API.
    487     * </p>
    488     * <p>
    489     * Adapted from https://github.com/google/guava
    490     * </p>
    491     *
    492     * @param <T> the element type
    493     * @param list  the list to return consecutive sublists of
    494     * @param size  the desired size of each sublist (the last may be smaller)
    495     * @return a list of consecutive sublists
    496     * @throws NullPointerException if list is null
    497     * @throws IllegalArgumentException if size is not strictly positive
    498     * @since 4.0
    499     */
    500    public static <T> List<List<T>> partition(final List<T> list, final int size) {
    501        Objects.requireNonNull(list, "list");
    502        if (size <= 0) {
    503            throw new IllegalArgumentException("Size must be greater than 0");
    504        }
    505        return new Partition<>(list, size);
    506    }
    507
    508    /**
    509     * Returns a predicated (validating) list backed by the given list.
    510     * <p>
    511     * Only objects that pass the test in the given predicate can be added to the list.
    512     * Trying to add an invalid object results in an IllegalArgumentException.
    513     * It is important not to use the original list after invoking this method,
    514     * as it is a backdoor for adding invalid objects.
    515     * </p>
    516     *
    517     * @param <E> the element type
    518     * @param list  the list to predicate, must not be null
    519     * @param predicate  the predicate for the list, must not be null
    520     * @return a predicated list backed by the given list
    521     * @throws NullPointerException if the List or Predicate is null
    522     */
    523    public static <E> List<E> predicatedList(final List<E> list, final Predicate<E> predicate) {
    524        return PredicatedList.predicatedList(list, predicate);
    525    }
    526
    527    /**
    528     * Removes the elements in {@code remove} from {@code collection}. That is, this
    529     * method returns a list containing all the elements in {@code collection}
    530     * that are not in {@code remove}. The cardinality of an element {@code e}
    531     * in the returned collection is the same as the cardinality of {@code e}
    532     * in {@code collection} unless {@code remove} contains {@code e}, in which
    533     * case the cardinality is zero. This method is useful if you do not wish to modify
    534     * {@code collection} and thus cannot call {@code collection.removeAll(remove);}.
    535     * <p>
    536     * This implementation iterates over {@code collection}, checking each element in
    537     * turn to see if it's contained in {@code remove}. If it's not contained, it's added
    538     * to the returned list. As a consequence, it is advised to use a collection type for
    539     * {@code remove} that provides a fast (e.g. O(1)) implementation of
    540     * {@link Collection#contains(Object)}.
    541     * </p>
    542     *
    543     * @param <E>  the element type
    544     * @param collection  the collection from which items are removed (in the returned collection)
    545     * @param remove  the items to be removed from the returned {@code collection}
    546     * @return a {@code List} containing all the elements of {@code c} except
    547     * any elements that also occur in {@code remove}.
    548     * @throws NullPointerException if either parameter is null
    549     * @since 3.2
    550     */
    551    public static <E> List<E> removeAll(final Collection<E> collection, final Collection<?> remove) {
    552        Objects.requireNonNull(collection, "collection");
    553        Objects.requireNonNull(remove, "remove");
    554        final List<E> list = new ArrayList<>();
    555        for (final E obj : collection) {
    556            if (!remove.contains(obj)) {
    557                list.add(obj);
    558            }
    559        }
    560        return list;
    561    }
    562
    563    /**
    564     * Returns a List containing all the elements in {@code collection}
    565     * that are also in {@code retain}. The cardinality of an element {@code e}
    566     * in the returned list is the same as the cardinality of {@code e}
    567     * in {@code collection} unless {@code retain} does not contain {@code e}, in which
    568     * case the cardinality is zero. This method is useful if you do not wish to modify
    569     * the collection {@code c} and thus cannot call {@code collection.retainAll(retain);}.
    570     * <p>
    571     * This implementation iterates over {@code collection}, checking each element in
    572     * turn to see if it's contained in {@code retain}. If it's contained, it's added
    573     * to the returned list. As a consequence, it is advised to use a collection type for
    574     * {@code retain} that provides a fast (e.g. O(1)) implementation of
    575     * {@link Collection#contains(Object)}.
    576     * </p>
    577     *
    578     * @param <E>  the element type
    579     * @param collection  the collection whose contents are the target of the #retailAll operation
    580     * @param retain  the collection containing the elements to be retained in the returned collection
    581     * @return a {@code List} containing all the elements of {@code c}
    582     * that occur at least once in {@code retain}.
    583     * @throws NullPointerException if either parameter is null
    584     * @since 3.2
    585     */
    586    public static <E> List<E> retainAll(final Collection<E> collection, final Collection<?> retain) {
    587        final List<E> list = new ArrayList<>(Math.min(collection.size(), retain.size()));
    588
    589        for (final E obj : collection) {
    590            if (retain.contains(obj)) {
    591                list.add(obj);
    592            }
    593        }
    594        return list;
    595    }
    596
    597    /**
    598     * Selects all elements from input collection which match the given
    599     * predicate into an output list.
    600     * <p>
    601     * A {@code null} predicate matches no elements.
    602     * </p>
    603     *
    604     * @param <E> the element type
    605     * @param inputCollection  the collection to get the input from, may not be null
    606     * @param predicate  the predicate to use, may be null
    607     * @return the elements matching the predicate (new list)
    608     * @throws NullPointerException if the input list is null
    609     * @since 4.0
    610     * @see CollectionUtils#select(Iterable, Predicate)
    611     */
    612    public static <E> List<E> select(final Collection<? extends E> inputCollection,
    613            final Predicate<? super E> predicate) {
    614        return CollectionUtils.select(inputCollection, predicate, new ArrayList<>(inputCollection.size()));
    615    }
    616
    617    /**
    618     * Selects all elements from inputCollection which don't match the given
    619     * predicate into an output collection.
    620     * <p>
    621     * If the input predicate is {@code null}, the result is an empty list.
    622     * </p>
    623     *
    624     * @param <E> the element type
    625     * @param inputCollection the collection to get the input from, may not be null
    626     * @param predicate the predicate to use, may be null
    627     * @return the elements <strong>not</strong> matching the predicate (new list)
    628     * @throws NullPointerException if the input collection is null
    629     * @since 4.0
    630     * @see CollectionUtils#selectRejected(Iterable, Predicate)
    631     */
    632    public static <E> List<E> selectRejected(final Collection<? extends E> inputCollection,
    633            final Predicate<? super E> predicate) {
    634        return CollectionUtils.selectRejected(inputCollection, predicate, new ArrayList<>(inputCollection.size()));
    635    }
    636
    637    /**
    638     * Subtracts all elements in the second list from the first list,
    639     * placing the results in a new list.
    640     * <p>
    641     * This differs from {@link List#removeAll(Collection)} in that
    642     * cardinality is respected; if <Code>list1</Code> contains two
    643     * occurrences of <Code>null</Code> and <Code>list2</Code> only
    644     * contains one occurrence, then the returned list will still contain
    645     * one occurrence.
    646     * </p>
    647     *
    648     * @param <E> the element type
    649     * @param list1  the list to subtract from
    650     * @param list2  the list to subtract
    651     * @return a new list containing the results
    652     * @throws NullPointerException if either list is null
    653     */
    654    public static <E> List<E> subtract(final List<E> list1, final List<? extends E> list2) {
    655        final ArrayList<E> result = new ArrayList<>();
    656        final HashBag<E> bag = new HashBag<>(list2);
    657        for (final E e : list1) {
    658            if (!bag.remove(e, 1)) {
    659                result.add(e);
    660            }
    661        }
    662        return result;
    663    }
    664
    665    /**
    666     * Returns the sum of the given lists.  This is their intersection
    667     * subtracted from their union.
    668     *
    669     * @param <E> the element type
    670     * @param list1  the first list
    671     * @param list2  the second list
    672     * @return  a new list containing the sum of those lists
    673     * @throws NullPointerException if either list is null
    674     */
    675    public static <E> List<E> sum(final List<? extends E> list1, final List<? extends E> list2) {
    676        return subtract(union(list1, list2), intersection(list1, list2));
    677    }
    678
    679    /**
    680     * Returns a synchronized list backed by the given list.
    681     * <p>
    682     * You must manually synchronize on the returned list's iterator to
    683     * avoid non-deterministic behavior:
    684     * </p>
    685     * <pre>
    686     * List list = ListUtils.synchronizedList(myList);
    687     * synchronized (list) {
    688     *     Iterator i = list.iterator();
    689     *     while (i.hasNext()) {
    690     *         process (i.next());
    691     *     }
    692     * }
    693     * </pre>
    694     * <p>
    695     * This method is just a wrapper for {@link Collections#synchronizedList(List)}.
    696     * </p>
    697     *
    698     * @param <E> the element type
    699     * @param list  the list to synchronize, must not be null
    700     * @return a synchronized list backed by the given list
    701     * @throws NullPointerException if the list is null
    702     */
    703    public static <E> List<E> synchronizedList(final List<E> list) {
    704        return Collections.synchronizedList(list);
    705    }
    706
    707    /**
    708     * Returns a transformed list backed by the given list.
    709     * <p>
    710     * This method returns a new list (decorating the specified list) that
    711     * will transform any new entries added to it.
    712     * Existing entries in the specified list will not be transformed.
    713     * </p>
    714     * <p>
    715     * Each object is passed through the transformer as it is added to the
    716     * List. It is important not to use the original list after invoking this
    717     * method, as it is a backdoor for adding untransformed objects.
    718     * </p>
    719     * <p>
    720     * Existing entries in the specified list will not be transformed.
    721     * If you want that behavior, see {@link TransformedList#transformedList}.
    722     * </p>
    723     *
    724     * @param <E> the element type
    725     * @param list  the list to predicate, must not be null
    726     * @param transformer  the transformer for the list, must not be null
    727     * @return a transformed list backed by the given list
    728     * @throws NullPointerException if the List or Transformer is null
    729     */
    730    public static <E> List<E> transformedList(final List<E> list,
    731                                              final Transformer<? super E, ? extends E> transformer) {
    732        return TransformedList.transformingList(list, transformer);
    733    }
    734
    735    /**
    736     * Returns a new list containing the second list appended to the
    737     * first list.  The {@link List#addAll(Collection)} operation is
    738     * used to append the two given lists into a new list.
    739     *
    740     * @param <E> the element type
    741     * @param list1  the first list
    742     * @param list2  the second list
    743     * @return a new list containing the union of those lists
    744     * @throws NullPointerException if either list is null
    745     */
    746    public static <E> List<E> union(final List<? extends E> list1, final List<? extends E> list2) {
    747        final ArrayList<E> result = new ArrayList<>(list1.size() + list2.size());
    748        result.addAll(list1);
    749        result.addAll(list2);
    750        return result;
    751    }
    752
    753    /**
    754     * Returns an unmodifiable list backed by the given list.
    755     * <p>
    756     * This method uses the implementation in the decorators subpackage.
    757     * </p>
    758     *
    759     * @param <E>  the element type
    760     * @param list  the list to make unmodifiable, must not be null
    761     * @return an unmodifiable list backed by the given list
    762     * @throws NullPointerException if the list is null
    763     */
    764    public static <E> List<E> unmodifiableList(final List<? extends E> list) {
    765        return UnmodifiableList.unmodifiableList(list);
    766    }
    767
    768    /**
    769     * Don't allow instances.
    770     */
    771    private ListUtils() {
    772        // empty
    773    }
    774
    775}