package list;

/**
 * Doubly Linked List implementation
 * @author Winston Prakash
 */
public class DoublyLinkedList<E> implements List<E>{
    Entry<E> head;
    Entry<E> tail;
    
    int size = 0;
    
    public void append(E item) {
        Entry<E> newEntry = new Entry<E>(item, null, null);
        if (head == null){
            head =  newEntry;
        }else if (tail == null){
            tail = newEntry;
            head.setNext(tail);
            tail.setPrevious(head);
        }else{
            tail.setNext(newEntry);
            newEntry.setPrevious(tail);
            tail = newEntry;
        }
        size++;
    }
    
    public void insert(int index, E item) {
        checkRange(index);
        if (index == 0){
            Entry<E> newEntry = new Entry<E>(item, head, null);
            head.setPrevious(newEntry);
            head = newEntry;
        }else{
            Entry<E> entry = findEntry(index);
            Entry<E> newEntry = new Entry<E>(item, entry, entry.previous);
            entry.getPrevious().setNext(newEntry);
            entry.setPrevious(newEntry);
        }
        size++;
    }
    
    public boolean remove(E item) {
        if(size > 0){
            Entry<E> entry = head;
            for (int i = 0; i < size; i++){
                if (item.equals(entry.getElement())){
                    removeEntry(entry);
                    return true;
                }else{
                    entry = entry.getNext();
                }
            }
        }
        return false;
    }
    
    public void removeAt(int index) {
        removeEntry(findEntry(index));
    }
    
    private void removeEntry(Entry<E> entry){
        if(entry != head){
            entry.getPrevious().setNext(entry.getNext());
            entry.getNext().setPrevious(entry.getPrevious());
        }else{
            head = head.getNext();
            head.setPrevious(null);
        }
        entry.setNext(null);
        entry.setPrevious(null);
        entry.setElement(null);
        size--;
    }
    
    public boolean contains(E item) {
        return indexOf(item) != -1;
    }
    
    public int indexOf(E item) {
        if(size > 0){
            Entry entry = head;
            for (int i = 0; i < size; i++){
                if (item.equals(entry.getElement())){
                    return i;
                }else{
                    entry = entry.getNext();
                }
            }
        }
        return -1;
    }
    
    public E get(int index) {
        return findEntry(index).getElement();
    }
    
    public void set(int index, E item) {
        Entry<E> entry =  findEntry(index);
        entry.setElement(item);
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public void display() {
        Entry entry = head;
        for (int i = 0; i < size; i++){
            System.out.print(entry.getElement() + "(");
            System.out.print(i + ") ");
            entry = entry.getNext();
        }
    }
    
    private Entry<E> findEntry(int index){
        checkRange(index);
        Entry<E> entry;
        if(index < (size >> 1) ){
            entry = head;
            for (int i = 0; i < index; i++){
                entry = entry.getNext();
            }
        }else{
            entry = tail;
            for (int i = size - 1; i > index; i--){
                entry = entry.getPrevious();
            }
        }
        return entry;
    }
    
    private void checkRange(int index){
        if ((index < 0) || (index >= size)){
            throw new IndexOutOfBoundsException("Index: " + index + "Size: " + size);
        }
    }
    
    public List.Iterator<E> iterator() {
        return new ListIterator<E>(head);
    }
    
    private static class ListIterator<E> implements  List.Iterator<E>{
        private Entry<E> entry;
        
        ListIterator(Entry<E> head){
            entry = head;
        }
        public boolean hasNext() {
            return entry.getNext() != null;
        }
        
        public E next() {
            // TODO check for end of list
            E element = entry.getElement();
            entry = entry.getNext();
            return element;
        }
        
        public void remove() {
            // TODO check for end of list
            // Check for concurrent modification
            entry.getPrevious().setNext(entry.getNext());
            entry.getNext().setPrevious(entry.getPrevious());
            entry =  entry.getNext();
        }
    }
    
    private static class Entry<E>{
        private E element;
        private Entry<E> next;
        private Entry<E> previous;
        Entry(E element, Entry<E> next, Entry<E> previous){
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
        
        void setNext(Entry<E> next){
            this.next = next;
        }
        Entry<E> getNext(){
            return next;
        }
        void setPrevious(Entry<E> previous){
            this.previous = previous;
        }
        Entry<E> getPrevious(){
            return previous;
        }
        
        void setElement(E element){
            this.element = element;
        }
        E getElement(){
            return element;
        }
    }
}