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}