README
¶
diff
A difference algorithm package for go.
The algorithm is described by Eugene Myers in "An O(ND) Difference Algorithm and its Variations".
Example
You can use diff.Ints, diff.Runes, diff.ByteStrings, and diff.Bytes
diff.Runes([]rune("sögen"), []rune("mögen")) // returns []Changes{{0,0,1,1}}
or you can implement diff.Data
type MixedInput struct {
A []int
B []string
}
func (m *MixedInput) Equal(i, j int) bool {
return m.A[i] == len(m.B[j])
}
and call
m := &MixedInput{..}
diff.Diff(len(m.A), len(m.B), m)
Also has granularity functions to merge changes that are close by.
diff.Granular(1, diff.ByteStrings("emtire", "umpire")) // returns []Changes{{0,0,3,3}}
Documentation at http://godoc.org/github.com/mb0/diff
Documentation
¶
Overview ¶
Package diff implements a difference algorithm. The algorithm is described in "An O(ND) Difference Algorithm and its Variations", Eugene Myers, Algorithmica Vol. 1 No. 2, 1986, pp. 251-266.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Change ¶
type Change struct {
A, B int // position in input a and b
Del int // delete Del elements from input a
Ins int // insert Ins elements from input b
}
A Change contains one or more deletions or inserts at one position in two sequences.
func ByteStrings ¶
ByteStrings returns the differences of two strings in bytes.
func Diff ¶
Diff returns the differences of data. data.Equal is called repeatedly with 0<=i<n and 0<=j<m
Example ¶
package main
import (
"fmt"
"github.com/mb0/diff"
)
// Diff on inputs with different representations
type MixedInput struct {
A []int
B []string
}
var names map[string]int
func (m *MixedInput) Equal(a, b int) bool {
return m.A[a] == names[m.B[b]]
}
func main() {
names = map[string]int{
"one": 1,
"two": 2,
"three": 3,
}
m := &MixedInput{
[]int{1, 2, 3, 1, 2, 2, 1},
[]string{"three", "two", "one", "two", "one", "three"},
}
changes := diff.Diff(len(m.A), len(m.B), m)
for _, c := range changes {
fmt.Println("change at", c.A, c.B)
}
}
Output: change at 0 0 change at 2 2 change at 5 4 change at 7 5
func Granular ¶
Granular merges neighboring changes smaller than the specified granularity. The changes must be ordered by ascending positions as returned by this package.
Example ¶
package main
import (
"fmt"
"github.com/mb0/diff"
)
func main() {
a := "hElLo!"
b := "hello!"
changes := diff.Granular(5, diff.ByteStrings(a, b)) // ignore small gaps in differences
for l := len(changes) - 1; l >= 0; l-- {
change := changes[l]
b = b[:change.B] + "|" + b[change.B:change.B+change.Ins] + "|" + b[change.B+change.Ins:]
}
fmt.Println(b)
}
Output: h|ell|o!
Source Files