/**
  *
  * Programmieraufgabe P-23 (LinkedList.java)
  *
  * @author ergaenzt: Leonhard Fellermayr
  * @version 1.0
  *
  */

import java.util.ListIterator;
import java.util.NoSuchElementException;

public class LinkedList implements InfoIIListe
{

    Link first;
    Link last;

    private void leeren()
    {
	first = null;
	last = null;
    }

    public LinkedList()
    {
	leeren();
    }

    public ListIterator listIterator()
    {
	return new LinkedListIterator(this);
    }

    public Object getFirst ()
    {
	if (first==null) throw new NoSuchElementException();
	else return first.data;
    }

    public Object getLast ()
    {
	if (last==null) throw new NoSuchElementException();
	else return last.data;
    }

    public void addFirst (Object obj)
    {
	Link newLink = new Link();
	newLink.data = obj;
	newLink.next = first;
	newLink.prev = null;
	if (first == null) {
	    first = newLink;
	    last = newLink;
	} else {
	    first.prev = newLink;
	    first = newLink;
	}
    }

    public void addLast (Object obj)	/** IMPLEMENTIERT */
    {
	Link newLink = new Link ();
	newLink.data = obj;
	newLink.next = null;
	newLink.prev = last;
	if (last == null) {		/** Liste war bisher leer */
		first = newLink;
		last  = newLink;
	} else {			/** Liste nichtleer: neues letztes Element */
		last.next = newLink;
		last = newLink;
	}
    }

    public Object removeFirst ()	/** IMPLEMENTIERT */
    {
	if (first == null)
		throw new NoSuchElementException ();

	Object obj = first.data;

	first = first.next;
	first.prev = null;

	return obj;

    }

    public Object removeLast ()		/** IMPLEMENTIERT */
    {
	if (last == null)
		throw new NoSuchElementException ();

	Object obj = last.data;

	last = last.prev;
	last.next = null;

	return obj;

    }
}

/* ************************************************************** */

class Link
{

    public Object data;
    public Link next;
    public Link prev;

}

/* ************************************************************** */

class LinkedListIterator implements ListIterator
{

    /* @param ITERATOR_AT_BEGINNING error/message code for "iterator at beginning of list" */

    private final int ITERATOR_AT_BEGINNING = -1;

    /** @param position Position index.
      *
      *         Element(0)   Element(1)   Element(2)   ... Element(n)   
      *        ^            ^            ^            ^               ^
      * Index: 0            1            2            3               n+1
      */

    private Link forward;
    private Link backward;
    private LinkedList list;
    private Link lastReturned;
    private int position;

    public LinkedListIterator(LinkedList l)
    {
	position = 0;
	forward = l.first;
	backward = null;
	list = l;
	lastReturned = null;
    }
    
    public void add(Object obj)
    {
	lastReturned = null;
	if (backward == null) {
	    list.addFirst(obj);
	    backward = list.first;
	} else if (!hasNext()) {
	    list.addLast(obj);
	    backward = backward.next;
	} else {
	    Link newLink = new Link();
	    newLink.data = obj;
	    newLink.next = forward;
	    newLink.prev = backward;
	    backward.next = newLink;
	    forward.prev = newLink;
	    backward = newLink;
	}
	position++;
    }
    
    public boolean hasNext()
    {
	return forward != null;
    }
    
    public boolean hasPrevious()
    {
	return backward != null;
    }
    
    public Object next()
    {

	if (!hasNext ())
		throw new NoSuchElementException ();

	position++; /** increment */

	lastReturned = forward;
	backward = forward;
	forward = forward.next;
	return backward.data;

    }

    /** listSize () */
    /** Returns length of the list (item count). */

    public int listSize ()
    {
	int i = 0;
	while (hasNext ())
		i++;
	return i;
    }

    /** nextIndex () */
    /** Returns the index of the element that would be returned by a subsequent call to next.
      * (note: Returns list size if the list iterator is at the end of the list.) */

    public int nextIndex()		/** IMPLEMENTIERT */
    {
	return position;
    }

    /** previous () */
    /** Returns the previous element in the list. */

    public Object previous()		/** IMPLEMENTIERT */
    {

	if (!hasPrevious ())
		throw new NoSuchElementException ();

	position--; /** decrement */

	lastReturned = backward;
	forward = backward;
	backward = backward.prev;
	return forward.data;

    }
    
    /** previousIndex () */
    /** Returns the index of the element that would be returned by a subsequent call to previous.
      * Returns ITERATOR_AT_BEGINNING if the list iterator is at the beginning of the list. */

    public int previousIndex()		/** IMPLEMENTIERT */
    {

	if ( hasPrevious () )
		return position - 1;
	else
		return ITERATOR_AT_BEGINNING;

    }

    /** Note that the remove() and set(Object) methods are not defined in terms of the cursor
        position; they are defined to operate on the last element returned by a call to next()
        or previous(). */

    /** remove () */
    /** Removes the last element that was returned by next or previous. */

    public void remove()		/** IMPLEMENTIERT */
    {

	/** nothing was returned before -> throw exception */
	if (lastReturned == null)
		throw new IllegalStateException ();

	/** first element should be removed */
	if (lastReturned.prev == null)
		list.removeFirst ();

	/** last element should be removed */
	else if (lastReturned.next == null)
		list.removeLast ();

	/** element in the middle of the list should be removed
	  * -> we have to change the prev and next references */
	else
	{
		lastReturned.prev.next = lastReturned.next;
		lastReturned.next.prev = lastReturned.prev;
	}

	lastReturned = null;

    }

    /** set (Object) */
    /** Replaces the last element returned by next or previous with the specified element. */

    public void set(Object obj)		/** IMPLEMENTIERT */
    {

	/** nothing was returned before -> throw exception */
	if (lastReturned == null)
		throw new IllegalStateException ();

	/** replace data */
	lastReturned.data = obj;

    }

}