//DLLNode.java

/**
 * A doubly-linked Node.
 * Contains an Object, and references to the next and previous nodes.
 *
 * @author Zach Tomaszewski
 * @version 1 Oct 2004
 */
public class DLLNode {

  private Object contents;
  private DLLNode next;
  private DLLNode prev;
  
  /**
   * Creates a new Node with no links
   */
  public DLLNode(Object contents) {
    this(contents, null, null);
  }
  
  /**
   * Create a new node with the given contents, and links
   */
  public DLLNode(Object contents, DLLNode prev, DLLNode next){
    this.setValue(contents);
    this.setNext(next);
    this.setPrev(prev);
  }


  /**
   * Sets this node to contain the given value
   *
   * @param value  The new contents of this node.
   */
  public void setValue(Object value) {
    this.contents = value;
  }
  
  /**
   * Returns this node's contents.
   */
  public Object getValue() {
    return this.contents;
  }
  
  /**
   * Set this node's next reference to the given node.
   *
   * @param next  The node this node should point to as next in a list.
   */
  public void setNext(DLLNode next){
    this.next = next;
  }

  /**
   * Returns the next node in a list after this node.
   */ 
  public DLLNode getNext(){
    return this.next;
  }

  /**
   * Set this node's previous reference to the given node.
   *
   * @param prev  The node this node should point to as coming before 
   *              it in a list.
   */
  public void setPrev(DLLNode prev){
    this.prev = prev;
  }

  /**
   * Returns the node before this node in a list.
   */ 
  public DLLNode getPrev(){
    return this.prev;
  }

}//end class


//DLList.java

import java.util.List;
import java.util.Collection;
import java.util.ListIterator;
import java.util.Iterator;

/**
 * A List.
 * Implemented as a doubly-linked list of nodes.
 *
 * @author Zach Tomaszewski
 * @version 01 Oct 2004
 */
public class DLList implements List {
  
  /* uses only a head and no tail for simplicity of implementation */
  protected DLLNode head;

  public String toString() {
    String repres = "[";
    DLLNode cursor = head;
    while (cursor != null) {
      repres += cursor.getValue().toString();
      cursor = cursor.getNext();
      if (cursor != null) {
        repres += ", ";  //add spacer between elements
      }
    }
    repres += "]";
    return repres;
  }
   
  public boolean add (Object o) {
    DLLNode last = getLastNode();
    if (last == null) { //no last node because list is empty
      head = new DLLNode(o);
    }else {
      last.setNext(new DLLNode(o, last, null));
    }
    return true;  //will always add o to the list  
  }
  
  public void add(int index, Object newObj){
    if (index == this.size()) {
      //just adding to the end of the list
      this.add(newObj);
    }else {
      DLLNode oldPos = getNode(index); //will throw any IndexOutOfBoundsEx.
      if (oldPos == head) { //acutally adding to head of list
        head = new DLLNode(newObj, null, oldPos);
        oldPos.setPrev(head);
      }else { //adding amidst list
        DLLNode newNode = new DLLNode(newObj, oldPos.getPrev(), oldPos);
        oldPos.getPrev().setNext(newNode);
        oldPos.setPrev(newNode);
      }
    }
  }
  
  public void clear() {   
    head = null;
    /* this makes the chain of nodes unreachable 
     * (despite references among themselves)
     * and thus all nodes are garbage collected.
     */
  }
  
  public boolean contains(Object o) {
    return (getNode(o) != null); 
  }
  
  public boolean isEmpty() {
    return (head == null);
  }
  
  public int size() {
    int count = 0;
    //count the nodes
    for (DLLNode cursor = head; 
         cursor != null; 
         cursor = cursor.getNext(), count++) { }
    return count;
  }
  
  
  public boolean equals(Object rhsList) {
    if (!(rhsList instanceof DLList)) {
      return false; 
    }
    DLList rhs = (DLList) rhsList;
    DLLNode lhsCursor = this.head;
    DLLNode rhsCursor = rhs.head;
    
    //go through both lists, comparing each position as we go
    while (lhsCursor != null && rhsCursor != null &&
           (lhsCursor.getValue()).equals(rhsCursor.getValue())) {
      lhsCursor = lhsCursor.getNext();
      rhsCursor = rhsCursor.getNext();
    }
    //if we reached the end of identical lists, then lhs == rhs == null.
    //otherwise dropped out early because lhs != rhs
    return (lhsCursor == null && rhsCursor == null);
  }
  
  
  public Object get(int index) {
    return this.getNode(index).getValue();
  }
  
  public Object set(int index, Object newObj) {
    DLLNode node = getNode(index);
    Object old = node.getValue();  //need to return original value
    node.setValue(newObj);
    return old;
  }
  
  
  public int indexOf(Object o){
    DLLNode cursor = head;
    int index = 0;
    while(cursor != null && !cursor.getValue().equals(o)) {
      cursor = cursor.getNext();
      index++;
    }
    //return index value only if really found a match
    return (cursor != null) ? index : -1;
  }
  
