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