/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.set;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;
import java.util.Objects;
import java.util.function.Predicate;

import org.apache.commons.collections4.CollectionUtils;
import org.apache.commons.collections4.OrderedIterator;
import org.apache.commons.collections4.functors.UniquePredicate;
import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
import org.apache.commons.collections4.list.UnmodifiableList;

Decorates another Set to ensure that the order of addition is
retained and used by the iterator.

If an object is added to the set for a second time, it will remain in the
original position in the iteration. The order can be observed from the set
via the iterator or toArray methods.


The ListOrderedSet also has various useful direct methods. These include many
from List, such as get(int),
remove(int) and indexOf(int). An unmodifiable
List view of the set can be obtained via asList().


This class cannot implement the List interface directly as
various interface methods (notably equals/hashCode) are incompatible with a
set.


This class is Serializable from Commons Collections 3.1.

Type parameters:
<E> – the type of the elements in this set
Since:
3.0/**
 * Decorates another <code>Set</code> to ensure that the order of addition is
 * retained and used by the iterator.
 * <p>
 * If an object is added to the set for a second time, it will remain in the
 * original position in the iteration. The order can be observed from the set
 * via the iterator or toArray methods.
 * </p>
 * <p>
 * The ListOrderedSet also has various useful direct methods. These include many
 * from <code>List</code>, such as <code>get(int)</code>,
 * <code>remove(int)</code> and <code>indexOf(int)</code>. An unmodifiable
 * <code>List</code> view of the set can be obtained via <code>asList()</code>.
 * </p>
 * <p>
 * This class cannot implement the <code>List</code> interface directly as
 * various interface methods (notably equals/hashCode) are incompatible with a
 * set.
 * </p>
 * <p>
 * This class is Serializable from Commons Collections 3.1.
 * </p>
 *
 * @param <E> the type of the elements in this set
 * @since 3.0
 */
public class ListOrderedSet<E>
    extends AbstractSerializableSetDecorator<E> {

    
Serialization version /** Serialization version */
    private static final long serialVersionUID = -228664372470420141L;

    
Internal list to hold the sequence of objects /** Internal list to hold the sequence of objects */
    private final List<E> setOrder;

    
Factory method to create an ordered set specifying the list and set to use.

The list and set must both be empty.
Params:
set – the set to decorate, must be empty and not null
list – the list to decorate, must be empty and not null
Type parameters:
<E> – the element type
Throws:
NullPointerException – if set or list is null
IllegalArgumentException – if either the set or list is not empty
Returns:
a new ordered set
Since:
4.0/**
     * Factory method to create an ordered set specifying the list and set to use.
     * <p>
     * The list and set must both be empty.
     *
     * @param <E> the element type
     * @param set the set to decorate, must be empty and not null
     * @param list the list to decorate, must be empty and not null
     * @return a new ordered set
     * @throws NullPointerException if set or list is null
     * @throws IllegalArgumentException if either the set or list is not empty
     * @since 4.0
     */
    public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set, final List<E> list) {
        if (set == null) {
            throw new NullPointerException("Set must not be null");
        }
        if (list == null) {
            throw new NullPointerException("List must not be null");
        }
        if (set.size() > 0 || list.size() > 0) {
            throw new IllegalArgumentException("Set and List must be empty");
        }
        return new ListOrderedSet<>(set, list);
    }

    
Factory method to create an ordered set.

An ArrayList is used to retain order.
Params:
set – the set to decorate, must not be null
Type parameters:
<E> – the element type
Throws:
NullPointerException – if set is null
Returns:
a new ordered set
Since:
4.0/**
     * Factory method to create an ordered set.
     * <p>
     * An <code>ArrayList</code> is used to retain order.
     *
     * @param <E> the element type
     * @param set the set to decorate, must not be null
     * @return a new ordered set
     * @throws NullPointerException if set is null
     * @since 4.0
     */
    public static <E> ListOrderedSet<E> listOrderedSet(final Set<E> set) {
        return new ListOrderedSet<>(set);
    }

    
Factory method to create an ordered set using the supplied list to retain order.

A HashSet is used for the set behaviour.

NOTE: If the list contains duplicates, the duplicates are removed,
altering the specified list.
Params:
list – the list to decorate, must not be null
Type parameters:
<E> – the element type
Throws:
NullPointerException – if list is null
Returns:
a new ordered set
Since:
4.0/**
     * Factory method to create an ordered set using the supplied list to retain order.
     * <p>
     * A <code>HashSet</code> is used for the set behaviour.
     * <p>
     * NOTE: If the list contains duplicates, the duplicates are removed,
     * altering the specified list.
     *
     * @param <E> the element type
     * @param list the list to decorate, must not be null
     * @return a new ordered set
     * @throws NullPointerException if list is null
     * @since 4.0
     */
    public static <E> ListOrderedSet<E> listOrderedSet(final List<E> list) {
        if (list == null) {
            throw new NullPointerException("List must not be null");
        }
        CollectionUtils.filter(list, UniquePredicate.uniquePredicate());
        final Set<E> set = new HashSet<>(list);

        return new ListOrderedSet<>(set, list);
    }

    // -----------------------------------------------------------------------
    
