Решение на Piece table от Добромир Иванов

Обратно към всички решения

Към профила на Добромир Иванов

Резултати

  • 10 точки от тестове
  • 0 бонус точки
  • 10 точки общо
  • 8 успешни тест(а)
  • 0 неуспешни тест(а)

Код

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
}

Лог от изпълнението

PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.002s
PASS
ok  	_/tmp/d20181107-53-1d31bws	0.003s

История (1 версия и 0 коментара)

Добромир обнови решението на 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
+}