  public int lastIndexOf(Object o){
    DLLNode cursor = getLastNode();
    int index = this.size() - 1;
    while(cursor != null && !cursor.getValue().equals(o)) {
      cursor = cursor.getPrev();
      index--;
    }
    //return index value only if really found a match
    return (cursor != null) ? index : -1;
  }
  
  
  public Object remove(int index) {
    DLLNode node = getNode(index); //will throw any IndexOutOfBoundsException
    Object old = node.getValue(); //return deleted value
    if (node == head) {
      head = node.getNext();
      head.setPrev(null);
    }else {
      node.getPrev().setNext(node.getNext()); // if a > n > c, now a > c
      if (node.getNext() != null) {
        node.getNext().setPrev(node.getPrev()); // if a < n < c, now a < c
      }
    }
    return old;
  }
  
  public boolean remove(Object o) {
    DLLNode node = this.getNode(o); //find first occurance
    if (node == null) { //no occurance found
      return false;
    }else {
      if (node == head) {
        head = node.getNext();
        head.setPrev(null);
      }else {
        node.getPrev().setNext(node.getNext()); // if a > n > c, now a > c
        if (node.getNext() != null) {
          node.getNext().setPrev(node.getPrev()); // if a < n < c, now a < c
        }
      }
      return true;
    }
  }
  
  
  public Object[] toArray() {
    return toArray(new Object[0]);
  }
  
  public Object[] toArray(Object[] a) {
    if (a.length < this.size()) { // a is too small for this list
      a = (Object[]) java.lang.reflect.Array.newInstance(
                       a.getClass().getComponentType(), this.size());
    }
    int i = 0;
    for(DLLNode cursor = head;
        cursor != null;
        i++, cursor = cursor.getNext()){
      a[i] = cursor.getValue();
    }
    if (this.size() < a.length) { //a was longer than list
      a[this.size()] = null; //set element after end of list to null
    }
    return a;

  }
  
  // UNSUPPORTED INTERFACE METHODS
  public boolean addAll(Collection c){
    throw new UnsupportedOperationException();
  }
  public boolean addAll(int index, Collection c){
    throw new UnsupportedOperationException();
  }  
  public boolean containsAll(Collection c){
    throw new UnsupportedOperationException();
  }  
  public Iterator iterator() {
    throw new UnsupportedOperationException();
  }
  public ListIterator listIterator() {
    throw new UnsupportedOperationException();
  }
  public ListIterator listIterator(int index) {
    throw new UnsupportedOperationException();
  }
  public boolean removeAll(Collection c){
    throw new UnsupportedOperationException();
  }
  public boolean retainAll(Collection c){
    throw new UnsupportedOperationException();
  }  
  public List subList(int fromIndex, int toIndex){
      throw new UnsupportedOperationException();
  }  
  
  // PRIVATE HELPER METHODS
  
  /**
   * Returns the node at the given position in the list.
   * Positioning starts at 0.
   *
   * @throws IndexOutOfBoundsException if position is not in the range 
   *                                   of the list: pos < 0 || pos >= size()
   */
  private DLLNode getNode(int position){
    DLLNode cursor = head;
    for (int i = 0; i < position; i++, cursor = cursor.getNext()){
      if (cursor == null) {
        //ran off the list before reaching position
        throw new IndexOutOfBoundsException();
      }
    }
    if (cursor != null) {
      return cursor;
    }else {
      //cursor is null, such when asking for pos 0 in an empty list
      throw new IndexOutOfBoundsException();
    }
  }    

  /**
   * Returns the first node containing the given Object.
   *
   * @return The found node, or null if no node in this list contains o.
   */
  private DLLNode getNode(Object o){
    DLLNode cursor = head;
    while(cursor != null && !cursor.getValue().equals(o)) {
      cursor = cursor.getNext();
    }
    return cursor;
  }    

  /**
   * Returns the last node in this list.
   * 
   * @return the last node or null if this list is empty
   */
  private DLLNode getLastNode() {
    DLLNode cursor = head;
    while (cursor != null && cursor.getNext() != null) {
      cursor = cursor.getNext();
    }
    return cursor;
  }

}//end class


//DLLTest.java

/**
 * Tests of the class DLList.
 *
 * @author Zach Tomaszewski
 * @version 12 Oct 2004
 */
public class DLLTest {

  /**
   * Creates a DLList, reverses it, and re-reverses it.
   * Prints the list out each time an action is performed on it.
   */
  public static void main(String[] args){
    DLList list = new DLList();
    list.add("one");
    list.add("two");
    list.add("three");
    list.add("four");
    System.out.print("A new list:              \t");
    System.out.println(list.toString());

    list = reverseList(list);
    System.out.print("The list after reversal: \t");
    System.out.println(list.toString());
    
    list = reverseList(list);
    System.out.print("The list reversed again: \t");    
    System.out.println(list.toString());
    System.out.println("Done.");
  }

  
  /**
   * Returns a reversed copy of a given list.
   *
   * @param original  The list to reverse, which is unchanged by this method.
   * @return a reversed copy of original
   */
  public static DLList reverseList(java.util.List original) {
    DLList rev = new DLList();
    for (int i = 0; i < original.size(); i++){
      //move through original, copying each element to start of rev
      rev.add(0, original.get(i));
    }
    return rev;
  }

}//end class