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;

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

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

        // no sense trying to catch an OutOfMemoryError
    }

    @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);
        }

        // fill in the array elements
        Node cur = first;
        for (int i = 0; i < numInBag; ++i) {
            a[i] = (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() {
        // check for error condition: nothing to remove
        if (first == null) {
            throw new NoSuchElementException();
        }

        // remove first item from the bag
        Node toDelete = first;
        E result = first.data;
        first = first.next;
        --numInBag;

        // null out for express garbage collection
        toDelete.next = null;
        toDelete.data = null;

        // send back the removed data
        return result;
    }

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

    private void deleteDataAt(Node toRemove) {
        // move data from first item to here
        toRemove.data = first.data;

        // remove first item
        remove();   // updates numInBag
        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 getFrequency(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) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

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

    // ---------- 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;
    }

    // ---------- private class --------------- //
    /**
     * A class adding a pointer to each data element, forming the links in the
     * chain holding a Bag's elements. 
     *
     * NOTES TO STUDENTS: 
     * - This class is not static, so it has access to the type parameter of 
     *   its enclosing class.
     * - I have made its instance variables private, but because it is part of
     *   its enclosing class, its enclosing class has access.
     */
    private class Node {

        private E data;
        private Node next;

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

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

}