CS2030 Practical Assessment #2

Back to homepage

Editor

An editor (like vim) allows us to craft a document (e.g. Java program) that facilitates undoing or redoing edits. We can represent a document as a stack of lines where the top of the stack is the most recently added line. In addition, we desire that the stack be an immutable data structure that never modifies itself in place. Consequently, every operation returns a fresh stack reflecting the updated state; the original is never changed. This makes structures safe to share across computations and a natural fit for the functional style practised throughout this course.

Task

Your task is to first design a generic immutable stack, so that type-parameterizing to String will allow us to represent a text document. We then encapsulate this document in an Editor to support further edits such as insert, delete, undo and redo.

Take Note!

This task comprises a number of levels. You are required to complete ALL levels.

The following are the constraints imposed on this task. In general, you should keep to the constructs and programming discipline instilled throughout the module.

• Write each class or interface in its own file. Do not use single letter names for classes or interfaces.
• Ensure that ALL object properties and class constants are declared private final
• Ensure that ALL classes/interfaces are NOT cyclic dependent.
• ONLY the following java libraries ARE allowed: functional interfaces from java.util.function
• The following are NOT allowed: var, null, default, enum, instanceof (except checking for an instance of its own class)
• You DO NOT need to use bounded type parameters or bounded wildcards.
• You are NOT allowed to define anonymous inner classes or method references ::. Define lambdas instead.
• Use only &&, || and ! in logical expressions. DO NOT use bitwise operators.
• You are NOT allowed to use * wildcard imports.
• You are NOT allowed to define array constructs, e.g. String[] or using ellipsis, e.g. String...
• You are NOT allowed to perform string processing using methods from String, StringBuffer, StringBuilder, etc.
• You are NOT allowed to use exception handling
• You are NOT allowed to use Java reflection, i.e. Object::getClasses and other methods from java.lang.Class

In the following level specifications, you will be guided on the classes and non-private methods to define.

• DO NOT create any other classes;
• any other method you create MUST be declared private.
• all constructors MUST be declared private.

The Maybe class has been provided for you. DO NOT replace it with your own version.

Level 1

An immutable stack is naturally represented as a recursive linked structure. A stack is either

• empty containing no elements, or
• a head (e.g. one element) paired with a tail (e.g. another IStack).

Implement a generic class IStack<T> with the following two properties; DO NOT include any other properties.

private final Maybe<T> top;
private final IStack<T> rest;

Also include the following methods:

• a static method empty() that returns an empty IStack;
• a peek() method that returns Maybe<T> with the top element encapsulated within, or Maybe.empty in the case of an empty stack;
• a push method that takes in an element of type T and returns the new stack;
• a toString() method that returns "IStack:empty" for an empty stack, or "IStack:non-empty" otherwise.

$ javac your_java_files
$ jshell your_java_files_in_bottom-up_dependency_order

jshell> IStack<String> s = IStack.<String>empty()
s ==> IStack:empty

jshell> s.peek()
$.. ==> Maybe.empty

jshell> s.push("line1")
$.. ==> IStack:non-empty

jshell> s.push("line1").peek()
$.. ==> Maybe[line1]

jshell> s.push("line1").push("line2").peek()
$.. ==> Maybe[line2]

jshell> s.push("line1").push("line2").push("line3").peek()
$.. ==> Maybe[line3]

Level 2

Now include the pop() method that returns the resulting stack with the top element removed. Note that performing a pop() operation on an empty stack remains as an empty stack.

In addition, include the following methods:

• a print() method to output the elements of the stack in last-in-first-out order;
• a size() method to return the size of the stack. Clearly, the size of a non-empty stack is one more than the size of its tail

$ javac your_java_files
$ jshell your_java_files_in_bottom-up_dependency_order

jshell> IStack<String> s = IStack.<String>empty().
   ...> push("line1").
   ...> push("line2").
   ...> push("line3")
