Добромир обнови решението на 06.11.2018 21:52 (преди 9 месеца)
+package main
+
+import (
+ "strings"
+)
+
+type Editor interface {
+ // Insert text starting from given position.
+ Insert(position uint, text string) Editor
+
+ // Delete length items from offset.
+ Delete(offset, length uint) Editor
+
+ // Undo reverts latest change.
+ Undo() Editor
+
+ // Redo re-applies latest undone change.
+ Redo() Editor
+
+ // String returns complete representation of what a file looks
+ // like after all manipulations.
+ String() string
+}
+
+type piece struct {
+ offset uint
+ length uint
+ origin bool
+}
+
+type editorImpl struct {
+ origin []byte
+ add []byte
+ changes []piece
+ undo []editorImpl
+ redo *editorImpl
+}
+
+func (editor editorImpl) Insert(position uint, text string) Editor {
+ editor.saveUndo()
+ editor.redo = nil
+
+ if cap(editor.add) == 0 {
+ editor.add = make([]byte, 0, len(text))
+ }
+
+ newChange := piece{uint(len(editor.add)), uint(len(text)), false}
+ editor.add = append(editor.add, []byte(text)...)
+ offsetIndex, _ := pieceContainingByteOffset(position, editor.changes)
+
+ originalLength := editor.changes[offsetIndex].length
+ if originalLength > position {
+ editor.changes[offsetIndex].length = position
+ }
+
+ editor.changes = insertPieceAt(editor.changes, newChange, offsetIndex+1)
+ if originalLength > position {
+ newChange = piece{editor.changes[offsetIndex].offset + position, originalLength - position, true}
+ editor.changes = insertPieceAt(editor.changes, newChange, offsetIndex+2)
+ }
+
+ return editor
+}
+
+func (editor editorImpl) Delete(offset, length uint) Editor {
+ editor.saveUndo()
+ editor.redo = nil
+
+ remaining := length
+ offsetIndex, totalBytes := pieceContainingByteOffset(offset, editor.changes)
+
+ relativeOffset := editor.changes[offsetIndex].length - (totalBytes - offset)
+ originalLength := editor.changes[offsetIndex].length
+
+ // Should never happen
+ if relativeOffset > editor.changes[offsetIndex].length {
+ return editor
+ }
+
+ editor.changes[offsetIndex].length = relativeOffset
+ if originalLength > remaining+relativeOffset {
+ newPiece := piece{
+ relativeOffset + remaining,
+ originalLength - relativeOffset - remaining,
+ editor.changes[offsetIndex].origin}
+ editor.changes = insertPieceAt(editor.changes, newPiece, offsetIndex+1)
+ remaining = 0
+ } else {
+ remaining -= originalLength - relativeOffset
+ }
+
+ for i := offsetIndex + 1; i < len(editor.changes) && remaining > 0; i++ {
+ if remaining >= editor.changes[i].length {
+ remaining -= editor.changes[i].length
+ editor.changes = append(editor.changes[:i], editor.changes[i+1:]...)
+ i -= 1
+ } else {
+ editor.changes[i].offset += remaining
+ editor.changes[i].length -= remaining
+ remaining = 0
+ }
+ }
+
+ return editor
+}
+
+func (editor editorImpl) Undo() Editor {
+ if len(editor.undo) == 0 {
+ return editor
+ }
+
+ changesCopy := make([]piece, len(editor.changes))
+ copy(changesCopy, editor.changes)
+
+ undoneEditor := editor.undo[len(editor.undo)-1]
+ undoneEditor.redo = &editor
+ return undoneEditor
+}
+
+func (editor editorImpl) Redo() Editor {
+ if editor.redo == nil {
+ return editor
+ }
+ return *editor.redo
+}
+
+func (editor editorImpl) String() string {
+ var sb strings.Builder
+
+ for _, change := range editor.changes {
+ if change.origin {
+ sb.Write(editor.origin[change.offset : change.offset+change.length])
+ } else {
+ sb.Write(editor.add[change.offset : change.offset+change.length])
+ }
+ }
+
+ return sb.String()
+}
+
+func (editor *editorImpl) saveUndo() {
+ changesCopy := make([]piece, len(editor.changes))
+ copy(changesCopy, editor.changes)
+
+ editor.undo = append(editor.undo, editorImpl{
+ editor.origin, editor.add, changesCopy, editor.undo, nil,
+ })
+}
+
+func NewEditor(content string) Editor {
+ editor := editorImpl{
+ []byte(content),
+ make([]byte, 0, 16),
+ make([]piece, 0, 16),
+ make([]editorImpl, 0, 8),
+ nil,
+ }
+ editor.changes = append(editor.changes, piece{0, uint(len(content)), true})
+ return editor
+}
+
+func pieceContainingByteOffset(offset uint, chain []piece) (i int, totalChars uint) {
+ var chainElem piece
+ totalChars = 0
+ i = 0
+ for i, chainElem = range chain {
+ totalChars += chainElem.length
+ if totalChars >= offset {
+ break
+ }
+ }
+ return i, totalChars
+}
+
+func insertPieceAt(slice []piece, el piece, index int) []piece {
+ slice = append(slice, piece{})
+ slice = append(slice[:index+1], slice[index:]...)
+ slice[index] = el
+ return slice
+}