    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.set;
    018
    019import java.io.IOException;
    020import java.io.InvalidObjectException;
    021import java.io.ObjectInputStream;
    022import java.util.ArrayList;
    023import java.util.Collection;
    024import java.util.HashSet;
    025import java.util.List;
    026import java.util.ListIterator;
    027import java.util.Objects;
    028import java.util.Set;
    029import java.util.function.Predicate;
    030
    031import org.apache.commons.collections4.CollectionUtils;
    032import org.apache.commons.collections4.OrderedIterator;
    033import org.apache.commons.collections4.functors.UniquePredicate;
    034import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
    035import org.apache.commons.collections4.list.UnmodifiableList;
    036
    037/**
    038 * Decorates another {@code Set} to ensure that the order of addition is
    039 * retained and used by the iterator.
    040 * <p>
    041 * If an object is added to the set for a second time, it will remain in the
    042 * original position in the iteration. The order can be observed from the set
    043 * via the iterator or toArray methods.
    044 * </p>
    045 * <p>
    046 * The ListOrderedSet also has various useful direct methods. These include many
    047 * from {@code List}, such as {@code get(int)},
    048 * {@code remove(int)} and {@code indexOf(int)}. An unmodifiable
    049 * {@code List} view of the set can be obtained via {@code asList()}.
    050 * </p>
    051 * <p>
    052 * This class cannot implement the {@code List} interface directly as
    053 * various interface methods (notably equals/hashCode) are incompatible with a
    054 * set.
    055 * </p>
    056 * <p>
    057 * This class is Serializable from Commons Collections 3.1.
    058 * </p>
    059 *
    060 * @param <E> The type of the elements in this set
    061 * @since 3.0
    062 */
    063public class ListOrderedSet<E>
    064    extends AbstractSerializableSetDecorator<E> {
    065
    066    /**
    067     * Internal iterator handle remove.
    068     */
    069    static class OrderedSetIterator<E>
    070        extends AbstractIteratorDecorator<E>
    071        implements OrderedIterator<E> {
    072
    073        /** Object we iterate on */
    074        private final Collection<E> set;
    075
    076        /** Last object retrieved */
    077        private E last;
    078
    079        private OrderedSetIterator(final ListIterator<E> iterator, final Collection<E> set) {
    080            super(iterator);
    081            this.set = set;
    082        }
    083
    084        @Override
    085        public boolean hasPrevious() {
    086            return ((ListIterator<E>) getIterator()).hasPrevious();
    087        }
    088
    089        @Override
    090        public E next() {
    091            last = getIterator().next();
    092            return last;
    093        }
    094
    095        @Override
    096        public E previous() {
    097            last = ((ListIterator<E>) getIterator()).previous();
    098            return last;
    099        }
    100
    101        @Override
    102        public void remove() {
    103            set.remove(last);
    104            getIterator().remove();
    105            last = null;
    106        }
    107    }
    108
    109    /** Serialization version */
    110    private static final long serialVersionUID = -228664372470420141L;
    111
    112    /**
    113     * Factory method to create an ordered set using the supplied list to retain order.
    114     * <p>
    115     * A {@code HashSet} is used for the set behavior.
    116     * </p>
    117     * <p>
    118     * NOTE: If the list contains duplicates, the duplicates are removed,
    119     * altering the specified list.
    120     * </p>
    121     *
    122     * @param <E> The element type
    123     * @param list The list to decorate, must not be null
    124     * @return A new ordered set
    125     * @throws NullPointerException if list is null
    126     * @since 4.0
    127     */
    128    public static <E> ListOrderedSet<E> listOrderedSet(final List<E> list) {
    129        Objects.requireNonNull(list, "list");
    130        CollectionUtils.filter(list, UniquePredicate.uniquePredicate());
    131        final Set<E> set = new HashSet<>(list);
    132
    133        return new ListOrderedSet<>(set, list);
    134    }
    135
    136    /**
    137     * Factory method to create an ordered set.
    138     * <p>
    139     * An {@code ArrayList} is used to retain order.
    140     * </p>
    141     *
    142     * @param <E> The element type
    143     * @param set The set to decorate, must not be null
    144     * @return A new ordered set
    145     * @throws NullPointerException if set is null
    146     * @since 4.0
    147     */
    148    public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set) {
    149        return new ListOrderedSet<>(set);
    150    }
    151
    152    /**
    153     * Factory method to create an ordered set specifying the list and set to use.
    154     * <p>
    155     * The list and set must both be empty.
    156     * </p>
    157     *
    158     * @param <E> The element type
    159     * @param set The set to decorate, must be empty and not null
    160     * @param list The list to decorate, must be empty and not null
    161     * @return A new ordered set
    162     * @throws NullPointerException if set or list is null
    163     * @throws IllegalArgumentException if either the set or list is not empty
    164     * @since 4.0
    165     */
    166    public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set, final List<E> list) {
    167        Objects.requireNonNull(set, "set");
    168        Objects.requireNonNull(list, "list");
    169        if (!set.isEmpty() || !list.isEmpty()) {
    170            throw new IllegalArgumentException("Set and List must be empty");
    171        }
    172        return new ListOrderedSet<>(set, list);
    173    }
    174
    175    /** Internal list to hold the sequence of objects */
    176    private final List<E> setOrder;
    177
    178    /**
    179     * Constructs a new empty {@code ListOrderedSet} using a
    180     * {@code HashSet} and an {@code ArrayList} internally.
    181     *
    182     * @since 3.1
    183     */
    184    public ListOrderedSet() {
    185        super(new HashSet<>());
    186        setOrder = new ArrayList<>();
    187    }
    188
    189    /**
    190     * Constructor that wraps (not copies).
    191     *
    192     * @param set The set to decorate, must not be null
    193     * @throws NullPointerException if set is null
    194     */
    195    protected ListOrderedSet(final Set<E> set) {
    196        super(set);
    197        setOrder = new ArrayList<>(set);
    198    }
    199
    200    /**
    201     * Constructor that wraps (not copies) the Set and specifies the list to
    202     * use.
    203     * <p>
    204     * The set and list must both be correctly initialized to the same elements.
    205     * </p>
    206     *
    207     * @param set The set to decorate, must not be null
    208     * @param list The list to decorate, must not be null
    209     * @throws NullPointerException if set or list is null
    210     */
    211    protected ListOrderedSet(final Set<E> set, final List<E> list) {
    212        super(set);
    213        setOrder = Objects.requireNonNull(list, "list");
    214    }
    215
    216    @Override
    217    public boolean add(final E object) {
    218        if (decorated().add(object)) {
    219            setOrder.add(object);
    220            return true;
    221        }
    222        return false;
    223    }
    224
    225    /**
    226     * Inserts the specified element at the specified position if it is not yet
    227     * contained in this ordered set (optional operation). Shifts the element
    228     * currently at this position and any subsequent elements to the right.
    229     *
    230     * @param index The index at which the element is to be inserted
    231     * @param object The element to be inserted
    232     * @see List#add(int, Object)
    233     */
    234    public void add(final int index, final E object) {
    235        if (index < 0 || index > setOrder.size()) {
    236            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + setOrder.size());
    237        }
    238        if (!contains(object)) {
    239            decorated().add(object);
    240            setOrder.add(index, object);
    241        }
    242    }
    243
    244    @Override
    245    public boolean addAll(final Collection<? extends E> coll) {
    246        boolean result = false;
    247        for (final E e : coll) {
    248            result |= add(e);
    249        }
    250        return result;
    251    }
    252
    253    /**
    254     * Inserts all elements in the specified collection not yet contained in the
    255     * ordered set at the specified position (optional operation). Shifts the
    256     * element currently at the position and all subsequent elements to the
    257     * right.
    258     *
    259     * @param index The position to insert the elements
    260     * @param coll The collection containing the elements to be inserted
    261     * @return {@code true} if this ordered set changed as a result of the call
    262     * @see List#addAll(int, Collection)
    263     */
    264    public boolean addAll(final int index, final Collection<? extends E> coll) {
    265        if (index < 0 || index > setOrder.size()) {
    266            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + setOrder.size());
    267        }
    268        boolean changed = false;
    269        // collect all elements to be added for performance reasons
    270        final List<E> toAdd = new ArrayList<>();
    271        for (final E e : coll) {
    272            if (contains(e)) {
    273                continue;
    274            }
    275            decorated().add(e);
    276            toAdd.add(e);
    277            changed = true;
    278        }
    279
    280        if (changed) {
    281            setOrder.addAll(index, toAdd);
    282        }
    283
    284        return changed;
    285    }
    286
    287    /**
    288     * Gets an unmodifiable view of the order of the Set.
    289     *
    290     * @return An unmodifiable list view
    291     */
    292    public List<E> asList() {
    293        return UnmodifiableList.unmodifiableList(setOrder);
    294    }
    295
    296    @Override
    297    public void clear() {
    298        decorated().clear();
    299        setOrder.clear();
    300    }
    301
    302    /**
    303     * Gets the element at the specified position in this ordered set.
    304     *
    305     * @param index The position of the element in the ordered {@link Set}.
    306     * @return The element at position {@code index}
    307     * @see List#get(int)
    308     */
    309    public E get(final int index) {
    310        return setOrder.get(index);
    311    }
    312
    313    /**
    314     * Returns the index of the first occurrence of the specified element in
    315     * ordered set.
    316     *
    317     * @param object The element to search for
    318     * @return The index of the first occurrence of the object, or {@code -1} if
    319     *         this ordered set does not contain this object
    320     * @see List#indexOf(Object)
    321     */
    322    public int indexOf(final Object object) {
    323        return setOrder.indexOf(object);
    324    }
    325
    326    @Override
    327    public OrderedIterator<E> iterator() {
    328        return new OrderedSetIterator<>(setOrder.listIterator(), decorated());
    329    }
    330
    331    /**
    332     * Deserializes the set and re-checks that the iteration order matches the
    333     * decorated set, as the constructors guarantee.
    334     *
    335     * @param in  The input stream
    336     * @throws IOException Thrown if an error occurs while reading from the stream
    337     * @throws ClassNotFoundException if a class read from the stream cannot be loaded
    338     */
    339    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    340        in.defaultReadObject();
    341        if (setOrder.size() != size() || !new HashSet<>(setOrder).equals(decorated())) {
    342            throw new InvalidObjectException("Inconsistent ListOrderedSet deserialized: iteration order does not match the set");
    343        }
    344    }
    345
    346    /**
    347     * Removes the element at the specified position from the ordered set.
    348     * Shifts any subsequent elements to the left.
    349     *
    350     * @param index The index of the element to be removed
    351     * @return The element that has been remove from the ordered set
    352     * @see List#remove(int)
    353     */
    354    public E remove(final int index) {
    355        final E obj = setOrder.remove(index);
    356        remove(obj);
    357        return obj;
    358    }
    359
    360    @Override
    361    public boolean remove(final Object object) {
    362        final boolean result = decorated().remove(object);
    363        if (result) {
    364            setOrder.remove(object);
    365        }
    366        return result;
    367    }
    368
    369    @Override
    370    public boolean removeAll(final Collection<?> coll) {
    371        boolean result = false;
    372        for (final Object name : coll) {
    373            result |= remove(name);
    374        }
    375        return result;
    376    }
    377
    378    /**
    379     * @since 4.4
    380     */
    381    @Override
    382    public boolean removeIf(final Predicate<? super E> filter) {
    383        if (Objects.isNull(filter)) {
    384            return false;
    385        }
    386        final boolean result = decorated().removeIf(filter);
    387        if (result) {
    388            setOrder.removeIf(filter);
    389        }
    390        return result;
    391    }
    392
    393    /**
    394     * {@inheritDoc}
    395     * <p>
    396     * This implementation iterates over the elements of this set, checking
    397     * each element in turn to see if it's contained in {@code coll}.
    398     * If it's not contained, it's removed from this set. As a consequence,
    399     * it is advised to use a collection type for {@code coll} that provides
    400     * a fast (for example O(1)) implementation of {@link Collection#contains(Object)}.
    401     * </p>
    402     */
    403    @Override
    404    public boolean retainAll(final Collection<?> coll) {
    405        final boolean result = decorated().retainAll(coll);
    406        if (!result) {
    407            return false;
    408        }
    409        if (decorated().isEmpty()) {
    410            setOrder.clear();
    411        } else {
    412            setOrder.removeIf(e -> !decorated().contains(e));
    413        }
    414        return result;
    415    }
    416
    417    @Override
    418    public Object[] toArray() {
    419        return setOrder.toArray();
    420    }
    421
    422    @Override
    423    public <T> T[] toArray(final T[] a) {
    424        return setOrder.toArray(a);
    425    }
    426
    427    /**
    428     * Uses the underlying List's toString so that order is achieved. This means
    429     * that the decorated Set's toString is not used, so any custom toStrings
    430     * will be ignored.
    431     *
    432     * @return A string representation of the ordered set
    433     */
    434    // Fortunately List.toString and Set.toString look the same
    435    @Override
    436    public String toString() {
    437        return setOrder.toString();
    438    }
    439
    440}