Николай обнови решението на 04.11.2018 15:07 (преди 9 месеца)
+package main
+
+import "strings"
+
+type Editor interface {
+ Insert(position uint, text string) Editor
+ Delete(offset, length uint) Editor
+ Undo() Editor
+ Redo() Editor
+ String() string
+}
+
+type piece struct {
+ origin bool
+ offset int
+ length int
+}
+
+type change struct {
+ insert bool
+ pieces []piece
+ startIdx int
+ startOffset int
+ endIdx int
+ endOffset int
+ appendEnd bool
+}
+
+type PieceTable struct {
+ origin []byte
+ add []byte
+ chain []piece
+ changes []change
+ changeIdx int
+}
+
+func (pt PieceTable) Insert(position uint, text string) Editor {
+ newText := []byte(text)
+
+ if len(newText) == 0 {
+ c := change{}
+ pt.addChange(&c)
+ return pt
+ }
+
+ var idx, offset int
+ var found bool
+ pos := 0
+ for i, piece := range pt.chain {
+ if int(position) >= pos && int(position) < pos+piece.length {
+ idx = i
+ offset = int(position) - pos
+ found = true
+ break
+ }
+
+ pos += piece.length
+ }
+
+ if !found {
+ idx = len(pt.chain)
+ }
+
+ newPieces := make([]piece, 0, 3)
+
+ if offset > 0 {
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[idx].origin,
+ offset: pt.chain[idx].offset,
+ length: offset,
+ })
+ }
+
+ newPiece := piece{
+ origin: false,
+ offset: len(pt.add),
+ length: len(newText),
+ }
+ newPieces = append(newPieces, newPiece)
+
+ if found {
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[idx].origin,
+ offset: pt.chain[idx].offset + offset,
+ length: pt.chain[idx].length - offset,
+ })
+ }
+
+ var newChain []piece
+ if found {
+ newChain = append(pt.chain[0:idx], append(newPieces, pt.chain[idx+1:]...)...)
+ } else {
+ newChain = append(pt.chain[0:idx], newPieces...)
+ }
+
+ pt.add = append(pt.add, newText...)
+ pt.chain = newChain
+
+ c := change{
+ insert: true,
+ pieces: []piece{newPiece},
+ startIdx: idx,
+ startOffset: offset,
+ }
+ pt.addChange(&c)
+
+ return pt
+}
+
+func (pt PieceTable) Delete(offset, length uint) Editor {
+ if length == 0 {
+ c := change{}
+ pt.addChange(&c)
+ return pt
+ }
+
+ var startIdx, startOffset, endIdx, endOffset int
+ var startFound, endFound bool
+ end := offset + length
+ pos := 0
+ for i, piece := range pt.chain {
+ if int(offset) >= pos && int(offset) < pos+piece.length {
+ startIdx = i
+ startOffset = int(offset) - pos
+ startFound = true
+ }
+
+ if int(end) >= pos && int(end) < pos+piece.length {
+ endIdx = i
+ endOffset = int(end) - pos
+ endFound = true
+ break
+ }
+
+ pos += piece.length
+ }
+
+ if !startFound {
+ // add dummy change
+ c := change{}
+ pt.addChange(&c)
+ return pt
+ }
+
+ if !endFound {
+ endIdx = len(pt.chain) - 1
+ endOffset = pt.chain[endIdx].length
+ }
+
+ deletedPieces := make([]piece, 0, endIdx-startIdx+1)
+ if startIdx == endIdx {
+ deletedPieces = append(deletedPieces, piece{
+ origin: pt.chain[startIdx].origin,
+ offset: pt.chain[startIdx].offset + startOffset,
+ length: endOffset - startOffset,
+ })
+ } else {
+ deletedPieces = append(deletedPieces, piece{
+ origin: pt.chain[startIdx].origin,
+ offset: pt.chain[startIdx].offset + startOffset,
+ length: pt.chain[startIdx].length - startOffset,
+ })
+ deletedPieces = append(deletedPieces, pt.chain[startIdx+1:endIdx]...)
+ deletedPieces = append(deletedPieces, piece{
+ origin: pt.chain[endIdx].origin,
+ offset: pt.chain[endIdx].offset,
+ length: endOffset,
+ })
+ }
+
+ newPieces := make([]piece, 0, 2)
+ if startOffset > 0 {
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[startIdx].origin,
+ offset: pt.chain[startIdx].offset,
+ length: startOffset,
+ })
+ }
+ appendEnd := false
+ if pt.chain[endIdx].length-endOffset > 0 {
+ appendEnd = true
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[endIdx].origin,
+ offset: pt.chain[endIdx].offset + endOffset,
+ length: pt.chain[endIdx].length - endOffset,
+ })
+ }
+
+ newChain := append(pt.chain[0:startIdx], append(newPieces, pt.chain[endIdx+1:]...)...)
+ pt.chain = newChain
+
+ c := change{
+ insert: false,
+ pieces: deletedPieces,
+ startIdx: startIdx,
+ startOffset: startOffset,
+ endIdx: endIdx,
+ endOffset: endOffset,
+ appendEnd: appendEnd,
+ }
+ pt.addChange(&c)
+
+ return pt
+}
+
+func (pt *PieceTable) addChange(change *change) {
+ pt.changeIdx += 1
+ pt.changes = pt.changes[0:pt.changeIdx]
+ pt.changes = append(pt.changes, *change)
+}
+
+func (pt PieceTable) Undo() Editor {
+ if pt.changeIdx == -1 {
+ return pt
+ }
+
+ c := &pt.changes[pt.changeIdx]
+ if c.insert {
+ if c.startOffset == 0 {
+ pt.chain = append(pt.chain[0:c.startIdx], pt.chain[c.startIdx+1:]...)
+ } else {
+ oldPiece := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: pt.chain[c.startIdx].length + pt.chain[c.startIdx+2].length,
+ }
+ pt.chain = append(pt.chain[0:c.startIdx], append([]piece{oldPiece}, pt.chain[c.startIdx+3:]...)...)
+ }
+ } else {
+ if c.startIdx == c.endIdx {
+ if c.startOffset > 0 && c.appendEnd {
+ oldPiece := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: pt.chain[c.startIdx].length + (c.endOffset - c.startOffset) + pt.chain[c.startIdx+1].length,
+ }
+ pt.chain = append(pt.chain[0:c.startIdx], append([]piece{oldPiece}, pt.chain[c.endIdx+2:]...)...)
+ } else if c.startOffset > 0 {
+ oldPiece := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: pt.chain[c.startIdx].length + (c.endOffset - c.startOffset),
+ }
+ pt.chain = append(pt.chain[0:c.startIdx], append([]piece{oldPiece}, pt.chain[c.endIdx+1:]...)...)
+ } else if c.startOffset == 0 && c.appendEnd {
+ oldPiece := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset - c.endOffset,
+ length: pt.chain[c.startIdx].length + c.endOffset,
+ }
+ pt.chain = append(pt.chain[0:c.startIdx], append([]piece{oldPiece}, pt.chain[c.endIdx+1:]...)...)
+ } else {
+ pt.chain = append(pt.chain[0:c.startIdx], append(c.pieces, pt.chain[c.startIdx:]...)...)
+ }
+ } else {
+ if c.startOffset > 0 && c.appendEnd {
+ left := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: pt.chain[c.startIdx].length + c.pieces[0].length,
+ }
+ right := piece{
+ origin: pt.chain[c.startIdx+1].origin,
+ offset: pt.chain[c.startIdx+1].offset - c.endOffset,
+ length: pt.chain[c.startIdx+1].length + c.endOffset,
+ }
+
+ // pt.chain[0:c.startIdx] + left + c.pieces[1:len(c.pieces)-1] + right + pt.chain[c.startIdx+2:]
+ oldPieces := make([]piece, 0, len(c.pieces))
+ oldPieces = append(oldPieces, left)
+ oldPieces = append(oldPieces, c.pieces[1:len(c.pieces)-1]...)
+ oldPieces = append(oldPieces, right)
+ pt.chain = append(pt.chain[0:c.startIdx], append(oldPieces, pt.chain[c.startIdx+2:]...)...)
+ } else if c.startOffset > 0 {
+ left := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: pt.chain[c.startIdx].length + c.pieces[0].length,
+ }
+
+ // pt.chain[0:c.startIdx] + left + c.pieces[1:] + pt.chain[c.startIdx+1:]
+ oldPieces := make([]piece, 0, len(c.pieces))
+ oldPieces = append(oldPieces, left)
+ oldPieces = append(oldPieces, c.pieces[1:]...)
+ pt.chain = append(pt.chain[0:c.startIdx], append(oldPieces, pt.chain[c.startIdx+1:]...)...)
+ } else if c.startOffset == 0 && c.appendEnd {
+ right := piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset - c.endOffset,
+ length: pt.chain[c.startIdx].length + c.endOffset,
+ }
+
+ // pt.chain[0:c.startIdx] + c.pieces[:len(c.pieces)-1] + right + pt.chain[c.startIdx+1:]
+ oldPieces := make([]piece, 0, len(c.pieces))
+ oldPieces = append(oldPieces, c.pieces[:len(c.pieces)-1]...)
+ oldPieces = append(oldPieces, right)
+ pt.chain = append(pt.chain[0:c.startIdx], append(oldPieces, pt.chain[c.startIdx+1:]...)...)
+ } else {
+ pt.chain = append(pt.chain[0:c.startIdx], append(c.pieces, pt.chain[c.startIdx:]...)...)
+ }
+ }
+ }
+
+ pt.changeIdx -= 1
+ return pt
+}
+
+func (pt PieceTable) Redo() Editor {
+ if pt.changeIdx+1 >= len(pt.changes) {
+ return pt
+ }
+
+ pt.changeIdx += 1
+ c := &pt.changes[pt.changeIdx]
+ if c.insert {
+ found := c.startIdx != len(pt.chain)
+ newPieces := make([]piece, 0, 3)
+
+ if c.startOffset > 0 {
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: c.startOffset,
+ })
+ }
+
+ newPieces = append(newPieces, c.pieces...)
+
+ if found {
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset + c.startOffset,
+ length: pt.chain[c.startIdx].length - c.startOffset,
+ })
+ }
+
+ var newChain []piece
+ if found {
+ newChain = append(pt.chain[0:c.startIdx], append(newPieces, pt.chain[c.startIdx+1:]...)...)
+ } else {
+ newChain = append(pt.chain[0:c.startIdx], newPieces...)
+ }
+
+ pt.chain = newChain
+ } else {
+ newPieces := make([]piece, 0, 2)
+ if c.startOffset > 0 {
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[c.startIdx].origin,
+ offset: pt.chain[c.startIdx].offset,
+ length: c.startOffset,
+ })
+ }
+ newPieces = append(newPieces, piece{
+ origin: pt.chain[c.endIdx].origin,
+ offset: pt.chain[c.endIdx].offset + c.endOffset,
+ length: pt.chain[c.endIdx].length - c.endOffset,
+ })
+
+ newChain := append(pt.chain[0:c.startIdx], append(newPieces, pt.chain[c.endIdx+1:]...)...)
+ pt.chain = newChain
+ }
+
+ return pt
+}
+
+func (pt PieceTable) String() string {
+ var buffer strings.Builder
+ for _, piece := range pt.chain {
+ if piece.origin {
+ buffer.WriteString(string(pt.origin[piece.offset : piece.offset+piece.length]))
+ } else {
+ buffer.WriteString(string(pt.add[piece.offset : piece.offset+piece.length]))
+ }
+ }
+ return buffer.String()
+}
+
+func NewEditor(text string) Editor {
+ origin := []byte(text)
+ return PieceTable{
+ origin: origin,
+ add: nil,
+ chain: []piece{
+ piece{
+ origin: true,
+ offset: 0,
+ length: len(origin),
+ },
+ },
+ changes: nil,
+ changeIdx: -1,
+ }
+}