Интерфейси и nil

Програмиране с Go

Курс във Факултета по Математика и Информатика към СУ

Решение на Piece table от Христо Христов

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

Към профила на Христо Христов

Резултати

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

Код

package main
import (
"bytes"
"math"
)
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
}
// ItskoEditor start //
type ItskoEditor struct {
table *DoublyLinkedList
origin *bytes.Buffer
add *bytes.Buffer
history []*Change
redo []*Change
}
// Constructors //
func NewEditor(origin string) Editor {
newEditor := ItskoEditor{
origin: new(bytes.Buffer),
table: listConstructor(),
add: new(bytes.Buffer),
history: make([]*Change, 0),
redo: make([]*Change, 0),
}
newEditor.origin.WriteString(origin)
originPiece := pieceConstructor(true, 0, len(origin))
editorTableRoot := newEditor.table.root
editorTableTail := newEditor.table.tail
originNode := nodeConstructor(editorTableRoot, editorTableTail, originPiece)
editorTableRoot.child = originNode
editorTableTail.parent = originNode
return newEditor
}
// Additional structs //
type Piece struct {
origin bool
offset int
length int
}
func pieceConstructor(origin bool, offset, length int) *Piece {
piece := new(Piece)
piece.origin = origin
piece.offset = offset
piece.length = length
return piece
}
func (obj *ItskoEditor) generateAddPiece(data string) *Piece {
currentBufferEnd := obj.add.Len()
obj.add.WriteString(data)
return pieceConstructor(false, currentBufferEnd, len(data))
}
type Change struct {
before *DoublyLinkedList
after *DoublyLinkedList
}
func changeConstructor(before *DoublyLinkedList, after *DoublyLinkedList) *Change {
//newChange := new(Change)
//newChange.before = before
//newChange.after = after
return &Change{before: before, after: after}
}
// List- related structs //
type Node struct {
parent *Node
child *Node
data *Piece
}
func nodeConstructor(parent *Node, child *Node, data *Piece) *Node {
newNode := new(Node)
newNode.parent = parent
newNode.child = child
newNode.data = data
return newNode
}
func (node *Node) splitNode(relativePointOfSplit int) (left, right *Node) {
leftPiece := pieceConstructor(node.data.origin, node.data.offset, relativePointOfSplit)
rightPiece := pieceConstructor(
node.data.origin,
node.data.offset+relativePointOfSplit,
node.data.length-relativePointOfSplit)
left = nodeConstructor(node.parent, nil, leftPiece)
node.parent.child = left
right = nodeConstructor(nil, node.child, rightPiece)
node.child.parent = right
return left, right
}
type DoublyLinkedList struct {
root *Node
tail *Node
}
// List Constructors //
func listConstructor() *DoublyLinkedList {
root := new(Node)
tail := new(Node)
root.parent = tail
root.child = tail
tail.parent = root
tail.child = root
root.data = pieceConstructor(false, 0, 0)
tail.data = pieceConstructor(false, 0, math.MaxInt32)
return &DoublyLinkedList{root: root, tail: tail}
}
func listConstructorByGivenNodes(root *Node, tail *Node) *DoublyLinkedList {
return &DoublyLinkedList{root: root, tail: tail}
}
// List Methods //
func (object *DoublyLinkedList) initialize(piece *Piece) {
newNode := new(Node)
newNode.data = piece
object.root.child = newNode
newNode.parent = object.root
object.tail.parent = newNode
newNode.parent = object.tail
}
// ItskoEditor Methods //
func (editor *ItskoEditor) appendNode(currentNode *Node, text string) (initialState, newState *DoublyLinkedList) {
addedNode := nodeConstructor(
currentNode,
currentNode.child,
editor.generateAddPiece(text))
initialState = listConstructorByGivenNodes(currentNode, currentNode)
newState = listConstructorByGivenNodes(currentNode, addedNode)
addedNode.child = currentNode.child //TODO: Delet dis
currentNode.child.parent = addedNode
currentNode.child = addedNode
return initialState, newState
}
func (editor *ItskoEditor) splitAndAppendNode(
currentNode *Node,
positionOfSplit int,
text string,
) (initialState, newState *DoublyLinkedList) {
leftHalf, rightHalf := currentNode.splitNode(positionOfSplit)
centralNode := nodeConstructor(leftHalf, rightHalf, editor.generateAddPiece(text))
leftHalf.child = centralNode
rightHalf.parent = centralNode
initialState = listConstructorByGivenNodes(currentNode, currentNode)
newState = listConstructorByGivenNodes(leftHalf, rightHalf)
return initialState, newState
}
func (editor *ItskoEditor) addToHistory(initialState, newState *DoublyLinkedList) {
editor.history = append(editor.history, changeConstructor(initialState, newState))
}
func (editor *ItskoEditor) applyChange(initialState, goalState *DoublyLinkedList) {
initialState.restoreConnections()
initialRoot, initialTail := initialState.root, initialState.tail
goalRoot, goalTail := goalState.root, goalState.tail
goalRoot.parent = initialRoot.parent
initialRoot.parent.child = goalRoot
goalTail.child = initialTail.child
initialTail.child.parent = goalTail
goalState.restoreConnections()
}
// Interface //
func (obj ItskoEditor) Insert(position uint, text string) Editor {
obj.resetRedo()
var pos int = (int)(position)
var lengthSoFar int = 0
currentNode := obj.table.root
nextNode := currentNode.child
var initialState *DoublyLinkedList
var newState *DoublyLinkedList
for true {
lengthSoFar += currentNode.data.length
if lengthSoFar+nextNode.data.length < pos {
currentNode = nextNode
nextNode = nextNode.child
continue
} else { // simply append the new text
if lengthSoFar == pos || currentNode.child == obj.table.tail {
initialState, newState = obj.appendNode(currentNode, text)
break
} else { // split the current Piece into two and insert the added in between
currentNode = nextNode
initialState, newState = obj.splitAndAppendNode(currentNode, pos-lengthSoFar, text)
break
}
}
}
obj.addToHistory(initialState, newState)
return &obj
}
func (obj *ItskoEditor) resetRedo() {
obj.redo = make([]*Change, 0)
}
func (obj ItskoEditor) Delete(offset, length uint) Editor {
obj.resetRedo()
oldStart, newStart, currentNode, lengthSoFar := obj.generateDeleteStarts((int)(offset))
oldEnd, newEnd := obj.generateDeleteEnds(currentNode, newStart, lengthSoFar, (int)(offset+length))
if newStart != newEnd {
newStart.child = newEnd
newEnd.parent = newStart
}
initialState := listConstructorByGivenNodes(oldStart, oldEnd)
newState := listConstructorByGivenNodes(newStart, newEnd)
obj.applyChange(initialState, newState)
obj.addToHistory(initialState, newState)
return obj
}
func (editor *ItskoEditor) generateDeleteStarts(offset int) (oldStart, newStart, currentNode *Node, lengthSoFar int) {
currentNode = editor.table.root
lengthSoFar = 0
for true {
lengthSoFar += currentNode.data.length
if lengthSoFar+currentNode.child.data.length < offset {
currentNode = currentNode.child
continue
} else {
if lengthSoFar == offset || currentNode.child == editor.table.tail {
oldStart = currentNode
newStart = currentNode
return
} else {
currentNode = currentNode.child
oldStart = currentNode
newStart = nodeConstructor(
currentNode.parent,
nil,
pieceConstructor(
currentNode.data.origin,
currentNode.data.offset,
offset-lengthSoFar,
),
)
currentNode = currentNode.parent
return
}
}
}
return
}
func (editor *ItskoEditor) generateDeleteEnds(
currentNode, newStart *Node,
lengthSoFar, offsetOfEndOfDelete int,
) (oldEnd, newEnd *Node) {
for true {
if lengthSoFar+currentNode.child.data.length < offsetOfEndOfDelete {
currentNode = currentNode.child
lengthSoFar += currentNode.data.length
continue
} else {
if lengthSoFar == offsetOfEndOfDelete || currentNode.child == editor.table.tail {
if newStart == editor.table.root {
}
oldEnd = currentNode
newEnd = newStart
return
} else {
currentNode = currentNode.child
oldEnd = currentNode
newEnd = nodeConstructor(
nil,
currentNode.child,
pieceConstructor(
currentNode.data.origin,
currentNode.data.offset+offsetOfEndOfDelete-lengthSoFar,
lengthSoFar+currentNode.data.length-offsetOfEndOfDelete,
),
)
return
}
}
}
return
}
func (obj ItskoEditor) Undo() Editor {
if len(obj.history) > 0 {
change := obj.history[len(obj.history)-1]
obj.history = obj.history[:len(obj.history)-1]
obj.applyChange(change.after, change.before)
obj.addToRedo(change.before, change.after)
}
return &obj
}
func (editor *ItskoEditor) addToRedo(initialState, newState *DoublyLinkedList) {
editor.redo = append(editor.redo, changeConstructor(initialState, newState))
}
func (obj ItskoEditor) Redo() Editor {
if len(obj.redo) > 0 {
change := obj.redo[len(obj.redo)-1]
obj.redo = obj.redo[:len(obj.redo)-1]
//change.after.restoreConnections()
obj.applyChange(change.before, change.after)
obj.addToHistory(change.before, change.after)
}
return &obj
}
func (state *DoublyLinkedList) restoreConnections() {
tail := state.tail
root := state.root
currentNode := tail
if tail == root {
return
}
currentNode.child.parent = currentNode // TODO: Can be removed
for currentNode != root {
currentNode.parent.child = currentNode
currentNode = currentNode.parent
}
currentNode.parent.child = currentNode
}
func (obj ItskoEditor) String() string {
var actualText bytes.Buffer
currentNode := obj.table.root
stringifiedAddBuffer := obj.add.String()
stringifiedOriginBuffer := obj.origin.String()
for currentNode != obj.table.tail {
bufferOffset := currentNode.data.offset
printLength := currentNode.data.length
var printBuffer *string
if currentNode.data.origin {
printBuffer = &stringifiedOriginBuffer
} else {
printBuffer = &stringifiedAddBuffer
}
actualText.WriteString(
(*printBuffer)[bufferOffset : bufferOffset+printLength])
currentNode = currentNode.child
}
return actualText.String()
}

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

PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.003s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s
PASS
ok  	_/tmp/d20181107-53-19at1rz	0.002s

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

Христо обнови решението на 07.11.2018 13:36 (преди 9 месеца)

package main
-func help() {
-println("pls")
+import (
-}
+ "bytes"
+ "math"
+)
+
+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
+}
+
+// ItskoEditor start //
+type ItskoEditor struct {
+ table *DoublyLinkedList
+ origin *string
+ add *bytes.Buffer
+
+ history []*Change
+ redo []*Change
+}
+
+// Constructors //
+func NewEditor(origin string) Editor {
+ newEditor := ItskoEditor{
+ origin: &origin,
+ table: listConstructor(),
+ add: new(bytes.Buffer),
+ history: make([]*Change, 0),
+ redo: make([]*Change, 0),
+ }
+
+ originPiece := pieceConstructor(true, 0, len(origin))
+
+ editorTableRoot := newEditor.table.root
+ editorTableTail := newEditor.table.tail
+ originNode := nodeConstructor(editorTableRoot, editorTableTail, originPiece)
+
+ editorTableRoot.child = originNode
+ editorTableTail.parent = originNode
+
+ return newEditor
+}
+
+// Additional structs //
+type Piece struct {
+ origin bool
+ offset int
+ length int
+}
+
+func pieceConstructor(origin bool, offset, length int) *Piece {
+ piece := new(Piece)
+
+ piece.origin = origin
+ piece.offset = offset
+ piece.length = length
+
+ return piece
+}
+
+func (obj *ItskoEditor) generateAddPiece(data string) *Piece {
+ currentBufferEnd := obj.add.Len()
+ obj.add.WriteString(data)
+ return pieceConstructor(false, currentBufferEnd, len(data))
+}
+
+type Change struct {
+ before *DoublyLinkedList
+ after *DoublyLinkedList
+}
+
+func changeConstructor(before *DoublyLinkedList, after *DoublyLinkedList) *Change {
+ //newChange := new(Change)
+ //newChange.before = before
+ //newChange.after = after
+
+ return &Change{before: before, after: after}
+}
+
+// List- related structs //
+type Node struct {
+ parent *Node
+ child *Node
+ data *Piece
+}
+
+func nodeConstructor(parent *Node, child *Node, data *Piece) *Node {
+ newNode := new(Node)
+
+ newNode.parent = parent
+ newNode.child = child
+ newNode.data = data
+
+ return newNode
+}
+
+func (node *Node) splitNode(relativePointOfSplit int) (left, right *Node) {
+ leftPiece := pieceConstructor(node.data.origin, node.data.offset, relativePointOfSplit)
+ rightPiece := pieceConstructor(
+ node.data.origin,
+ node.data.offset+relativePointOfSplit,
+ node.data.length-relativePointOfSplit)
+
+ left = nodeConstructor(node.parent, nil, leftPiece)
+ node.parent.child = left
+ right = nodeConstructor(nil, node.child, rightPiece)
+ node.child.parent = right
+ return left, right
+}
+
+type DoublyLinkedList struct {
+ root *Node
+ tail *Node
+}
+
+// List Constructors //
+func listConstructor() *DoublyLinkedList {
+ root := new(Node)
+ tail := new(Node)
+
+ root.parent = tail
+ root.child = tail
+ tail.parent = root
+ tail.child = root
+
+ root.data = pieceConstructor(false, 0, 0)
+ tail.data = pieceConstructor(false, 0, math.MaxInt32)
+
+ return &DoublyLinkedList{root: root, tail: tail}
+}
+
+func listConstructorByGivenNodes(root *Node, tail *Node) *DoublyLinkedList {
+ return &DoublyLinkedList{root: root, tail: tail}
+
+}
+
+// List Methods //
+func (object *DoublyLinkedList) initialize(piece *Piece) {
+ newNode := new(Node)
+ newNode.data = piece
+
+ object.root.child = newNode
+ newNode.parent = object.root
+ object.tail.parent = newNode
+ newNode.parent = object.tail
+}
+
+// ItskoEditor Methods //
+func (editor *ItskoEditor) appendNode(currentNode *Node, text string) (initialState, newState *DoublyLinkedList) {
+ addedNode := nodeConstructor(
+ currentNode,
+ currentNode.child,
+ editor.generateAddPiece(text))
+
+ initialState = listConstructorByGivenNodes(currentNode, currentNode)
+ newState = listConstructorByGivenNodes(currentNode, addedNode)
+
+ addedNode.child = currentNode.child //TODO: Delet dis
+ currentNode.child.parent = addedNode
+ currentNode.child = addedNode
+
+ return initialState, newState
+}
+
+func (editor *ItskoEditor) splitAndAppendNode(
+ currentNode *Node,
+ positionOfSplit int,
+ text string,
+) (initialState, newState *DoublyLinkedList) {
+
+ leftHalf, rightHalf := currentNode.splitNode(positionOfSplit)
+ centralNode := nodeConstructor(leftHalf, rightHalf, editor.generateAddPiece(text))
+ leftHalf.child = centralNode
+ rightHalf.parent = centralNode
+
+ initialState = listConstructorByGivenNodes(currentNode, currentNode)
+ newState = listConstructorByGivenNodes(leftHalf, rightHalf)
+ return initialState, newState
+}
+
+func (editor *ItskoEditor) addToHistory(initialState, newState *DoublyLinkedList) {
+ editor.history = append(editor.history, changeConstructor(initialState, newState))
+}
+
+func (editor *ItskoEditor) applyChange(initialState, goalState *DoublyLinkedList) {
+ initialState.restoreConnections()
+ initialRoot, initialTail := initialState.root, initialState.tail
+ goalRoot, goalTail := goalState.root, goalState.tail
+
+ goalRoot.parent = initialRoot.parent
+ initialRoot.parent.child = goalRoot
+
+ goalTail.child = initialTail.child
+ initialTail.child.parent = goalTail
+ goalState.restoreConnections()
+}
+
+// Interface //
+func (obj ItskoEditor) Insert(position uint, text string) Editor {
+ obj.resetRedo()
+ var pos int = (int)(position)
+ var lengthSoFar int = 0
+ currentNode := obj.table.root
+ nextNode := currentNode.child
+ var initialState *DoublyLinkedList
+ var newState *DoublyLinkedList
+
+ for true {
+ lengthSoFar += currentNode.data.length
+ if lengthSoFar+nextNode.data.length < pos {
+ currentNode = nextNode
+ nextNode = nextNode.child
+ continue
+ } else { // simply append the new text
+ if lengthSoFar == pos || currentNode.child == obj.table.tail {
+ initialState, newState = obj.appendNode(currentNode, text)
+ break
+ } else { // split the current Piece into two and insert the added in between
+ currentNode = nextNode
+ initialState, newState = obj.splitAndAppendNode(currentNode, pos-lengthSoFar, text)
+ break
+ }
+ }
+ }
+ obj.addToHistory(initialState, newState)
+ return &obj
+}
+
+func (obj *ItskoEditor) resetRedo() {
+ obj.redo = make([]*Change, 0)
+}
+
+func (obj ItskoEditor) Delete(offset, length uint) Editor {
+ obj.resetRedo()
+ oldStart, newStart, currentNode, lengthSoFar := obj.generateDeleteStarts((int)(offset))
+ oldEnd, newEnd := obj.generateDeleteEnds(currentNode, newStart, lengthSoFar, (int)(offset+length))
+
+ if newStart != newEnd {
+ newStart.child = newEnd
+ newEnd.parent = newStart
+ }
+
+ initialState := listConstructorByGivenNodes(oldStart, oldEnd)
+ newState := listConstructorByGivenNodes(newStart, newEnd)
+ obj.applyChange(initialState, newState)
+
+ obj.addToHistory(initialState, newState)
+
+ return obj
+}
+
+func (editor *ItskoEditor) generateDeleteStarts(offset int) (oldStart, newStart, currentNode *Node, lengthSoFar int) {
+ currentNode = editor.table.root
+ lengthSoFar = 0
+ for true {
+ lengthSoFar += currentNode.data.length
+ if lengthSoFar+currentNode.child.data.length < offset {
+ currentNode = currentNode.child
+ continue
+ } else {
+ if lengthSoFar == offset || currentNode.child == editor.table.tail {
+ oldStart = currentNode
+ newStart = currentNode
+ return
+ } else {
+ currentNode = currentNode.child
+ oldStart = currentNode
+ newStart = nodeConstructor(
+ currentNode.parent,
+ nil,
+ pieceConstructor(
+ currentNode.data.origin,
+ currentNode.data.offset,
+ offset-lengthSoFar,
+ ),
+ )
+ currentNode = currentNode.parent
+ return
+ }
+ }
+ }
+ return
+}
+
+func (editor *ItskoEditor) generateDeleteEnds(
+ currentNode, newStart *Node,
+ lengthSoFar, offsetOfEndOfDelete int,
+) (oldEnd, newEnd *Node) {
+ for true {
+ if lengthSoFar+currentNode.child.data.length < offsetOfEndOfDelete {
+ currentNode = currentNode.child
+ lengthSoFar += currentNode.data.length
+ continue
+ } else {
+ if lengthSoFar == offsetOfEndOfDelete || currentNode.child == editor.table.tail {
+ if newStart == editor.table.root {
+
+ }
+ oldEnd = currentNode
+ newEnd = newStart
+ return
+ } else {
+ currentNode = currentNode.child
+ oldEnd = currentNode
+ newEnd = nodeConstructor(
+ nil,
+ currentNode.child,
+ pieceConstructor(
+ currentNode.data.origin,
+ currentNode.data.offset+offsetOfEndOfDelete-lengthSoFar,
+ lengthSoFar+currentNode.data.length-offsetOfEndOfDelete,
+ ),
+ )
+ return
+ }
+ }
+ }
+ return
+}
+
+func (obj ItskoEditor) Undo() Editor {
+ if len(obj.history) > 0 {
+ change := obj.history[len(obj.history)-1]
+ obj.history = obj.history[:len(obj.history)-1]
+ obj.applyChange(change.after, change.before)
+ obj.addToRedo(change.before, change.after)
+ }
+ return &obj
+}
+
+func (editor *ItskoEditor) addToRedo(initialState, newState *DoublyLinkedList) {
+ editor.redo = append(editor.redo, changeConstructor(initialState, newState))
+}
+
+func (obj ItskoEditor) Redo() Editor {
+ if len(obj.redo) > 0 {
+ change := obj.redo[len(obj.redo)-1]
+ obj.redo = obj.redo[:len(obj.redo)-1]
+ //change.after.restoreConnections()
+ obj.applyChange(change.before, change.after)
+ obj.addToHistory(change.before, change.after)
+ }
+ return &obj
+}
+
+func (state *DoublyLinkedList) restoreConnections() {
+ tail := state.tail
+ root := state.root
+ currentNode := tail
+
+ if tail == root {
+ return
+ }
+
+ currentNode.child.parent = currentNode // TODO: Can be removed
+
+ for currentNode != root {
+ currentNode.parent.child = currentNode
+ currentNode = currentNode.parent
+ }
+ currentNode.parent.child = currentNode
+}
+
+func (obj ItskoEditor) String() string {
+ var actualText bytes.Buffer
+ currentNode := obj.table.root
+ stringifiedAddBuffer := obj.add.String()
+
+ for currentNode != obj.table.tail {
+ bufferOffset := currentNode.data.offset
+ printLength := currentNode.data.length
+ var printBuffer *string
+ if currentNode.data.origin {
+ printBuffer = obj.origin
+ } else {
+ printBuffer = &stringifiedAddBuffer
+ }
+ actualText.WriteString(
+ (*printBuffer)[bufferOffset : bufferOffset+printLength])
+ currentNode = currentNode.child
+ }
+ return actualText.String()
+}

