ChengJade11.java

import java.util.Comparator;
 
//============================================================================//
/**
 * Implementation of homework 11.
 * 
 * @author     Cheng Jade
 * @assignment ICS211 Homework TA11
 * @date       Nov 26, 2008
 * @bugs       None
 */
public class ChengJade11 {
  /**
   * The main entry point of the program.
   *
   * @param args The command line arguments (not used).
   */
  public static void main(final String[] args) {
 
    // Test the sort on a list with no items.
    final LinkedList<String> list = new LinkedList<String>();
    final StringComparator comparator = new StringComparator();
    list.bubbleSort(comparator);
    System.out.println("A sorted, empty list:\n\n" + list);
 
    // Next, test the sort on a list with one item.
    list.add("Mom");
    list.bubbleSort(comparator);
    System.out.println("A sorted, one-item list:\n\n" + list);
 
    // Next, test the sort on a list with two item.
    list.add("Dad");
    list.bubbleSort(comparator);
    System.out.println("A sorted, two-item list:\n\n" + list);
 
    // Next, test the sort on a few more items including a null item (the class
    // supports null values).
    list.add("Sister");
    list.add("Brother");
    list.add("Uncle");
    list.add("Aunt");
    list.add(null);
    list.add("Cousin");
    list.add("Nephew");
    list.add("Neice");
    list.add(null);
    System.out.println("An unsorted list with several items:\n\n" + list);
 
    // Sort the list using a StringComparator, and display it again.
    list.bubbleSort(comparator);
    System.out.println("A sorted list with several items:\n\n" + list);
 
    System.exit(0);
  }
}
 
/**
 * A comparator class that compares two strings ignoring case.
 */
class StringComparator implements Comparator<String> {
  /**
   * Compares two strings ignoring case.  Two null strings are considered equal,
   * a non-null string is considered greater than a null string, and two
   * non-null strings are compared using compareToIgnoreCase from the String
   * class.
   *
   * @param s1 The first string.
   * @param s2 The second string.
   * @return A value compatible with compareToIgnoreCase from the String class.
   */
  public int compare(final String s1, final String s2) {
    if (s1 == null)
      return s2 == null ? 0 : -1;
    return s2 == null ? 1 : s1.compareToIgnoreCase(s2);
  }
}
 
/**
 * An exception thrown when an invalid position is passed to the remove method
 * of the LinkedList class.
 */
@SuppressWarnings("serial")
class BadItemCountException extends RuntimeException {
  /**
   * Initializes a new instance of the class.
   *
   * @param message The message describing the failure.
   */
  public BadItemCountException(final String message) {
    super(message);
  }
}
//============================================================================//
 
/*
 * a generic list implemented using a linked list of nodes
 * @author Biagioni, Edoardo
 * @assignment lecture 9 and assignment 10
 * @date February 11, 2008
 * @inspiration William Albritton's GenericLinkedList.java
 * http://www2.hawaii.edu
 * /~walbritt/ics211/linkedListGeneric/GenericLinkedList.java
 */
class LinkedList<T> {
  /*
   * only need to store a single pointer to the node at the head of the list.
   * The pointer is null if the list is empty. Also record the size of the list.
   */
  protected Node<T> head;
  /* invariant: size is the number of nodes in the list pointed to by head */
  protected int     size;
 
 
  /* no-arguments default constructor creates an empty list */
  public LinkedList() {
    head = null; // start with an empty list
    size = 0;
  }
 
 
  /* accessor method */
  public int size() {
    return size;
  }
 
 
  /*
   * @param value to add to the end of the list
   */
  public void add(T value) {
    head = addAtEnd(head, value);
    size++;
  }
 
 
  //==========================================================================//
  /**
   * Sorts the list using the bubble sort algorithm.
   * 
   * @param comparator A generic Comparator for T.
   * @throws NullPointerException if the comparator is null.
   */
  public void bubbleSort(final Comparator<T> comparator) {
    // The comparator is required by the method.
    if (comparator == null)
      throw new NullPointerException("c");
 
    // Do nothing if there are fewer than two items in the collection.
    if (head == null || head.getNext() == null)
      return;
 
    // Perform the bubble sort for a singly-linked list.
    boolean swapped;
    do {
      swapped = false;
      for (Node<T> i = head; i.getNext() != null; i = i.getNext())
        if (comparator.compare(i.getValue(), i.getNext().getValue()) > 0)
          swapped = swap(i, i.getNext());
    } while (swapped);
 
    // If this were a doubly-linked list, the following algorithm could be used.
    // It is slightly simpler (I think).
    //
    // for (BinaryNode<T> i = head; i != null; i = i.next)
    //   for (BinaryNode<T> j = tail; j != i; j = j.previous)
    //     if (comparator.compare(j.value, i.value) < 0)
    //       swap(i, j);
  }
 