Constructs a new empty ListOrderedSet using a
HashSet and an ArrayList internally.
Since:
3.1/**
     * Constructs a new empty <code>ListOrderedSet</code> using a
     * <code>HashSet</code> and an <code>ArrayList</code> internally.
     *
     * @since 3.1
     */
    public ListOrderedSet() {
        super(new HashSet<E>());
        setOrder = new ArrayList<>();
    }

    
Constructor that wraps (not copies).
Params:
set – the set to decorate, must not be null
Throws:
IllegalArgumentException – if set is null/**
     * Constructor that wraps (not copies).
     *
     * @param set the set to decorate, must not be null
     * @throws IllegalArgumentException if set is null
     */
    protected ListOrderedSet(final Set<E> set) {
        super(set);
        setOrder = new ArrayList<>(set);
    }

    
Constructor that wraps (not copies) the Set and specifies the list to
use.

The set and list must both be correctly initialised to the same elements.
Params:
set – the set to decorate, must not be null
list – the list to decorate, must not be null
Throws:
NullPointerException – if set or list is null/**
     * Constructor that wraps (not copies) the Set and specifies the list to
     * use.
     * <p>
     * The set and list must both be correctly initialised to the same elements.
     *
     * @param set the set to decorate, must not be null
     * @param list the list to decorate, must not be null
     * @throws NullPointerException if set or list is null
     */
    protected ListOrderedSet(final Set<E> set, final List<E> list) {
        super(set);
        if (list == null) {
            throw new NullPointerException("List must not be null");
        }
        setOrder = list;
    }

    // -----------------------------------------------------------------------
    
Gets an unmodifiable view of the order of the Set.
Returns:
an unmodifiable list view/**
     * Gets an unmodifiable view of the order of the Set.
     *
     * @return an unmodifiable list view
     */
    public List<E> asList() {
        return UnmodifiableList.unmodifiableList(setOrder);
    }

    // -----------------------------------------------------------------------
    @Override
    public void clear() {
        decorated().clear();
        setOrder.clear();
    }

    @Override
    public OrderedIterator<E> iterator() {
        return new OrderedSetIterator<>(setOrder.listIterator(), decorated());
    }

    @Override
    public boolean add(final E object) {
        if (decorated().add(object)) {
            setOrder.add(object);
            return true;
        }
        return false;
    }

    @Override
    public boolean addAll(final Collection<? extends E> coll) {
        boolean result = false;
        for (final E e : coll) {
            result |= add(e);
        }
        return result;
    }

    @Override
    public boolean remove(final Object object) {
        final boolean result = decorated().remove(object);
        if (result) {
            setOrder.remove(object);
        }
        return result;
    }

    
Since:
4.4/**
     * @since 4.4
     */
    @Override
    public boolean removeIf(final Predicate<? super E> filter) {
        if (Objects.isNull(filter)) {
            return false;
        }
        final boolean result = decorated().removeIf(filter);
        if (result) {
            setOrder.removeIf(filter);
        }
        return result;
    }

    @Override
    public boolean removeAll(final Collection<?> coll) {
        boolean result = false;
        for (final Object name : coll) {
            result |= remove(name);
        }
        return result;
    }

    
{@inheritDoc}

This implementation iterates over the elements of this set, checking
each element in turn to see if it's contained in coll.
If it's not contained, it's removed from this set. As a consequence,
it is advised to use a collection type for coll that provides a fast (e.g. O(1)) implementation of Collection.contains(Object). /**
     * {@inheritDoc}
     * <p>
     * This implementation iterates over the elements of this set, checking
     * each element in turn to see if it's contained in <code>coll</code>.
     * If it's not contained, it's removed from this set. As a consequence,
     * it is advised to use a collection type for <code>coll</code> that provides
     * a fast (e.g. O(1)) implementation of {@link Collection#contains(Object)}.
     */
    @Override
    public boolean retainAll(final Collection<?> coll) {
        final boolean result = decorated().retainAll(coll);
        if (result == false) {
            return false;
        }
        if (decorated().size() == 0) {
            setOrder.clear();
        } else {
            for (final Iterator<E> it = setOrder.iterator(); it.hasNext();) {
                if (!decorated().contains(it.next())) {
                    it.remove();
                }
            }
        }
        return result;
    }

    @Override
    public Object[] toArray() {
        return setOrder.toArray();
    }

    @Override
    public <T> T[] toArray(final T a[]) {
        return setOrder.toArray(a);
    }

    // -----------------------------------------------------------------------
    // Additional methods that comply to the {@link List} interface
    // -----------------------------------------------------------------------

    
