/*
    * 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.multiset;
  
  import java.io.IOException;
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
  import java.util.AbstractCollection;
  import java.util.AbstractSet;
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.Objects;
  import java.util.Set;
  
  import org.apache.commons.collections4.IteratorUtils;
  import org.apache.commons.collections4.MultiSet;
  import org.apache.commons.collections4.Transformer;
  
  /**
   * Abstract implementation of the {@link MultiSet} interface to simplify the
   * creation of subclass implementations.
   *
   * @param <E> the type held in the multiset
   * @since 4.1
   */
  public abstract class AbstractMultiSet<E> extends AbstractCollection<E> implements MultiSet<E> {
  
      /**
       * Inner class AbstractEntry.
       *
       * @param <E> the element type.
       */
      protected abstract static class AbstractEntry<E> implements Entry<E> {
  
          @Override
          public boolean equals(final Object object) {
              if (object instanceof Entry) {
                  final Entry<?> other = (Entry<?>) object;
                  final E element = getElement();
                  final Object otherElement = other.getElement();
  
                  return this.getCount() == other.getCount() &&
                         Objects.equals(element, otherElement);
              }
              return false;
          }
  
          @Override
          public int hashCode() {
              final E element = getElement();
              return (element == null ? 0 : element.hashCode()) ^ getCount();
          }
  
          @Override
          public String toString() {
              return String.format("%s:%d", getElement(), getCount());
          }
      }
  
      /**
       * Inner class EntrySet.
       *
       * @param <E> the element type.
       */
      protected static class EntrySet<E> extends AbstractSet<Entry<E>> {
  
          private final AbstractMultiSet<E> parent;
  
          /**
           * Constructs a new view of the MultiSet.
           *
           * @param parent  the parent MultiSet
           */
          protected EntrySet(final AbstractMultiSet<E> parent) {
              this.parent = parent;
          }
  
          @Override
          public boolean contains(final Object obj) {
              if (!(obj instanceof Entry<?>)) {
                  return false;
              }
              final Entry<?> entry = (Entry<?>) obj;
              final Object element = entry.getElement();
              return parent.getCount(element) == entry.getCount();
         }
 
         @Override
         public Iterator<Entry<E>> iterator() {
             return parent.createEntrySetIterator();
         }
 
         @Override
         public boolean remove(final Object obj) {
             if (!(obj instanceof Entry<?>)) {
                 return false;
             }
             final Entry<?> entry = (Entry<?>) obj;
             final Object element = entry.getElement();
             if (parent.contains(element)) {
                 final int count = parent.getCount(element);
                 if (entry.getCount() == count) {
                     parent.remove(element, count);
                     return true;
                 }
             }
             return false;
         }
 
         @Override
         public int size() {
             return parent.uniqueElements();
         }
     }
 
     /**
      * Inner class iterator for the MultiSet.
      */
     private static final class MultiSetIterator<E> implements Iterator<E> {
         private final AbstractMultiSet<E> parent;
         private final Iterator<Entry<E>> entryIterator;
         private Entry<E> current;
         private int itemCount;
         private boolean canRemove;
 
         /**
          * Constructs a new instance.
          *
          * @param parent the parent multiset
          */
         MultiSetIterator(final AbstractMultiSet<E> parent) {
             this.parent = parent;
             this.entryIterator = parent.entrySet().iterator();
             this.current = null;
             this.canRemove = false;
         }
 
         /** {@inheritDoc} */
         @Override
         public boolean hasNext() {
             return itemCount > 0 || entryIterator.hasNext();
         }
 
         /** {@inheritDoc} */
         @Override
         public E next() {
             if (itemCount == 0) {
                 current = entryIterator.next();
                 itemCount = current.getCount();
             }
             canRemove = true;
             itemCount--;
             return current.getElement();
         }
 
         /** {@inheritDoc} */
         @Override
         public void remove() {
             if (!canRemove) {
                 throw new IllegalStateException();
             }
             final int count = current.getCount();
             if (count > 1) {
                 parent.remove(current.getElement());
             } else {
                 entryIterator.remove();
             }
             canRemove = false;
         }
     }
 
     /**
      * Inner class UniqueSet.
      *
      * @param <E> the element type.
      */
     protected static class UniqueSet<E> extends AbstractSet<E> {
 
         /** The parent multiset */
         protected final AbstractMultiSet<E> parent;
 
         /**
          * Constructs a new unique element view of the MultiSet.
          *
          * @param parent  the parent MultiSet
          */
         protected UniqueSet(final AbstractMultiSet<E> parent) {
             this.parent = parent;
         }
 
         @Override
         public void clear() {
             parent.clear();
         }
 
         @Override
         public boolean contains(final Object key) {
             return parent.contains(key);
         }
 
         @Override
         public boolean containsAll(final Collection<?> coll) {
             return parent.containsAll(coll);
         }
 
         @Override
         public Iterator<E> iterator() {
             return parent.createUniqueSetIterator();
         }
 
         @Override
         public boolean remove(final Object key) {
             return parent.remove(key, parent.getCount(key)) != 0;
         }
 
         @Override
         public int size() {
             return parent.uniqueElements();
         }
     }
 
     /** View of the elements */
     private transient Set<E> uniqueSet;
 
     /** View of the entries */
     private transient Set<Entry<E>> entrySet;
 
     /**
      * Constructor needed for subclass serialisation.
      */
     protected AbstractMultiSet() {
     }
 
     @Override
     public boolean add(final E object) {
         add(object, 1);
         return true;
     }
 
     @Override
     public int add(final E object, final int occurrences) {
         throw new UnsupportedOperationException();
     }
 
     /**
      * Clears the multiset removing all elements from the entrySet.
      */
     @Override
     public void clear() {
         final Iterator<Entry<E>> it = entrySet().iterator();
         while (it.hasNext()) {
             it.next();
             it.remove();
         }
     }
 
     /**
      * Determines if the multiset contains the given element.
      *
      * @param object the object to search for
      * @return true if the multiset contains the given element
      */
     @Override
     public boolean contains(final Object object) {
         return getCount(object) > 0;
     }
 
     /**
      * Create a new view for the set of entries in this multiset.
      *
      * @return a view of the set of entries
      */
     protected Set<Entry<E>> createEntrySet() {
         return new EntrySet<>(this);
     }
 
     /**
      * Creates an entry set iterator.
      * Subclasses can override this to return iterators with different properties.
      *
      * @return the entrySet iterator
      */
     protected abstract Iterator<Entry<E>> createEntrySetIterator();
 
     /**
      * Create a new view for the set of unique elements in this multiset.
      *
      * @return a view of the set of unique elements
      */
     protected Set<E> createUniqueSet() {
         return new UniqueSet<>(this);
     }
 
     /**
      * Creates a unique set iterator.
      * Subclasses can override this to return iterators with different properties.
      *
      * @return the uniqueSet iterator
      */
     protected Iterator<E> createUniqueSetIterator() {
         final Transformer<Entry<E>, E> transformer = Entry::getElement;
         return IteratorUtils.transformedIterator(entrySet().iterator(), transformer);
     }
 
     /**
      * Read the multiset in using a custom routine.
      * @param in the input stream
      * @throws IOException any of the usual I/O related exceptions
      * @throws ClassNotFoundException if the stream contains an object which class cannot be loaded
      * @throws ClassCastException if the stream does not contain the correct objects
      */
     protected void doReadObject(final ObjectInputStream in)
             throws IOException, ClassNotFoundException {
         final int entrySize = in.readInt();
         for (int i = 0; i < entrySize; i++) {
             @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
             final E obj = (E) in.readObject();
             final int count = in.readInt();
             setCount(obj, count);
         }
     }
 
     /**
      * Write the multiset out using a custom routine.
      * @param out the output stream
      * @throws IOException any of the usual I/O related exceptions
      */
     protected void doWriteObject(final ObjectOutputStream out) throws IOException {
         out.writeInt(entrySet().size());
         for (final Entry<E> entry : entrySet()) {
             out.writeObject(entry.getElement());
             out.writeInt(entry.getCount());
         }
     }
 
     /**
      * Returns an unmodifiable view of the entries of this multiset.
      *
      * @return the set of entries in this multiset
      */
     @Override
     public Set<Entry<E>> entrySet() {
         if (entrySet == null) {
             entrySet = createEntrySet();
         }
         return entrySet;
     }
 
     @Override
     public boolean equals(final Object object) {
         if (object == this) {
             return true;
         }
         if (!(object instanceof MultiSet)) {
             return false;
         }
         final MultiSet<?> other = (MultiSet<?>) object;
         if (other.size() != size()) {
             return false;
         }
         for (final Entry<E> entry : entrySet()) {
             if (other.getCount(entry.getElement()) != getCount(entry.getElement())) {
                 return false;
             }
         }
         return true;
     }
 
     /**
      * Returns the number of occurrence of the given element in this multiset by
      * iterating over its entrySet.
      *
      * @param object the object to search for
      * @return the number of occurrences of the object, zero if not found
      */
     @Override
     public int getCount(final Object object) {
         for (final Entry<E> entry : entrySet()) {
             final E element = entry.getElement();
             if (Objects.equals(element, object)) {
                 return entry.getCount();
             }
         }
         return 0;
     }
 
     @Override
     public int hashCode() {
         return entrySet().hashCode();
     }
 
     /**
      * Gets an iterator over the multiset elements. Elements present in the
      * MultiSet more than once will be returned repeatedly.
      *
      * @return the iterator
      */
     @Override
     public Iterator<E> iterator() {
         return new MultiSetIterator<>(this);
     }
 
     @Override
     public boolean remove(final Object object) {
         return remove(object, 1) != 0;
     }
 
     @Override
     public int remove(final Object object, final int occurrences) {
         throw new UnsupportedOperationException();
     }
 
     @Override
     public boolean removeAll(final Collection<?> coll) {
         boolean result = false;
         for (final Object obj : coll) {
             final boolean changed = remove(obj, getCount(obj)) != 0;
             result = result || changed;
         }
         return result;
     }
 
     @Override
     public int setCount(final E object, final int count) {
         if (count < 0) {
             throw new IllegalArgumentException("Count must not be negative.");
         }
 
         final int oldCount = getCount(object);
         if (oldCount < count) {
             add(object, count - oldCount);
         } else {
             remove(object, oldCount - count);
         }
         return oldCount;
     }
 
     /**
      * Returns the number of elements in this multiset.
      *
      * @return current size of the multiset
      */
     @Override
     public int size() {
         int totalSize = 0;
         for (final Entry<E> entry : entrySet()) {
             totalSize += entry.getCount();
         }
         return totalSize;
     }
 
     /**
      * Implement a toString() method suitable for debugging.
      *
      * @return a debugging toString
      */
     @Override
     public String toString() {
         return entrySet().toString();
     }
 
     /**
      * Returns the number of unique elements in this multiset.
      *
      * @return the number of unique elements
      */
     protected abstract int uniqueElements();
 
     /**
      * Returns a view of the unique elements of this multiset.
      *
      * @return the set of unique elements in this multiset
      */
     @Override
     public Set<E> uniqueSet() {
         if (uniqueSet == null) {
             uniqueSet = createUniqueSet();
         }
         return uniqueSet;
     }
 
 }