package ListPackage;

import java.io.Serializable;

public class DoubleLinkedList implements LinkedList,Serializable {

    private class ListIterator implements Iterator,Serializable {
        Node current;
        boolean notAtBeginning=false;

        public ListIterator() {
            current = getHead();
        }

        @Override
        public Object begin() {
            notAtBeginning = false;
            current = getHead();
            return current.elem;
        }

        @Override
        public Object currentElem() {
            return current.elem;
        }

        @Override
        public Object end() {
            Node p = getHead();
            boolean first=true;
            while( ( (p != dlist[0]) || first ) ) {
                first=false;
                p = dlist[p.next];
            }

            return p.elem;
        }

        @Override
        public boolean hasNext() {
            if(isEmpty()) return false;
            if ( (current == dlist[0])&&(notAtBeginning)) {
                return false;
            }
            return true;
        }

        @Override
        public Object next() {
            notAtBeginning = true;
            Node p = current;
            current = dlist[p.next];
            return p.elem;
        }

    }

    private class Node implements Serializable{
        public Node(int p, int n,Object e) {
            prev = p;
            next = n;
            try {
                elem = ((Element) e).clone();
            }
            catch(Exception excp) {
                //System.out.println(excp.toString());
                elem = e;
            }
        }
        public int prev,next;
        public Object elem;
    }

    private Node[] dlist;
    private int nrElem=0;
    private int vectorSize=0;
    private int headIndex=0;


    public DoubleLinkedList() {
        dlist = new Node[100];
    }

    private void resize() {
        Node[] ndlist = new Node[2 * dlist.length];
        for(int i=0;i<dlist.length;i++) {
            ndlist[i]=dlist[i];
        }
        dlist = ndlist;
    }

    private Node getHead() {
        int i=0;
        int result=0;
        boolean found=false;
        while((i<vectorSize)&&(!found)) {
            if (dlist[i]!=null){
                if(dlist[i].prev==-1) {
                    found=true;
                    result=i;
                }
            }
            i++;
        }

        headIndex = result;
        return dlist[result];
    }

    private void print() {
        for(int j=0;j<vectorSize;j++) {
            if(dlist[j]==null) {
                System.out.println(j+" null");
            }
            else {
                System.out.println(j+" "+dlist[j].elem+" "+dlist[j].prev+" "+dlist[j].next);
            }
        }
    }

    @Override
    public void append(Object e) {
        if(nrElem >= dlist.length-1) {
            resize();
        }

        int pos = vectorSize;
        //find first null position

        int i=0;
        boolean found=false;
        while( (i < vectorSize) && (!found) ) {
            if((dlist[i]==null)&&(i!=0)) {
                found = true;
                pos = i;
            }
            i++;
        }

        Node elem;
        elem = new Node(0,0,e);

        if(nrElem>0) {
            Node p = getHead();
            while( p.next != 0 ) {
                p = dlist[p.next];
            }

            if(p.prev!=-1) {
                elem.prev = dlist[p.prev].next;
            }
            else {
                elem.prev=0;
            }
            elem.next = 0;

            dlist[pos] = elem;

            p.next = pos;
            if(pos == vectorSize) {
                vectorSize++;
            }
            nrElem++;
        }
        else {
            elem.prev = -1;
            elem.next = 0;
            if(pos == vectorSize) {
                vectorSize++;
            }
            dlist[pos] = elem;
            nrElem++;
        }
    }

    @Override
    public int count() {
        return nrElem;
    }

    @Override
    public void deleteElem(int index) throws IndexOutOfBoundsException {

        if(index > nrElem-1) {
            throw new IndexOutOfBoundsException("Index out of bounds!");
        }

        Node p = getHead();
        if(p.next == 0) {
            nrElem = 0;
            dlist[0] = null;
            vectorSize = 0;
            return;
        }

        int j = 0;
        int realIndex=headIndex;
        boolean first=true;
        while( ((p != dlist[0])||first) && (j < index) ) {

            if (p.next!=0) {
                realIndex = p.next;
            }

            p = dlist[p.next];
            j++;
        }

        if ( j == index ) {
            if( p.next != 0 ) {

                if(p.prev!=-1){
                    dlist[p.prev].next = p.next;
                }

                dlist[p.next].prev = p.prev;
                dlist[realIndex] = null;
                nrElem--;
            }
            else {
                dlist[p.prev].next = 0;
                dlist[realIndex]=null;
                vectorSize--;
                nrElem--;
            }
        }
    }

    @Override
    public Object getElem(int index) throws IllegalRequestException {
        Node p = getHead();
        int i = 0;
        boolean first=true;
        while( ((p != dlist[0])||first) && (index != i ) ) {
            p = dlist[p.next];
            i++;
        }
        if ((index == i)&&(p!=null)) return p.elem;
        else {
            throw new IllegalRequestException("Could not retrieve element!");
        }
    }

    @Override
    public Iterator getIterator() {
        return new ListIterator();
    }

    @Override
    public void insertElem(int index,Object e) {
        index--;

        if(vectorSize >= dlist.length-1) {
            resize();
        }

        if( index < 0 ) {
                getHead();
                Node newp = new Node(-1,headIndex,e);
                dlist[headIndex].prev = vectorSize;
                dlist[vectorSize] = newp;
                vectorSize++;
                nrElem++;
        }
        else {
            if ( index < nrElem-1 ) {
                Node p = getHead();
                int i = 0;
                boolean first=true;
                while( ( ( p != dlist[0] ) || first ) &&
                        ( index != i ) ) {
                    p = dlist[p.next];
                    i++;
                }

                if(index == i) {
                    Node newp = new Node(0,0,e);
                    int oldnext = p.next;
                    newp.prev = dlist[p.next].prev;
                    newp.next = oldnext;
                    p.next = vectorSize;
                    dlist[vectorSize] = newp;
                    vectorSize++;
                    nrElem++;
                }
            }
            else append(e);
        }

    }

    @Override
    public boolean isEmpty() {
        return nrElem == 0;
    }

    @Override
    public void setElem(int index, Object e) throws IndexOutOfBoundsException {
        if(index > nrElem-1) {
            throw new IndexOutOfBoundsException("Index out of bounds!");
        }

        Node p = getHead();
        int i = 0;
        boolean first=true;
        while( ((p != dlist[0])||first) && (index != i ) ) {
            p = dlist[p.next];
            i++;
        }

        if (index==i) {
            try {
                p.elem = ((Element) e).clone();
            }
            catch(Exception excp) {
                p.elem = e;
            }
        }
    }
}