    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.list;
    018
    019import java.lang.reflect.InvocationTargetException;
    020import java.util.ArrayList;
    021import java.util.Collection;
    022import java.util.HashSet;
    023import java.util.Iterator;
    024import java.util.List;
    025import java.util.ListIterator;
    026import java.util.Objects;
    027import java.util.Set;
    028import java.util.function.Predicate;
    029
    030import org.apache.commons.collections4.ListUtils;
    031import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
    032import org.apache.commons.collections4.iterators.AbstractListIteratorDecorator;
    033import org.apache.commons.collections4.set.UnmodifiableSet;
    034
    035/**
    036 * Decorates a {@code List} to ensure that no duplicates are present much
    037 * like a {@code Set}.
    038 * <p>
    039 * The {@code List} interface makes certain assumptions/requirements. This
    040 * implementation breaks these in certain ways, but this is merely the result of
    041 * rejecting duplicates. Each violation is explained in the method, but it
    042 * should not affect you. Bear in mind that Sets require immutable objects to
    043 * function correctly.
    044 * </p>
    045 * <p>
    046 * The {@link org.apache.commons.collections4.set.ListOrderedSet ListOrderedSet}
    047 * class provides an alternative approach, by wrapping an existing Set and
    048 * retaining insertion order in the iterator.
    049 * </p>
    050 * <p>
    051 * This class is Serializable from Commons Collections 3.1.
    052 * </p>
    053 *
    054 * @param <E> the type of the elements in the list.
    055 * @since 3.0
    056 */
    057public class SetUniqueList<E> extends AbstractSerializableListDecorator<E> {
    058
    059    /**
    060     * Inner class iterator.
    061     */
    062    static class SetListIterator<E> extends AbstractIteratorDecorator<E> {
    063
    064        private final Set<E> set;
    065        private E last;
    066
    067        protected SetListIterator(final Iterator<E> it, final Set<E> set) {
    068            super(it);
    069            this.set = set;
    070        }
    071
    072        @Override
    073        public E next() {
    074            last = super.next();
    075            return last;
    076        }
    077
    078        @Override
    079        public void remove() {
    080            super.remove();
    081            set.remove(last);
    082            last = null;
    083        }
    084    }
    085
    086    /**
    087     * Inner class iterator.
    088     */
    089    static class SetListListIterator<E> extends
    090            AbstractListIteratorDecorator<E> {
    091
    092        private final Set<E> set;
    093        private E last;
    094
    095        protected SetListListIterator(final ListIterator<E> it, final Set<E> set) {
    096            super(it);
    097            this.set = set;
    098        }
    099
    100        @Override
    101        public void add(final E object) {
    102            if (!set.contains(object)) {
    103                super.add(object);
    104                set.add(object);
    105            }
    106        }
    107
    108        @Override
    109        public E next() {
    110            last = super.next();
    111            return last;
    112        }
    113
    114        @Override
    115        public E previous() {
    116            last = super.previous();
    117            return last;
    118        }
    119
    120        @Override
    121        public void remove() {
    122            super.remove();
    123            set.remove(last);
    124            last = null;
    125        }
    126
    127        @Override
    128        public void set(final E object) {
    129            throw new UnsupportedOperationException("ListIterator does not support set");
    130        }
    131    }
    132
    133    /** Serialization version. */
    134    private static final long serialVersionUID = 7196982186153478694L;
    135
    136    /**
    137     * Factory method to create a SetList using the supplied list to retain order.
    138     * <p>
    139     * If the list contains duplicates, these are removed (first indexed one
    140     * kept). A {@code HashSet} is used for the set behavior.
    141     *
    142     * @param <E>  the element type
    143     * @param list  the list to decorate, must not be null
    144     * @return a new {@link SetUniqueList}
    145     * @throws NullPointerException if list is null
    146     * @since 4.0
    147     */
    148    public static <E> SetUniqueList<E> setUniqueList(final List<E> list) {
    149        Objects.requireNonNull(list, "list");
    150        if (list.isEmpty()) {
    151            return new SetUniqueList<>(list, new HashSet<>());
    152        }
    153        final List<E> temp = new ArrayList<>(list);
    154        list.clear();
    155        final SetUniqueList<E> sl = new SetUniqueList<>(list, new HashSet<>());
    156        sl.addAll(temp);
    157        return sl;
    158    }
    159
    160    /** Internal Set to maintain uniqueness. */
    161    private final Set<E> set;
    162
    163    /**
    164     * Constructor that wraps (not copies) the List and specifies the set to use.
    165     * <p>
    166     * The set and list must both be correctly initialized to the same elements.
    167     *
    168     * @param set  the set to decorate, must not be null
    169     * @param list  the list to decorate, must not be null
    170     * @throws NullPointerException if set or list is null
    171     */
    172    protected SetUniqueList(final List<E> list, final Set<E> set) {
    173        super(list);
    174        this.set = Objects.requireNonNull(set, "set");
    175    }
    176
    177    /**
    178     * Adds an element to the list if it is not already present.
    179     * <p>
    180     * <em>(Violation)</em> The {@code List} interface requires that this
    181     * method returns {@code true} always. However, this class may return
    182     * {@code false} because of the {@code Set} behavior.
    183     *
    184     * @param object  the object to add
    185     * @return true if object was added
    186     */
    187    @Override
    188    public boolean add(final E object) {
    189        // gets initial size
    190        final int sizeBefore = size();
    191
    192        // adds element if unique
    193        add(size(), object);
    194
    195        // compares sizes to detect if collection changed
    196        return sizeBefore != size();
    197    }
    198
    199    /**
    200     * Adds an element to a specific index in the list if it is not already
    201     * present.
    202     * <p>
    203     * <em>(Violation)</em> The {@code List} interface makes the assumption
    204     * that the element is always inserted. This may not happen with this
    205     * implementation.
    206     *
    207     * @param index  the index to insert at
    208     * @param object  the object to add
    209     */
    210    @Override
    211    public void add(final int index, final E object) {
    212        // adds element if it is not contained already
    213        if (!set.contains(object)) {
    214            set.add(object);
    215            super.add(index, object);
    216        }
    217    }
    218
    219    /**
    220     * Adds a collection of objects to the end of the list avoiding duplicates.
    221     * <p>
    222     * Only elements that are not already in this list will be added, and
    223     * duplicates from the specified collection will be ignored.
    224     * <p>
    225     * <em>(Violation)</em> The {@code List} interface makes the assumption
    226     * that the elements are always inserted. This may not happen with this
    227     * implementation.
    228     *
    229     * @param coll  the collection to add in iterator order
    230     * @return true if this collection changed
    231     */
    232    @Override
    233    public boolean addAll(final Collection<? extends E> coll) {
    234        return addAll(size(), coll);
    235    }
    236
    237    /**
    238     * Adds a collection of objects a specific index in the list avoiding
    239     * duplicates.
    240     * <p>
    241     * Only elements that are not already in this list will be added, and
    242     * duplicates from the specified collection will be ignored.
    243     * <p>
    244     * <em>(Violation)</em> The {@code List} interface makes the assumption
    245     * that the elements are always inserted. This may not happen with this
    246     * implementation.
    247     *
    248     * @param index  the index to insert at
    249     * @param coll  the collection to add in iterator order
    250     * @return true if this collection changed
    251     */
    252    @Override
    253    public boolean addAll(final int index, final Collection<? extends E> coll) {
    254        final List<E> temp = new ArrayList<>();
    255        for (final E e : coll) {
    256            if (set.add(e)) {
    257                temp.add(e);
    258            }
    259        }
    260        return super.addAll(index, temp);
    261    }
    262
    263    /**
    264     * Gets an unmodifiable view as a Set.
    265     *
    266     * @return an unmodifiable set view
    267     */
    268    public Set<E> asSet() {
    269        return UnmodifiableSet.unmodifiableSet(set);
    270    }
    271
    272    @Override
    273    public void clear() {
    274        super.clear();
    275        set.clear();
    276    }
    277
    278    @Override
    279    public boolean contains(final Object object) {
    280        return set.contains(object);
    281    }
    282
    283    @Override
    284    public boolean containsAll(final Collection<?> coll) {
    285        return set.containsAll(coll);
    286    }
    287
    288    /**
    289     * Create a new {@link Set} with the same type as the provided {@code set}
    290     * and populate it with all elements of {@code list}.
    291     *
    292     * @param set  the {@link Set} to be used as return type, must not be null
    293     * @param list  the {@link List} to populate the {@link Set}
    294     * @return a new {@link Set} populated with all elements of the provided
    295     *   {@link List}
    296     */
    297    protected Set<E> createSetBasedOnList(final Set<E> set, final List<E> list) {
    298        Set<E> subSet;
    299        if (set.getClass().equals(HashSet.class)) {
    300            subSet = new HashSet<>(list.size());
    301        } else {
    302            try {
    303                subSet = set.getClass().getDeclaredConstructor(set.getClass()).newInstance(set);
    304            } catch (final InstantiationException
    305                    | IllegalAccessException
    306                    | InvocationTargetException
    307                    | NoSuchMethodException ie) {
    308                subSet = new HashSet<>();
    309            }
    310        }
    311        subSet.addAll(list);
    312        return subSet;
    313    }
    314
    315    @Override
    316    public Iterator<E> iterator() {
    317        return new SetListIterator<>(super.iterator(), set);
    318    }
    319
    320    @Override
    321    public ListIterator<E> listIterator() {
    322        return new SetListListIterator<>(super.listIterator(), set);
    323    }
    324
    325    @Override
    326    public ListIterator<E> listIterator(final int index) {
    327        return new SetListListIterator<>(super.listIterator(index), set);
    328    }
    329
    330    @Override
    331    public E remove(final int index) {
    332        final E result = super.remove(index);
    333        set.remove(result);
    334        return result;
    335    }
    336
    337    @Override
    338    public boolean remove(final Object object) {
    339        final boolean result = set.remove(object);
    340        if (result) {
    341            super.remove(object);
    342        }
    343        return result;
    344    }
    345
    346    @Override
    347    public boolean removeAll(final Collection<?> coll) {
    348        boolean result = false;
    349        for (final Object name : coll) {
    350            result |= remove(name);
    351        }
    352        return result;
    353    }
    354
    355    /**
    356     * @since 4.4
    357     */
    358    @Override
    359    public boolean removeIf(final Predicate<? super E> filter) {
    360        final boolean result = super.removeIf(filter);
    361        set.removeIf(filter);
    362        return result;
    363    }
    364
    365    /**
    366     * {@inheritDoc}
    367     * <p>
    368     * This implementation iterates over the elements of this list, checking
    369     * each element in turn to see if it's contained in {@code coll}.
    370     * If it's not contained, it's removed from this list. As a consequence,
    371     * it is advised to use a collection type for {@code coll} that provides
    372     * a fast (e.g. O(1)) implementation of {@link Collection#contains(Object)}.
    373     */
    374    @Override
    375    public boolean retainAll(final Collection<?> coll) {
    376        final boolean result = set.retainAll(coll);
    377        if (!result) {
    378            return false;
    379        }
    380        if (set.isEmpty()) {
    381            super.clear();
    382        } else {
    383            // use the set as parameter for the call to retainAll to improve performance
    384            super.retainAll(set);
    385        }
    386        return result;
    387    }
    388
    389    /**
    390     * Sets the value at the specified index avoiding duplicates.
    391     * <p>
    392     * The object is set into the specified index. Afterwards, any previous
    393     * duplicate is removed. If the object is not already in the list then a
    394     * normal set occurs. If it is present, then the old version is removed.
    395     *
    396     * @param index  the index to insert at
    397     * @param object  the object to set
    398     * @return the previous object
    399     */
    400    @Override
    401    public E set(final int index, final E object) {
    402        final int pos = indexOf(object);
    403        final E removed = super.set(index, object);
    404
    405        if (pos != -1 && pos != index) {
    406            // the object is already in the unique list
    407            // (and it hasn't been swapped with itself)
    408            super.remove(pos); // remove the duplicate by index
    409        }
    410
    411        set.remove(removed); // remove the item deleted by the set
    412        set.add(object); // add the new item to the unique set
    413
    414        return removed; // return the item deleted by the set
    415    }
    416
    417    /**
    418     * {@inheritDoc}
    419     * <p>
    420     * NOTE: from 4.0, an unmodifiable list will be returned, as changes to the
    421     * subList can invalidate the parent list.
    422     */
    423    @Override
    424    public List<E> subList(final int fromIndex, final int toIndex) {
    425        final List<E> superSubList = super.subList(fromIndex, toIndex);
    426        final Set<E> subSet = createSetBasedOnList(set, superSubList);
    427        return ListUtils.unmodifiableList(new SetUniqueList<>(superSubList, subSet));
    428    }
    429
    430}