package list;

/**
 * Singly Linked List implementation
 * @author Winston Prakash
 */
public class SinglyLinkedList<E> implements List<E>{
    private Entry<E> head;
    private Entry<E> tail;
    
    int size = 0;
    
    public void append(E item) {
        Entry<E> newEntry = new Entry<E>(item, null);
        if (head == null){
            head =  newEntry;
        }else if (tail == null){
            tail = newEntry;
            head.setNext(tail);
        }else{
            tail.setNext(newEntry);
            tail = newEntry;
        }
        size++;
    }
    
    public void insert(int index, E item) {
        checkRange(index);
        if (index == 0){
            Entry<E> newEntry = new Entry<E>(item, head);
            head = newEntry;
        }else{
            Entry<E> entry = findEntry(index - 1);
            Entry<E> newEntry = new Entry<E>(item, entry.next);
            entry.setNext(newEntry);
        }
        size++;
    }
    
    public boolean remove(E item) {
        if(size > 0){
            Entry<E> entry = head;
            Entry<E> prev = null;
            for (int i = 0; i < size; i++){
                if (item.equals(entry.getElement())){
                    if (entry == head){
                        head = entry.getNext();
                    }else{
                        prev.setNext(entry.getNext());
                    }
                    entry.setNext(null);
                    entry.setElement(null);
                    size--;
                    return true;
                }else{
                    prev = entry;
                    entry = entry.getNext();
                }
            }
        }
        return false;
    }
    
    public void removeAt(int index) {
        checkRange(index);
        Entry<E> entry = head;
        if(index == 0){
            head = entry.getNext();
        }else{
            Entry<E> prevEntry = findEntry(index - 1);
            entry = prevEntry.getNext();
            prevEntry.setNext(entry.getNext());
        }
        entry.setNext(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 = head;
        for (int i = 0; i < index; i++){
            entry = entry.getNext();
        }
        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 class ListIterator<E> implements  List.Iterator<E>{
        private Entry<E> entry;
        private Entry<E> prev;
        
        ListIterator(Entry<E> head){
            entry = head;
            prev = head;
        }
        public boolean hasNext() {
            return entry.getNext() != null;
        }
        
        public E next() {
            // TODO check for end of list
            E element = entry.getElement();
            prev = entry;
            entry = entry.getNext();
            return element;
        }
        
        public void remove() {
            // TODO check for end of list
            prev.setNext(entry.getNext());
            entry =  entry.getNext();
        }
    }
    
    private static class Entry<E>{
        private E element;
        private Entry<E> next;
        Entry(E element, Entry<E> next){
            this.element = element;
            this.next = next;
        }
        
        void setNext(Entry<E> next){
            this.next = next;
        }
        Entry<E> getNext(){
            return next;
        }
        void setElement(E element){
            this.element = element;
        }
        E getElement(){
            return element;
        }
    }
}