CodingGyan

Memento: Editor Snapshots

medium Design Principles and Patterns

Problem

Build a text editor with snapshots. Commands: TYPE text (add the text to the end of the document; the text is everything after the first space and may contain spaces), SNAPSHOT (save the current text; print its number: 1 for the first snapshot, 2 for the second, ...), RESTORE n (replace the document by snapshot n; print unknown for a number that does not exist) and SHOW (print the document, or (empty) if it has no text). TYPE and a good RESTORE print ok. Use the memento pattern: the editor creates and reads snapshot objects, and another object (the caretaker) only stores them.

Constraints

  • 1 <= lines <= 1000

Examples

Input

TYPE hi
SNAPSHOT
TYPE !
SHOW
RESTORE 1
SHOW

Output

ok
1
ok
hi!
ok
hi

Solutions

Best approachTime O(n * text length)Space O(snapshots * text length)

The editor owns its state and decides what a snapshot contains. The caretaker keeps the snapshots but cannot read them, so the editor's internals stay hidden. Undo history, save points and game checkpoints work this way.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process lines.
 * Input   : Several command lines.
 * Output  : One result per command.
 * Approach: Editor, memento and caretaker.
 * Time    : O(n * text length)
 * Space   : O(snapshots * text length)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A Memento is a sealed snapshot. Only the editor looks inside it.
        static class Memento {
            private final String text;

            Memento(String text) {
                this.text = text;
            }
        }

        // Step 2: The editor creates snapshots and restores from them.
        static class Editor {
            private String text = "";

            void type(String more) {
                text += more;
            }

            Memento save() {
                return new Memento(text);
            }

            void restore(Memento memento) {
                text = memento.text;
            }

            String show() {
                return text.isEmpty() ? "(empty)" : text;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        Editor editor = new Editor();
        // Step 3: The caretaker is only a list of mementos. It cannot read or change them.
        java.util.List<Memento> caretaker = new java.util.ArrayList<Memento>();
        String[] output = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            String line = lines[i];
            if (line.startsWith("TYPE ")) {
                editor.type(line.substring(5));
                output[i] = "ok";
            } else if (line.equals("SNAPSHOT")) {
                caretaker.add(editor.save());
                output[i] = String.valueOf(caretaker.size());
            } else if (line.startsWith("RESTORE ")) {
                int number = Integer.parseInt(line.substring(8).trim());
                if (number >= 1 && number <= caretaker.size()) {
                    editor.restore(caretaker.get(number - 1));
                    output[i] = "ok";
                } else {
                    output[i] = "unknown";
                }
            } else {
                output[i] = editor.show();
            }
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            all.add(scanner.nextLine());
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. Who may look inside a memento?
  2. What does the caretaker store?