CS U370 Assignment #4 Assigned: Friday, Feb. 15, 2008 Due: Tuesday, February 26, 2008 The purpose of this assignment is: * To translate an algebraic specification of an immutable abstract data type into executable Java code * To use generic types and the java.util.Comparator interface * To see how simple selection and sorting algorithms can be specified algebraically * To introduce a non-trivial example that illustrates and motivates future topics Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. Turn in your solution using the Web interface provided for this class. by 10 p.m. on the due date. Your solutions should consist of a file that contains nothing but your AllRoutes.java file. That file 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 depend on the readability of your code (comments and indentation), and part will depend on your following the procedure above for submitting your work. Late assignments may be discounted, and very late assignments may be discarded. -------------------------------------------------- Your assignment is to write the code for a single file, AllRoutes.java, that declares a public class named AllRoutes that implements the AllRoutes ADT specified below. Note that AllRoutes.java must be part of the geography package. ***** For full credit on this assignment your implementation must: 1. Respect the abstraction barrier of other classes with which it interacts 2. Discourage clients from violating the abstraction barrier of the AllRoutes class 3. Follow the design recipe we learned in order to create a "cookbook" implementation of the AllRoutes class. Specification of the AllRoutes ADT. AllRoutes is an immutable abstract data type. In our implementation language, Java, it corresponds to the geography.AllRoutes class, which is specified below. The AllRoutes class 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 will be in the geography package, and shall define a public class named AllRoutes, which provides the following public methods, which are specified below. ***************************************************************** 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(); ***************************************************************** 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 and sort methods must not have any side effects. --------------------------------------------------