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