/*
	File:	dll.java
	doubly linked list

	yanushka
 */

import java.util.*;

/**
	The class Test manages an exercise of the DLL< Integer > class.
 */
class Test
{
    private final static int	BASE = 100,
				SIZE = 10;

    public static void main( String [] args )
    {
	DLL< Integer >	dll = new DLL< Integer >();
	Random		rand = new Random();
	int		ndx;
	Integer		el;

//		Add at least SIZE Integer objects to dll.
	for ( int i = 0; i < SIZE + Math.abs( rand.nextInt() ) % SIZE; i++ ) {
	    dll.add( i, Math.abs( rand.nextInt() ) % BASE );
	    System.out.println( "" + i + " " + dll );
	}
//		Add or remove 2 * SIZE objects to or from dll.
	for ( int i = 0; i < 2 * SIZE; i++ ) {
	    ndx = Math.abs( rand.nextInt() ) % dll.size();
	    if ( ndx % 2 == 0 ) {
	        el = BASE + Math.abs( rand.nextInt() ) % BASE;
	        dll.add( ndx, el );
	    } else
		el = dll.remove( ndx );
	    System.out.println( "" + ndx + " " + el + "    " + dll );
	}
//		Add at tail of dll.
	ndx = dll.size();
	el = BASE + Math.abs( rand.nextInt() ) % BASE;
	dll.add( ndx, el );
	System.out.println( "\n" + dll.size() + "     " + dll );
//		Add a clone of dll to tail of dll.
	dll.addAll( dll.size(), ( DLL< Integer > )dll.clone() );
	System.out.println( "\n" + dll.size() + "     " + dll );
    }
}

/**
	The class DLL manages a doubly linked list of elements of the class E.

	It is based on the class KWLinkedList of Ch. 4  of the text.
	It provides some of the methods of java.util.LinkedList class.
 */
