PA 9: MyStringBuilder

Due date: Thursday, March 12 @ 11:59PM

Introduction

This assignment will require you to build StringBuilder class and its corresponding methods from scratch. You will also be expected to test your code extensively by writing your own test cases.

Getting Started

There are a number of ways to get started on development. The following is the recommended way to ensure that your code will compile during grading.

If you are using your own machine or are on a lab computer to complete the assignment, go to step 2 directly. Otherwise, ssh into your cs8bwi20 account.
- ssh cs8bwi20__@ieng6.ucsd.edu
Acquire the starter files.
- From ieng6:
  - Log in to your cs8bwi20 account.
  - From the command line, use the command cp -r ~/../public/pa9 ~/ (this will copy the entire starter files directory to your home directory)
  - Type ls ~ to verify that you have copied the pa9 directory over.
- From GitHub:
  - git clone https://github.com/CaoAssignments/cse8b-wi20-pa9-MyStringBuilder-starter.git
  - Alternatively, you can download the repo as a zipped folder.
If you downloaded the repo as a zipped folder, navigate to it through your terminal or text editor (Atom, Eclipse, etc.). If you git cloned the repo, you can switch into that directory immediately.
- cd cse8b-wi20-pa9-MyStringBuilder-starter
- Optional: You may choose to rename this repo. You can do this by using this command:
  - mv cse8b-wi20-pa9-MyStringBuilder-starter pa9
You can now start working on it through vim using the following command or open the directory in your preferred editor.
- vim MyStringBuilder.java or gvim MyStringBuilder.java
To compile your code, use the javac command.
- Syntax: javac file1.java file2.java etc...
- Example: javac MyStringBuilder.java
To run your code, use the java command passing in the name of the class with the main method that you want to run.
- Syntax: java nameOfClass
- Example: java MyStringBuilder

MyStringBuilder (MSB)

Strings are implemented differently across different programming languages. In Java, Strings are actual Objects! Furthermore, we have multiple classes which implement sequences of characters in varying ways (char arrays, ArrayLists of Characters, Strings, StringBuilder). These all have similar capabilities with different implementations internally. Here, we now explore one internal implementation by writing a simple string data structure. While it is similar to the StringBuilder class, the internal workings of our StringBuilder will be one we have not seen before. We will call it MyStringBuilder to differentiate it from the default Java implementation.

The MyStringBuilder will be used to construct, store, and modify characters in a specific order. Before we talk about how our MyStringBuilder will be implemented, let’s pretend we were using a char array (we won’t use an actual char array in this assignment). In memory, elements of an array are stored next to each other like this:

Suppose we made a mistake with “CSE” and we meant to spell “CASE”. The char array would have {‘C’, ‘S’, ‘E’}. To fix our mistake, we would have to (1) create a new array, (2) move ‘S’ and ‘E’ back, and then (3) assign the letter ‘A’ to position 1.

Create a new array:
& 3. Copy items and add A:

This is inefficient and slow. If the array we are copying is very long, this could take a very long time! In MyStringBuilder, we will instead use references to link different letters together. CSE will be represented as C → S → E. Let’s think about how we could insert the letter ‘A’ into our MyStringBuilder now.

Nice! We didn’t have to remake our entire MyStringBuilder and copy all of its contents!

But, char is a primitive type and not an Object-subclassed type. Primitive types don’t have the ability to point to each other. To solve this issue, we will contain the char inside a class whose sole purpose is to hold chars and references to the next char in the sequence. We will call this class a node.

Note: The diagrams in this writeup are not accurate representations, they are just for you to get a better sense of what is happening - we encourage you to draw your own accurate diagrams/memory models to visualize the logic behind the algorithms. For the diagrams, let start be the reference to the first CharNode, end be the reference to the last CharNode, length is the length of String, next is the next reference in CharNode, data is the character in CharNode.

This MyStringBuilder has the word “agc”. Notice that the chars are not actually inside MyStringBuilder - MyStringBuilder has a reference i.e. start which points to the first node, which contains information of a char ‘a’. The first node has a reference next that points to another node, which contains information of another char ‘g’. Note that data and next are simply instance variables of type CharNode. We can use these to join all of the CharNodes together. Upon finishing the implementation of MyStringBuilder, the data structure should be able to store infinitely many characters (theoretically). Notice that MyStringBuilder has a reference end that points to the last node. You might need to iterate through your MyStringBuilder in order to add and delete characters. To “iterate” through a MyStringBuilder, you need a way to keep track of where your current position. This will be done using an additional CharNode reference (i.e. the currNode reference in the figure above). Notice the two references pointing to the first CharNode.

