CS 5500 Assignment #3. Assigned: Wednesday, 10 September 2014 Due: Monday, 22 September 2014 Revised: Friday, 12 September (changes marked by ! in column 79) Friday, 12 September (changes marked by ! in column 79) Sunday, 14 September (changes marked by ! in column 79) This is an individual assignment. Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. For this assignment, you will write Java code that implements the ADT specified below. You must write all of your program's source code by yourself. You are not allowed to use source code written by other students, you are not allowed to use source code obtained from the World-Wide Web or other sources, and you are not allowed to use software packages unless they are already installed on the standard CCIS Linux machines. The instructors have given you a SearchableString.java file that defines a Java interface for the SearchableString ADT. Your implementation must be written in Java. All of its source code (except for the SearchableString interface itself, which is within the file provided by your instructors) must be contained within a single file named SearchableStrings.java Your SearchableStrings.java file must begin with a block comment that 1. gives your name (as you want the instructor to spell it) 2. gives your preferred email address(es) for contacting you ! Your implementation will reside within the default package, so the SearchableStrings.java file must not contain a package statement. That source file may contain import statements that import from the standard libraries for Java version "1.6.0_32" as installed on CCIS Linux machines. The first class defined within your SearchableStrings.java file must be a public class named SearchableStrings. That class must define a public static method named make that takes a single argument of type String and returns a SearchableString. That SearchableString must behave as specified below. Your implementation will be compiled by copying it into a fresh directory, copying the SearchableString.java file into that directory, and copying a TestProgram.java file written by the instructors into that directory, followed by execution of javac TestProgram.java within that directory. Your implementation will then be tested by executing java TestProgram within that directory. Your test program will be graded on these criteria: 1. your block comment at the beginning of the file 2. your implementation's ability to compile without errors when combined with SearchableString.java and correct black-box test programs 3. your implementation's correctness with respect to the specification below 4. the readability of your source code ---------------------------------------------------------------- Specification of the SearchableString ADT. SearchableString is an immutable abstract data type whose values represent strings that support approximate string search. The dynamic methods of the SearchableString ADT are listed within the Java interface defined by the SearchableString.java file supplied by the instructors. The SearchableString ADT 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 implementations of this ADT shall be in the default package, and shall define a public class named SearchableStrings. The operations of the SearchableString ADT shall be provided by the following public methods: Signature: Static methods: SearchableStrings.make : String -> SearchableString Dynamic methods (for which the receiver is a SearchableString): distance : SearchableString × int -> int bestMatch : SearchableString -> int toString : -> String equals : Object -> boolean hashCode : -> int Restrictions: Null arguments may not be passed to any of the above methods except for equals(Object). Algebraic specification: SearchableStrings.make(s).toString() = s ! SearchableStrings.make(s1).equals(null) = false SearchableStrings.make(s1).equals(SearchableStrings.make(s2)) = s1.equals(s2) SearchableStrings.make(s).hashCode() = s.hashCode() ! Axiomatic specification: If x is not a SearchableString then SearchableStrings.make(s1).equals(x) = false If i < 0 then SearchableStrings.make(s1).distance(SearchableStrings.make(s2), i) = s1.length() + s2.length() + 1 If 0 ≤ i ≤ s1.length() - s2.length() then SearchableStrings.make(s1).distance(SearchableStrings.make(s2), i) = f(s1.substring(i, i+s2.length()), s2) + s1.length() - s2.length() where f is the function defined below. If 0 ≤ i and i > s1.length() - s2.length() then SearchableStrings.make(s1).distance(SearchableStrings.make(s2), i) = s1.length() + s2.length() + 1 If s1.length() < s2.length() then SearchableStrings.make(s1).bestMatch(SearchableStrings.make(s2)) = s1.length() + s2.length() + 1 If s1.length() ≥ s2.length() then SearchableStrings.make(s1).bestMatch(SearchableStrings.make(s2)) is the least non-negative integer j such that for all k > j SearchableStrings.make(s1).distance(SearchableStrings.make(s2), j) ! ≤ SearchableStrings.make(s1).distacne(SearchableStrings.make(s2), k) ! Definition of the auxiliary function f: If 0 = s1.length() = s2.length() then f(s1,s2) = 0 If 0 < n = s1.length() = s2.length() and s1.charAt(0) == s2.charAt(0) then f(s1, s2) = f(s1.substring(1, n), s2.substring(1, n)) If 0 < n = s1.length() = s2.length() and s1.charAt(0) != s2.charAt(0) then f(s1, s2) = 1 + f(s1.substring(1, n), s2.substring(1, n)) -------------------------------------------------- Examples. Suppose x1 = SearchableStrings.make("telegraph") x2 = SearchableStrings.make("telegram") x3 = SearchableStrings.make("elegant") x4 = SearchableStrings.make("graph") Then x1.distance(x1, -1) = 19 x1.distance(x1, 0) = 0 x1.distance(x1, 1) = 19 x1.distance(x2, 0) = 2 x1.distance(x2, 1) = 9 x1.distance(x3, 0) = 9 x1.distance(x3, 1) = 5 x1.distance(x4, 0) = 9 x1.distance(x4, 4) = 4 x1.bestMatch(x1) = 0 x1.bestMatch(x2) = 0 x1.bestMatch(x3) = 1 x1.bestMatch(x4) = 4 --------------------------------------------------