class DLL< E > implements Cloneable
{
    private Node< E > 	head,
			tail;
    private int		size;

/**
	Construct an empty doubly linked list.
 */
    public DLL()
    {
	head = tail = null;
	size = 0;
    }

/**
	Clone this DLL object deeply.

	Note the typical call to super.clone() does not apply here
	since it sets head and tail of the cloned object to head and
	tail of this DLL object.

	The algorithm is to construct a cloned DLL< E > object, then
	use an iterator of this DLL< E > object to add each element
	to the cloned one.
 */
    public Object clone()
    {
	DLL< E >	cloned = new DLL< E >();

	ListIterator< E >	itr = listIterator();
	E			element;
	while ( itr.hasNext() ) {
	    element = itr.next();
	    cloned.add( cloned.size(), element );
//	    System.out.println( element.toString() + " " + cloned );
	} 

	return cloned;
    }

/**
	Add all elements of a doubly linked list to this one at location index.
	@param ndx, the position to add the list
	@param dll, a doubly linked list to add
 */
    public void addAll( int ndx, DLL< E > dll )
    {
	ListIterator< E >	itr = dll.listIterator();
	E			element;

	for ( int i = 0; itr.hasNext(); i++ ) {
	    element = itr.next();
	    add( ndx + i, element );
	}
    }

/**
	Return a ListIterator for this doubly linked list object
	that starts at position 0.
	@return a ListIterator for this doubly linked list
 */
    public ListIterator< E > listIterator()
    {
	return new DLLIterator( 0 );
    }

/**
	Return a ListIterator for this doubly linked list object
	that starts at position ndx.
	@param ndx, the position to start the ListIterator object
	@return a ListIterator for this doubly linked list at location ndx
 */
    public ListIterator< E > listIterator( int ndx )
    {
	return new DLLIterator( ndx );
    }

/**
	Return an Iterator for this doubly linked list object
	that starts at position ndx.
	@param ndx, the position to start the ListIterator object
	@return an Iterator for this doubly linked list
 */
    public Iterator< E > iterator( int ndx )
    {
	return new DLLIterator( ndx );
    }

/**
	Add an element at the specified index.
	@param ndx, the position to insert an element
	@param element, the element to insert
 */
    public void add( int ndx, E element )
    {
	listIterator( ndx ).add( element );
    }

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

/**
	Get the element at position ndx.
	@param ndx, position of element to retrieve
	@return the element at ndx
 */
    public E get( int ndx )
    {
	return listIterator( ndx ).next();
    }

/**
	Remove the element at position ndx.
	@param ndx, position of element to remove
	@return the element formerly at ndx
 */
    public E remove( int ndx )
    {
	ListIterator< E > 	itr = listIterator( ndx );
	E			answer = itr.next();

	itr.remove();
	return answer;
    }

/**
	@return a String version for the data in this doubly linked list
 */
    public String toString()
    {
	String			ans = "";
	ListIterator< E >	itr = listIterator();
	E			element;

	while ( itr.hasNext() ) {
	    element = itr.next();
	    ans += element.toString() + " ";
	}

	return ans;
    }

/**	
	The inner Node class maintains an entry in a doubly linked list.
 */
    private static class Node< E >
    {
	private E		data;
	private Node< E >	next,
				prev;

/**
	Construct a Node object with the given element as data.
	@param element, value to place in data
 */
	private Node( E element )
	{
	    data = element;
	    next = prev = null;
	}
    }

/**
	The inner class DLLIterator manages a ListIterator for this
	doubly linked list object.
	From the ListIterator< E > specification, an iterator for a list 
	allows methods to traverse the list in either direction, modify the 
	list during iteration and obtain the iterator's current position in 
	the list. A ListIterator has no current element.  Its cursor position 
	always lies between the element that would be returned by a call to 
	previous() and the element that would be returned by a call to next(). 
	In a list of length n + 1, there are n + 2 valid index values, 
	from 0 to n, inclusive.

          	Element(0)   Element(1)   Element(2)   ...   Element(n)   
       	       ^           ^            ^            ^     ^           ^
 	Index: 0           1            2            3     n          n+1
 */
    private class DLLIterator implements ListIterator< E >
    {
	private Node< E >	nextNode,
				lastReturnedNode;
	private int		ndx;

/**
	Construct a default iterator.
 */
	public DLLIterator()
	{
	    nextNode = lastReturnedNode = null;
	    ndx = 0;
	}

/**
	Construct a iterator to start at the nth node.
	@param n, the index of the node to reference
 */
	public DLLIterator( int n )
	{
	    if ( ( n < 0 ) || ( n > size ) ) {
		throw new IndexOutOfBoundsException( "invalid index of " + n );
	    }

	    lastReturnedNode = null;
	    ndx = n;
	    if ( n == size ) {
		nextNode = null;
	    } else {
		nextNode = head;
		for ( int i = 0; i < n; i++ )
		    nextNode = nextNode.next;
	    }
	}

/**
	@return true if this iterator has a next node
 */
	public boolean hasNext()
	{
	    return nextNode != null;
	}

/**
	Move the iterator forward and return the next element.
	@return the next element of this iterator
 */
	public E next()
	{
	    if ( !hasNext() ) {
		throw new NoSuchElementException();
	    }
	    lastReturnedNode = nextNode;
	    nextNode = nextNode.next;
	    ndx++;
	    return lastReturnedNode.data;
	}

/**
	@return true if this iterator has a previous node
 */
	public boolean hasPrevious()
	{
	    return ( ( nextNode == null ) && ( size > 0 ) ) ||
			nextNode.prev != null;
	}

/**
	Move the iterator backward and return the previous element.
	@return the previous element of this iterator
 */
	public E previous()
	{
	    if ( !hasPrevious() ) {
		throw new NoSuchElementException();
	    }
	    if ( nextNode == null )
		nextNode = tail;
	    else
		nextNode = nextNode.prev;
	    ndx--;
	    return lastReturnedNode.data;
	}

/**
	@return the index of the item to be returned by next()
 */
	public int nextIndex()
	{
	    return ndx;
	}

/**
	@return the index of the item to be returned by previous()
 */
	public int previousIndex()
	{
	    return ndx - 1;
	}

/**
	Add a new node between the item that next() will return and
	the item previous() will return.
	@param element, item to insert
 */
	public void add( E element )
	{
	    if ( head == null ) {
//			Add to an empty list.  See p. 235 of text.
		head = new Node< E >( element );
		tail = head;
	    } else if ( nextNode == head ) {
//			Insert at head of list.  See p. 236 of text.
		Node< E > 	newNode = new Node< E >( element );
		newNode.next = nextNode;
		nextNode.prev = newNode;
		head = newNode;
	    } else if ( nextNode == null ) {
//			Insert at tail of list.  See p. 237 of text.
		Node< E > 	newNode = new Node< E >( element );
		tail.next = newNode;
		newNode.prev = tail;
		tail = newNode;
	    } else {
//			Insert in middle of list.  See p. 238 of text.
		Node< E > 	newNode = new Node< E >( element );
		newNode.prev = nextNode.prev;
		nextNode.prev.next = newNode;
		newNode.next = nextNode;
		nextNode.prev = newNode;
	    }
	    size++;
	    ndx++;
	    lastReturnedNode = null;
	}

/**
	Replace the data in the last returned node with a new element.
	@param element, the new data
 */
	public void set( E element )
	{
	    if ( lastReturnedNode == null ) {
		throw new IllegalStateException();
	    }

	    lastReturnedNode.data = element;
	}

/**
	Remove the last returned node.  From the ListIterator< E > 
	specification, remove() operates on the last element returned by 
	a call to next() or previous().
 */
	public void remove()
	{
	    if ( lastReturnedNode == null ) {
		throw new IllegalStateException();
	    }
//		Unlink the last returned node from its next neighbor.
	    if ( lastReturnedNode.next != null ) {
	        lastReturnedNode.next.prev = lastReturnedNode.prev;
	    } else {
//		lastReturnedNode is at the tail of the doubly linked list.
		tail = lastReturnedNode.prev;
		if ( tail != null ) {
		    tail.next = null;
		} else {
//			List is now empty.
		    head = null;
		}
	    }
//		Unlink the last returned node from its previous neighbor.
	    if ( lastReturnedNode.prev != null ) {
	        lastReturnedNode.prev.next = lastReturnedNode.next;
	    } else {
//		lastReturnedNode is at the head of the doubly linked list.
		head = lastReturnedNode.next;
		if ( head != null ) {
		    head.prev = null;
		} else {
		    tail = null;
		}
	    }
	    lastReturnedNode = null;
	    size--;
	    ndx--;
	}
    }
}