Abstract Data Types (ADT) An Abstract Data Type is a wrapper which provides external functionality by defining an interface. The implementation behind the interface is often left to the code to implement as they see fit. One of the most common ADTs is the String library. It was developed across multiple languages to support common String manipulations. Before the String ADT came into existence most programmers who required any sort of String like functionality used character arrays to simulate a String, writing their own manipulation routine. For this assignment we will time warp back to the pre-String era and create our own. Below is an interface for a String library. package String_T; public interface Stringt ! //Concatenates 2 strings, public Stringt Concat(Stringt s); //Returns a string from index 0 to but not including i. public Stringt Before(int i); //Returns a string from i to end. public Stringt After(int i); // Returns the length of this. public int Length(); //Creates a deep clone of this. public Stringt clone(); // Returns the character at index i of this; public char CharAt(int i); this.concat(S) //Returns a character array representation of this. public char[] TOArray(); //Complete the below 2 functions, which are to //implement some non-trivial behaviour //of stringt, e.g. trim, toupper, tolower, reverse, indexof etc. //It is left to you. //public Stringt SomeKool Functioni (???); //public someType SomeKool Function2 (???); } The interface assumes that no String library exists but only character arrays. We will call the data type StringT to avoid conflict with the actual String data type. An implementation of the interface should be called MyStringT, which provides an implementation of the given interface, and is immutable. You will notice that the last 2 functions are not defined. You can choose any 2 behaviours of a standard String operation to implement. The first must return a StringT and the 2nd some other type. Here is the String JavaDoc, https://docs.oracle.com/javase/7/docs/api/java/lang/String.html for some ideas. Thus, to create a String the constructor must support a character array as a parameter to the implementation constructor. This constructor will convert the character array to an internal representation. The Default constructor will create an empty data structure, and thus represent an empty String. The internal representation is left to you, your options are linked list or arrays, or a combination The library can return a character array with the function ToArray as defined above. All exceptions which constitute incorrect usage of the methods of Stringt, should be trapped, and returned to the caller as StringTexception. For example, CharAt(-1) would reference a non existent character in this, and thus should throw an exception. Create a test harness to completely test your implementation. Be sure that your test harness completely tests all aspects of your implementation and proves to the marker that you have done so. Place your test harness in a package called, Test. One aspect of the test harness, it to print without using String. You will notice that printing to system.out supports printing a character array. If you are using AsciiDisplayer you may use the following construct out.writeString(new String your character array))