[Google] Design Text Editor
Original question is here: https://www.careercup.com/question?id=5726975948226560
This is my implementation using StringBuilder with a cursor index instead of LinkedList. The key point is: use java enum as much as possible and don't use String directly. Using String directly is not a good OOP. As for OOP/OOD, think about how to encapsulate the code, and reuse the code. In TextEditor implemention, it uses the same implementation for undos and normal insert, delete, move cursor.
Java enum is as powerful as a class (in fact, enum is a class). In the code, it demonstrates 2 ways to use java enum:
Using enum has the following benefits
The below implementation is a little over-engineered, but it demonstrates how OOP/OOD is supposed to be.
Original question is here: https://www.careercup.com/question?id=5726975948226560
This is my implementation using StringBuilder with a cursor index instead of LinkedList. The key point is: use java enum as much as possible and don't use String directly. Using String directly is not a good OOP. As for OOP/OOD, think about how to encapsulate the code, and reuse the code. In TextEditor implemention, it uses the same implementation for undos and normal insert, delete, move cursor.
Java enum is as powerful as a class (in fact, enum is a class). In the code, it demonstrates 2 ways to use java enum:
- abstract method can be used in enum
- A method can be overriden in enum
Using enum has the following benefits
- passing different enums to a method, the method can behavior differently (Strategy pattern).
- reduce the usage of if-else or case statement, which in turn reduces the code complexity (see here for explanation).
The below implementation is a little over-engineered, but it demonstrates how OOP/OOD is supposed to be.
public class TextEditor {
private final StringBuilder text;
// store undo edits.
private final Stack<UndoEdit> undoEdits;
private int cursorIndex;
public TextEditor() {
this.text = new StringBuilder();
undoEdits = new Stack<>();
cursorIndex = 0;
}
public boolean moveCursorLeft() {
return moveCursorLeft(Undo.SAVE);
}
private boolean moveCursorLeft(final Undo undo) {
if (cursorIndex == 0) {
return false;
}
cursorIndex--;
undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_RIGHT), this);
return true;
}
public boolean moveCursorRight() {
return moveCursorRight(Undo.SAVE);
}
private boolean moveCursorRight(final Undo undo) {
if (cursorIndex == text.length()) {
return false;
}
cursorIndex++;
undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_LEFT), this);
return true;
}
public boolean insertCharacter(final char ch) {
return insertCharacter(ch, Undo.SAVE);
}
private boolean insertCharacter(final char ch, final Undo undo) {
text.insert(cursorIndex, ch);
cursorIndex++;
undo.add(new UndoEdit(UndoEdit.Operation.BACKSPACE), this);
return true;
}
public boolean backspace() {
return backspace(Undo.SAVE);
}
private boolean backspace(final Undo undo) {
if (cursorIndex == 0) {
return false;
}
cursorIndex--;
final char ch = text.charAt(cursorIndex);
undo.add(new UndoEdit(UndoEdit.Operation.INSERT_CHARACTER, ch), this);
text.deleteCharAt(cursorIndex);
return true;
}
public boolean undo() {
if (!undoEdits.empty()) {
final UndoEdit edit = undoEdits.pop();
return edit.apply(this);
}
return false;
}
private void saveForUndo(final UndoEdit action) {
undoEdits.add(action);
}
// for unit test/debug
int cursor() {
return cursorIndex;
}
@Override
public String toString() {
return new StringBuilder(text).insert(cursorIndex, "|").toString();
}
enum Undo {
SAVE {
@Override
public void add(final UndoEdit edit, final TextEditor textEditor) {
textEditor.saveForUndo(edit);
}
},
UNSAVE;
/**
* Default implementation for doing nothing
*
* @param edit
* @param textEditor
*/
public void add(final UndoEdit edit, final TextEditor textEditor) {
// do nothing
}
}
/**
* Helper class to encapsulate undo operation and character.
*/
private static class UndoEdit {
private static final char EMPTY_CHAR = '\0';
private final Operation operation;
private final char ch;
public UndoEdit(final Operation operation) {
this.operation = operation;
this.ch = EMPTY_CHAR;
}
public UndoEdit(final Operation operation, final char ch) {
this.operation = operation;
this.ch = ch;
}
public boolean apply(final TextEditor editor) {
return operation.apply(ch, editor);
}
@Override
public String toString() {
return operation.toString() + " " + ch;
}
enum Operation {
MOVE_CURSOR_LEFT {
@Override
public boolean apply(final char ch, final TextEditor editor) {
return editor.moveCursorLeft(Undo.UNSAVE);
}
},
MOVE_CURSOR_RIGHT {
@Override
public boolean apply(final char ch, final TextEditor editor) {
return editor.moveCursorRight(Undo.UNSAVE);
}
},
INSERT_CHARACTER {
@Override
public boolean apply(final char ch, final TextEditor editor) {
return editor.insertCharacter(ch, Undo.UNSAVE);
}
},
BACKSPACE {
@Override
public boolean apply(final char ch, final TextEditor editor) {
return editor.backspace(Undo.UNSAVE);
}
};
public abstract boolean apply(char ch, TextEditor editor);
}
}
}
好像原题有要求“All functions above should take O(1) time. ”
代码里的text.insert和text.deleteCharAt会不会有问题呢……
代码里的text.insert和text.deleteCharAt会不会有问题呢……
StringBuilder's deleteChar and insertChar have linear time complexity. Here is the new code to use doubly linkedlist. Since it is well encapsulated, it is easy to switch to a different implementation:
[Java] 纯文本查看 复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
| public class TextEditor { private static final char EMPTY_CHAR = '\0'; private final ListNode head; private final ListNode tail; // store undo edits. private final Stack<UndoEdit> undoEdits; private ListNode cursor; public TextEditor() { head = new ListNode(); tail = new ListNode(); head.next = tail; tail.prev = head; undoEdits = new Stack<>(); cursor = tail; } public boolean moveCursorLeft() { return moveCursorLeft(Undo.SAVE); } private boolean moveCursorLeft(final Undo undo) { if (cursor.prev == head) { return false; } cursor = cursor.prev; undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_RIGHT), this); return true; } public boolean moveCursorRight() { return moveCursorRight(Undo.SAVE); } private boolean moveCursorRight(final Undo undo) { if (cursor.next == null) { return false; } cursor = cursor.next; undo.add(new UndoEdit(UndoEdit.Operation.MOVE_CURSOR_LEFT), this); return true; } public boolean insertCharacter(final char ch) { return insertCharacter(ch, Undo.SAVE); } private boolean insertCharacter(final char ch, final Undo undo) { final ListNode node = new ListNode(ch); node.prev = cursor.prev; node.next = cursor; cursor.prev.next = node; cursor.prev = node; undo.add(new UndoEdit(UndoEdit.Operation.BACKSPACE), this); return true; } public boolean backspace() { return backspace(Undo.SAVE); } private boolean backspace(final Undo undo) { if (cursor.prev == head) { return false; } final char ch = cursor.prev.ch; undo.add(new UndoEdit(UndoEdit.Operation.INSERT_CHARACTER, ch), this); final ListNode deleted = cursor.prev; deleted.prev.next = cursor; cursor.prev = deleted.prev; deleted.prev = null; deleted.next = null; return true; } public boolean undo() { if (!undoEdits.empty()) { final UndoEdit edit = undoEdits.pop(); return edit.apply(this); } return false; } private void saveForUndo(final UndoEdit action) { undoEdits.add(action); } // for unit test/debug ListNode cursor() { return cursor; } @Override public String toString() { final StringBuilder builder = new StringBuilder(); ListNode node = head.next; while (node != null) { if (node == cursor) { builder.append("|"); } if (node != tail) { builder.append(node.ch); } node = node.next; } return builder.toString(); } enum Undo { SAVE { @Override public void add(final UndoEdit edit, final TextEditor textEditor) { textEditor.saveForUndo(edit); } }, UNSAVE; /** * Default implementation for doing nothing * * @param edit * @param textEditor */ public void add(final UndoEdit edit, final TextEditor textEditor) { // do nothing } } /** * Helper class to encapsulate undo operation and character. */ private static class UndoEdit { private final Operation operation; private final char ch; public UndoEdit(final Operation operation) { this.operation = operation; this.ch = EMPTY_CHAR; } public UndoEdit(final Operation operation, final char ch) { this.operation = operation; this.ch = ch; } public boolean apply(final TextEditor editor) { return operation.apply(ch, editor); } @Override public String toString() { return operation.toString() + " " + ch; } enum Operation { MOVE_CURSOR_LEFT { @Override public boolean apply(final char ch, final TextEditor editor) { return editor.moveCursorLeft(Undo.UNSAVE); } }, MOVE_CURSOR_RIGHT { @Override public boolean apply(final char ch, final TextEditor editor) { return editor.moveCursorRight(Undo.UNSAVE); } }, INSERT_CHARACTER { @Override public boolean apply(final char ch, final TextEditor editor) { return editor.insertCharacter(ch, Undo.UNSAVE); } }, BACKSPACE { @Override public boolean apply(final char ch, final TextEditor editor) { return editor.backspace(Undo.UNSAVE); } }; public abstract boolean apply(char ch, TextEditor editor); } } static class ListNode { char ch; ListNode prev; ListNode next; ListNode() { ch = EMPTY_CHAR; } ListNode(final char ch) { this.ch = ch; } @Override public boolean equals(final Object o) { final ListNode that = (ListNode) o; return ch == that.ch; } }} |
