CS 3500 Assignment #4 Due: Tuesday, 8 October 2013 Final version. The purposes of this assignment are: * to design an iterator abstraction for a binary search tree * to use and observe the design of an iterator abstraction for file input * to design a binary search tree that implements a sorting abstraction * to practice writing abstraction function and representation invariants * to learn to design the repOK methods You will write several classes as shown below. Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. You will submit this assignment within Web-CAT. Your file of Java code should begin with a block comment that lists 1. Your name, as you want the instructor to write it. 2. Your email address. 3. Any remarks that you wish to make to the instructor. Part of your grade will depend on the quality and correctness of your code, part will assess the tests you design - especially the test coverage, part will depend on the readability of your code (comments and indentation), and part will depend on how well you follow the procedure above for submitting your work. Assignments submitted between 12:00 am and 11:59 pm the day after the due date will receive a 20 percentage point penalty on the assignment. -------------------------------------------------- Your assignment is to write the code for a single file, BTree.java, that implements the class BTree as given below and two classes StringByLength and StringByLex each of which implements the Comparator interface - the first one ordering the String-s by their length, the second by their lexicographical ordering. -------------------------------------------------- Specification of the BTree. BTree is a mutable data type whose values represent String data items, organized as a binary search tree, with the ordering specified by the provided Comparator. The BTree class implements the Iterable interface by providing an Iterator that generates the individual elements of the BTree in the order specified by the provided Comparator. The BTree shall be implemented in Java, and will be tested using Sun's Java 2 Runtime Environment, Standard Edition, version 1.6.0. The code for this implementation shall be in the default package, and shall define a public class named BTree. The operations of the BTree class shall be provided by the following public methods of the BTree class: Signature: Static method binTree : Comparator -> BTree (the constructor) Dynamic methods (for which the receiver is an BTree): build : Iterable -> void toString : -> String equals : Object -> boolean hashCode : -> int plus the methods required to implement the Iterable interface Specifications are given as detailed comments: /** * Factory method to generate * an empty binary search tree * with the given Comparator * * @param comp the given Comparator * @return new empty binary search tree that uses the * given Comparator for ordering */ public static BTree binTree(Comparator comp) /** * Modifies: * this binary search tree by inserting the * Strings from the given * Iterable collection * The tree will not have any duplicates * - if an item to be added equals an item * that is already in the tree, it will not be added. * * @param iter the given Iterable collection */ public void build(Iterable iter) /** * Effect: * Produces a String that consists of * all Strings in this tree * separated by comma and a space, * generated in the order defined by this tree's * Comparator. * So for a tree with Strings * "hello" "bye" and "aloha" * ordered lexicographically, * the result would be "aloha, bye, hello" * */ public String toString() /** * Effect: * Produces false if o is not an instance of BTree. * Produces true if this tree and the given BTree * contain the same Strings and * are ordered by the same Comparator. * So if the first tree was built with Strings * "hello" "bye" and "aloha" ordered * lexicographically, and the second tree was built * with Strings "aloha" "hello" and "bye" * and ordered lexicographically, * the result would be true. * * @param o the object to compare with this */ public boolean equals(Object o) /** * Effect: * Produces an integer that is compatible * with the implemented equals method * and is likely to be different * for objects that are not equal. */ public int hashCode() The user may interact with the BTree in the following way: class Algorithm { /** * Read the given text file, insert all words * into a binary search tree with the order defined * by the given Comparator * and produce an ArrayList of words * sorted by the given Comparator. * * @param comp the given Comparator * @param fileName the given file name * @return */ public static ArrayList sortFile(Comparator comp, String fileName){ ArrayList result = new ArrayList(); BTree b = BTree.binTree(comp); b.build(new StringIterator("myfile.txt")); for (String s : b) { result.add(s); } return result; } } utilizing the class StringIterator that for a given input file produces an iterator that generates all words in the given file (eliminating commas, spaces, and other delimiters). Additional requirements: ------------------------ The remove() method must throw an UnsupportedOperationException every time it is called. The implementation of the iterator for the binary search tree should allow two or more iterators to access the data elements concurrently, but if the 'build' method is invoked while an iterator is traversing, the implementation should throw the ConcurrentModificationException. Any attempt to invoke the next() method on an empty tree should throw the NoSuchElementException. You are required to document your implementation with an abstraction function (that should include the two requirement described above), as well as with the representation invariant comments for every method in your code. Additionally, you are required to design the 'repOK' methods for your implementation that will be included in your class definitions. Finally, make sure that the internal representation is hidden from the client as much as possible. Warning: -------- There are many facets to this assignment. Make sure you have most of it done by the end of the weekend, so you can ask questions in classes on Monday and Tuesday.