Module assignment: Undo, redo and history editor

What you will build

This assignment brings the whole module together in one program. You will build the core of a text editor. The editor holds a list of words, and it accepts commands such as type, undo, redo, print, longest and history. Each command changes the editor in a specific way, and each one must give exactly the output the specification asks for.

You will meet every structure from this module in one place. The redo history is a stack, because the most recently undone word must come back first. The history of recent actions is a queue with a fixed size, because only the last five actions should be kept, and the oldest should leave first. The longest word query needs a second stack that remembers the best value at each depth, so that undoing a word restores the old answer without rescanning the text. The assignment is a problem set, not a game or a website. You write one C++ program that reads from standard input and writes to standard output. Your program will be checked by comparing its printed output with the expected output, character by character, for every test case. That is why the output format in this lesson matters as much as the logic.

Work through the specification slowly. Most lost marks come from a missed rule, not from a hard algorithm. Re-read each command rule after you finish your first version.

The specification

Input

The first line holds one integer q, the number of commands, with 1 <= q <= 1000. The next q lines each hold one command. Every command starts with one of the six words below. Some commands are followed by a word.

Words are made only of lowercase letters a to z. Each word has between 1 and 10 letters. A command line never has extra spaces inside it, except the single space between the command and its word.

Commands

type WORD appends WORD to the end of the text. Then the redo history is cleared, because a new edit ends any chain of redo steps. This command is recorded in the action history as type WORD. It prints nothing.

undo removes the last word of the text, if there is one. The removed word is pushed onto the redo stack. This command is recorded as undo. If the text is empty, undo does nothing and is not recorded. It prints nothing.

redo takes the most recently undone word off the redo stack and appends it to the text. This command is recorded as redo. If the redo stack is empty, redo does nothing and is not recorded. It prints nothing.

print prints the text. The words are separated by a single space, and there is no space at the start or the end. If the text is empty, print prints an empty line. It is not recorded, and it changes nothing.

longest prints the length of the longest word in the current text, as a single integer. If the text is empty, it prints 0. It is not recorded, and it changes nothing.

history prints the recorded actions, one per line, oldest first. The editor keeps only the last five recorded actions. Each line shows the action exactly as it was recorded, for example type cat, undo or redo. If fewer than five actions have been recorded, print only those. If none have been recorded, print nothing. It is not recorded, and it changes nothing.

Output

Print exactly what each command asks for, in the order the commands appear. Each printed line ends with a newline. Nothing else may be printed.

Examples

Example 1 has nine commands. Trace it before you read the explanation.

9
type hello
type big
type world
undo
print
redo
redo
type again
history

The output is:

hello big
type big
type world
undo
redo
type again

Here is the reasoning. After the three type commands the text is hello big world. The undo removes world and records undo. The print shows hello big. The first redo puts world back and records redo. The second redo finds the redo stack empty, so it does nothing and records nothing. The last type adds again and records type again. The history now holds six recorded actions, so the oldest one, type hello, is dropped. The last five are type big, type world, undo, redo and type again, in that order.

Example 2 has six commands, and its output starts with an empty line.

6
print
undo
type x
undo
redo
print

The output is:

The first print runs on an empty text, so it prints an empty line. The first undo does nothing, because the text is empty, so it is not recorded. The type x adds x. The second undo removes it and pushes it onto the redo stack. The redo puts it back and records redo. The final print shows x.

Example 3 checks the longest-word query.

6
type cat
type horse
longest
undo
longest
undo

The output is:

5
3

After type cat and type horse, the longest word is horse, with 5 letters. The first undo removes horse, so the longest word is cat, with 3 letters. The second undo removes cat, but the query is not repeated, so nothing more is printed.

Requirements checklist

Use this list while you work. Tick a box only when you have tested that rule with a small input.

Grading rubric

The rubric describes three levels of solution. Your score is the level your program reaches when it is run on a full set of hidden tests. The three examples above are part of every set, so a program that fails an example cannot score above the 60 percent level.

60 percent: the core works. The program passes all three examples. type, undo and print behave correctly, including the empty-text cases. The redo stack may be missing or may not be cleared by type. The longest and history commands may be missing, or may print the wrong answer in some cases.

80 percent: every command works, with some edge-case errors. The program handles all six commands. It may fail a few hidden tests, for example a sequence where type must clear the redo stack, a redo after several undos, or a history with exactly five or six actions. The longest answer may be correct but slow, because it rescans the text on every query. Your solution is in this band if the program is correct on normal sequences but breaks on edge cases.

100 percent: correct on every test, with the right structures. The program passes every hidden test, including edge cases such as an empty text, a redo chain broken by a new type, and a history that has overflowed. The redo history uses a stack. The history of actions keeps exactly five entries, using a queue or a circular buffer, and drops the oldest entry when a sixth arrives. The longest-word query is answered from a stored value, updated on every type, undo and redo, so the query costs O(1). The program prints nothing extra.

A 100 percent solution is not one that uses the most code. A short program that handles every rule correctly and uses the right structure for each job is better than a long one with mistakes.

Hints

Each hint is hidden. Try the step on your own first, and open a hint only when you are stuck. Each one answers one question.

Hint 1: how should the text be stored?

Use a vector<string> for the words. Adding a word is push_back, and removing the last word is pop_back. You can print the words by looping over the vector and putting a space between them. Do not join them into one string until you print, because the words must stay separate for undo.

