Merge pull request #52 from sergi/remove-the-stack-implementation
Remove the own stack implementation
diff --git a/diffmatchpatch/dmp.go b/diffmatchpatch/dmp.go
index f42a537..4e61821 100644
--- a/diffmatchpatch/dmp.go
+++ b/diffmatchpatch/dmp.go
@@ -849,7 +849,12 @@
// semantically trivial equalities.
func (dmp *DiffMatchPatch) DiffCleanupSemantic(diffs []Diff) []Diff {
changes := false
- equalities := new(Stack) // Stack of indices where equalities are found.
+ // Stack of indices where equalities are found.
+ type equality struct {
+ data int
+ next *equality
+ }
+ var equalities *equality
var lastequality string
// Always equal to diffs[equalities[equalitiesLength - 1]][1]
@@ -861,7 +866,10 @@
for pointer < len(diffs) {
if diffs[pointer].Type == DiffEqual { // Equality found.
- equalities.Push(pointer)
+ equalities = &equality{
+ data: pointer,
+ next: equalities,
+ }
lengthInsertions1 = lengthInsertions2
lengthDeletions1 = lengthDeletions2
lengthInsertions2 = 0
@@ -881,7 +889,7 @@
(len(lastequality) <= difference1) &&
(len(lastequality) <= difference2) {
// Duplicate record.
- insPoint := equalities.Peek().(int)
+ insPoint := equalities.data
diffs = append(
diffs[:insPoint],
append([]Diff{Diff{DiffDelete, lastequality}}, diffs[insPoint:]...)...)
@@ -889,11 +897,13 @@
// Change second copy to insert.
diffs[insPoint+1].Type = DiffInsert
// Throw away the equality we just deleted.
- equalities.Pop()
+ equalities = equalities.next
- if equalities.Len() > 0 {
- equalities.Pop()
- pointer = equalities.Peek().(int)
+ if equalities != nil {
+ equalities = equalities.next
+ }
+ if equalities != nil {
+ pointer = equalities.data
} else {
pointer = -1
}
@@ -1106,7 +1116,11 @@
func (dmp *DiffMatchPatch) DiffCleanupEfficiency(diffs []Diff) []Diff {
changes := false
// Stack of indices where equalities are found.
- equalities := new(Stack)
+ type equality struct {
+ data int
+ next *equality
+ }
+ var equalities *equality
// Always equal to equalities[equalitiesLength-1][1]
lastequality := ""
pointer := 0 // Index of current position.
@@ -1123,13 +1137,16 @@
if len(diffs[pointer].Text) < dmp.DiffEditCost &&
(postIns || postDel) {
// Candidate found.
- equalities.Push(pointer)
+ equalities = &equality{
+ data: pointer,
+ next: equalities,
+ }
preIns = postIns
preDel = postDel
lastequality = diffs[pointer].Text
} else {
// Not a candidate, and can never become one.
- equalities.Clear()
+ equalities = nil
lastequality = ""
}
postIns = false
@@ -1165,24 +1182,29 @@
((preIns && preDel && postIns && postDel) ||
((len(lastequality) < dmp.DiffEditCost/2) && sumPres == 3)) {
+ insPoint := equalities.data
+
// Duplicate record.
- diffs = append(diffs[:equalities.Peek().(int)],
- append([]Diff{Diff{DiffDelete, lastequality}}, diffs[equalities.Peek().(int):]...)...)
+ diffs = append(diffs[:insPoint],
+ append([]Diff{Diff{DiffDelete, lastequality}}, diffs[insPoint:]...)...)
// Change second copy to insert.
- diffs[equalities.Peek().(int)+1].Type = DiffInsert
- equalities.Pop() // Throw away the equality we just deleted.
+ diffs[insPoint+1].Type = DiffInsert
+ // Throw away the equality we just deleted.
+ equalities = equalities.next
lastequality = ""
if preIns && preDel {
// No changes made which could affect previous entry, keep going.
postIns = true
postDel = true
- equalities.Clear()
+ equalities = nil
} else {
- if equalities.Len() > 0 {
- equalities.Pop()
- pointer = equalities.Peek().(int)
+ if equalities != nil {
+ equalities = equalities.next
+ }
+ if equalities != nil {
+ pointer = equalities.data
} else {
pointer = -1
}
diff --git a/diffmatchpatch/dmp_test.go b/diffmatchpatch/dmp_test.go
index a543085..99883bc 100644
--- a/diffmatchpatch/dmp_test.go
+++ b/diffmatchpatch/dmp_test.go
@@ -1562,6 +1562,21 @@
}
}
+func Benchmark_DiffCleanupSemantic(b *testing.B) {
+ s1 := readFile("speedtest1.txt", b)
+ s2 := readFile("speedtest2.txt", b)
+
+ dmp := New()
+
+ diffs := dmp.DiffMain(s1, s2, false)
+
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ dmp.DiffCleanupSemantic(diffs)
+ }
+}
+
func readFile(filename string, b *testing.B) string {
bytes, err := ioutil.ReadFile(filename)
if err != nil {
diff --git a/diffmatchpatch/stack.go b/diffmatchpatch/stack.go
deleted file mode 100644
index 045f5d3..0000000
--- a/diffmatchpatch/stack.go
+++ /dev/null
@@ -1,68 +0,0 @@
-package diffmatchpatch
-
-import (
- "fmt"
-)
-
-// Stack represents a generic stack implementation.
-type Stack struct {
- top *Element
- size int
-}
-
-// Element holds a generic stack element.
-type Element struct {
- value interface{}
- next *Element
-}
-
-// Len returns the stack's length
-func (s *Stack) Len() int {
- return s.size
-}
-
-// Push appends a new element onto the stack
-func (s *Stack) Push(value interface{}) {
- s.top = &Element{value, s.top}
- s.size++
-}
-
-// Pop removes the top element from the stack and return its value
-// If the stack is empty, return nil
-func (s *Stack) Pop() (value interface{}) {
- if s.size > 0 {
- value, s.top = s.top.value, s.top.next
- s.size--
- return
- }
- return nil
-}
-
-// Peek returns the value of the element on the top of the stack
-// but don't remove it. If the stack is empty, return nil
-func (s *Stack) Peek() (value interface{}) {
- if s.size > 0 {
- value = s.top.value
- return
- }
- return -1
-}
-
-// Clear empties the stack
-func (s *Stack) Clear() {
- s.top = nil
- s.size = 0
-}
-
-func main() {
- stack := new(Stack)
-
- stack.Push("Things")
- stack.Push("and")
- stack.Push("Stuff")
-
- for stack.Len() > 0 {
- fmt.Printf("%s ", stack.Pop().(string))
- }
- fmt.Println()
-}
