/*
    * 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
    *
    *      https://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.list;
  
  import java.io.IOException;
  import java.io.InvalidObjectException;
  import java.io.ObjectInputStream;
  import java.lang.reflect.InvocationTargetException;
  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.Objects;
  import java.util.Set;
  import java.util.function.Predicate;
  
  import org.apache.commons.collections4.ListUtils;
  import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
  import org.apache.commons.collections4.iterators.AbstractListIteratorDecorator;
  import org.apache.commons.collections4.set.ListOrderedSet;
  import org.apache.commons.collections4.set.UnmodifiableSet;
  
  /**
   * Decorates a {@code List} to ensure that no duplicates are present much
   * like a {@code Set}.
   * <p>
   * The {@code List} interface makes certain assumptions/requirements. This
   * implementation breaks these in certain ways, but this is merely the result of
   * rejecting duplicates. Each violation is explained in the method, but it
   * should not affect you. Bear in mind that Sets require immutable objects to
   * function correctly.
   * </p>
   * <p>
   * The {@link ListOrderedSet ListOrderedSet}
   * class provides an alternative approach, by wrapping an existing Set and
   * retaining insertion order in the iterator.
   * </p>
   * <p>
   * This class is Serializable from Commons Collections 3.1.
   * </p>
   *
   * @param <E> The type of the elements in the list.
   * @since 3.0
   */
  public class SetUniqueList<E> extends AbstractSerializableListDecorator<E> {
  
      /**
       * Inner class iterator.
       */
      static class SetListIterator<E> extends AbstractIteratorDecorator<E> {
  
          private final Set<E> set;
          private E last;
  
          protected SetListIterator(final Iterator<E> it, final Set<E> set) {
              super(it);
              this.set = set;
          }
  
          @Override
          public E next() {
              last = super.next();
              return last;
          }
  
          @Override
          public void remove() {
              super.remove();
              set.remove(last);
              last = null;
          }
      }
  
      /**
       * Inner class iterator.
       */
      static class SetListListIterator<E> extends
              AbstractListIteratorDecorator<E> {
  
          private final Set<E> set;
          private E last;
  
          protected SetListListIterator(final ListIterator<E> it, final Set<E> set) {
             super(it);
             this.set = set;
         }
 
         @Override
         public void add(final E object) {
             if (!set.contains(object)) {
                 super.add(object);
                 set.add(object);
             }
         }
 
         @Override
         public E next() {
             last = super.next();
             return last;
         }
 
         @Override
         public E previous() {
             last = super.previous();
             return last;
         }
 
         @Override
         public void remove() {
             super.remove();
             set.remove(last);
             last = null;
         }
 
         /**
          * Always throws {@link UnsupportedOperationException}.
          *
          * @param object Ignored.
          * @throws UnsupportedOperationException Always thrown.
          */
         @Override
         public void set(final E object) {
             throw new UnsupportedOperationException("ListIterator does not support set");
         }
     }
 
     /** Serialization version. */
     private static final long serialVersionUID = 7196982186153478694L;
 
     /**
      * Factory method to create a SetList using the supplied list to retain order.
      * <p>
      * If the list contains duplicates, these are removed (first indexed one
      * kept). A {@code HashSet} is used for the set behavior.
      *
      * @param <E>  the element type
      * @param list  The list to decorate, must not be null
      * @return A new {@link SetUniqueList}
      * @throws NullPointerException if list is null
      * @since 4.0
      */
     public static <E> SetUniqueList<E> setUniqueList(final List<E> list) {
         Objects.requireNonNull(list, "list");
         if (list.isEmpty()) {
             return new SetUniqueList<>(list, new HashSet<>());
         }
         final List<E> temp = new ArrayList<>(list);
         list.clear();
         final SetUniqueList<E> sl = new SetUniqueList<>(list, new HashSet<>());
         sl.addAll(temp);
         return sl;
     }
 
     /** Internal Set to maintain uniqueness. */
     private final Set<E> set;
 
     /**
      * Constructor that wraps (not copies) the List and specifies the set to use.
      * <p>
      * The set and list must both be correctly initialized 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 SetUniqueList(final List<E> list, final Set<E> set) {
         super(list);
         this.set = Objects.requireNonNull(set, "set");
     }
 
     /**
      * Adds an element to the list if it is not already present.
      * <p>
      * <em>(Violation)</em> The {@code List} interface requires that this
      * method returns {@code true} always. However, this class may return
      * {@code false} because of the {@code Set} behavior.
      *
      * @param object  The object to add
      * @return true if object was added
      */
     @Override
     public boolean add(final E object) {
         // gets initial size
         final int sizeBefore = size();
 
         // adds element if unique
         add(size(), object);
 
         // compares sizes to detect if collection changed
         return sizeBefore != size();
     }
 
     /**
      * Adds an element to a specific index in the list if it is not already
      * present.
      * <p>
      * <em>(Violation)</em> The {@code List} interface makes the assumption
      * that the element is always inserted. This may not happen with this
      * implementation.
      *
      * @param index  The index to insert at
      * @param object  The object to add
      */
     @Override
     public void add(final int index, final E object) {
         if (index < 0 || index > size()) {
             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
         }
         // adds element if it is not contained already
         if (!set.contains(object)) {
             set.add(object);
             super.add(index, object);
         }
     }
 
     /**
      * Adds a collection of objects to the end of the list avoiding duplicates.
      * <p>
      * Only elements that are not already in this list will be added, and
      * duplicates from the specified collection will be ignored.
      * <p>
      * <em>(Violation)</em> The {@code List} interface makes the assumption
      * that the elements are always inserted. This may not happen with this
      * implementation.
      *
      * @param coll  The collection to add in iterator order
      * @return true if this collection changed
      */
     @Override
     public boolean addAll(final Collection<? extends E> coll) {
         return addAll(size(), coll);
     }
 
     /**
      * Adds a collection of objects a specific index in the list avoiding
      * duplicates.
      * <p>
      * Only elements that are not already in this list will be added, and
      * duplicates from the specified collection will be ignored.
      * <p>
      * <em>(Violation)</em> The {@code List} interface makes the assumption
      * that the elements are always inserted. This may not happen with this
      * implementation.
      *
      * @param index  The index to insert at
      * @param coll  The collection to add in iterator order
      * @return true if this collection changed
      */
     @Override
     public boolean addAll(final int index, final Collection<? extends E> coll) {
         if (index < 0 || index > size()) {
             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
         }
         final List<E> temp = new ArrayList<>();
         for (final E e : coll) {
             if (set.add(e)) {
                 temp.add(e);
             }
         }
         return super.addAll(index, temp);
     }
 
     /**
      * Gets an unmodifiable view as a Set.
      *
      * @return An unmodifiable set view
      */
     public Set<E> asSet() {
         return UnmodifiableSet.unmodifiableSet(set);
     }
 
     @Override
     public void clear() {
         super.clear();
         set.clear();
     }
 
     @Override
     public boolean contains(final Object object) {
         return set.contains(object);
     }
 
     @Override
     public boolean containsAll(final Collection<?> coll) {
         return set.containsAll(coll);
     }
 
     /**
      * Create a new {@link Set} with the same type as the provided {@code set}
      * and populate it with all elements of {@code list}.
      *
      * @param set  The {@link Set} to be used as return type, must not be null
      * @param list  The {@link List} to populate the {@link Set}
      * @return A new {@link Set} populated with all elements of the provided
      *   {@link List}
      */
     protected Set<E> createSetBasedOnList(final Set<E> set, final List<E> list) {
         Set<E> subSet;
         if (set.getClass().equals(HashSet.class)) {
             subSet = new HashSet<>(list.size());
         } else {
             try {
                 subSet = set.getClass().getDeclaredConstructor(set.getClass()).newInstance(set);
             } catch (final InstantiationException
                     | IllegalAccessException
                     | InvocationTargetException
                     | NoSuchMethodException ie) {
                 subSet = new HashSet<>();
             }
         }
         subSet.addAll(list);
         return subSet;
     }
 
     @Override
     public Iterator<E> iterator() {
         return new SetListIterator<>(super.iterator(), set);
     }
 
     @Override
     public ListIterator<E> listIterator() {
         return new SetListListIterator<>(super.listIterator(), set);
     }
 
     @Override
     public ListIterator<E> listIterator(final int index) {
         return new SetListListIterator<>(super.listIterator(index), set);
     }
 
     /**
      * Deserializes the list and re-checks the no-duplicate invariant the
      * constructors guarantee.
      *
      * @param in  The input stream
      * @throws IOException Thrown if an error occurs while reading from the stream
      * @throws ClassNotFoundException if a class read from the stream cannot be loaded
      */
     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
         in.defaultReadObject();
         if (set.size() != size() || !new HashSet<>(decorated()).equals(set)) {
             throw new InvalidObjectException("Inconsistent SetUniqueList deserialized: backing list does not match the uniqueness set");
         }
     }
 
     @Override
     public E remove(final int index) {
         final E result = super.remove(index);
         set.remove(result);
         return result;
     }
 
     @Override
     public boolean remove(final Object object) {
         final boolean result = set.remove(object);
         if (result) {
             super.remove(object);
         }
         return result;
     }
 
     @Override
     public boolean removeAll(final Collection<?> coll) {
         boolean result = false;
         for (final Object name : coll) {
             result |= remove(name);
         }
         return result;
     }
 
     /**
      * @since 4.4
      */
     @Override
     public boolean removeIf(final Predicate<? super E> filter) {
         final boolean result = super.removeIf(filter);
         set.removeIf(filter);
         return result;
     }
 
     /**
      * {@inheritDoc}
      * <p>
      * This implementation iterates over the elements of this list, checking
      * each element in turn to see if it's contained in {@code coll}.
      * If it's not contained, it's removed from this list. As a consequence,
      * it is advised to use a collection type for {@code coll} that provides
      * a fast (for example O(1)) implementation of {@link Collection#contains(Object)}.
      */
     @Override
     public boolean retainAll(final Collection<?> coll) {
         final boolean result = set.retainAll(coll);
         if (!result) {
             return false;
         }
         if (set.isEmpty()) {
             super.clear();
         } else {
             // use the set as parameter for the call to retainAll to improve performance
             super.retainAll(set);
         }
         return result;
     }
 
     /**
      * Sets the value at the specified index avoiding duplicates.
      * <p>
      * The object is set into the specified index. Afterwards, any previous
      * duplicate is removed. If the object is not already in the list then a
      * normal set occurs. If it is present, then the old version is removed.
      *
      * @param index  The index to insert at
      * @param object  The object to set
      * @return The previous object
      */
     @Override
     public E set(final int index, final E object) {
         final int pos = indexOf(object);
         final E removed = super.set(index, object);
 
         if (pos != -1 && pos != index) {
             // the object is already in the unique list
             // (and it hasn't been swapped with itself)
             super.remove(pos); // remove the duplicate by index
         }
 
         set.remove(removed); // remove the item deleted by the set
         set.add(object); // add the new item to the unique set
 
         return removed; // return the item deleted by the set
     }
 
     /**
      * {@inheritDoc}
      * <p>
      * NOTE: from 4.0, an unmodifiable list will be returned, as changes to the
      * subList can invalidate the parent list.
      */
     @Override
     public List<E> subList(final int fromIndex, final int toIndex) {
         final List<E> superSubList = super.subList(fromIndex, toIndex);
         final Set<E> subSet = createSetBasedOnList(set, superSubList);
         return ListUtils.unmodifiableList(new SetUniqueList<>(superSubList, subSet));
     }
 
 }