s ==> IStack:non-empty

jshell> s.print()
line3
line2
line1

jshell> s.size()
$.. ==> 3

jshell> s.pop().peek()
$.. ==> Maybe[line2]

jshell> s.pop().print()
line2
line1

jshell> s.pop().size()
$.. ==> 2

jshell> s.pop().pop().peek()
$.. ==> Maybe[line1]

jshell> s.pop().pop().pop().peek()
$.. ==> Maybe.empty

jshell> s.pop().pop().pop().print()

jshell> s.pop().pop().pop().size()
$.. ==> 0

jshell> s.pop().pop().pop().pop().peek()
$.. ==> Maybe.empty

jshell> s.pop().pop().pop().pop().print()

jshell> s.pop().pop().pop().pop().size()
$.. ==> 0

Level 3

We now wrap the document stack (IStack<String>) inside an Editor. For a line-based editor, we need to insert a line at an arbitrary position where position 0 is the top of the document. Because the stack is immutable we cannot update it in place. Instead, we use a two-phase recursive strategy:

• Unwind — recurse down the stack, popping elements off until we reach position 0, keeping track of the elements we passed.
• Rebuild — on the way back up, push the passed elements back on top of the newly inserted line.

The result is a brand-new stack with the line inserted at the right position; the original stack is untouched. Write the Editor class following the specifications below:

• a static method empty() that returns an empty Editor document;
• a method insertAt that takes in a String and an integer pos that returns a new document with the strings inserted at position pos. In the case of pos < 0 or pos exceeding the number of lines in the document, return the same document;
• a method deleteAt that takes an integer pos and return a new document with the element at position pos removed. In the case of invalid pos values, return the same document;
• a doc() method that returns the current document as an IStack<String>;
• a toString() method that returns "Editor".

$ javac your_java_files
$ jshell your_java_files_in_bottom-up_dependency_order

jshell> Editor ed = Editor.empty()
ed ==> Editor

jshell> Editor ed = Editor.empty().
   ...> insertAt("References.", 0).
   ...> insertAt("Conclusion goes here.", 0).
   ...> insertAt("Main argument follows.", 0);
ed ==> Editor

jshell> ed.doc().print()
Main argument follows.
Conclusion goes here.
References.

jshell> Editor ed2 = ed.insertAt("Introduction added here.", 1)
ed2 ==> Editor

jshell> ed2.doc().print()
Main argument follows.
Introduction added here.
Conclusion goes here.
References.

jshell> ed2.deleteAt(3).doc().print()
Main argument follows.
Introduction added here.
Conclusion goes here.

jshell> ed2.deleteAt(3).deleteAt(1).doc().print()
Main argument follows.
Conclusion goes here.

jshell> ed2.deleteAt(1).deleteAt(3).doc().print()
Main argument follows.
Conclusion goes here.
References.

Level 4

So far our operations on the encapsulated IStack<String> within an Editor produce new stacks but throw away the old ones. We now wrap the document stack inside an Editor that remembers past states so that edits can be undone and redone.

The key idea is to maintain two other separate IStack<Editor> structures for the past and future operations. These are represented respectively as:

• Undo stack — a sequence of past operations/states, most recent on top
• Redo stack — operations/states that were undone but can be reapplied

In the case of an undo operation, before any edit is applied, the current document is pushed onto the undo stack. Undoing an edit simply pops the stack and restores the previous document. However, undo alone loses the future; once you undo an edit you cannot reapply it. We fix this with a second redo stack.

Include the undo() and redo methods in the Editor class:

• undo() — pops from undo stack then pushes onto the redo stack;
• redo() — pops from the redo stack then pushes onto the undo stack.

$ javac your_java_files
$ jshell your_java_files_in_bottom-up_dependency_order

jshell> Editor e0 = Editor.empty()
e0 ==> Editor

jshell> Editor e1 = e0.insertAt("Roses are red.", 0)
e1 ==> Editor