  /**
   * Swaps two nodes by switching the nodes' values.
   * 
   * @param n1 the first node to swap.
   * @param n2 the second node to swap.
   * @return This method always returns true.
   */  
  private boolean swap(final Node<T> n1, final Node<T> n2) {
    assert n1 != null;
    assert n2 != null;
 
    final T temp = n1.getValue();
    n1.setValue(n2.getValue());
    n2.setValue(temp);
 
    return true;
  }
  //==========================================================================//
 
    /*
   * @param node of the list to which the value should be added @param value to
   * add to the end of the list
   */
  private Node<T> addAtEnd(Node<T> node, T value) {
    if (node == null) { // special case
      return new Node<T>(value, null);
    } else if (node.getNext() == null) { // other special case
      node.setNext(new Node<T>(value, null));
    } else {
      addAtEnd(node.getNext(), value);
    }
    return node;
  }
 
 
  /*
   * iterative implementation of the same method
   * @param value to add to the end of the list
   */
  public void add2(T value) {
    if (head == null) {
      head = new Node<T>(value, null);
    } else {
      Node<T> node = head; // guaranteed not to be null initially
      while (node.getNext() != null) {
        node = node.getNext(); // guaranteed not to be null here
      }
      // now, node.getNext() is guaranteed to be null
      // similar to the second special case in addAtEnd
      node.setNext(new Node<T>(value, null));
    }
    size++;
  }
 
 
  /*
   * @param position of item to be removed
   * @throws BadItemCountException if this is not a valid position position is
   * 1-based, so position = 1 removes the head
   */
  public void remove(int position) throws BadItemCountException {
    if ((position < 1) || (position > size)) {
      throw new BadItemCountException("invalid position " + position
          + ", only 1.." + size + " available");
    }
    if (position == 1) {
      head = head.getNext();
    } else {
      Node<T> node = head;
      for (int i = 2; i < position; i++) {
        node = node.getNext();
      }
      // set this node's "next" pointer to refer to the
      // node that is after the next
      node.setNext(node.getNext().getNext());
    }
    size--; // one less item
  }
 
 
  /*
   * convert the list to a printable string
   * @return a string representing the stack
   */
  public String toString() {
    return toString(head);
  }
 
 
  private String toString(Node<T> node) {
    if (node == null) {
      return "";
    } else {
      return node.getValue() + "\n" + toString(node.getNext());
    }
  }
 
 
  /*
   * unit test -- test all the methods in this class
   * @param ignored
   */
  public static void main(String[] args) {
    /* create two empty lists, make sure they print out correctly */
    LinkedList<String> list1 = new LinkedList<String>();
    LinkedList<String> list2 = new LinkedList<String>();
    System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
    System.out.println("list1.size() = " + list1.size() + ", list2.size() = " + list2.size());
 
    /* insert some items, keep checking */
    list1.add("hello");
    list1.add("world");
    list2.add("foo");
    list2.add("bar");
    list2.add("baz");
    System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
    System.out.println("list1.size() = " + list1.size() + ", list2.size() = " + list2.size());
 
    /* remove an item at an invalid position */
    boolean caught = false;
    try {
      list2.remove(4);
    } catch (BadItemCountException e) {
      caught = true;
    }
    if (!caught) {
      System.out.println("error: no exception for invalid remove");
      System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
    }
    System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
 
    /* remove some items at valid positions */
    try {
      list1.remove(1);
      System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
      list2.remove(2);
      System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
      list2.remove(2);
      System.out.println("list1 = '" + list1 + "', list2 = '" + list2 + "'");
    } catch (Exception e) {
      System.out.println("caught unexpected exception " + e + ", list1 = '" + list1 + ", list2 = " + list2);
    }
    System.out.println("list1.size() = " + list1.size() + ", list2.size() = " + list2.size());
  }
}
 
/*
 * a class for nodes that store arbitrary objects
 * @author Biagioni, Edoardo
 * @assignment lecture 9
 * @date February 11, 2008
 */
class Node<T> {
  /*
   * two fields, the first to store the item itself, the second is a pointer to
   * the next node in the linked list. If there is no next node, the pointer is
   * null.
   */
  private T       item;
  private Node<T> nextNode;
 
 
  /*
   * constructor:
   * @param value, the value for the node
   * @param next, the next node in the linked list
   */
  public Node(T value, Node<T> next) {
    item = value;
    nextNode = next;
  }
 
 
  /* accessor methods */
  public T getValue() {
    return item;
  }
 
 
  public Node<T> getNext() {
    return nextNode;
  }
 
 
  /* mutator methods */
  public void setNext(Node<T> newNext) {
    nextNode = newNext;
  }
 
 
  public void setValue(T value) {
    item = value;
  }
}
 
Valid HTML 4.01 Valid CSS