In this project, you will implement your own class, called MyStringBuilder, which is similar in functionality to the standard StringBuilder, but is implemented using a linked list of characters rather than an array. You will then test the performance of your class against the Java predefined StringBuilder and String classes in a simple simulation.

// CS 0445 Spring 2019 // Read this class and its comments very carefully to make sure you implement // the class properly. Note the items that are required and that cannot be // altered! Generally speaking you will implement your MyStringBuilder using // a singly linked list of nodes. See more comments below on the specific // requirements for the class.

// For more details on the general functionality of most of these methods, // see the specifications of the similar method in the StringBuilder class. public class MyStringBuilder { // These are the only three instance variables you are allowed to have. // See details of CNode class below. In other words, you MAY NOT add // any additional instance variables to this class. However, you may // use any method variables that you need within individual methods. // But remember that you may NOT use any variables of any other // linked list class or of the predefined StringBuilder or // or StringBuffer class in any place in your code. You may only use the // String class where it is an argument or return type in a method. private CNode firstC; // reference to front of list. This reference is necessary // to keep track of the list private CNode lastC; // reference to last node of list. This reference is // necessary to improve the efficiency of the append() // method private int length; // number of characters in the list

// You may also add any additional private methods that you need to // help with your implementation of the public methods.

// Create a new MyStringBuilder initialized with the chars in String s public MyStringBuilder(String s) { if (s == null || s.length() == 0) // Special case for empty String { // or null reference firstC = null; lastC = null; length = 0; } else { // Create front node to get started firstC = new CNode(s.charAt(0)); length = 1; CNode currNode = firstC; // Create remaining nodes, copying from String. Note // how each new node is simply added to the end of the // previous one. Trace this to see what is going on. for (int i = 1; i < s.length(); i++) { CNode newNode = new CNode(s.charAt(i)); currNode.next = newNode; currNode = newNode; length++; } lastC = currNode; } }

// Create a new MyStringBuilder initialized with the chars in array s public MyStringBuilder(char [] s) { }

// Create a new empty MyStringBuilder public MyStringBuilder() { }

// Append MyStringBuilder b to the end of the current MyStringBuilder, and // return the current MyStringBuilder. Be careful for special cases! public MyStringBuilder append(MyStringBuilder b) { }

// Append String s to the end of the current MyStringBuilder, and return // the current MyStringBuilder. Be careful for special cases! public MyStringBuilder append(String s) { }

// Append char array c to the end of the current MyStringBuilder, and // return the current MyStringBuilder. Be careful for special cases! public MyStringBuilder append(char [] c) { }

// Append char c to the end of the current MyStringBuilder, and // return the current MyStringBuilder. Be careful for special cases! public MyStringBuilder append(char c) { }

// Return the character at location "index" in the current MyStringBuilder. // If index is invalid, throw an IndexOutOfBoundsException. public char charAt(int index) { }

// Delete the characters from index "start" to index "end" - 1 in the // current MyStringBuilder, and return the current MyStringBuilder. // If "start" is invalid or "end" <= "start" do nothing (just return the // MyStringBuilder as is). If "end" is past the end of the MyStringBuilder, // only remove up until the end of the MyStringBuilder. Be careful for // special cases! public MyStringBuilder delete(int start, int end) { }

// Delete the character at location "index" from the current // MyStringBuilder and return the current MyStringBuilder. If "index" is // invalid, do nothing (just return the MyStringBuilder as is). // Be careful for special cases! public MyStringBuilder deleteCharAt(int index) { }

// Find and return the index within the current MyStringBuilder where // String str first matches a sequence of characters within the current // MyStringBuilder. If str does not match any sequence of characters // within the current MyStringBuilder, return -1. Think carefully about // what you need to do for this method before implementing it. public int indexOf(String str) { }

// Insert String str into the current MyStringBuilder starting at index // "offset" and return the current MyStringBuilder. if "offset" == // length, this is the same as append. If "offset" is invalid // do nothing. public MyStringBuilder insert(int offset, String str) { }

// Insert character c into the current MyStringBuilder at index // "offset" and return the current MyStringBuilder. If "offset" == // length, this is the same as append. If "offset" is invalid, // do nothing. public MyStringBuilder insert(int offset, char c) { }

// Insert char array c into the current MyStringBuilder starting at index // index "offset" and return the current MyStringBuilder. If "offset" is // invalid, do nothing. public MyStringBuilder insert(int offset, char [] c) { }

// Return the length of the current MyStringBuilder public int length() { }

// Delete the substring from "start" to "end" - 1 in the current // MyStringBuilder, then insert String "str" into the current // MyStringBuilder starting at index "start", then return the current // MyStringBuilder. If "start" is invalid or "end" <= "start", do nothing. // If "end" is past the end of the MyStringBuilder, only delete until the // end of the MyStringBuilder, then insert. This method should be done // as efficiently as possible. In particular, you may NOT simply call // the delete() method followed by the insert() method, since that will // require an extra traversal of the linked list. public MyStringBuilder replace(int start, int end, String str) { }

// Reverse the characters in the current MyStringBuilder and then // return the current MyStringBuilder. public MyStringBuilder reverse() { } // Return as a String the substring of characters from index "start" to // index "end" - 1 within the current MyStringBuilder public String substring(int start, int end) { }

// Return the entire contents of the current MyStringBuilder as a String public String toString() { }

// You must use this inner class exactly as specified below. Note that // since it is an inner class, the MyStringBuilder class MAY access the // data and next fields directly. private class CNode { private char data; private CNode next;

public CNode(char c) { data = c; next = null; }

public CNode(char c, CNode n) { data = c; next = n; } } }