import java.util.Collection;

/**
 * A type intermediate between {@link java.util.List List}s and 
 * {@link java.util.Set Set}s: it allows duplicates, but is not sequential.
 * This type is sometimes called <em>MultiSet</em>.
 * <p>
 * This version of the interface extends the Collection interface, and so
 * contains more methods than the one from last week. Various of the inherited
 * methods have been given default implementations.
 * <p>
 * <b>NOTE:</b>
 * The default implementations are provided as an example of using default
 * method definitions in an interface. <b>In this case</b> these default
 * implementations are not ideal, and should not be included in the interface.
 * The version of <b>Bag</b> used later in teh course will not include them.
 * We will discuss the reasons behind that in class.
 *
 * @param <T> the base type of this Bag
 * @author Mark Young (A00000000)
 */
public interface Bag<T> extends Collection<T> {

    /**
     * Remove an item from this Bag. The item to remove is at the discretion of
     * the implementation.
     *
     * @return an arbitrary item removed from this Bag
     */
    public T remove();

    /**
     * Count how many times the given item appears in this Bag. That is, count
     * each {@code e} such that {@code Objects.equals(anItem, e)}.
     *
     * @param anItem the item to count
     * @return how many times that item appears in this Bag
     */
    public int count(T anItem);
    
    /*
     * Some default implementations for methods. I don't know why Collection
     * doesn't give these itself!
     */
    
    /**
     * Add all of the elements from collection {@code c} to this Bag.
     *
     * @param c the collection whose elements are to be added to this Bag
     * @return true if the Bag has elements added, false if not (this is the 
     * behaviour required by the {@link java.util.Collection Collection}
     * interface)
     */
    @Override
    public default boolean addAll(Collection<? extends T> c) {
        int oldSize = size();
        for (var item : c) {
            add(item);
        }
        return oldSize != size();
    }
    
    /**
     * Remove all elements from this Bag.
     */
    @Override
    public default void clear() {
        while (!isEmpty()) {
            remove();
        }
    }
    
    /**
     * Check whether this Bag contains each of the elements of {@code c}.
     *
     * @param c the collection of items to check for
     * @return true if this Bag contains all those items; false otherwise
     */
    @Override
    public default boolean containsAll(Collection<?> c) {
        for (var obj : c) {
            if (!contains(obj)) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * Check whether this Bag is empty.
     *
     * @return true if this Bag is empty; false otherwise
     */
    @Override
    public default boolean isEmpty() {
        return size() == 0;
    }
    
    /**
     * Remove every element of {@code c} from this Bag. Only one copy of each
     * item is removed, unless {@code c} itself contains duplicates, in which
     * case the same number of that item is removed from this Bag.
     * <p>
     * The collection {@code c} may contain items that do not appear in this
     * Bag, and for those items nothing is removed from this Bag, and no
     * exception is thrown.
     *
     * @param c the collection whose elements are to be removed from this Bag
     * @return true if this Bag has had elements removed; false otherwise
     */
    @Override
    public default boolean removeAll(Collection<?> c) {
        int oldSize = size();
        for (var obj : c) {
            remove(obj);
        }
        return oldSize != size();
    }
    
    /**
     * Keep only the items in collection {@code c} in this Bag, removing all 
     * others. All duplicates in this Bag are either retained (if in {@code c}
     * or removed (if not in {@code c}) uniformly.
     * <p>
     * Items in {@code c} that do not appear in this Bag have no effect.
     *
     * @param c the collection whose elements are to be retained in this Bag
     * @return true if items were removed from this Bag; false otherwise
     */
    @Override
    public default boolean retainAll(Collection<?> c) {
        int oldSize = size();
        for (Object obj : toArray()) {
            if (!c.contains(obj)) {
                remove(obj);
            }
        }
        return oldSize != size();
    }

}