Project 2 ADT Character String Implement the ADT character string type, LinkedString, as another implementation of class String in Java. A doubly linked list must be used to store a list of characters (there is ONLY one external reference, head, to the linked list). This class must be implemented as an immutable class as class String. In Java, String is an immutable object (its internal states, such as data structures, cannot be changed once it's created). Immutable means that once the constructor for an object has completed execution that instance can't be altered. This is uscful as it mcans you can pass references to the object around, without worrying that somcone else is going to change its contents. Any method that is invoked which seems to modify the value, will actually create another String. Your LinkedString class must be immutable as well. For example, three String objects, a, b, and ab, are involved in the following code segment. String anew String ("AA") String bnew String("BB"); String ab-a.concat (b) After String a new String ("AA") ; 1s executed, a new String object a is created After string b- new String ("BB") ; 1s executed, another new String object b 1s created After String aba.concat (b) i is executed, another new String object ab is created. String a(this string) and String b( a string passed into method concat) are not changed due to String immutability. Method concat simply copies the contents of both a and b, and use them to make a new string object The LinkedString class uses a different data structure, a doubly linked list. This data structure is LinkedString 's internal state. An immutable LinkedString object means its linked list can't be altered once the object is created. All characteristics and behaviors of LinkedString objects must be the same as String objects. When a LinkedString object calls a method, this LinkedString object and LinkedString object(s) passed into this method must be unchanged during invocation of this method. If the method returns a LinkedString object, a new LinkedString object must be made without changing this LinkedString object and other LinkedString existing objects. The following shows how object immutability can be enforced when implementing method concat. For example, three LinkedString objects, a, b, and ab, are involved in the following code segment. Linkedstring anew LinkedString "AA") LinkedString b = new LinkedString ("BB" ); LinkedString aba.concat (b) After LinkedString a - new LinkedString("AA");is executed, a new LinkedString object as created with all characters stored in a linked list. null null head After Linkedstring b new Linkedstring ("BB") ; 1s executed, another new LinkedString object bis created with all characters stored in a linked list null null head After LinkedString ab- aconcat (b) ;is executed, another new LinkedString object ab 1s created with all characters stored in a linked list. ull null head ab Method concat must be implemented in a way in which a new linked string is made without modifying this linked string a and the other linked string b to enforce object immutability. In order to do this, method concat can simply copy characters in order like this. null null nu11 null head head copy copy copy copy null null head ab Modifying like this would violates object immutability null null null null head head ab Carefully implement each method, and make sure object immutability is maintained. Otherwise, the project will turned with no credits ADT Character String Specification: Specify operations to (DON'T change the names of the operations.) Three overloading constructors: create an empty LinkedString instance. A new character linked list is allocated so that it represents the sequence of 0 characters currently contained in the character list argument. (LinkedString) create a LinkedString instance containing a sequence of characters. A new character linked list is allocated so that it represents the sequence of characters currently contained in the character list argument. (LinkedString(charlI) create a LinkedString instance containing same sequence of characters as a String instance A new character linked list is initialized so that it represents the same sequence of characters as the String argument (LinkedString(String) Other methods (MUST be implemented to enforce object immutability): return the char value at the specified index. The first character in this linked character string is in position zero (char charAt(int)). Note: This linked string must be kept immutable. concatenate the specified linked character string to the end of this linked character string (LinkedString concat(LinkedString)). Note: This linked string and the specified linked string must be kept immutable returns true if, and only if, length0 is 0. (boolean isEmpty) Note: This linked string must be kept immutable return the length of this linked character string (int length() Note: This linked string must be kept immutable. return a new linked character string that is a substring of this linked character string (LinkedString substring(int int)). Note: This linked string must be kept immutable. ADT Character String Design: Complete a UML diagram to include all classes that are needed to meet the specifications. An interface class is usually defined to include all operations. A class implementing this interface provides implementation details Exceptions should to be considered when opcrations are designed. ADT Character String Reference-based Implementation: Implement all classes included the design. Javadoc comments should be included during this activity. Data structure doubly linked list must be used to store a sequence of characters in LinkedString objects. All characters should be linked cach other. Implement LinkedString so that it is consistent with the String class. A LinkedString object must be an immutable object. Class comments must be included right above the corresponding class header. Method comments must be included right above the corresponding method header. All comments must be written in Javadoc format. There will be no credits if comments are not complete, and/or not written in Javadoc format ADT Character String Test/Debug: Note: It is required to store all testing data in a file. No credit will be given if not It is required to use decomposition design technique for testing programs. No credit will be given if not To test LinkedString design, all operations in the design must be tested. This can be done as follows: Create an array list of LinkesString objects using testing data stored in a text file, and check emptiness of all linked strings. Display all linked strings and their lengths in the array list. Retrieve the last character or mid character of each LinkedString object from the array list, and display them. Display all linked strings in the array list again to make sure that all objects are not changed. Concatenate a linked string with next linked string, and display the concatenated string, repeat f list. Display inked strings in the array list again to make sure that all objects are not changed Get sub strings and display both substrings and original strings. Test other methods for the entire array It is not efficient to let main to do al. Method main should be very small and should be the only method in the class. It should invoke a method (start) that is decomposed into more methods (createList, displayList,.. in a separate class. Every method should be designed as a single-minded method. For example, Class LinkedStringTest contains method main; class LinkedStringUtility is a helper class. Both classes are used for testing. public class LinkedStringTest public static void main(String[) args) [ LinkedStringUtility. start Note: This class shows only two methods. You must design/implement the rest of the class public class LinkedStringUtility l *Creates a list of Linkedstring objects and operates on them public static void start) ArrayList stringList new ArrayList * Create an array list of LinkesString objects using testing data * st ored in a text file .. createList(.. *Display all linked strings in the array list. .. displayList //The rest of the testing methods must be completed by yourself Project 2 ADT Character String Implement the ADT character string type, LinkedString, as another implementation of class String in Java. A doubly linked list must be used to store a list of characters (there is ONLY one external reference, head, to the linked list). This class must be implemented as an immutable class as class String. In Java, String is an immutable object (its internal states, such as data structures, cannot be changed once it's created). Immutable means that once the constructor for an object has completed execution that instance can't be altered. This is uscful as it mcans you can pass references to the object around, without worrying that somcone else is going to change its contents. Any method that is invoked which seems to modify the value, will actually create another String. Your LinkedString class must be immutable as well. For example, three String objects, a, b, and ab, are involved in the following code segment. String anew String ("AA") String bnew String("BB"); String ab-a.concat (b) After String a new String ("AA") ; 1s executed, a new String object a is created After string b- new String ("BB") ; 1s executed, another new String object b 1s created After String aba.concat (b) i is executed, another new String object ab is created. String a(this string) and String b( a string passed into method concat) are not changed due to String immutability. Method concat simply copies the contents of both a and b, and use them to make a new string object The LinkedString class uses a different data structure, a doubly linked list. This data structure is LinkedString 's internal state. An immutable LinkedString object means its linked list can't be altered once the object is created. All characteristics and behaviors of LinkedString objects must be the same as String objects. When a LinkedString object calls a method, this LinkedString object and LinkedString object(s) passed into this method must be unchanged during invocation of this method. If the method returns a LinkedString object, a new LinkedString object must be made without changing this LinkedString object and other LinkedString existing objects. The following shows how object immutability can be enforced when implementing method concat. For example, three LinkedString objects, a, b, and ab, are involved in the following code segment. Linkedstring anew LinkedString "AA") LinkedString b = new LinkedString ("BB" ); LinkedString aba.concat (b) After LinkedString a - new LinkedString("AA");is executed, a new LinkedString object as created with all characters stored in a linked list. null null head After Linkedstring b new Linkedstring ("BB") ; 1s executed, another new LinkedString object bis created with all characters stored in a linked list null null head After LinkedString ab- aconcat (b) ;is executed, another new LinkedString object ab 1s created with all characters stored in a linked list. ull null head ab Method concat must be implemented in a way in which a new linked string is made without modifying this linked string a and the other linked string b to enforce object immutability. In order to do this, method concat can simply copy characters in order like this. null null nu11 null head head copy copy copy copy null null head ab Modifying like this would violates object immutability null null null null head head ab Carefully implement each method, and make sure object immutability is maintained. Otherwise, the project will turned with no credits ADT Character String Specification: Specify operations to (DON'T change the names of the operations.) Three overloading constructors: create an empty LinkedString instance. A new character linked list is allocated so that it represents the sequence of 0 characters currently contained in the character list argument. (LinkedString) create a LinkedString instance containing a sequence of characters. A new character linked list is allocated so that it represents the sequence of characters currently contained in the character list argument. (LinkedString(charlI) create a LinkedString instance containing same sequence of characters as a String instance A new character linked list is initialized so that it represents the same sequence of characters as the String argument (LinkedString(String) Other methods (MUST be implemented to enforce object immutability): return the char value at the specified index. The first character in this linked character string is in position zero (char charAt(int)). Note: This linked string must be kept immutable. concatenate the specified linked character string to the end of this linked character string (LinkedString concat(LinkedString)). Note: This linked string and the specified linked string must be kept immutable returns true if, and only if, length0 is 0. (boolean isEmpty) Note: This linked string must be kept immutable return the length of this linked character string (int length() Note: This linked string must be kept immutable. return a new linked character string that is a substring of this linked character string (LinkedString substring(int int)). Note: This linked string must be kept immutable. ADT Character String Design: Complete a UML diagram to include all classes that are needed to meet the specifications. An interface class is usually defined to include all operations. A class implementing this interface provides implementation details Exceptions should to be considered when opcrations are designed. ADT Character String Reference-based Implementation: Implement all classes included the design. Javadoc comments should be included during this activity. Data structure doubly linked list must be used to store a sequence of characters in LinkedString objects. All characters should be linked cach other. Implement LinkedString so that it is consistent with the String class. A LinkedString object must be an immutable object. Class comments must be included right above the corresponding class header. Method comments must be included right above the corresponding method header. All comments must be written in Javadoc format. There will be no credits if comments are not complete, and/or not written in Javadoc format ADT Character String Test/Debug: Note: It is required to store all testing data in a file. No credit will be given if not It is required to use decomposition design technique for testing programs. No credit will be given if not To test LinkedString design, all operations in the design must be tested. This can be done as follows: Create an array list of LinkesString objects using testing data stored in a text file, and check emptiness of all linked strings. Display all linked strings and their lengths in the array list. Retrieve the last character or mid character of each LinkedString object from the array list, and display them. Display all linked strings in the array list again to make sure that all objects are not changed. Concatenate a linked string with next linked string, and display the concatenated string, repeat f list. Display inked strings in the array list again to make sure that all objects are not changed Get sub strings and display both substrings and original strings. Test other methods for the entire array It is not efficient to let main to do al. Method main should be very small and should be the only method in the class. It should invoke a method (start) that is decomposed into more methods (createList, displayList,.. in a separate class. Every method should be designed as a single-minded method. For example, Class LinkedStringTest contains method main; class LinkedStringUtility is a helper class. Both classes are used for testing. public class LinkedStringTest public static void main(String[) args) [ LinkedStringUtility. start Note: This class shows only two methods. You must design/implement the rest of the class public class LinkedStringUtility l *Creates a list of Linkedstring objects and operates on them public static void start) ArrayList stringList new ArrayList * Create an array list of LinkesString objects using testing data * st ored in a text file .. createList(.. *Display all linked strings in the array list. .. displayList //The rest of the testing methods must be completed by yourself