Мирослав обнови решението на 04.11.2018 19:27 (преди 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 pieceTable []*piece
+
+func (pt *pieceTable) InsertAt(i int, p ...*piece) {
+ if i < 0 || i > len(*pt) {
+ return
+ }
+ *pt = append((*pt)[:i], append(p, (*pt)[i:]...)...)
+}
+
+func (pt *pieceTable) RemoveAt(i int) {
+ if i < 0 || i > len(*pt) {
+ return
+ }
+ copy((*pt)[i:], (*pt)[i+1:])
+ (*pt)[len(*pt)-1] = nil
+ *pt = (*pt)[:len(*pt)-1]
+}
+
+type piece struct {
+ origin bool
+ offset int
+ length int
+}
+
+func newPiece(origin bool, offset, length int) *piece {
+ return &piece{
+ origin: origin,
+ offset: offset,
+ length: length,
+ }
+}
+
+type addBuffer []byte
+
+type action struct {
+ apply func(*pieceEditor)
+ revert func(*pieceEditor)
+}
+
+var emptyAction = action{
+ apply: func(*pieceEditor) {},
+ revert: func(*pieceEditor) {},
+}
+
+func newAction(apply, revert func(*pieceEditor)) action {
+ return action{
+ apply: apply,
+ revert: revert,
+ }
+}
+
+type actionStack struct {
+ actions []action
+ pos int
+}
+
+func (as *actionStack) Push(a action) action {
+ if as.pos != len(as.actions) {
+ // not at the end, overwrite all others
+ as.actions = as.actions[:as.pos]
+ }
+ as.actions = append(as.actions, a)
+ as.pos++
+ return a
+}
+
+func (as *actionStack) Pop() action {
+ if as.pos == 0 {
+ return emptyAction
+ }
+ as.pos--
+ return as.actions[as.pos]
+}
+
+func (as *actionStack) Undo(pe *pieceEditor) {
+ a := as.Pop()
+ a.revert(pe)
+}
+
+func (as *actionStack) Redo(pe *pieceEditor) {
+ if as.pos == len(as.actions) {
+ return
+ }
+ as.actions[as.pos].apply(pe)
+ as.pos++
+}
+
+type pieceEditor struct {
+ oBuf string
+ aBuf addBuffer
+ pTab pieceTable
+
+ sLen int
+ actions *actionStack
+}
+
+func (pe *pieceEditor) Insert(position uint, text string) Editor {
+ if text == "" {
+ return pe
+ }
+
+ pos := int(position)
+ insPos, insLen, insInd := len(pe.aBuf), len(text), 0
+ pe.aBuf = append(pe.aBuf, addBuffer(text)...)
+ if pos >= pe.sLen {
+ insInd = len(pe.pTab)
+ pos = pe.sLen
+ }
+ if pos == 0 || pos == pe.sLen {
+ a := pe.actions.Push(newAction(
+ func(pe *pieceEditor) {
+ pe.pTab.InsertAt(insInd, newPiece(false, insPos, insLen))
+ pe.sLen += insLen
+ },
+ func(pe *pieceEditor) {
+ pe.sLen -= insLen
+ pe.pTab.RemoveAt(insInd)
+ },
+ ))
+ a.apply(pe)
+ return pe
+ }
+
+ // find the correct place to insert in piece table
+ lenSum := 0
+ for _, p := range pe.pTab {
+ if lenSum >= pos {
+ break
+ }
+ insInd++
+ lenSum += p.length
+ }
+
+ // if the position doesn't intersect with piece just add it
+ if lenSum == pos {
+ a := pe.actions.Push(newAction(
+ func(pe *pieceEditor) {
+ pe.pTab.InsertAt(insInd, newPiece(false, insPos, insLen))
+ pe.sLen += insLen
+ },
+ func(pe *pieceEditor) {
+ pe.sLen -= insLen
+ pe.pTab.RemoveAt(insInd)
+ },
+ ))
+ a.apply(pe)
+ return pe
+ }
+
+ // if position intersects with piece we need to split it like so:
+ // Define piece as a vector with the following base: p(offset,len)
+ // => p(off, len) = p1(off, len-(lenSum-pos)) + p2(off+p1.len, lenSum-pos)
+ // The new sequence in piece table should be: [ p1, newPiece, p2 ]
+ breakLen := lenSum - pos
+ fpOff, fpLen := pe.pTab[insInd-1].offset, pe.pTab[insInd-1].length-breakLen
+ spOff, spLen := pe.pTab[insInd-1].offset+fpLen, breakLen
+ sOff, sLen := pe.pTab[insInd-1].offset, pe.pTab[insInd-1].length
+ a := pe.actions.Push(newAction(
+ func(pe *pieceEditor) {
+ pe.pTab[insInd-1].offset = fpOff
+ pe.pTab[insInd-1].length = fpLen
+ pe.pTab.InsertAt(insInd,
+ newPiece(false, insPos, insLen),
+ newPiece(pe.pTab[insInd-1].origin, spOff, spLen),
+ )
+ pe.sLen += insLen
+ },
+ func(pe *pieceEditor) {
+ pe.sLen -= insLen
+ pe.pTab.RemoveAt(insInd)
+ pe.pTab.RemoveAt(insInd)
+ pe.pTab[insInd-1].offset = sOff
+ pe.pTab[insInd-1].length = sLen
+ },
+ ))
+ a.apply(pe)
+ return pe
+}
+
+func (pe *pieceEditor) Delete(offset, length uint) Editor {
+ if length == 0 {
+ return pe
+ }
+
+ off, delLen := int(offset), int(length)
+ delInd, lenSum := 0, 0
+
+ // find the correct deletion place in piece table
+ for _, p := range pe.pTab {
+ if lenSum >= off {
+ break
+ }
+ delInd++
+ lenSum += p.length
+ }
+ if off > lenSum {
+ return pe
+ }
+
+ var applies []func(*pieceEditor)
+ var reverts []func(*pieceEditor)
+
+ // if previous piece intersects with the deletion area it must be shortened
+ // there are three cases:
+ // 1. The deletion area is completely within the piece. In that case we
+ // should split the piece in three:
+ // p(off,len) = p(off,delP.off-off) + delP + p(delP.off+delP.len, off+len-(delP.off+delP.len))
+ // 2. The deletion area ends at the same place as the last piece:
+ // - 2.1: The deletion area starts at the same place as the piece:
+ // In that case we should just remove the whole piece.
+ // - 2.2: The deletion area doesn't start at the same place as the piece:
+ // In that case we should set the length of the piece to `p.off = delP.off - p.off`.
+ // - If either `1`, or `2` is valid, then this is the only action we need to execute and it is ok to return.
+ // - If neither are valid, then we should shorten the length of last piece with `lenSum-delP.off`
+ // and continue with processing the next pieces.
+ if lenSum > off {
+ lastPiece := pe.pTab[delInd-1]
+ if off+delLen < lastPiece.offset+lastPiece.length {
+ a := pe.actions.Push(newAction(
+ func(pe *pieceEditor) {
+ pe.pTab.InsertAt(delInd, newPiece(
+ lastPiece.origin,
+ off+delLen,
+ lastPiece.offset+lastPiece.length-off-delLen,
+ ))
+ lastPiece.length = off - lastPiece.offset
+ },
+ func() func(*pieceEditor) {
+ oldLen := lastPiece.length
+ return func(pe *pieceEditor) {
+ lastPiece.length = oldLen
+ pe.pTab.RemoveAt(delInd)
+ }
+ }(),
+ ))
+ a.apply(pe)
+ return pe
+ }
+ if off+delLen == lastPiece.offset+lastPiece.length {
+ var a action
+ if off == lastPiece.offset {
+ a = newAction(
+ func(pe *pieceEditor) {
+ pe.pTab.RemoveAt(delInd - 1)
+ },
+ func() func(*pieceEditor) {
+ pc := pe.pTab[delInd-1]
+ return func(pe *pieceEditor) {
+ pe.pTab.InsertAt(delInd-1, pc)
+ }
+ }(),
+ )
+ } else {
+ a = newAction(
+ func(pe *pieceEditor) {
+ lastPiece.length -= off - lastPiece.offset
+ },
+ func() func(*pieceEditor) {
+ oldLen := lastPiece.length
+ return func(pe *pieceEditor) {
+ lastPiece.length = oldLen
+ }
+ }(),
+ )
+ }
+ pe.actions.Push(a).apply(pe)
+ return pe
+ }
+
+ breakOff := lenSum - off
+ applies = append(applies, func(pe *pieceEditor) {
+ lastPiece.length -= breakOff
+ pe.sLen -= breakOff
+ })
+ reverts = append(reverts, func(pe *pieceEditor) {
+ pe.sLen += breakOff
+ lastPiece.length += breakOff
+ })
+ delLen -= breakOff
+ }
+
+ // Continue to process pieces until the desired delP.len is reached.
+ // Discard all pieces that you pass by and shorten the last one.
+ i := 0
+ for delLen > 0 && delInd+i < len(pe.pTab) {
+ if delLen < pe.pTab[delInd+i].length {
+ applies = append(applies, func() func(*pieceEditor) {
+ dL := delLen
+ return func(pe *pieceEditor) {
+ pe.pTab[delInd].offset += dL
+ pe.pTab[delInd].length -= dL
+ pe.sLen -= dL
+ }
+ }())
+ reverts = append(reverts, func() func(*pieceEditor) {
+ dL := delLen
+ return func(pe *pieceEditor) {
+ pe.sLen += dL
+ pe.pTab[delInd].length += dL
+ pe.pTab[delInd].offset -= dL
+ }
+ }())
+ break
+ }
+ applies = append(applies, func(pe *pieceEditor) {
+ pe.sLen -= pe.pTab[delInd].length
+ pe.pTab.RemoveAt(delInd)
+ })
+ reverts = append(reverts, func() func(*pieceEditor) {
+ pc := pe.pTab[delInd+i]
+ return func(pe *pieceEditor) {
+ pe.pTab.InsertAt(delInd, pc)
+ pe.sLen += pc.length
+ }
+ }())
+ delLen -= pe.pTab[delInd+i].length
+ i++
+ }
+
+ a := pe.actions.Push(newAction(
+ func(pe *pieceEditor) {
+ for _, apply := range applies {
+ apply(pe)
+ }
+ },
+ func(pe *pieceEditor) {
+ for i := len(reverts) - 1; i >= 0; i-- {
+ reverts[i](pe)
+ }
+ },
+ ))
+ a.apply(pe)
+ return pe
+}
+
+func (pe *pieceEditor) Undo() Editor {
+ pe.actions.Undo(pe)
+ return pe
+}
+
+func (pe *pieceEditor) Redo() Editor {
+ pe.actions.Redo(pe)
+ return pe
+}
+
+func (pe *pieceEditor) String() string {
+ sb := strings.Builder{}
+ for _, p := range pe.pTab {
+ if p.origin {
+ sb.WriteString(pe.oBuf[p.offset : p.offset+p.length])
+ continue
+ }
+ sb.Write(pe.aBuf[p.offset : p.offset+p.length])
+ }
+ return sb.String()
+}
+
+func NewEditor(text string) Editor {
+ pe := &pieceEditor{
+ oBuf: text,
+ pTab: []*piece{newPiece(true, 0, len(text))},
+ sLen: len(text),
+ actions: new(actionStack),
+ }
+ return pe
+}