Returns the element at the specified position in this ordered set.
Params:
index – the position of the element in the ordered Set.
See Also:
List.get(int)
Returns:
the element at position index/**
     * Returns the element at the specified position in this ordered set.
     *
     * @param index the position of the element in the ordered {@link Set}.
     * @return the element at position {@code index}
     * @see List#get(int)
     */
    public E get(final int index) {
        return setOrder.get(index);
    }

    
Returns the index of the first occurrence of the specified element in
ordered set.
Params:
object – the element to search for
See Also:
List.indexOf(Object)
Returns:
the index of the first occurrence of the object, or -1 if this ordered set does not contain this object/**
     * Returns the index of the first occurrence of the specified element in
     * ordered set.
     *
     * @param object the element to search for
     * @return the index of the first occurrence of the object, or {@code -1} if
     *         this ordered set does not contain this object
     * @see List#indexOf(Object)
     */
    public int indexOf(final Object object) {
        return setOrder.indexOf(object);
    }

    
Inserts the specified element at the specified position if it is not yet
contained in this ordered set (optional operation). Shifts the element
currently at this position and any subsequent elements to the right.
Params:
index – the index at which the element is to be inserted
object – the element to be inserted
See Also:
List.add(int, Object)/**
     * Inserts the specified element at the specified position if it is not yet
     * contained in this ordered set (optional operation). Shifts the element
     * currently at this position and any subsequent elements to the right.
     *
     * @param index the index at which the element is to be inserted
     * @param object the element to be inserted
     * @see List#add(int, Object)
     */
    public void add(final int index, final E object) {
        if (!contains(object)) {
            decorated().add(object);
            setOrder.add(index, object);
        }
    }

    
Inserts all elements in the specified collection not yet contained in the
ordered set at the specified position (optional operation). Shifts the
element currently at the position and all subsequent elements to the
right.
Params:
index – the position to insert the elements
coll – the collection containing the elements to be inserted
See Also:
List.addAll(int, Collection)
Returns:
true if this ordered set changed as a result of the call/**
     * Inserts all elements in the specified collection not yet contained in the
     * ordered set at the specified position (optional operation). Shifts the
     * element currently at the position and all subsequent elements to the
     * right.
     *
     * @param index the position to insert the elements
     * @param coll the collection containing the elements to be inserted
     * @return {@code true} if this ordered set changed as a result of the call
     * @see List#addAll(int, Collection)
     */
    public boolean addAll(final int index, final Collection<? extends E> coll) {
        boolean changed = false;
        // collect all elements to be added for performance reasons
        final List<E> toAdd = new ArrayList<>();
        for (final E e : coll) {
            if (contains(e)) {
                continue;
            }
            decorated().add(e);
            toAdd.add(e);
            changed = true;
        }

        if (changed) {
            setOrder.addAll(index, toAdd);
        }

        return changed;
    }

    
Removes the element at the specified position from the ordered set.
Shifts any subsequent elements to the left.
Params:
index – the index of the element to be removed
See Also:
List.remove(int)
Returns:
the element that has been remove from the ordered set/**
     * Removes the element at the specified position from the ordered set.
     * Shifts any subsequent elements to the left.
     *
     * @param index the index of the element to be removed
     * @return the element that has been remove from the ordered set
     * @see List#remove(int)
     */
    public E remove(final int index) {
        final E obj = setOrder.remove(index);
        remove(obj);
        return obj;
    }

    
Uses the underlying List's toString so that order is achieved. This means
that the decorated Set's toString is not used, so any custom toStrings
will be ignored.
Returns:
a string representation of the ordered set/**
     * Uses the underlying List's toString so that order is achieved. This means
     * that the decorated Set's toString is not used, so any custom toStrings
     * will be ignored.
     *
     * @return a string representation of the ordered set
     */
    // Fortunately List.toString and Set.toString look the same
    @Override
    public String toString() {
        return setOrder.toString();
    }

    // -----------------------------------------------------------------------
    
Internal iterator handle remove.
/**
     * Internal iterator handle remove.
     */
    static class OrderedSetIterator<E>
        extends AbstractIteratorDecorator<E>
        implements OrderedIterator<E> {

        
Object we iterate on /** Object we iterate on */
        private final Collection<E> set;

        
Last object retrieved /** Last object retrieved */
        private E last;

        private OrderedSetIterator(final ListIterator<E> iterator, final Collection<E> set) {
            super(iterator);
            this.set = set;
        }

        @Override
        public E next() {
            last = getIterator().next();
            return last;
        }

        @Override
        public void remove() {
            set.remove(last);
            getIterator().remove();
            last = null;
        }

        @Override
        public boolean hasPrevious() {
            return ((ListIterator<E>) getIterator()).hasPrevious();
        }

        @Override
        public E previous() {
            last = ((ListIterator<E>) getIterator()).previous();
            return last;
        }
    }

}