/*
    * 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.bag;
  
  import java.io.IOException;
  import java.io.ObjectInputStream;
  import java.io.ObjectOutputStream;
  import java.lang.reflect.Array;
  import java.util.Collection;
  import java.util.ConcurrentModificationException;
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.Objects;
  import java.util.Set;
  
  import org.apache.commons.collections4.Bag;
  import org.apache.commons.collections4.CollectionUtils;
  import org.apache.commons.collections4.set.UnmodifiableSet;
  
  /**
   * Abstract implementation of the {@link Bag} interface to simplify the creation
   * of subclass implementations.
   * <p>
   * Subclasses specify a Map implementation to use as the internal storage. The
   * map will be used to map bag elements to a number; the number represents the
   * number of occurrences of that element in the bag.
   * </p>
   *
   * @param <E> the type of elements in this bag
   * @since 3.0 (previously DefaultMapBag v2.0)
   */
  public abstract class AbstractMapBag<E> implements Bag<E> {
  
      /**
       * Inner class iterator for the Bag.
       */
      static class BagIterator<E> implements Iterator<E> {
          private final AbstractMapBag<E> parent;
          private final Iterator<Map.Entry<E, MutableInteger>> entryIterator;
          private Map.Entry<E, MutableInteger> current;
          private int itemCount;
          private final int mods;
          private boolean canRemove;
  
          /**
           * Constructs a new instance.
           *
           * @param parent the parent bag
           */
          BagIterator(final AbstractMapBag<E> parent) {
              this.parent = parent;
              this.entryIterator = parent.map.entrySet().iterator();
              this.current = null;
              this.mods = parent.modCount;
              this.canRemove = false;
          }
  
          /** {@inheritDoc} */
          @Override
          public boolean hasNext() {
              return itemCount > 0 || entryIterator.hasNext();
          }
  
          /** {@inheritDoc} */
          @Override
          public E next() {
              if (parent.modCount != mods) {
                  throw new ConcurrentModificationException();
              }
              if (itemCount == 0) {
                  current = entryIterator.next();
                  itemCount = current.getValue().value;
              }
              canRemove = true;
              itemCount--;
              return current.getKey();
          }
  
          /** {@inheritDoc} */
          @Override
          public void remove() {
              if (parent.modCount != mods) {
                  throw new ConcurrentModificationException();
              }
             if (!canRemove) {
                 throw new IllegalStateException();
             }
             final MutableInteger mut = current.getValue();
             if (mut.value > 1) {
                 mut.value--;
             } else {
                 entryIterator.remove();
             }
             parent.size--;
             canRemove = false;
         }
     }
 
     /**
      * Mutable integer class for storing the data.
      */
     protected static class MutableInteger {
 
         /** The value of this mutable. */
         protected int value;
 
         /**
          * Constructs a new instance.
          * @param value the initial value
          */
         MutableInteger(final int value) {
             this.value = value;
         }
 
         @Override
         public boolean equals(final Object obj) {
             if (!(obj instanceof MutableInteger)) {
                 return false;
             }
             return ((MutableInteger) obj).value == value;
         }
 
         @Override
         public int hashCode() {
             return value;
         }
     }
 
     /** The map to use to store the data */
     private transient Map<E, MutableInteger> map;
 
     /** The current total size of the bag */
     private int size;
 
     /** The modification count for fail fast iterators */
     private transient int modCount;
 
     /** Unique view of the elements */
     private transient Set<E> uniqueSet;
 
     /**
      * Constructor needed for subclass serialization.
      */
     protected AbstractMapBag() {
     }
 
     /**
      * Constructor that assigns the specified Map as the backing store. The map
      * must be empty and non-null.
      *
      * @param map the map to assign
      */
     protected AbstractMapBag(final Map<E, MutableInteger> map) {
         this.map = Objects.requireNonNull(map, "map");
     }
 
     /**
      * Constructs a new instance that assigns the specified Map as the backing store. The map
      * must be empty and non-null. The bag is filled from the iterable elements.
      *
      * @param map the map to assign.
      * @param iterable The bag is filled from these iterable elements.
      */
     protected AbstractMapBag(final Map<E, MutableInteger> map, final Iterable<? extends E> iterable) {
         this(map);
         iterable.forEach(this::add);
     }
 
     /**
      * Adds a new element to the bag, incrementing its count in the underlying map.
      *
      * @param object the object to add
      * @return {@code true} if the object was not already in the {@code uniqueSet}
      */
     @Override
     public boolean add(final E object) {
         return add(object, 1);
     }
 
     /**
      * Adds a new element to the bag, incrementing its count in the map.
      *
      * @param object the object to search for
      * @param nCopies the number of copies to add
      * @return {@code true} if the object was not already in the {@code uniqueSet}
      */
     @Override
     public boolean add(final E object, final int nCopies) {
         modCount++;
         if (nCopies > 0) {
             final MutableInteger mut = map.get(object);
             size += nCopies;
             if (mut == null) {
                 map.put(object, new MutableInteger(nCopies));
                 return true;
             }
             mut.value += nCopies;
         }
         return false;
     }
 
     /**
      * Invokes {@link #add(Object)} for each element in the given collection.
      *
      * @param coll the collection to add
      * @return {@code true} if this call changed the bag
      */
     @Override
     public boolean addAll(final Collection<? extends E> coll) {
         boolean changed = false;
         for (final E current : coll) {
             final boolean added = add(current);
             changed = changed || added;
         }
         return changed;
     }
 
     /**
      * Clears the bag by clearing the underlying map.
      */
     @Override
     public void clear() {
         modCount++;
         map.clear();
         size = 0;
     }
 
     /**
      * Determines if the bag contains the given element by checking if the
      * underlying map contains the element as a key.
      *
      * @param object the object to search for
      * @return true if the bag contains the given element
      */
     @Override
     public boolean contains(final Object object) {
         return map.containsKey(object);
     }
 
     /**
      * Returns {@code true} if the bag contains all elements in the given
      * collection, respecting cardinality.
      *
      * @param other the bag to check against
      * @return {@code true} if the Bag contains all the collection
      */
     boolean containsAll(final Bag<?> other) {
         for (final Object current : other.uniqueSet()) {
             if (getCount(current) < other.getCount(current)) {
                 return false;
             }
         }
         return true;
     }
 
     /**
      * Determines if the bag contains the given elements.
      *
      * @param coll the collection to check against
      * @return {@code true} if the Bag contains all the collection
      */
     @Override
     public boolean containsAll(final Collection<?> coll) {
         if (coll instanceof Bag) {
             return containsAll((Bag<?>) coll);
         }
         return containsAll(new HashBag<>(coll));
     }
 
     /**
      * Reads the map in using a custom routine.
      *
      * @param map the map to use
      * @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 Map<E, MutableInteger> map, final ObjectInputStream in)
             throws IOException, ClassNotFoundException {
         this.map = map;
         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();
             map.put(obj, new MutableInteger(count));
             size += count;
         }
     }
 
     /**
      * Writes the map 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(map.size());
         for (final Entry<E, MutableInteger> entry : map.entrySet()) {
             out.writeObject(entry.getKey());
             out.writeInt(entry.getValue().value);
         }
     }
 
     /**
      * Compares this Bag to another. This Bag equals another Bag if it contains
      * the same number of occurrences of the same elements.
      *
      * @param object the Bag to compare to
      * @return true if equal
      */
     @Override
     public boolean equals(final Object object) {
         if (object == this) {
             return true;
         }
         if (!(object instanceof Bag)) {
             return false;
         }
         final Bag<?> other = (Bag<?>) object;
         if (other.size() != size()) {
             return false;
         }
         for (final E element : map.keySet()) {
             if (other.getCount(element) != getCount(element)) {
                 return false;
             }
         }
         return true;
     }
 
     /**
      * Gets the number of occurrence of the given element in this bag by
      * looking up its count in the underlying map.
      *
      * @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) {
         final MutableInteger count = map.get(object);
         if (count != null) {
             return count.value;
         }
         return 0;
     }
 
     /**
      * Utility method for implementations to access the map that backs this bag.
      * Not intended for interactive use outside of subclasses.
      *
      * @return the map being used by the Bag
      */
     protected Map<E, MutableInteger> getMap() {
         return map;
     }
 
     /**
      * Gets a hash code for the Bag compatible with the definition of equals.
      * The hash code is defined as the sum total of a hash code for each
      * element. The per element hash code is defined as
      * {@code (e==null ? 0 : e.hashCode()) ^ noOccurrences)}. This hash code
      * is compatible with the Set interface.
      *
      * @return the hash code of the Bag
      */
     @Override
     public int hashCode() {
         int total = 0;
         for (final Entry<E, MutableInteger> entry : map.entrySet()) {
             final E element = entry.getKey();
             final MutableInteger count = entry.getValue();
             total += (element == null ? 0 : element.hashCode()) ^ count.value;
         }
         return total;
     }
 
     /**
      * Returns true if the underlying map is empty.
      *
      * @return true if bag is empty
      */
     @Override
     public boolean isEmpty() {
         return map.isEmpty();
     }
 
     /**
      * Gets an iterator over the bag elements. Elements present in the Bag more
      * than once will be returned repeatedly.
      *
      * @return the iterator
      */
     @Override
     public Iterator<E> iterator() {
         return new BagIterator<>(this);
     }
 
     /**
      * Removes all copies of the specified object from the bag.
      *
      * @param object the object to remove
      * @return true if the bag changed
      */
     @Override
     public boolean remove(final Object object) {
         final MutableInteger mut = map.get(object);
         if (mut == null) {
             return false;
         }
         modCount++;
         map.remove(object);
         size -= mut.value;
         return true;
     }
 
     /**
      * Removes a specified number of copies of an object from the bag.
      *
      * @param object the object to remove
      * @param nCopies the number of copies to remove
      * @return true if the bag changed
      */
     @Override
     public boolean remove(final Object object, final int nCopies) {
         final MutableInteger mut = map.get(object);
         if (mut == null) {
             return false;
         }
         if (nCopies <= 0) {
             return false;
         }
         modCount++;
         if (nCopies < mut.value) {
             mut.value -= nCopies;
             size -= nCopies;
         } else {
             map.remove(object);
             size -= mut.value;
         }
         return true;
     }
 
     /**
      * Removes objects from the bag according to their count in the specified
      * collection.
      *
      * @param coll the collection to use
      * @return true if the bag changed
      */
     @Override
     public boolean removeAll(final Collection<?> coll) {
         boolean result = false;
         if (coll != null) {
             for (final Object current : coll) {
                 final boolean changed = remove(current, 1);
                 result = result || changed;
             }
         }
         return result;
     }
 
     /**
      * Remove any members of the bag that are not in the given bag, respecting
      * cardinality.
      * @see #retainAll(Collection)
      * @param other the bag to retain
      * @return {@code true} if this call changed the collection
      */
     boolean retainAll(final Bag<?> other) {
         boolean result = false;
         final Bag<E> excess = new HashBag<>();
         for (final E current : uniqueSet()) {
             final int myCount = getCount(current);
             final int otherCount = other.getCount(current);
             if (1 <= otherCount && otherCount <= myCount) {
                 excess.add(current, myCount - otherCount);
             } else {
                 excess.add(current, myCount);
             }
         }
         if (!excess.isEmpty()) {
             result = removeAll(excess);
         }
         return result;
     }
 
     /**
      * Remove any members of the bag that are not in the given bag, respecting
      * cardinality.
      *
      * @param coll the collection to retain
      * @return true if this call changed the collection
      */
     @Override
     public boolean retainAll(final Collection<?> coll) {
         if (coll instanceof Bag) {
             return retainAll((Bag<?>) coll);
         }
         return retainAll(new HashBag<>(coll));
     }
 
     /**
      * Returns the number of elements in this bag.
      *
      * @return current size of the bag
      */
     @Override
     public int size() {
         return size;
     }
 
     /**
      * Returns an array of all of this bag's elements.
      *
      * @return an array of all of this bag's elements
      */
     @Override
     public Object[] toArray() {
         final Object[] result = new Object[size()];
         int i = 0;
         for (final E current : map.keySet()) {
             for (int index = getCount(current); index > 0; index--) {
                 result[i++] = current;
             }
         }
         return result;
     }
 
     /**
      * Returns an array of all of this bag's elements.
      * If the input array has more elements than are in the bag,
      * trailing elements will be set to null.
      *
      * @param <T> the type of the array elements
      * @param array the array to populate
      * @return an array of all of this bag's elements
      * @throws ArrayStoreException if the runtime type of the specified array is not
      *   a supertype of the runtime type of the elements in this list
      * @throws NullPointerException if the specified array is null
      */
     @Override
     public <T> T[] toArray(T[] array) {
         final int size = size();
         if (array.length < size) {
             @SuppressWarnings("unchecked") // safe as both are of type T
             final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
             array = unchecked;
         }
 
         int i = 0;
         for (final E current : map.keySet()) {
             for (int index = getCount(current); index > 0; index--) {
                 // unsafe, will throw ArrayStoreException if types are not compatible, see Javadoc
                 @SuppressWarnings("unchecked")
                 final T unchecked = (T) current;
                 array[i++] = unchecked;
             }
         }
         while (i < array.length) {
             array[i++] = null;
         }
         return array;
     }
 
     /**
      * Implement a toString() method suitable for debugging.
      *
      * @return a debugging toString
      */
     @Override
     public String toString() {
         if (isEmpty()) {
             return "[]";
         }
         final StringBuilder buf = new StringBuilder();
         buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
         final Iterator<E> it = uniqueSet().iterator();
         while (it.hasNext()) {
             final Object current = it.next();
             final int count = getCount(current);
             buf.append(count);
             buf.append(CollectionUtils.COLON);
             buf.append(current);
             if (it.hasNext()) {
                 buf.append(CollectionUtils.COMMA);
             }
         }
         buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
         return buf.toString();
     }
 
     /**
      * Returns an unmodifiable view of the underlying map's key set.
      *
      * @return the set of unique elements in this bag
      */
     @Override
     public Set<E> uniqueSet() {
         if (uniqueSet == null) {
             uniqueSet = UnmodifiableSet.<E>unmodifiableSet(map.keySet());
         }
         return uniqueSet;
     }
 
 }