Hint 2: what does undo need to remember?

When undo removes a word, it must be able to put the same word back. Use a stack<string> named redo. Push the removed word onto it. When redo runs, take redo.top(), append it to the text, and then call redo.pop(). Remember that pop() returns nothing, so read top() first.

Hint 3: when is the redo stack cleared?

Only one event clears it: a new type command. Pop everything from the redo stack in a loop before you add the new word. A plain undo or redo never clears it, because those commands are part of the same chain of changes.

Hint 4: how do you keep only five actions?

Use a queue<string> named recent. Push each recorded action onto it. If its size is now more than five, pop from the front. That removes the oldest action. To print the history, copy the queue, then read and pop the copy from the front, so the real queue is not changed.

Hint 5: how can longest be fast?

Keep a second vector<int> named best, in step with the text. Entry i of best holds the longest word length among the first i + 1 words. When you add a word, push the larger of the new length and the last entry. When you remove a word, pop the last entry of best too. Then longest just reads the last entry, or prints 0 when best is empty. This is a stack of maxima, the same idea as practice exercise 8 in the first lesson.

Hint 6: how do you read the input safely?

Read q with cin >> q, then call getline once to finish that line. Inside the loop, call getline for each command, put the line into a stringstream, and read the command word with >>. For type, read the word from the same stream. Using getline for every line keeps the line structure safe, even for an empty line such as the one print prints.

Reference solution

Try the assignment first. The solution below passes all three examples, and it follows the 100 percent rules. Read it after you have a version of your own, and compare the structures, not just the output. Every choice in it matches one hint.

Reference solution

#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
 
int main() {
    int q;
    cin >> q;
    string line;
    getline(cin, line);                 // finish the line that holds q
 
    vector<string> text;                // the words in the document
    vector<int> best;                   // best[i] = longest word among text[0..i]
    stack<string> redo;                 // words taken back by undo
    queue<string> recent;               // the last 5 recorded actions, oldest first
 
    auto record = [&](const string& action) {
        recent.push(action);
        if (recent.size() > 5) recent.pop();
    };
    auto append = [&](const string& word) {
        int prev = best.empty() ? 0 : best.back();
        best.push_back(max(prev, (int)word.size()));
        text.push_back(word);
    };
 
    for (int i = 0; i < q; i++) {
        getline(cin, line);
        stringstream ss(line);
        string cmd;
        ss >> cmd;
        if (cmd == "type") {
            string word;
            ss >> word;
            append(word);
            while (!redo.empty()) redo.pop();   // a new edit ends the redo chain
            record("type " + word);
        } else if (cmd == "undo") {
            if (!text.empty()) {
                redo.push(text.back());
                text.pop_back();
                best.pop_back();
                record("undo");
            }
        } else if (cmd == "redo") {
            if (!redo.empty()) {
                append(redo.top());
                redo.pop();
                record("redo");
            }
        } else if (cmd == "print") {
            for (size_t j = 0; j < text.size(); j++) {
                if (j > 0) cout << " ";
                cout << text[j];
            }
            cout << "\n";
        } else if (cmd == "longest") {
            cout << (best.empty() ? 0 : best.back()) << "\n";
        } else if (cmd == "history") {
            queue<string> copy = recent;
            while (!copy.empty()) {
                cout << copy.front() << "\n";
                copy.pop();
            }
        }
    }
    return 0;
}

Notice three design choices. The record lambda keeps the history at five entries in one place, so no command can forget the limit. The append lambda is the only function that adds a word, so best and text can never drift apart. And history copies the queue before reading it, so printing does not change the state.

Testing your work

Testing is part of the assignment. Write your own input files, predict the output by hand, and then run your program. A mismatch means either your prediction or your code is wrong, so trace the sequence step by step until you find the difference.

Use these test ideas, one at a time:

A redo after a new type. The redo must print nothing new, and the word must stay on the redo stack only until the type clears it.
Five type commands followed by history, then a sixth type and history again. The first history has five lines, and the second drops the oldest.
An undo on an empty text, followed by print. The print must show an empty line, and the undo must not appear in history.
Several undo commands followed by the same number of redo commands. The text must come back in the original order.
longest after undo of the longest word. The answer must drop to the length of the next longest word still in the text.
A word of length 10, the largest allowed, to check that the length is stored as a number and not truncated.

A good habit is to write the expected output before you run the program. Then you cannot fool yourself with a result you already expected.

Going further

Once your program scores 100 percent, you may extend it. Add a command delete that removes the first word, and decide whether it is recorded and how it interacts with redo. Add a command reverse that prints the words in reverse order without changing the text, and implement it with a stack. These extensions are optional. Keep the specified commands unchanged, because the rubric tests them exactly.

What you practised

A stack that restores the most recent undo, and that is cleared by a new edit.
A fixed-size history, kept with a queue, that drops its oldest entry.
A stack of maxima that answers a query in constant time and survives undo.
Line-based input and output that must match exactly.
Testing by predicting the output first, then checking the program.

Module assignment: Undo, redo and history editor

What you will build

The specification

Input

Commands

Output

Examples

Requirements checklist

Grading rubric

Hints

Reference solution

Testing your work

Going further

What you practised

Stuck? Ask the tutor