package class3_3_LinkedList_051;

import java.util.*;

public class LinkedList<E> implements List<E> {


//    /*package*/ Object[] testGetArray() {
//        return (head;
//    }

    private class Node {
        private Node next;
        private E value;

        private Node(Node next, E value) {
            this.next = next;
            this.value = value;
        }
    }

    private Node head = null;

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in this list
     */
    @Override
    public int size() {

        int count = 0;
        Node current = head;

        while (current != null) {
            count++;
            current = current.next;
        }

        return count;
    }

    /**
     * Appends the specified element to the end of this list.
     * <p>
     * <p>This method is equivalent to {@link java.util.LinkedList#addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link java.util.Collection#add})
     */
    @Override
    public boolean add(E e) {
        Node current = head;

        if(current != null) {
            int sz = size();
            for(int i = 0; i < sz-1; i++) {
                current = current.next;
            }
            current.next = new Node(null, e);
        } else {
            head = new Node(null, e);
        }

        return true;
    }

    /**
     * Print out the value of each element in the LinkedList.
     * Simple debugging method
     */
    public void debug() {
        Node current = head;
        while(current != null) {
            System.out.println("Current: "+current.value);
            current = current.next;
        }
    }

    /**
     * Inserts the specified element at the specified position in this list.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index   index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException     if the index is out of range
     *                                       (<tt>index &lt; 0 || index &gt; size()</tt>)
     */
    @Override
    public void add(int index, E element) {
        throw new UnsupportedOperationException("This method isn't written yet.");
    }
    public boolean addFirst(int i, E e) {
        //Adds an element to index 0 of linked list
        i = 0;
        Node prevHead = head;
//        Node prevTail = tail; // TODO: FIX COMPILE ERROR
//        Node current = new Node(prevHead, prevTail, e);
//        head = current;
//        prevHead.prev = current; // TODO
//        prevTail.next = current;
//        size++;
        return true;
    }

    /**
     * Removes all of the elements from this list.
     * The list will be empty after this call returns.
     */
    @Override
    public void clear() {
        head = null;
    }

    /**
     * Returns {@code true} if this list contains the specified element.
     * More formally, returns {@code true} if and only if this list contains
     * at least one element {@code e} such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested
     * @return {@code true} if this list contains the specified element
     */
    @Override
    public boolean contains(Object o) {
        throw new UnsupportedOperationException("This method isn't written yet.");
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of the element to return
     * @return the element at the specified position in this list
     * @throws IndexOutOfBoundsException if the index is out of range
     *                                   (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    @Override
    public E get(int index) {
        Node current;
        if (index <= 0) {
            return null;
        }
        current = head.next;
        for (int i = 1; i < index; i++) {
            if (current == null) {
                return null;
            }
        }
        return current.value;
    }

    // ALTERNATE IMPLEMENTATION:
//    public E get(int index) {
//        Node head = null;
//        Node tail = null;
////        Reference next; // TODO
//        if (index < 0 || index >=size()) {
//            throw new IndexOutOfBoundsException();
//        }
//
//        if ( index < size() - 1){
//        // TODO: FIX COMPILE ERRORS
////            Node<E> current = head;
////            for (int j = 0; j <i ; j++) {
////                current = current.next();
////            }
////            return current.getValue();
//        }
////        return tail.getValue(); // TODO
//        return null;
//    }

    /**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for
     * @return the index of the first occurrence of the specified element in
     * this list, or -1 if this list does not contain the element
     */
    @Override
    public int indexOf(Object o){
        int index = 0;
        int count = 0;
        Node current = head;
        // TODO: FIX COMPILE ERROR:
//        while(current.hasNext()){
//            if(current == o){
//                count = index;
//            }else{
//                index++;
//            }
//        }

        return count;
    }

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     *
     * @return <tt>true</tt> if this list contains no elements
     */
    @Override
    public boolean isEmpty() {
        throw new UnsupportedOperationException("This method isn't written yet.");
    }

    /**
     * Removes the element at the specified position in this list.  Shifts any
     * subsequent elements to the left (subtracts one from their indices).
     * Returns the element that was removed from the list.
     *
     * @param index the index of the element to be removed
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException     if the index is out of range
     *                                       (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    @Override
    public E remove(int index) {
        throw new UnsupportedOperationException("This method isn't written yet.");
    }

    /**
     * Removes the first occurrence of the specified element from this list,
     * if it is present.  If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index
     * {@code i} such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
     * (if such an element exists).  Returns {@code true} if this list
     * contained the specified element (or equivalently, if this list
     * changed as a result of the call).
     *
     * @param o element to be removed from this list, if present
     * @return {@code true} if this list contained the specified element
     */
    @Override
    public boolean remove(Object o) {
        boolean removed = false;
        if(head!=null) {
            Node next;
            Node prev;
            Node current;
            if (head.value.equals(o)) {
                if (head.next != null) {
                    head = head.next;
                    removed = true;
                } else {
                    head = null;
                    removed = true;
                }
            } else if (head != null && head.next != null) {
                prev = head;
                current = head.next;
                while (!removed && current != null) {

                    if (current.value.equals(o)) {
                        if (current.next == null) {
                            prev.next = null;
                            removed = true;
                        } else {
                            next = current.next;
                            prev.next = next;
                            removed = true;
                        }
                    } else {
                        prev = current;
                        current = current.next;
                    }
                }
            } else {
                removed = false;
            }
        }
        return removed;
    }

    /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @param index   index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException     if the index is out of range
     *                                       (<tt>index &lt; 0 || index &gt;= size()</tt>)
     */
    @Override
    public E set(int index, E element) {
        throw new UnsupportedOperationException("This method isn't written yet.");
    }

    /**
     * Returns an array containing all of the elements in this list
     * in proper sequence (from first to last element).
     * <p>
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this list.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     * <p>
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this list
     * in proper sequence
     */
    @Override
    public Object[] toArray() {
        // With Iterator instead of ListIterator
        int size = 0;
        Iterator<E> iter = iterator();
        while(iter.hasNext()) {
            iter.next();
            size++;
        }

        Object[] result = new Object[size];

        iter = iterator();
        int i = 0;
        while (iter.hasNext())
            result[i++] = iter.next();

        return result;
        // Original:
//        int size = 0;
//        ListIterator<E> li = listIterator(0);
//        while(li.hasNext()) {
//            li.next();
//            size++;
//        }
//
//        Object[] result = new Object[size];
//
//        li = listIterator(0);
//        int i = 0;
//        while (li.hasNext())
//            result[i++] = li.next();
//
//        return result;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node next = head;

            /**
             * Returns {@code true} if the iteration has more elements.
             * (In other words, returns {@code true} if {@link #next} would
             * return an element rather than throwing an exception.)
             *
             * @return {@code true} if the iteration has more elements
             */
            @Override
            public boolean hasNext() {
                return next != null;
            }

            /**
             * Returns the next element in the iteration.
             *
             * @return the next element in the iteration
             * @throws NoSuchElementException if the iteration has no more elements
             */
            @Override
            public E next() throws NoSuchElementException {
                // TODO: We need to also advance to the next
                // to avoid an infinite loop here.
                // TODO: Throw NoSuchElementException if no "next" to be found.
                return this.next.value;
            }
        };
    }

    // ----- not implemented ------

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return null;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        return null;
    }
}