import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * An implementation of the Bag interface using a chain to hold its elements.
 * This implementation is missing the iterator method and the X-All methods.
 * (That is, they are present, but throw UnsupportedOperationExceptions.)
 * 
 * @author Mark Young (A00000000)
 * @param <E> the base class of this Bag
 */
public class LinkedBag<E> implements Bag<E> {

    // ---------- instance variables ---------- //
    private Node first;
    private int numInBag;
    private int numChanges;

    // ---------- constructor ----------------- //
    /**
     * Create an empty Bag using a chain representation.
     */
    public LinkedBag() {
        numInBag = 0;
        first = null;
        numChanges = 0;
    }

    // ---------- core methods ---------------- //
    @Override
    public boolean add(E e) {
        first = new Node(e, first);
        ++numInBag;
        ++numChanges;
        return true;
    }

    @Override
    public String toString() {
        return Arrays.toString(toArray());
    }

    @Override
    public Object[] toArray() {
        return toArray(new Object[numInBag]);
    }

    @SuppressWarnings("unchecked")
    @Override
    public <T> T[] toArray(T[] a) {
        // check if given array is big enuf
        if (a.length < numInBag) {
            // replace with a bigger array of the same runtime type
            a = Arrays.copyOf(a, numInBag);
        }

        // copy Bag elements
        int index = 0;
        Node cur = first;
        while (cur != null) {
            a[index++] = (T) cur.data;
            cur = cur.next;
        }

        // add a null at the end (if space available)
        if (a.length > numInBag) {
            a[numInBag] = null;
        }

        // return the revised array
        return a;
    }

    // ---------- removal methods ------------- //
    @Override
    public E remove() {
        if (first == null) {
            throw new NoSuchElementException();
        }
        return removeNode(first);
    }

    @Override
    public boolean remove(Object o) {
        Node posn = findNode(o);
        if (posn == null) {
            return false;
        } else {
            removeNode(posn);
            return true;
        }
    }

    // ---------- other public methods -------- //
    @Override
    public int size() {
        return numInBag;
    }

    @Override
    public boolean isEmpty() {
        return numInBag == 0;
    }

    @Override
    public boolean contains(Object o) {
        return findNode(o) != null;
    }

    @Override
    public void clear() {
        numInBag = 0;
        while (first != null) {
            first.data = null;
            first = first.next;
        }
    }

    @Override
    public int count(E anItem) {
        int count = 0;
        Node cur = first;
        while (cur != null) {
            if (Objects.equals(anItem, cur.data)) {
                ++count;
            }
            cur = cur.next;
        }
        return count;
    }

    // ---------- unimplemented methods ------- //
    @Override
    public Iterator<E> iterator() {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean changed = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                it.remove();
            }
        }
        return changed;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean changed = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
            }
        }
        return changed;
    }

    // ---------- private methods ------------- //
    /**
     * Find the Node with {@code anItem} as its data. Return null if
     * {@code anItem} is not {@code Objects.equals} to any element of this Bag.
     *
     * @param anItem the item to find
     * @return the Node containing it, or null if it's not in the chain
     */
    private Node findNode(Object anItem) {
        Node cur = first;
        while (cur != null) {
            if (Objects.equals(cur.data, anItem)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * Remove the data in the given Node from this Bag. The caller is 
     * responsible for ensuring that {@code cur} is not {@code null}.
     * <p>
     * The data is removed by copying the data from the first Node in the chain
     * into the current Node and removing the first Node from the chain. The
     * change in element order doesn't matter for a Bag.
     *
     * @param cur the Node holding the data to be removed (not null)
     * @param the value removed
     */
    private E removeNode(Node cur) {
        E result = cur.data;
        cur.data = first.data;
        first.data = null;
        first = first.next;
        --numInBag;
        ++numChanges;
        return result;
    }

    // ---------- private class --------------- //
    /**
     * A class adding a pointer to each data element, forming the links in the
     * chain holding a Bag's elements. 
     */
    private class Node {

        E data;
        Node next;

        public Node(E e) {
            this(e, null);
        }

        private Node(E e, Node first) {
            data = e;
            next = first;
        }
    }

}
