Overview

You will implement a very primitive text editor which allows inserting and deleting characters one at a time, as well as an undo/redo process.

This will involve the following steps:

• Implement the Text.java interface (part 1). This will make the basic text editor work with the starter code in Editor.java.
• Implement the BoundedStack.java interface (part 2). If you used a linked list for part 1, you have to use arrays here, or if you used arrays for part 1, you have to use a linked list here.
• Use your BoundedStack implementation to get undo/redo working in Editor.java (part 3)

Grading and collaboration

The three parts are worth up to 40, 40, and 20 points, respectively.

For consideration of full credit, besides getting the code working perfectly, you must also:

• Include a completed README.txt file in your submission
• Implement the two interfaces using linked lists and arrays (you must do one of each, but it’s your choice which interface to implement with which data structure).
• Not use anything from java.util except possibly for java.util.Iterator and java.util.NoSuchElementException. We are supposed to be implemting our own data structures here, not using Java’s built-in stuff.
• Complete all methods with the specified big-O worst-case or amortized running time.
• Use good variable names, spacing, design, and appropriate documentation. See the coding style rubric for this class.

Review the late policy for projects. The grade penalty for (any fraction of) \(k\) days late is \(5^{k-1}\).

Review the course policy on collaboration for projects. No outside help is allowed from any human other than your instructor and the MGSP leader. This includes both giving and receiving assistance to your classmates or other Midshipmen.

Your instructors and MGSP leaders are happy to help you - please reach out if you get stuck or have any questions.

Starter code and submission

• Text.java
• Editor.java
• BoundedStack.java
• README.txt

You can get all these files at once by downloading the file proj1.tar.gz and running tar xzvf proj1.tar.gz

To submit everything using club, go to your directory for this project and run

club README.txt *.java

or using submit, run

submit -c=IC312 -p=proj1 README.txt *.java

Part 1: (Up to 40 pts) Implement the Text interface for a basic editor

The Text interface (javadoc here) shows the methods needed to keep track of a single line of text, with a current “cursor” position that can move left and right, and the ability to insert or delete at the current position.

Your task: Create a new public class MyText.java that implements the Text interface. Once your implementation is complete (and thoroughly tested!), the Editor.java class provided should give you a basic editor with insertions, deletions, movement, and printing.

Notes:

• You can implement the Text interface using linked list(s) or array(s), but then you have to use the other one for the BoundedStack interface in part 2. So read ahead and choose wisely.
• We will extensively test your MyText.java implementation, beyond what might be directly used in the Editor program. So you should test it yourself and make sure it works perfectly!
• Remember, you can’t use any of the built-in data structures in java.util.

Complexity: All of the Text interface functions must be \(O(1)\) worst-case or \(O(1)\) amortized time, except for the print() method which must be \(O(n)\).

Sample run: After this part, the Editor program should work like this (blue is program output, green is user input):

roche@ubuntu$ java Editor
command: h
HELP
  iX   insert letter X before the cursor
  d    delete letter at current position, then move cursor right
  <    move cursor left
  >    move cursor right
  p    print the entire text on one line, with the cursor on the next line
  h    show this help message
  q    quit
command: iF
command: ir
command: iu
command: ii
command: it
command: p
Fruit
     ^
command: <
command: <
command: <
command: <
command: d
command: d
command: il
command: iy
command: i
command: ib
command: ia
command: p
Fly bait
      ^
command: q

Part 2 (up to 40 pts): Implement the BoundedStack interface

We want to implement undo/redo functionality in the Editor.

The first step towards this goal is for you to implement the BoundedStack interface (javadoc here).

This interface is similar to a normal Stack like we have discussed in class, except that it has a limited capacity. When the capacity is reached and another push() operation occurs, the oldest item is first removed from the stack. So unlike a normal stack, there can be removals both from the top of the stack (pop() operation) and from the bottom of the stack (during push() if the stack is already at capacity).

The capacity can also be updated at any time by calling setCapacity().

Your task: Create a new class MyBoundedStack which implements the BoundedStack interface.

Requirement: Whatever kind of underlying data structure you used for MyText.java in part 1 (linked list or array), you must use the other kind for MyBoundedStack.

Complexity: All methods in MyBoundedStack.java must be worst-case or amortized \(O(1)\), except for setCapacity() which may be \(O(n)\) time.

Be sure to test your code extensively, because we certainly will!

Part 3 (up to 20 pts): Add undo functionality to the Editor

Now use your BoundedStack implementation to implement an “undo” feature in the Editor program.

Specifically, you will need to:

1. Create a new class which can be used to remember a single editor “action” of moving left/right, inserting, or deleting.

2. Add an instance of your BoundedStack implementation as a new field in the Editor class, to save the most recent actions that the user has performed.

3. Add two new commands to the to the program in Editor.java:

   • u: undo the most recent action. This can be called multiple times to undo more actions, up to the capacity of the BoundedStack.

   • cNN: set the undo capacity to whatever number is in NN.

     Hint: check you might want to use the methods String.substring() and Integer.parseInt().

Your task: Modify the Editor.java program and make any other classes needed in order to support a limited undo functionality. You must use your MyBoundedStack class to save the recent actions for undo.

Details:

• Only inserting, deleting, and moving count as actions to be undone. (So, for example, there is no way to “undo” a p command.)
• If someone tries to undo

Sample run:

roche@ubuntu$ java Editor
command: iD
command: io
command: i
command: in
command: io
command: it
command: p
Do not
      ^
command: <
command: <
command: d
command: iu
command: <
command: <
command: <
command: d
command: p
Donut
  ^
command: u
command: u
command: p
Do nut
   ^
command: u
command: u
command: p
Do nut
     ^
command: c1
command: >
command: ih
command: ii
command: in
command: ig
command: u
command: p
Do nuthin
         ^
command: u
ERROR
command: q

Bonus (up to 5 pts): Redo

Use another instance of your MyBoundedStack class to add a r command that will “redo” the most recent undone actions.

This should basically work the same as back/forward buttons in a web browser: Undoing (like hitting “back”) will add a new action to the top of the redo stack, and redoing (like hitting “forward”) will pop from the redo stack and push to the undo stack. But whenever a new action is taken, the redo stack should be cleared out.