Policies

Use of libraries and other data structures of any kind in this part to store your MyStringBuilder content will result in a zero. For example, you can’t use a Java StringBuilder to make your MyStringBuilder. Don’t use character arrays, Strings, etc. You are allowed to use String's charAt(), substring(), and length() instance methods (you shouldn't need anything else anyway). If you're using CharNodes as specified in the writeup, you're fine. All code must be from scratch and the logic must use only references, object instantiation, and object initialization.

Exception Handling

In this PA, you will be required to handle different exceptions using try and catch blocks in your methods. An exception is characterized as anything that disrupts the normal flow of the method. Some examples of different exceptions include NullPointerException, ArithmeticException and IndexOutOfBoundsException. You should enclose the part of your code that might cause the error in your try block. In your catch block, make sure you are catching the appropriate exception. You should then throw this exception using the throw keyword. Let's take a method attempting to divide by 0 as an example. To handle the exception in the method, you would do the following:

public static void divideByZero() throws ArithmeticException {
  try {
   System.out.println (39/0);
  }
  catch (ArithmeticException e) {
   System.out.println ("Exception caught!");
   throw e;
  }
}

MyException.java and and Its Subclasses

In the starter code, you are provided with four files: MyException.java, MSBOutofBoundsException.java, BadInputException.java and Constants.java. Make sure you read through each of the files before starting the assignment.

MyException.java

This class extends Throwable, which is the superclass of all errors and exceptions. Any MyException object can be thrown using the throw keyword, similar to what was shown in the example above. The constructor takes in two String objects, the first specifying where the MyException object is getting thrown from (which method is causing the error), and the second specifying a message used to describe the error.

MSBOutOfBoundsException.java

This class extends MyException.java. It should be thrown when your MSB object faces an out of bounds error.

BadInputException.java

This class also extends MyException.java. It should be thrown when the input into the MSB object is of an unintended type (such as a null object).

The Constructors

You will notice that the constructors for these exceptions takes a from String and a message String. Use the constants provided in Constants.java for the from argument and use whatever will help you debug as the message argument.

The mapping between constants and method signatures is as follows:

Constant	Method Signature (described in further sections)
FROM_CONSTRUCTOR	MyStringBuilder(String str) [constructor]
FROM_DEEPCOPY_CONSTRUCTOR	MyStringBuilder(MyStringBuilder param) [constructor]
FROM_APPEND_STR	append(String)
FROM_INSERT_CHAR	insert(char, int)
FROM_INSERT_STR	insert(String, int)
FROM_FIND_INDEX	findIndex(int)
FROM_REMOVE	remove(int)
FROM_DELETE_STARTINDEX	delete(int)
FROM_DELETE_STARTINDEX_ENDINDEX	delete(int, int)
FROM_SUBSTRING_STARTINDEX	substring(int)
FROM_SUBSTRING_STARTINDEX_ENDINDEX	substring(int, int)
FROM_CONCAT	concat(MyStringBuilder)

Defining our two Classes

Part A: CharNode

public class CharNode This class/file should contain:

a private char type named data, and
a private CharNode reference named next.
one and only public constructor. This takes in one parameter: a char, initializing the instance char letter. It leaves the next reference as null.
Public getters and setters for two instance variables i.e. getData(), getNext(), setData(), setNext(). Please make sure that the getters and setters are named as above.
Both the instance variables are private, so we must use getters and setters to access them.

The method signatures for getters and setters are as follows:

public char getData()
This should return data.
public CharNode getNext()
This should return next.

Setters are usually void return types but here the setters are returning the objects for the purpose of testing.

public CharNode setData(char newData)
This should update the data to newData and return the CharNode object.
public CharNode setNext(CharNode newNext)
This should update the next to newNext and return the CharNode object.

MyStringBuilder

public class MyStringBuilder

Our custom MyStringBuilder class will have

three protected instance variables:
- a reference to our first node (a CharNode).
- a reference to our last node (a CharNode).
- the length (number of CharNodes) in the current MyStringBuilder
Three constructors
- the first constructor takes a char input and should create a MyStringBuilder with the single CharNode representing the input.
- the second constructor creates a MyStringBuilder from a String. If the String is null, you should throw a BadInputException. If the String is empty, then the constructed MyStringBuilder object should also be empty (have no CharNodes). Hint: You should use the append() method of Part C for this.
- the third constructor constructs a MyStringBuilder using a MyStringBuilder object by deep copying its contents. If the MyStringBuilder object is null, you should throw a BadInputException. Since CharNodes store their proceeding nodes inside themselves, you should start from the reference to the first charNode and deep copy all charNodes until we get to the end and construct MyStringBuilder object.
  
  For example, consider the following MyStringBuilder in the diagram: start points to the charNode with 'r' and end points to the charNode with 't'. You should traverse from start charNode till the end charNode and deep copy each charNode i.e. deep copying data and next.

