/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package esinf_1160676_1161154;

import com.sun.javafx.geom.Curve;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.ConcurrentModificationException;
import java.util.Objects;

/**
 *
 * @author DEI-ISEP
 * @param <E> Generic list element type
 */
public class DoublyLinkedList<E> implements Iterable<E>, Cloneable {

// instance variables of the DoublyLinkedList
    private final Node<E> header;     // header sentinel
    private final Node<E> trailer;    // trailer sentinel
    private int size = 0;       // number of elements in the list
    private int modCount = 0;   // number of modifications to the list (adds or removes)

    /**
     * Creates both elements which act as sentinels
     */
    public DoublyLinkedList() {

        header = new Node<>(null, null, null);      // create header
        trailer = new Node<>(null, header, null);   // trailer is preceded by header
        header.setNext(trailer);                    // header is followed by trailer
    }

    /**
     * Returns the number of elements in the linked list
     *
     * @return the number of elements in the linked list
     */
    public int size() {
        return size;
    }

    /**
     * Checks if the list is empty
     *
     * @return true if the list is empty, and false otherwise
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * Returns (but does not remove) the first element in the list
     *
     * @return the first element of the list
     */
    public E first() {
        return header.getNext().getElement();
    }

    /**
     * Returns (but does not remove) the last element in the list
     *
     * @return the last element of the list
     */
    public E last() {
        return trailer.getPrev().getElement();
    }

    @Override
    public String toString() {
       ListIterator iterator=this.listIterator();
       String returnable="";
        while (iterator.hasNext()) {
            returnable+="\n"+iterator.next().toString();
        }
        return returnable;
    }


// public update methods
    /**
     * Adds an element e to the front of the list
     *
     * @param e element to be added to the front of the list
     */
    public void addFirst(E e) {
        // place just after the header
        addBetween(e, header, header.getNext());
    }

    /**
     * Adds an element e to the end of the list
     *
     * @param e element to be added to the end of the list
     */
    public void addLast(E e) {
        // place just before the trailer
        addBetween(e, trailer.getPrev(), trailer);
    }

    /**
     * Removes and returns the first element of the list
     *
     * @return the first element of the list
     */
    public E removeFirst() {
        return remove(header.getNext());
    }

    /**
     * Removes and returns the last element of the list
     *
     * @return the last element of the list
     */
    public E removeLast() {
        return remove(trailer.getPrev());
    }

// private update methods
    /**
     * Adds an element e to the linked list between the two given nodes.
     */
    private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
        Node node = new Node<>(e, predecessor, successor);
        node.setElement(e);
        node.setPrev(predecessor);
        predecessor.setNext(node);
        node.setNext(successor);
        successor.setPrev(node);
        size++;
        modCount++;
    }

    /**
     * Removes a given node from the list and returns its content.
     */
    private E remove(Node<E> node) {
        if (size != 0) {
            Node predecessor = node.getPrev();
            Node successor = node.getNext();
            predecessor.setNext(successor);
            successor.setPrev(predecessor);
            node.setNext(null);
            node.setPrev(null);
            size--;
            modCount++;
            return node.getElement();
        }
        return null;
    }
// Overriden methods

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof DoublyLinkedList)) {
            return false;
        }

        DoublyLinkedList<E> other = (DoublyLinkedList<E>) obj;

        if (this.size() != other.size()) {
            return false;
        }

        Node<E> thisNode = header;
        Node<E> otherNode = other.header;

        while (thisNode.getNext() != trailer) {
            thisNode = thisNode.getNext();
            otherNode = otherNode.getNext();
            if (!(thisNode.getElement().equals(otherNode.getElement()))) {
                return false;
            }
        }
        return true;
    }

    @Override
    public Object clone() throws CloneNotSupportedException {

        DoublyLinkedList<E> other = new DoublyLinkedList<>();
        if (size > 0) {
            Node<E> newNode = header.getNext();
            for (int i = 0; i < size; i++) {
                other.addLast(newNode.getElement());
                newNode = newNode.getNext();
            }
        }
        return other;
    }

    void removeFirst(int i) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

//---------------- nested DoublyLinkedListIterator class ----------------
    private class DoublyLinkedListIterator implements ListIterator<E> {

        private DoublyLinkedList.Node<E> nextNode, prevNode, lastReturnedNode; // node that will be returned using next and prev respectively
        private int nextIndex;  // Index of the next element
        private int expectedModCount;  // Expected number of modifications = modCount;

        public DoublyLinkedListIterator() {
            this.prevNode = header;
            this.nextNode = header.getNext();
            lastReturnedNode = null;
            nextIndex = 0;
            expectedModCount = modCount;
        }

        final void checkForComodification() {  // invalidate iterator on list modification outside the iterator
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public boolean hasNext() {
            return nextNode.getElement() != null;
        }

        @Override
        public E next() throws NoSuchElementException {
            checkForComodification();
            if (!hasNext()) {
                throw new NoSuchElementException("End of list reached.");
            }
            lastReturnedNode = nextNode;
            nextNode = lastReturnedNode.getNext();
            prevNode = lastReturnedNode;
            nextIndex++;
            return lastReturnedNode.getElement();
        }

        @Override
        public boolean hasPrevious() {
            return prevNode.getElement() != null;
        }

        @Override
        public E previous() throws NoSuchElementException {
            checkForComodification();
            if (!hasPrevious()) {
                throw new NoSuchElementException("Beggining of list reached.");
            }
            lastReturnedNode = prevNode;
            nextNode = lastReturnedNode;
            prevNode = lastReturnedNode.getPrev();
            nextIndex--;
            return lastReturnedNode.getElement();
        }

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

        @Override
        public int previousIndex() {
            return nextIndex - 1;
        }

        @Override
        public void remove() throws NoSuchElementException {
            checkForComodification();
            if (hasNext() || hasPrevious()) {
                if (lastReturnedNode == null) {
                    throw new NoSuchElementException();
                }
                if (lastReturnedNode == nextNode) {
                    nextIndex--;
                }
                DoublyLinkedList.this.remove(lastReturnedNode);
                lastReturnedNode = lastReturnedNode.getPrev();
                expectedModCount++;
            }
        }

        @Override
        public void set(E e) throws NoSuchElementException {
            if (lastReturnedNode == null) {
                throw new NoSuchElementException();
            }
            checkForComodification();
            lastReturnedNode.setElement(e);
        }

        @Override
        public void add(E e) {
            checkForComodification();
            DoublyLinkedList.this.addBetween(e, prevNode, nextNode);
            prevNode = prevNode.getNext();
            lastReturnedNode = prevNode;
            nextIndex++;
            expectedModCount++;
        }

    }    //----------- end of inner DoublyLinkedListIterator class ----------

//---------------- Iterable implementation ----------------
    @Override
    public Iterator<E> iterator() {
        return new DoublyLinkedListIterator();
    }

    public ListIterator<E> listIterator() {
        return new DoublyLinkedListIterator();
    }

//---------------- nested Node class ----------------
    private static class Node<E> {

        private E element;      // reference to the element stored at this node
        private Node<E> prev;   // reference to the previous node in the list
        private Node<E> next;   // reference to the subsequent node in the list

        public Node(E element, Node<E> prev, Node<E> next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }

        public E getElement() {
            return element;
        }

        public Node<E> getPrev() {
            return prev;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setElement(E element) { // Not on the original interface. Added due to list iterator implementation
            this.element = element;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    } //----------- end of nested Node class ----------

}