CS U370 Assignment #5 Section: Fall 2007, Prof. Hafner Assigned: Tuesday, March 11 Due: Friday, March 21 **************************************************************** For this assignment, you will enhance the AllRoutes program from Assignment 4 in two ways: Part 1. Turn in a new version of the AllRoutes class that satisfies the java API's Iterable interface. Part 2. Create a new class RouteTracer which is a client of the AllRoutes class. RouteTracer has a public method trace() which prints a description of the Route objects in an AllRoutes aggregate a, in the order specified by a comparator c. Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. Part of your grade will be determined by how well you hide your code, part of your grade will be determined by how well you follow the instructions for submitting your code, part of your grade will depend upon the correctness of your code, and part of your grade will depend upon the readability of your code (e.g. formatting and comments). Turn in your work before 10 pm on the due date using the Web-based submission system at: https://cgi.ccs.neu.edu/home/duanjj/csu370/csu370.php You will see two entry points for submitting the two parts of the assignment. Each submission must be a text file containing nothing but your new AllRoutes.java program (part 1) and nothing but your RouteTracer.java program (part 2). Those files 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. Late assignments may be discounted, and very late assignments may be discarded. -------------------------------------------------- Part 1 of your assignment is to write the code for a single file, AllRoutes.java, that declares a public class named AllRoutes that provides the behavior of the AllRoutes ADT specified below, and that implements the java.util.Iterator interface. Note that AllRoutes.java must be part of the geography package. Note further that the only difference between the AllRoutes ADT specified below and the specification of the AllRoutes ADT for assignment 4 is that the AllRoutes ADT below implements java.util.Iterator interface. -------------------------------------------------- Specification of the AllRoutes ADT (mostly the same as hw4) Signature and Java syntax: ***************************************************************** // Basic creators, to be located within the AllRoutes class. public static AllRoutes empty(); public static AllRoutes addLeg(AllRoutes, Route); // Derived creators, to be located within the AllRoutes class. public static AllRoutes select(AllRoutes, Comparator, Route); public static AllRoutes sort(AllRoutes, Comparator); public static AllRoutes insert(AllRoutes, Comparator, Route); // Predicate public static boolean isEmpty(AllRoutes); // Accessors public static int numberOfLegs(AllRoutes); public static int length(AllRoutes); public static City origin(AllRoutes); public static City destination(AllRoutes); public static Route firstLeg(AllRoutes); public static Route lastLeg(AllRoutes); public static AllRoutes withoutFirst(AllRoutes); public static AllRoutes withoutLast(AllRoutes); // Canonical Methods public String toString(); // Required by the java.util.Iterator interface public java.util.Iterator iterator(); ***************************************************************** Specification of behavior: ***************************************************************** AllRoutes.isEmpty(AllRoutes.empty()) = true AllRoutes.isEmpty(AllRoutes.addLeg(t, leg)) = false AllRoutes.numberOfLegs(AllRoutes.empty()) = 0 AllRoutes.numberOfLegs(AllRoutes.addLeg(t, leg) = AllRoutes.numberOfLegs(t) + 1 AllRoutes.length(AllRoutes.empty()) = 0 AllRoutes.length(AllRoutes.addLeg(t, leg)) = AllRoutes.length(t) + leg.travelMiles() AllRoutes.origin(AllRoutes.addLeg(t, leg)) = leg.startsAt() if AllRoutes.isEmpty(t) = true = AllRoutes.origin(t) otherwise AllRoutes.desination(AllRoutes.addLeg(t, leg)) = leg.endsAt() AllRoutes.firstLeg(AllRoutes.addLeg(t, leg)) = leg if AllRoutes.isEmpty(t) = true = AllRoutes.firstLeg(t) otherwise AllRoutes.lastLeg(AllRoutes.addLeg(t, leg)) = leg AllRoutes.withoutFirst(AllRoutes.addLeg(t, leg)) = AllRoutes.empty() if AllRoutes.isEmpty(t) = true = AllRoutes.addLeg(AllRoutes.withoutFirst(t), leg) otherwise AllRoutes.withoutLast(AllRoutes.addLeg(t, leg)) = t AllRoutes.select(AllRoutes.empty(), comp, route) = AllRoutes.empty() AllRoutes.select(AllRoutes.addLeg(t, leg), comp, route) = AllRoutes.addLeg(AllRoutes.select(t, comp, route), leg) if comp.compare(leg, route) = 0 AllRoutes.select(AllRoutes.addLeg(t, leg), comp, route) = AllRoutes.select(t, comp, route) if comp.compare(leg, route) != 0 AllRoutes.sort(AllRoutes.empty(), comp) = AllRoutes.empty() AllRoutes.sort(AllRoutes.addLeg(t, leg), comp) = addLeg(t, leg) if AllRoutes.isEmpty(t) = true = AllRoutes.insert(AllRoutes.sort(t, comp), comp, leg) otherwise AllRoutes.insert(AllRoutes.empty(), comp, newleg) = AllRoutes.addLeg(AllRoutes.empty(), newleg) AllRoutes.insert(AllRoutes.addLeg(t, leg), comp, newleg) = AllRoutes.addLeg(AllRoutes.addLeg(t, leg), newleg) if comp.compare(leg, newleg) <= 0 AllRoutes.insert(AllRoutes.addLeg(t, leg), comp, newleg) = AllRoutes.addLeg(AllRoutes.insert(t, comp, newleg), leg) if comp.compare(leg, newleg) > 0 AllRoutes.empty().toString() = "This AllRoutes is empty" AllRoutes.addLeg(t, leg).toString() = leg.toString() if AllRoutes.isEmpty(t) = true AllRoutes.addLeg(t, leg).toString() = t.toString() + "\n" + leg.toString() if AllRoutes.isEmpty(t) = false ============================================================= Note: The compare method of the comparator argument to the select, insert, and sort methods must not have any side effects. Note: The iterator() method is not specified by the algebraic specification above, because it returns a mutable object that implements the java.util.Iterator interface. This Iterator shall generate the routes of the AllRoutes aggregate, in order from the first to the last, following the protocol specified for the Iterator interface in the API for Java 2 Platform Standard Edition 6. If this Iterator's remove operation is called, it shall throw an UnsupportedOperationException. If this Iterator's next() method is called when the hasNext() method would return false, the next() method shall throw a NoSuchElementException. Clients of the AllRoutes ADT are allowed to rely upon these exceptions. ============================================================= Part 2 of your assignment is to write the code for a single file, RouteTracer.java, that declares a public class named RouteTracer that implements the RouteTracer ADT specified below. RouteTracer is an immutable data type. The RouteTracer ADT shall be implemented in Java, and will be tested using Sun's Java 2 Runtime Environment, Standard Edition, version 6. The code for this implementation of the RouteTracer ADT shall be in the geography package, and shall define a public class named RouteTracer that defines the following public methods, which are specified below. Specification of the RouteTracer ADT. Signature: public static RouteTracer getInstance(); public void trace(AllRoutes a, Comparator c); Behavior Specifications: routeTracer.getInstance().trace(a, c) => behavior defined by side effect The behavior of the trace method is defined by its "side effect", which is to iterate through the routes of the first argument, in sorted order according the its second argument, printing a description of each Route r that conforms to the following schema: Route i: A route from s to e traveling m miles d In the description schema above: i is an integer from 1 to the length of a, such that the routes listed in the output are numbered. s stands for the name of the starting city e stands for the name of the ending city m stands for the number of miles traveled, and d stands for the direction of travel ============================================================= To get any credit for part 2, you must make use of the iterator from Part 1. To get full credit for part 2, you must implement the RouteTracer class using the "singleton" design pattern.