Methods in MyStringBuilder

These are the following methods that you have to implement in MyStringBuilder.java.

Part B: Output the Length

length()

public int length()

It is useful to know the data structure’s size. One implementation of this would just have us traverse through each node, counting them. However, this is pretty inefficient to do this every time we want to know the length. Therefore, we have the length instance variable that will keep track of all changes to the length from other methods. You can therefore directly return the value from that instance variable for this method.

Note: Your other methods must appropriately update the length variable each time.

Part C: Append

Time to start adding functionality to our MyStringBuilder!

append()

public MyStringBuilder append(char c)

This is a helper method used to append a single char to the end of MyStringBuilder. It should be used by the method below, to append an entire string to MyStringBuilder.

If MyStringBuilder is empty, then start and end must point to a new CharNode containing this char.
Otherwise, use the MyStringBuilder object's end. Recall that the last node’s next reference is always null. You will make the previously last node point at a newly created CharNode containing c. Remember to update the instance variables. If you skipped the second MyStringBuilder constructor, you should revisit it now. A fresh MyStringBuilder object msb, in a diagram:

if we call msb.append('a'), then:

Afterwards if we call msb.append(‘b’), then:

public MyStringBuilder append (String str) throws BadInputException

This method should append an entire string to the end of your current MyStringBuilder object. It should then return your new MyStringBuilder object.

If the string is empty, nothing should be added to MyStringBuilder. This method requires exception handling. Look at the method header, which throws a BadInputException. What kind of input would you need to handle using this exception (what kind of input is the behavior of this method not defined for)?

Part D: Output as a String

toString()

public String toString()

Since the MSB class is a way to manipulate and store Strings, we should have a toString() method which returns an actual String object of our stored String. This function accomplishes that goal. Yet, what we currently have is not a char array or a String, but a sequence of nodes of chars. This function takes this sequence of CharNodes and turns the sequence of chars into a String.

Part E: Insert

insert()

public MyStringBuilder insert (char c, int index) throws MSBOutOfBoundsException

This is a helper method that will be used to insert an entire String at a specified index. The method should work as follows:

The index is the position in our sequence of nodes where we want to insert a char. Once finished, c will have position index. The previous node at position index will be at position index + 1. In fact, all nodes whose positions were index or higher will have their positions incremented. Remember to update the instance variables.

For example, you have a string “rest” and call insert('e', 3) on this string. Before insert() was called, the letter ‘t’ was at position 3. Now, ‘e’ is at position 3 while ‘t’ is at position 4, resulting in the string “reset”. Note that the node containing ‘s’ must point to a different node now.

Before insert():

After insert():

Exception Handling:

index must be non-negative (0 is not negative) and less than or equal to the length of the sequence. Make sure you handle any invalid input accordingly (by throwing the appropriate exception). (Notice that it is fine if index is equal to the length of the sequence. What does this mean?)

public MyStringBuilder insert (String str, int index) throws BadInputException, MSBOutOfBoundsException

This method should be similar to your append() method. index should represent the position in MyStringBuilder where the first character of the str should start. You will need to handle invalid input for both the index and str parameter. If str is null, throw BadInputException and if index is out of bounds, throw MSBOutOfBoundsException.

Hint: You might find using your other insert() method (the one that takes a char) as a useful subroutine.

Part F: Find Character at Index

protected CharNode findIndex(int index) throws MSBOutOfBoundsException

This method should find the character at a given index. You have to iterate through the CharNodes in MyStringBuilder until index is reached.

index should be non-negative, and index should be in the MyStringBuilder (i.e. length should be greater than index). Be sure to handle any exceptions accordingly.
- NOTE - If MyStringBuilder is empty, then any value of index would be out of bounds.

Part G: Remove a Char

remove()

public MyStringBuilder remove (int index) throws MSBOutOfBoundsException

This method should remove the CharNode at a given index. Like in insert(), index represents the position of the node which we want to remove. After this node is removed, the previous node at position index + 1 should be at position index. Remember to update the instance variables.

index should be non-negative and within the length of MyStringBuilder. Make sure you handle any exceptions appropriately.

Part H: Delete a Range of Chars

delete()