jshell> Editor e2 = e1.insertAt("Violets are blue.", 0)
e2 ==> Editor

jshell> Editor e3 = e2.insertAt("WRONG LINE", 0)
e3 ==> Editor

jshell> e3.doc().print()
WRONG LINE
Violets are blue.
Roses are red.

jshell> Editor e4 = e3.undo()
e4 ==> Editor

jshell> e4.doc().print()
Violets are blue.
Roses are red.

jshell> e4.undo().doc().print()
Roses are red.

jshell> e4.undo().undo().doc().print()

jshell> e4.undo().undo().undo().doc().print()

Calling undo() on an Editor with no history does not alter the Editor.

jshell> Editor e5 = e4.undo()
e5 ==> Editor

jshell> e5.doc().print()
Roses are red.

jshell> Editor e6 = e5.redo()
e6 ==> Editor

jshell> e6.doc().print()
Violets are blue.
Roses are red.

jshell> Editor e7 = e5.insertAt("Line X", 0)
e7 ==> Editor

jshell> e7.doc().print()
Line X
Roses are red.

jshell> e7.redo().doc().print()
Line X
Roses are red.

Notice from the last test case that a new edit (i.e. insertion or deletion) clears the redo stack.

Also note that any invalid edit (insertion or deletion) that does not change the document state will NOT be added to the undo/redo stacks. The following is an example demonstrating an invalid insertion.

jshell> Editor.empty().
   ...> insertAt("line 1", 0).
   ...> insertAt("line 2", 1). // last successful insert
   ...> insertAt("line 3", 10). // invalid insert
   ...> doc().print()
line 1
line 2

jshell> Editor.empty().
   ...> insertAt("line 1", 0).
   ...> insertAt("line 2", 1). // last successful insert
   ...> insertAt("line 3", 10). // invalid insert
   ...> undo(). // undo last successful insert
   ...> doc().print()
line 1

jshell> Editor.empty().
   ...> insertAt("line 1", 0).
   ...> insertAt("line 2", 1). // last successful insert
   ...> insertAt("line 3", 10). // invalid insert
   ...> undo(). // undo last successful insert
   ...> redo(). // redo last successful insert
   ...> doc().print()
line 1
line 2

Level 5

We now introduce flatMap to allow multi-step edits to be composed as a single undoable operation. An Editor is a monad over its document state. flatMap allows you to chain a sequence of edits where each step may inspect the current document before deciding what to do next. The entire chain is treated as a single undoable step: only one snapshot is pushed onto the history before the chain begins. Include a flatMap method that takes in a Function<IStack<String>, Editor> and returns the resulting Editor after the operation.

For the purpose of testing, also include a static of() method to wrap an IStack<String> in an Editor with empty undo and redo stacks.

jshell> Editor e = Editor.empty().
   ...> insertAt("Line A", 0).
   ...> insertAt("Line B", 0).
   ...> insertAt("Line C", 0)
e ==> Editor

jshell> e.doc().print()
Line C
Line B
Line A

jshell> UnaryOperator<IStack<String>> swap = doc ->
   ...> doc.size() <= 2 ? doc :
   ...> doc.peek().map(line -> 
   ...>    Editor.of(doc).deleteAt(0).insertAt(line,2).doc()).
   ...> orElse(doc)
swap ==> $Lambda..

jshell> Editor swapped = e.flatMap(doc -> Editor.of(swap.apply(doc)))
swapped ==> Editor

jshell> swapped.doc().print()
Line B
Line A
Line C

jshell> swapped.undo().doc().print()
Line C
Line B
Line A

jshell> swapped.undo().undo().doc().print()
Line B
Line A

flatMap(f) should snapshot the current document onto history then apply f, keeping in mind that the intermediate steps inside f do not pollute the undo stack. The returned editor should have the original (pre-chain) history with one entry prepended.