package org.uwaterloo.cs.deltaconway;

import java.util.Collection;
import java.util.Iterator;

public class DeltaList<E> implements Collection<E> {

    Node sentinel;
    Node tail;
    int size;

    private class Node {
        E e;
        Node next;
    }

    public class DeltaIterator implements Iterator<E> {
        Node current, last, secondLast;
        boolean canRemove;

        public DeltaIterator(Node sentinel) {
            last = sentinel;
            current = sentinel.next;
            canRemove = false;
        }

        @Override
        public boolean hasNext() {
            return current.next != null;
        }

        @Override
        public E next() {
            canRemove = true;
            E e = current.e;
            secondLast = last;
            last = current;
            current = current.next;
            return e;
        }

        @Override
        public void remove() {
            if (!canRemove) {
                throw new IllegalStateException();
            }
            secondLast.next = current;
            last = secondLast;
            canRemove = false;
        }

        private DeltaIterator createIteratorPlusOne() {
            return new DeltaIterator(current);
        }
    }

    public DeltaList() {
        sentinel = new Node();
        tail = sentinel;
        size = 0;
    }

    @Override
    public boolean add(E e) {
        Node node = new Node();
        node.e = e;
        tail.next = node;
        tail = node;
        size++;
        return true;
    }

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

    @Override
    public void clear() {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean contains(Object o) {
        E e;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            e = it.next();
            if (o == null ? e == null : o.equals(e)) {
                return true;
            }
        }
        return false;
    }

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

    @Override
    public boolean isEmpty() {
        return sentinel.next == null;
    }

    @Override
    public Iterator<E> iterator() {
        return deltaIterator();
    }

    /**
     * Creates a delta iterator.
     *
     * @return A delta iterator.
     */
    public DeltaIterator deltaIterator() {
        return new DeltaIterator(sentinel);
    }

    /**
     * Creates a delta iterator from an existing delta iterator by advancing the
     * existing iterator. The existing iterator is not actually modified and can
     * be used to traverse the list. Once the existing iterator is used again,
     * the new iterator cannot be used.
     *
     * @param it
     *            The existing iterator.
     * @return A new iterator.
     */
    public DeltaIterator deltaIteratorPlusOne(DeltaIterator it) {
        return it.createIteratorPlusOne();
    }

    @Override
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object[] toArray() {
        int i = 0;
        Object[] array = new Object[size];
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            array[i++] = it.next();
        }
        return array;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        // TODO
        throw new UnsupportedOperationException();
    }

}