public MyStringBuilder delete (int startIndex) throws MSBOutOfBoundsException

This is a method used to delete a range of characters. startIndex specifies an index in MyStringBuilder. All nodes starting from and including startIndex should be removed from MyStringBuilder. Remember to update the instance variables. After delete, the node at startIndex - 1 should now point to null as its next node.

The parameter startIndex must be nonnegative, and within the bounds of MyStringBuilder. Make sure you handle any exceptions and update instance variables appropriately.

Examples

Consider the string “abc”.

delete(1) will delete "bc".
delete(2) will delete ‘c’.
delete(0) will delete the whole sequence.

public MyStringBuilder delete (int startIndex, int endIndex) throws BadInputException, MSBOutOfBoundsException

This method deletes a subsequence of characters from MyStringBuilder. (Deleting the entire sequence is also considered deleting a subsequence). The nodes for deletion starts at position startIndex and deletes up to, but not including, the node at position endIndex.

If startIndex == endIndex, then nothing is deleted.
startIndex must be within the bounds of MyStringBuilder and non-negative, endIndex must be less than or equal to the length of MyStringBuilder. If these are not true, throw an MSBOutOfBoundsException. Notice that endIndex is allowed to be equal to the length of this MyStringBuilder.
If endIndex is less than startIndex throw a BadInputException.

Examples

Consider the string “abc”.

delete(1,1) does nothing.
delete(1, 2) will delete ‘b’ and cause the node containing ‘a’ to point at the node containing ‘c’.
delete(0, length()) will delete the whole sequence. When in doubt, draw it out!

Part I: Get substring

substring()

public String substring(int startIndex) throws MSBOutOfBoundsException This is a method used to get substring starting from startIndex. startIndex specifies an index in MyStringBuilder. All characters of nodes starting from and including startIndex should be concatenated and returned as string.

The parameter startIndex must be nonnegative, and within the bounds of MyStringBuilder. Make sure you handle any exceptions appropriately.

Examples

Consider the string “abc”.

substring(1) will return "bc".
substring(2) will return "c".
substring(0) will return "abc".

public String substring(int startIndex, int endIndex) throws MSBOutOfBoundsException, BadInputException

This method concatenates characters from startIndex to endIndex and returns the substring. All nodes starting from and including startIndex till endIndex, but not including the node at position endIndex are considered.

If startIndex == endIndex, then empty string is returned.
startIndex must be within the bounds of MyStringBuilder and non-negative, endIndex must be less than or equal to the length of MyStringBuilder. If these are not true, throw an MSBOutOfBoundsException. Notice that endIndex is allowed to be equal to the length of this MyStringBuilder.
If endIndex is less than startIndex throw a BadInputException.

Examples

Consider the string “abc”.

substring(1,1) will return an empty string.
substring(1, 2) will return "b".
substring(0, length()) will return "abc"

Part J: Concat two MSB Objects

concat()

public MyStringBuilder concat(MyStringBuilder rightOperand) throws BadInputException

This method concatenates two MSB objects together. rightOperand represents the MSB Object that should be the second part of the current MSB object. Remember to update the instance variables.

If your current MSB object's length is 0, then your current MSB object will start with the same start node as rightOperand. Therefore, it will have the same start, end and length variables as rightOperand.
If rightOperand is not a valid input, you need to throw a BadInputException.

We now have a working MyStringBuilder! This allows us to manipulate sequences of characters as we please. Make sure to test out your implementation, and then pat yourself on the back.

Student Satisfaction Survey

Please fill out our student satisfaction survey. We are changing how we approach giving assignments and would like to hear about your experiences. After filling out the survey, please write the following sentence at the top of your README.md file: I have completed the student satisfaction survey.

Style

Make sure you follow the below guidelines for styling since we will be grading you on it.

We will grade your code style thoroughly. Namely, there are a few things you must have in each file / class / method:

File header
Class header
Method header(s)
Inline comments
Proper indentation
Descriptive variable names
No magic numbers
Reasonably short methods (if you have implemented each method according to specification in this write-up, you’re fine). This is not enforced as strictly.
Lines shorter than 80 characters (keep in mind each tab is equivalent to 8 spaces).
Javadoc conventions (@param, @return tags, /** comments */, etc.)

A full style guideline can be found here. If you need any clarifications, feel free to ask on Piazza.

Submission

Submit the following files to Gradescope by Mar 12, Thursday, 11:59pm:

CharNode.java
MyStringBuilder.java

Well done! With that, we have wrapped up the last assignment in Intro to Computer Science: Java II. Congratulations for completing the course assignments and good luck in your future ventures!