import java.util.Comparator;
//============================================================================//
/**
* Implementation of homework 11.
*
* @author Cheng Jade
* @assignment ICS211 Homework TA11
* @date Apr 15, 2010
* @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);
// Test the sort on a list with one item.
list.add("Fiji");
list.bubbleSort(comparator);
System.out.println("A sorted, one-item list:\n\n" + list);
// Test the sort on a list with two item.
list.add("Egypt");
list.bubbleSort(comparator);
System.out.println("A sorted, two-item list:\n\n" + list);
// Test the sort on a few more items including a null item (the class
// supports null values).
list.add("Brazil");
list.add("Hungary");
list.add("Denmark");
list.add("Germany");
list.add("Zimbabwe");
list.add("Korea");
list.add("Lao");
list.add("Russia");
list.add("Malaysia");
list.add("Philippines");
list.add("Yemen");
list.add("Viet Nam");
list.add("Italy");
list.add("Japan");
list.add("New Zealand");
list.add("Argentina");
list.add("China");
list.add("Qatar");
list.add("USA");
list.add("Western Sahara");
list.add("Oman");
list.add("Singapore");
list.add("Thailand");
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);
// Test the sort on a list with duplicated item.
final LinkedList<String> duplicatedList = new LinkedList<String>();
duplicatedList.add("thailand");
duplicatedList.add("Thailand");
duplicatedList.add("Denmark");
duplicatedList.add("denmark");
System.out.println("An unsorted list with duplicated items:\n\n" + duplicatedList);
duplicatedList.bubbleSort(comparator);
System.out.println("A sorted list with duplicated items:\n\n" + duplicatedList);
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() {
this.head = null; // start with an empty list
this.size = 0;
}
/* accessor method */
public int size() {
return this.size;
}
/*
* @param value to add to the end of the list
*/
public void add(final T value) {
this.head = this.addAtEnd(this.head, value);
this.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 (this.head == null || this.head.getNext() == null)
return;
// Perform the bubble sort for a singly-linked list.
boolean swapped;
do {
swapped = false;
for (Node<T> i = this.head; i.getNext() != null; i = i.getNext())
if (comparator.compare(i.getValue(), i.getNext().getValue()) > 0)
swapped = this.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(final Node<T> node, final 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 {
this.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(final T value) {
if (this.head == null) {
this.head = new Node<T>(value, null);
} else {
Node<T> node = this.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));
}
this.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(final int position) throws BadItemCountException {
if ((position < 1) || (position > this.size)) {
throw new BadItemCountException("invalid position " + position
+ ", only 1.." + this.size + " available");
}
if (position == 1) {
this.head = this.head.getNext();
} else {
Node<T> node = this.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());
}
this.size--; // one less item
}
/*
* convert the list to a printable string
*
* @return a string representing the stack
*/
@Override
public String toString() {
return this.toString(this.head);
}
private String toString(final Node<T> node) {
if (node == null) {
return "";
} else {
return node.getValue() + "\n" + this.toString(node.getNext());
}
}
/*
* unit test -- test all the methods in this class
*
* @param ignored
*/
public static void main(final String[] args) {
/* create two empty lists, make sure they print out correctly */
final LinkedList<String> list1 = new LinkedList<String>();
final 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 (final 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 (final 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(final T value, final Node<T> next) {
this.item = value;
this.nextNode = next;
}
/* accessor methods */
public T getValue() {
return this.item;
}
public Node<T> getNext() {
return this.nextNode;
}
/* mutator methods */
public void setNext(final Node<T> newNext) {
this.nextNode = newNext;
}
public void setValue(final T value) {
this.item = value;
}
}
