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