import java.util.*;

/** Class KWLinkedList implements a double linked list and
 *  a ListIterator.  This is taken from the instructor's material
 * accompanying the text.
 *  @author Koffman & Wolfgang, with sorting routine by Timothy Rolfe
 */

public class KWLinkedList<E extends Comparable<E>>
        implements Iterable<E> {

  // Data Fields
  /** A reference to the head of the list. */
  private Node < E > head = null;

  /** A reference to the end of the list. */
  private Node < E > tail = null;

  /** The size of the list. */
  private int size = 0;

  public KWLinkedList()
  {;}

  // Generate  sublist delimited by the head and tail.  The passed
  // size is presumed to be correct.
  private KWLinkedList( Node<E> head, Node<E> tail, int size )
  {
    this.head = head;
    this.tail = tail;
    this.size = size;
    if ( size > 0 )
    {
      tail.next = null;
      head.prev = null;
    }
  }

  public KWLinkedList clone()
  { return new KWLinkedList (this.head, this.tail, this.size );  }

  public int size()  { return size;  }

  public void clear ( )
  {  head = tail = null;  size = 0;  }

  //Methods
  /**** BEGIN EXERCISE ****/
  /** Insert an object at the beginning of the list.
        @param item - the item to be added
   */
  public void addFirst(E item) {
    add(0, item);
  }

  /** Insert an object at the end of the list.
      @param item - the item to be added
   */
  public void addLast(E item) {
    add(size, item);
  }

  /** Get the first element in the list.
      @return The first element in the list.
   */
  public E getFirst() {
    return head.data;
  }

  /** Get the last element in the list.
      @return The last element in the list.
   */
  public E getLast() {
    return tail.data;
  }

  /** Return an Iterator to the list
          @return an Itertor tot the list
   */
  public Iterator < E > iterator() {
    return new KWListIter(0);
  }

  /** Return a ListIterator to the list
      @return a ListItertor to the list
   */
  public ListIterator < E > listIterator() {
    return new KWListIter(0);
  }

  /** Return a ListIterator that begins at index
      @param index - The position the iteration is to begin
      @return a ListIterator that begins at index
   */
  public ListIterator < E > listIterator(int index) {
    return new KWListIter(index);
  }

  /** Return a ListIterator that begins at the same
      place as an existing ListIterator
      @param iter - The other ListIterator
      @return a ListIterator that is a copy of iter

  disabled in Koffman and Wolfgang.  Enabled here.  */
  public ListIterator < E > listIterator(ListIterator < E > iter) {
    return new KWListIter( (KWListIter) iter);
  } /**/

  /**** END EXERCISE ****/

  /** Add an item at the specified index.
      @param index The index at which the object is to be
             inserted
      @param obj The object to be inserted
      @throws IndexOutOfBoundsException if the index is out
              of range (i < 0 || i > size())
   */
  public void add(int index, E obj) {
    listIterator(index).add(obj);
  }

  /** Get the element at position index.
      @param index Position of item to be retrieved
      @return The item at index
   */
  public E get(int index) {
    return listIterator(index).next();
  }

/********** Beginning of code added by Timothy Rolfe  **********/

   // toArray as specified in the Interface List
   public E[] toArray ( E x[] )
   {
      int n = this.size, k = 0;

      if ( x.length < n )
         x = (E[]) new Object[n];

      for ( E item : this )
         x[k++] = item;

      return x;
   }

   // The list structure is unchanged, while data values are moved
   // around within it.  Since class Node is a nested class, we have
   // access to its private fields.
   public void selectSort()
   {
      Node<E> front = head;

      if ( front == null )
         return;

      while ( front.next != null )
      {
         Node<E> check = front.next,
                 small = front;
         E       smallValue = small.data;

         while ( check != null )
         {
            if ( smallValue.compareTo(check.data) > 0 )
            {
               small = check;
               smallValue = small.data;
            }
            check = check.next;
         }
         // Finish the swap begun by setting smallValue
         small.data = front.data;
         front.data = smallValue;
         front = front.next;
      }
   }

   // NOTE:  Take advantage of the doubly-linked list
   public void insertSort()
   {  Node<E> working = head;

      // No work to do if the list is empty or has just one element
      if ( head == null || head.next == null )
         return;

      // The nodes to be inserted begin with the SECOND
      working      = working.next;
      // Transform the existing list into a one-node list
      head.prev    = head.next = null;
      tail         = head;
      working.prev = null; // I.e., this is now the front of the list

      while ( working != null )
      {  Node<E> current  = head;
         Node<E> hold     = working;    // Insert node from old list
         E       holdData = hold.data;  // Separate copy for convenience

         working = working.next;     // New front of the remaining list
         if ( working != null )      // Maintain appropriate back link
            working.prev = null;
         hold.next = hold.prev = null; // And remove links to old list

         // Find where this element belongs in the list being generated
         while ( current != null )
            // "<= 0" to guarantee a stable sort
            if ( holdData.compareTo(current.data) <= 0 )
               break;
            else
               current = current.next;

         // The "hold" node belongs BEFORE current
         hold.next = current;
         if ( current == null )   // Add to end of list
         {  hold.prev = this.tail;
            this.tail = this.tail.next = hold;
         }
         else    // Check whether this is the beginning or farther along
         {  if ( current.prev != null )
            {  hold.prev = current.prev;
               current.prev.next = hold;
               current.prev = hold;
            }
            else // We must be adding this to the front of the list
            {  hold.prev = null;
               current.prev = hold;
               head = hold;
            }
         }
      }
   }

/**
 * Recursive merge sort algorithm.  If the list has size greater
 * than one, split it into (nearly) equal halves (on an odd size,
 * the left sublist is the shorter).  The private constructor
 * receives the head and tail references and the size, and generates
 * a KWLinkedList with these fields.  Recursively mergeSort the two
 * sublists, and then perform a merge of the two resulting sorted
 * lists.
 */
   public void mergeSort()
   {
      KWLinkedList<E> leftList, rightList;
      Node<E>         current = this.head;
      int             leftSize = this.size / 2,
                      rightSize = this.size - leftSize,
                      k;     // loop variable

      if ( this.size < 2 ) return;

      // Traverse to the _end_ of the left sublist
      // Start at 1 to go (leftSize-1) steps
      for ( k = 1; k < leftSize; k++ )
         current = current.next;

      // NOTE:  it is CRITICAL that the right list be generated first, since
      //        creation of the left list sets current.next to null.
      rightList = new KWLinkedList<E> ( current.next, this.tail, rightSize );
      leftList  = new KWLinkedList<E> ( this.head, current, leftSize );
      this.head = this.tail = null;  this.size = 0;

      // Recursively sort these two sublists.
      leftList.mergeSort();  rightList.mergeSort();

      // Start out the list with a dummy header for convenience ---
      // that way the first entry is not a special case.
      current = this.head = new Node<E>(null);

      // Merge these two lists into a single list

      // Execute until one of the two lists goes empty.
      while (leftList.head != null && rightList.head != null )
      {
         // ? Pull from the right list ?
         if (leftList.head.data.compareTo(rightList.head.data) > 0 )
         {
            current.next = rightList.head;       // Link in the node
            rightList.head = rightList.head.next;// Advance this list
         }
         else // pull from the left list.
         {
            current.next = leftList.head;       // Link in the node
            leftList.head = leftList.head.next; // Advance this list
         }
         current.next.prev = current;  // Set the back link
         current = current.next;       // Update the current node
      }

      // Append the non-empty list at the back of the current list
      if ( leftList.head != null )     // Left sublist has contents
      {
         current.next = leftList.head;
         current.next.prev = current;  // Set the back link
         this.tail = leftList.tail;    // and grab the tail setting
      }
      else                             // Right sublist has contents
      {
         current.next = rightList.head;
         current.next.prev = current;  // Set the back link
         this.tail = rightList.tail;   // and grab the tail setting
      }
      // Regenerate the size
      this.size = leftList.size + rightList.size;
      // REMOVE the dummy header --- the garbage collector will recover it.
      this.head = this.head.next;
   }

   // Are the links valid in this doubly-linked list?
   public boolean valid()
   {
      Node current;

      if ( head == null )
         return true;
      if ( head.prev != null )
         return false;
      if ( head.next == null )
         return true;
      for ( current = head.next; current != null; current = current.next)
         if ( current.prev.next != current )
            return false;
      return true;
   }


   public void display()
   {
      for ( E item : this )
         System.out.print ( item + " " );
      System.out.println();
   }

  /********** End of code added by Timothy Rolfe  **********/

// Inner Classes

  /** A Node is the building block for a double-linked list. */
  private static class Node < E > {
    /** The data value. */
    private E data;

    /** The link to the next node. */
    private Node < E > next = null;

    /** The link to the previous node. */
    private Node < E > prev = null;

    /** Construct a node with the given data value.
        @param dataItem The data value
     */
    private Node(E dataItem) {
      data = dataItem;
    }
  } //end class Node

  /** Inner class to implement the ListIterator interface. */
  private class KWListIter implements ListIterator < E > {
    /** A reference to the next item. */
    private Node < E > nextItem;

    /** A reference to the last item returned. */
    private Node < E > lastItemReturned;

    /** The index of the current item. */
    private int index = 0;

    /** Construct a KWListIter that will reference the ith item.
        @param i The index of the item to be referenced
     */
    public KWListIter(int i) {
      // Validate i parameter.
      if (i < 0 || i > size) {
        throw new IndexOutOfBoundsException(
            "Invalid index " + i);
      }
      lastItemReturned = null; // No item returned yet.
      // Special case of last item.
      if (i == size) {
        index = size;
        nextItem = null;
      }
      else { // Start at the beginning
        nextItem = head;
        for (index = 0; index < i; index++) {
          nextItem = nextItem.next;
        }
      }
    }

    /** Clone the iterator passed by copying across its fields.
        @author Timothy Rolfe
        @param iter The iterator to be clones.
     */
    public KWListIter(KWListIter iter)
    {
       this.nextItem         = iter.nextItem;
       this.lastItemReturned = iter.lastItemReturned;
       this.index            = iter.index;
    }

    /** Indicate whether movement forward is defined.
        @return true if call to next will not throw an exception
     */
    public boolean hasNext() {
      return nextItem != null;
    }

    /** Move the iterator forward and return the next item.
        @return The next item in the list
        @throws NoSuchElementException if there is no such object
     */
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      lastItemReturned = nextItem;
      nextItem = nextItem.next;
      index++;
      return lastItemReturned.data;
    }

    /** Indicate whether movement backward is defined.
        @return true if call to previous will not throw an exception
     */
    public boolean hasPrevious() {
      return (nextItem == null && size != 0)
          || nextItem.prev != null;
    }

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

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

    /** Move the iterator backward and return the previous item.
        @return The previous item in the list
        @throws NoSuchElementException if there is no such object
     */
    public E previous() {
      if (!hasPrevious()) {
        throw new NoSuchElementException();
      }
      if (nextItem == null) { // Iterator past the last element
        nextItem = tail;
      }
      else {
        nextItem = nextItem.prev;
      }
      lastItemReturned = nextItem;
      index--;
      return lastItemReturned.data;
    }

    /** Add a new item between the item that will be returned
        by next and the item that will be returned by previous.
        If previous is called after add, the element added is
        returned.
        @param obj The item to be inserted
     */
    public void add(E obj) {
      if (head == null) { // Add to an empty list.
        head = new Node < E > (obj);
        tail = head;
      }
      else if (nextItem == head) { // Insert at head.
        // Create a new node.
        Node < E > newNode = new Node < E > (obj);
        // Link it to the nextItem.
        newNode.next = nextItem; // Step 1
        // Link nextItem to the new node.
        nextItem.prev = newNode; // Step 2
        // The new node is now the head.
        head = newNode; // Step 3
      }
      else if (nextItem == null) { // Insert at tail.
        // Create a new node.
        Node < E > newNode = new Node < E > (obj);
        // Link the tail to the new node.
        tail.next = newNode; // Step 1
        // Link the new node to the tail.
        newNode.prev = tail; // Step 2
        // The new node is the new tail.
        tail = newNode; // Step 3
      }
      else { // Insert into the middle.
        // Create a new node.
        Node < E > newNode = new Node < E > (obj);
        // Link it to nextItem.prev.
        newNode.prev = nextItem.prev; // Step 1
        nextItem.prev.next = newNode; // Step 2
        // Link it to the nextItem.
        newNode.next = nextItem; // Step 3
        nextItem.prev = newNode; // Step 4
      }
      // Increase size and index and set lastItemReturned.
      size++;
      index++;
      lastItemReturned = null;
    } // End of method add.

    /** Remove the last item returned. This can only be
     *  done once per call to next or previous.
     *  @throws IllegalStateException if next or previous
     *  was not called prior to calling this method
     */
    /**** BEGIN EXERCISE ****/
    public void remove() {
      if (lastItemReturned == null) {
        throw new IllegalStateException();
      }
      // Unlink this item from its next neighbor
      if (lastItemReturned.next != null) {
        lastItemReturned.next.prev = lastItemReturned.prev;
      }
      else { // Item is the tail
        tail = lastItemReturned.prev;
        if (tail != null) {
          tail.next = null;
        }
        else { // list is now empty
          head = null;
        }
      }
      // Unlink this item from its prev neighbor
      if (lastItemReturned.prev != null) {
        lastItemReturned.prev.next = lastItemReturned.next;
      }
      else { // Item is the head
        head = lastItemReturned.next;
        if (head != null) {
          head.prev = null;
        }
        else {
          tail = null;
        }
      }
      // Invalidate lastItemReturned
      lastItemReturned = null;
      // decrement both size and index
      size--;
      index--;
    }

    /** Remove the first instance of the object passed.
     *  @param o the object to be removed.
     */
    public boolean remove(E target) {
      Node < E > current = head;

      while ( current != null && ! target.equals(current.data) )
        current = current.next;

      if ( current == null )
         return false;

      // Unlink this item from its next neighbor
      if (current.next != null) {
        current.next.prev = current.prev;
      }
      else { // Item is the tail
        tail = current.prev;
        if (tail != null) {
          tail.next = null;
        }
        else { // list is now empty
          head = null;
        }
      }
      // Unlink this item from its prev neighbor
      if (current.prev != null) {
        current.prev.next = current.next;
      }
      else { // Item is the head
        head = current.next;
        if (head != null) {
          head.prev = null;
        }
        else {
          tail = null;
        }
      }
      // decrement both size and index
      size--;
      index--;
      return true;
    }

    /** Replace the last item returned with a new value
     *  @param item The new value
     *  @throws IllegalStateException if next or previous
     *  was not called prior to calling this method
     */
    public void set(E item) {
      if (lastItemReturned == null) {
        throw new IllegalStateException();
      }
      lastItemReturned.data = item;
    }

    /**** END EXERCISE ****/

  } //end class KWListIter
}