ChengJade11.java

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;
    }
}
 
Valid HTML 4.01 Valid CSS