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;
}
}
