Божин обнови решението на 05.11.2018 22:44 (преди 9 месеца)
+package main
+
+// Editor is a basic text editor.
+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
+}
+
+// PieceChainEditor implements Editor using the piece chain data structure.
+type PieceChainEditor struct {
+ origin []byte
+ add []byte
+ pieces []Piece
+}
+
+// Piece is used in the implementation of the piece data structure
+type Piece struct {
+ origin bool
+ offset int
+ length int
+}
+
+// NewEditor creates a new Editor.
+func NewEditor(text string) Editor {
+ textAsBytes := []byte(text)
+ piece := Piece{
+ origin: true,
+ offset: 0,
+ length: len(textAsBytes),
+ }
+
+ return &PieceChainEditor{
+ origin: textAsBytes,
+ add: nil,
+ pieces: []Piece{piece},
+ }
+}
+
+// PieceChainEditor implements Editor.
+func (e *PieceChainEditor) Insert(position uint, text string) Editor {
+ if len(text) != 0 {
+ e.insert(int(position), []byte(text))
+ }
+ return e
+}
+
+// PieceChainEditor implements Editor.
+func (e *PieceChainEditor) Delete(offset, length uint) Editor {
+ if length > 0 {
+ e.delete(int(offset), int(length))
+ }
+ return e
+}
+
+// PieceChainEditor implements Editor.
+func (e *PieceChainEditor) Undo() Editor {
+ return e
+}
+
+// PieceChainEditor implements Editor.
+func (e *PieceChainEditor) Redo() Editor {
+ return e
+}
+
+// PieceChainEditor implements Editor.
+func (e *PieceChainEditor) String() string {
+ s := ""
+ for _, piece := range e.pieces {
+ var source []byte
+ if piece.origin {
+ source = e.origin
+ } else {
+ source = e.add
+ }
+
+ s += string(source[piece.offset : piece.offset+piece.length])
+ }
+ return s
+}
+
+// insert inserts the given text at the given position.
+func (e *PieceChainEditor) insert(position int, text []byte) {
+ newPiece := Piece{
+ origin: false,
+ offset: len(e.add),
+ length: len(text),
+ }
+ e.add = append(e.add, text...)
+
+ var (
+ pieceEndsAt int
+ newPieceAdded bool
+ )
+ for idx, piece := range e.pieces {
+ pieceEndsAt += piece.length
+
+ if pieceEndsAt == position {
+ // Insert after the current piece.
+ e.pieces = append(
+ e.pieces[:idx+1],
+ append(
+ []Piece{newPiece},
+ e.pieces[idx+1:]...,
+ )...,
+ )
+
+ newPieceAdded = true
+ break
+ } else if pieceEndsAt > position {
+ // Split the current piece and insert in between.
+ pieceBegin := Piece{
+ origin: piece.origin,
+ offset: piece.offset,
+ length: position - pieceEndsAt + piece.length,
+ }
+ pieceEnd := Piece{
+ origin: piece.origin,
+ offset: piece.offset + position - pieceEndsAt + piece.length,
+ length: pieceEndsAt - position,
+ }
+
+ // Is this bad style?
+ // How can it be improved without creating a new underlying array and copying?
+ e.pieces = append(
+ e.pieces[:idx],
+ append(
+ []Piece{
+ pieceBegin,
+ newPiece,
+ pieceEnd,
+ },
+ e.pieces[idx+1:]...,
+ )...,
+ )
+
+ newPieceAdded = true
+ break
+ }
+ }
+
+ if !newPieceAdded {
+ // Given position is too big, insert at the end.
+ e.pieces = append(e.pieces, newPiece)
+ }
+}
+
+func (e *PieceChainEditor) delete(offset, length int) {
+ var (
+ pieceStartsAt int
+ deleteFromIndex = -1
+ deleteToIndex = -1
+ newPiece1 *Piece
+ newPiece2 *Piece
+ )
+
+ for idx, piece := range e.pieces {
+ if deleteFromIndex == -1 && pieceStartsAt+piece.length > offset {
+ deleteFromIndex = idx
+
+ if offset > pieceStartsAt {
+ newPiece1 = &Piece{
+ origin: piece.origin,
+ offset: piece.offset,
+ length: offset - pieceStartsAt,
+ }
+ }
+ }
+
+ if deleteToIndex == -1 &&
+ (idx == len(e.pieces)-1 || offset+length <= pieceStartsAt+piece.length) {
+ // This is the last piece to be deleted.
+ deleteToIndex = idx
+
+ if offset+length < pieceStartsAt+piece.length {
+ newPieceLength := pieceStartsAt + piece.length - (offset + length)
+
+ newPiece2 = &Piece{
+ origin: piece.origin,
+ offset: piece.offset + piece.length - newPieceLength,
+ length: newPieceLength,
+ }
+ }
+ }
+
+ pieceStartsAt += piece.length
+ }
+
+ if deleteFromIndex != -1 {
+ newPieces := e.pieces[:deleteFromIndex]
+ if newPiece1 != nil {
+ newPieces = append(newPieces, *newPiece1)
+ }
+ if newPiece2 != nil {
+ newPieces = append(newPieces, *newPiece2)
+ }
+ if deleteToIndex != -1 {
+ newPieces = append(newPieces, e.pieces[deleteToIndex+1:]...)
+ }
+ e.pieces = make([]Piece, len(newPieces))
+ copy(e.pieces, newPieces)
+ }
+}
+
+func main() {
+}