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