Христо обнови решението на 07.11.2018 15:37 (преди 9 месеца)

package main
import (
"bytes"
"math"
)
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
}
// ItskoEditor start //
type ItskoEditor struct {
table *DoublyLinkedList
- origin *string
+ origin *bytes.Buffer
add *bytes.Buffer
history []*Change
redo []*Change
}
// Constructors //
func NewEditor(origin string) Editor {
newEditor := ItskoEditor{
- origin: &origin,
+ origin: new(bytes.Buffer),
table: listConstructor(),
add: new(bytes.Buffer),
history: make([]*Change, 0),
redo: make([]*Change, 0),
}
+ newEditor.origin.WriteString(origin)
+
originPiece := pieceConstructor(true, 0, len(origin))
editorTableRoot := newEditor.table.root
editorTableTail := newEditor.table.tail
originNode := nodeConstructor(editorTableRoot, editorTableTail, originPiece)
editorTableRoot.child = originNode
editorTableTail.parent = originNode
return newEditor
}
// Additional structs //
type Piece struct {
origin bool
offset int
length int
}
func pieceConstructor(origin bool, offset, length int) *Piece {
piece := new(Piece)
piece.origin = origin
piece.offset = offset
piece.length = length
return piece
}
func (obj *ItskoEditor) generateAddPiece(data string) *Piece {
currentBufferEnd := obj.add.Len()
obj.add.WriteString(data)
return pieceConstructor(false, currentBufferEnd, len(data))
}
type Change struct {
before *DoublyLinkedList
after *DoublyLinkedList
}
func changeConstructor(before *DoublyLinkedList, after *DoublyLinkedList) *Change {
//newChange := new(Change)
//newChange.before = before
//newChange.after = after
return &Change{before: before, after: after}
}
// List- related structs //
type Node struct {
parent *Node
child *Node
data *Piece
}
func nodeConstructor(parent *Node, child *Node, data *Piece) *Node {
newNode := new(Node)
newNode.parent = parent
newNode.child = child
newNode.data = data
return newNode
}
func (node *Node) splitNode(relativePointOfSplit int) (left, right *Node) {
leftPiece := pieceConstructor(node.data.origin, node.data.offset, relativePointOfSplit)
rightPiece := pieceConstructor(
node.data.origin,
node.data.offset+relativePointOfSplit,
node.data.length-relativePointOfSplit)
left = nodeConstructor(node.parent, nil, leftPiece)
node.parent.child = left
right = nodeConstructor(nil, node.child, rightPiece)
node.child.parent = right
return left, right
}
type DoublyLinkedList struct {
root *Node
tail *Node
}
// List Constructors //
func listConstructor() *DoublyLinkedList {
root := new(Node)
tail := new(Node)
root.parent = tail
root.child = tail
tail.parent = root
tail.child = root
root.data = pieceConstructor(false, 0, 0)
tail.data = pieceConstructor(false, 0, math.MaxInt32)
return &DoublyLinkedList{root: root, tail: tail}
}
func listConstructorByGivenNodes(root *Node, tail *Node) *DoublyLinkedList {
return &DoublyLinkedList{root: root, tail: tail}
}
// List Methods //
func (object *DoublyLinkedList) initialize(piece *Piece) {
newNode := new(Node)
newNode.data = piece
object.root.child = newNode
newNode.parent = object.root
object.tail.parent = newNode
newNode.parent = object.tail
}
// ItskoEditor Methods //
func (editor *ItskoEditor) appendNode(currentNode *Node, text string) (initialState, newState *DoublyLinkedList) {
addedNode := nodeConstructor(
currentNode,
currentNode.child,
editor.generateAddPiece(text))
initialState = listConstructorByGivenNodes(currentNode, currentNode)
newState = listConstructorByGivenNodes(currentNode, addedNode)
addedNode.child = currentNode.child //TODO: Delet dis
currentNode.child.parent = addedNode
currentNode.child = addedNode
return initialState, newState
}
func (editor *ItskoEditor) splitAndAppendNode(
currentNode *Node,
positionOfSplit int,
text string,
) (initialState, newState *DoublyLinkedList) {
leftHalf, rightHalf := currentNode.splitNode(positionOfSplit)
centralNode := nodeConstructor(leftHalf, rightHalf, editor.generateAddPiece(text))
leftHalf.child = centralNode
rightHalf.parent = centralNode
initialState = listConstructorByGivenNodes(currentNode, currentNode)
newState = listConstructorByGivenNodes(leftHalf, rightHalf)
return initialState, newState
}
func (editor *ItskoEditor) addToHistory(initialState, newState *DoublyLinkedList) {
editor.history = append(editor.history, changeConstructor(initialState, newState))
}
func (editor *ItskoEditor) applyChange(initialState, goalState *DoublyLinkedList) {
initialState.restoreConnections()
initialRoot, initialTail := initialState.root, initialState.tail
goalRoot, goalTail := goalState.root, goalState.tail
goalRoot.parent = initialRoot.parent
initialRoot.parent.child = goalRoot
goalTail.child = initialTail.child
initialTail.child.parent = goalTail
goalState.restoreConnections()
}
// Interface //
func (obj ItskoEditor) Insert(position uint, text string) Editor {
obj.resetRedo()
var pos int = (int)(position)
var lengthSoFar int = 0
currentNode := obj.table.root
nextNode := currentNode.child
var initialState *DoublyLinkedList
var newState *DoublyLinkedList
for true {
lengthSoFar += currentNode.data.length
if lengthSoFar+nextNode.data.length < pos {
currentNode = nextNode
nextNode = nextNode.child
continue
} else { // simply append the new text
if lengthSoFar == pos || currentNode.child == obj.table.tail {
initialState, newState = obj.appendNode(currentNode, text)
break
} else { // split the current Piece into two and insert the added in between
currentNode = nextNode
initialState, newState = obj.splitAndAppendNode(currentNode, pos-lengthSoFar, text)
break
}
}
}
obj.addToHistory(initialState, newState)
return &obj
}
func (obj *ItskoEditor) resetRedo() {
obj.redo = make([]*Change, 0)
}
func (obj ItskoEditor) Delete(offset, length uint) Editor {
obj.resetRedo()
oldStart, newStart, currentNode, lengthSoFar := obj.generateDeleteStarts((int)(offset))
oldEnd, newEnd := obj.generateDeleteEnds(currentNode, newStart, lengthSoFar, (int)(offset+length))
if newStart != newEnd {
newStart.child = newEnd
newEnd.parent = newStart
}
initialState := listConstructorByGivenNodes(oldStart, oldEnd)
newState := listConstructorByGivenNodes(newStart, newEnd)
obj.applyChange(initialState, newState)
obj.addToHistory(initialState, newState)
return obj
}
func (editor *ItskoEditor) generateDeleteStarts(offset int) (oldStart, newStart, currentNode *Node, lengthSoFar int) {
currentNode = editor.table.root
lengthSoFar = 0
for true {
lengthSoFar += currentNode.data.length
if lengthSoFar+currentNode.child.data.length < offset {
currentNode = currentNode.child
continue
} else {
if lengthSoFar == offset || currentNode.child == editor.table.tail {
oldStart = currentNode
newStart = currentNode
return
} else {
currentNode = currentNode.child
oldStart = currentNode
newStart = nodeConstructor(
currentNode.parent,
nil,
pieceConstructor(
currentNode.data.origin,
currentNode.data.offset,
offset-lengthSoFar,
),
)
currentNode = currentNode.parent
return
}
}
}
return
}
func (editor *ItskoEditor) generateDeleteEnds(
currentNode, newStart *Node,
lengthSoFar, offsetOfEndOfDelete int,
) (oldEnd, newEnd *Node) {
for true {
if lengthSoFar+currentNode.child.data.length < offsetOfEndOfDelete {
currentNode = currentNode.child
lengthSoFar += currentNode.data.length
continue
} else {
if lengthSoFar == offsetOfEndOfDelete || currentNode.child == editor.table.tail {
if newStart == editor.table.root {
}
oldEnd = currentNode
newEnd = newStart
return
} else {
currentNode = currentNode.child
oldEnd = currentNode
newEnd = nodeConstructor(
nil,
currentNode.child,
pieceConstructor(
currentNode.data.origin,
currentNode.data.offset+offsetOfEndOfDelete-lengthSoFar,
lengthSoFar+currentNode.data.length-offsetOfEndOfDelete,
),
)
return
}
}
}
return
}
func (obj ItskoEditor) Undo() Editor {
if len(obj.history) > 0 {
change := obj.history[len(obj.history)-1]
obj.history = obj.history[:len(obj.history)-1]
obj.applyChange(change.after, change.before)
obj.addToRedo(change.before, change.after)
}
return &obj
}
func (editor *ItskoEditor) addToRedo(initialState, newState *DoublyLinkedList) {
editor.redo = append(editor.redo, changeConstructor(initialState, newState))
}
func (obj ItskoEditor) Redo() Editor {
if len(obj.redo) > 0 {
change := obj.redo[len(obj.redo)-1]
obj.redo = obj.redo[:len(obj.redo)-1]
//change.after.restoreConnections()
obj.applyChange(change.before, change.after)
obj.addToHistory(change.before, change.after)
}
return &obj
}
func (state *DoublyLinkedList) restoreConnections() {
tail := state.tail
root := state.root
currentNode := tail
if tail == root {
return
}
currentNode.child.parent = currentNode // TODO: Can be removed
for currentNode != root {
currentNode.parent.child = currentNode
currentNode = currentNode.parent
}
currentNode.parent.child = currentNode
}
func (obj ItskoEditor) String() string {
var actualText bytes.Buffer
currentNode := obj.table.root
stringifiedAddBuffer := obj.add.String()
+ stringifiedOriginBuffer := obj.origin.String()
for currentNode != obj.table.tail {
bufferOffset := currentNode.data.offset
printLength := currentNode.data.length
var printBuffer *string
if currentNode.data.origin {
- printBuffer = obj.origin
+ printBuffer = &stringifiedOriginBuffer
} else {
printBuffer = &stringifiedAddBuffer
}
actualText.WriteString(
(*printBuffer)[bufferOffset : bufferOffset+printLength])
currentNode = currentNode.child
}
return actualText.String()
}