Cursor-Based Text Editor: Typing, Backspace, and Four-Way Cursor Movement

Implement a `TextEditor` class that holds a text buffer and a single cursor. The editor starts empty, with the cursor at position 0. It supports three operations: 1. `type_in(char)`: type one character at the cursor. The character is inserted immediately before the cursor, so the cursor ends up just after it. 2. `backspace()`: delete the character immediately before the cursor. 3. `str()`: return the text with `|` marking the cursor position. In Python, implement it as `__str__`, so that `str(editor)` works. ```python class TextEditor: def __init__(self) -> None: ... def type_in(self, char: str) -> None: ... def backspace(self) -> None: ... def __str__(self) -> str: ... def move_cursor(self, direction: str) -> None: ... # Parts 2 and 3 ``` Example: ```text type_in("a"), type_in("b"), type_in("c") str(editor) == "abc|" backspace() str(editor) == "ab|" ``` The follow-ups add `move_cursor(direction)`, first for moving the cursor left and right, then for moving it up and down. ### Constraints and Clarifications - One cursor and no selection. - `direction` is one of `"left"`, `"right"`, `"up"` and `"down"`. The spelling is an assumption; the follow-up specified only `move_cursor(direction)`. - Moving up and down only makes sense when the text has several lines. Assume a line break is typed as the newline character `"\n"` through `type_in`, and that `str()` returns the newlines as they are. ### Clarifying Questions - Does `type_in` always receive exactly one character? Can it receive `"\n"`? - What should `backspace()` do when the cursor is at the very start of the text? And at the start of a line that is not the first? - Can the text itself contain `|`? If so, how should `str()` keep it apart from the cursor? - How often is `str()` called compared with the editing operations, and how long can the text get? ### Part 1 — Typing, backspace and rendering Implement `type_in`, `backspace` and `__str__`, and state the cost of each operation for your representation. ```hint Edits happen next to the cursor Every change in this part touches the character just before the cursor. Look for a representation in which that change does not shift the rest of the text. ``` #### What This Part Should Cover - The representation of the text and the cursor, and why it fits these operations - Correct behavior on an empty editor and for a backspace at the start - The time cost of each operation, including `__str__` ### Part 2 — Move the cursor left and right Add `move_cursor("left")` and `move_cursor("right")`, which move the cursor by one character. ```text start from "ab|" move_cursor("left") str(editor) == "a|b" type_in("x") str(editor) == "ax|b" move_cursor("right") str(editor) == "axb|" ``` ```hint Count what moves In your Part 1 representation, count how many characters change place when the cursor moves by one, and how many shift when you then type. If either number grows with the text, reconsider the representation. ``` #### Clarifying Questions for this Part - What should moving left at the start of the text, or right at the end, do? - When the text has several lines, does moving left from the start of a line go to the end of the previous line? #### What This Part Should Cover - Moving the cursor without making typing or backspace more expensive - Behavior at both ends of the text - The cost of a move ### Part 3 — Move the cursor up and down Add `move_cursor("up")` and `move_cursor("down")`, which move the cursor to the previous or next line, keeping its column where possible. ```text "ab\ncd|" move_cursor("up") "ab|\ncd" ``` (The strings are Python literals; `\n` is the newline.) ```hint Columns are per line A vertical move needs the cursor's column on its current line and the length of the line it lands on. Work out how your representation finds each of them, and what that costs. ``` #### Clarifying Questions for this Part - If the target line is shorter than the cursor's column, where does the cursor go? - After passing through a short line, should the next vertical move return the cursor to its original column? - What do up on the first line and down on the last line do? #### What This Part Should Cover - Finding the column and the start and length of the target line - Shorter lines, empty lines, and the first and last line - The cost of a vertical move, and whether a different representation would make it cheaper ### What a Strong Answer Covers - States the boundary policies (backspace and moves at the edges, joining lines, the `|` ambiguity) before coding - A representation that keeps typing, backspace and horizontal moves cheap, with the cost of every operation stated, including `str()` - Correct vertical movement across lines of different lengths, empty lines, and the first and last line - Runnable code checked against a short trace - Knowing when another representation fits better: frequent vertical moves, very long lines, very large documents ### Follow-up Questions - Add `undo()` and `redo()` for typing and backspace. What does each edit record, and what happens to the redo history after a new edit? - A document has very long lines, so vertical moves become slow. How would you make them independent of line length without slowing down typing? - Add word-wise movement that jumps the cursor to the start of the previous or next word. What changes, and what counts as a word?