gonp

README

gonp

gonp is a diff algorithm implementation in Go.

Algorithm

The algorithm gonp uses is based on "An O(NP) Sequence Comparison Algorithm" by described by Sun Wu, Udi Manber and Gene Myers. An O(NP) Sequence Comparison Algorithm(following, Wu's O(NP) Algorithm) is the efficient algorithm for comparing two sequences.

Computational complexity

The computational complexity of Wu's O(NP) Algorithm is averagely O(N+PD), in the worst case, is O(NP).

Getting started

string difference

diff := gonp.New([]rune("abc"), []rune("abd"))
diff.Compose()
ed := diff.Editdistance() // ed is 2
lcs := diff.Lcs() // lcs is "ab"

ses := diff.Ses()
// ses is []SesElem{
//        {e: 'a', t: Common},
//        {e: 'b', t: Common},
//        {e: 'c', t: Delete},
//        {e: 'd', t: Add},
//        }

int array difference

diff := gonp.New([]int{1,2,3}, []int{1,5,3})
diff.Compose()
ed := diff.Editdistance() // ed is 2
lcs := diff.Lcs() // lcs is [1,3]

ses := diff.Ses()
// ses is []SesElem{
//        {e: 1, t: Common},
//        {e: 2, t: Delete},
//        {e: 5, t: Add},
//        {e: 3, t: Common},
//        }

unified format difference

diff := gonp.New([]rune("abc"), []rune("abd"))
diff.Compose()

uniHunks := diff.UnifiedHunks()
diff.PrintUniHunks(uniHunks)
// @@ -1,3 +1,3 @@
//  a
//  b
// -c
// +d

Example

strdiff

$ make strdiff
go build -o strdiff examples/strdiff.go
$ ./strdiff abc abd
Editdistance: 2
LCS: ab
SES:
  a
  b
- c
+ d

intdiff

$ make intdiff
go build -o intdiff examples/intdiff.go
$ ./intdiff
diff [1 2 3 4 5] [1 2 9 4 5]
Editdistance: 2
LCS: [1 2 4 5]
SES:
  1
  2
- 3
+ 9
  4
  5

unistrdiff

$ make unistrdiff
go build -o unistrdiff examples/unistrdiff.go
$ ./unistrdiff abc abd
Editdistance:2
LCS:ab
Unified format difference:
@@ -1,3 +1,3 @@
 a
 b
-c
+d

uniintdiff

$ make uniintdiff
go build -o uniintdiff examples/uniintdiff.go
$ ./uniintdiff
diff [1 2 3 4 5] [1 2 9 4 5]
Editdistance: 2
LCS: [1 2 4 5]
Unified format difference:
@@ -1,5 +1,5 @@
 1
 2
-3
+9
 4
 5

unifilediff

$ make unifilediff
go build -o unifilediff examples/unifilediff.go
$ cat a.txt
a
b
c
$ cat b.txt
a
b
d
$ ./unifilediff a.txt b.txt
@@ -1,3 +1,3 @@
 a
 b
-c
+d

Documentation

Index

• Constants
• type Diff
  • func New[T Elem](a, b []T) *Diff[T]
  • func (diff *Diff[T]) Compose()
  • func (diff *Diff[T]) Editdistance() int
  • func (diff *Diff[T]) FprintSes(w io.Writer)
  • func (diff *Diff[T]) FprintUniHunks(w io.Writer, uniHunks []UniHunk[T])
  • func (diff *Diff[T]) Lcs() []T
  • func (diff *Diff[T]) OnlyEd()
  • func (diff *Diff[T]) Patch(seq []T) []T
  • func (diff *Diff[T]) PrintSes()
  • func (diff *Diff[T]) PrintUniHunks(uniHunks []UniHunk[T])
  • func (diff *Diff[T]) Ses() []SesElem[T]
  • func (diff *Diff[T]) SetContextSize(n int)
  • func (diff *Diff[T]) SetRouteSize(n int)
  • func (diff *Diff[T]) SprintSes() string
  • func (diff *Diff[T]) SprintUniHunks(uniHunks []UniHunk[T]) string
  • func (diff *Diff[T]) UniPatch(seq []T, uniHunks []UniHunk[T]) ([]T, error)
  • func (diff *Diff[T]) UnifiedHunks() []UniHunk[T]
• type Elem
• type Point
• type PointWithRoute
• type SesElem
  • func (e *SesElem[T]) GetElem() T
  • func (e *SesElem[T]) GetType() SesType
• type SesType
• type UniHunk
  • func (uniHunk *UniHunk[T]) GetChanges() []SesElem[T]
  • func (uniHunk *UniHunk[T]) SprintDiffRange() string

Constants

const (
	PhaseFrontDiff = iota
	PhaseInDiff
	PhaseBehindDiff
)

const (
	DefaultContextSize = 3
)

const (
	// limit of cordinate size
	DefaultRouteSize = 2000000
)

Types

type Diff

type Diff[T Elem] struct {
	// contains filtered or unexported fields
}

Diff is context for calculating difference between a and b

func New

func New[T Elem](a, b []T) *Diff[T]

New is initializer of Diff

func (*Diff[T]) Compose

func (diff *Diff[T]) Compose()

Compose composes diff between a and b

func (*Diff[T]) Editdistance

func (diff *Diff[T]) Editdistance() int

Editdistance returns edit distance between a and b

func (*Diff[T]) FprintSes

func (diff *Diff[T]) FprintSes(w io.Writer)

FprintSes emit about shortest edit script between a and b to w

func (*Diff[T]) FprintUniHunks

func (diff *Diff[T]) FprintUniHunks(w io.Writer, uniHunks []UniHunk[T])

FprintUniHunks emit about unified format difference between a and b to w

func (*Diff[T]) Lcs

func (diff *Diff[T]) Lcs() []T

Lcs returns LCS (Longest Common Subsequence) between a and b

func (*Diff[T]) OnlyEd

func (diff *Diff[T]) OnlyEd()

OnlyEd enables to calculate only edit distance

func (*Diff[T]) Patch

func (diff *Diff[T]) Patch(seq []T) []T

Patch applies SES between a and b to seq

func (*Diff[T]) PrintSes

func (diff *Diff[T]) PrintSes()

PrintSes prints shortest edit script between a and b

func (*Diff[T]) PrintUniHunks

func (diff *Diff[T]) PrintUniHunks(uniHunks []UniHunk[T])

PrintUniHunks prints unified format difference between and b

func (*Diff[T]) Ses

func (diff *Diff[T]) Ses() []SesElem[T]

Ses return SES (Shortest Edit Script) between a and b

func (*Diff[T]) SetContextSize

func (diff *Diff[T]) SetContextSize(n int)

SetContextSize sets the context size of unified format difference

func (*Diff[T]) SetRouteSize

func (diff *Diff[T]) SetRouteSize(n int)

SetRouteSize sets the context size of unified format difference

func (*Diff[T]) SprintSes

func (diff *Diff[T]) SprintSes() string

SprintSes returns string about shortest edit script between a and b

func (*Diff[T]) SprintUniHunks

func (diff *Diff[T]) SprintUniHunks(uniHunks []UniHunk[T]) string

SprintUniHunks returns string about unified format difference between a and b

func (*Diff[T]) UniPatch

func (diff *Diff[T]) UniPatch(seq []T, uniHunks []UniHunk[T]) ([]T, error)

UniPatch applies unified format difference between a and b to seq

func (*Diff[T]) UnifiedHunks

func (diff *Diff[T]) UnifiedHunks() []UniHunk[T]

UnifiedHunks composes unified format difference between a and b

type Elem

type Elem interface {
	~rune | ~string | ~byte | ~int | ~int8 | ~int16 | ~int64 | ~float32 | ~float64
}

Type constraints for element in SES

type Point

type Point struct {
	// contains filtered or unexported fields
}

Point is coordinate in edit graph

type PointWithRoute

type PointWithRoute struct {
	// contains filtered or unexported fields
}

PointWithRoute is coordinate in edit graph attached route

type SesElem

type SesElem[T Elem] struct {
	// contains filtered or unexported fields
}

SesElem is element of SES

func (*SesElem[T]) GetElem

func (e *SesElem[T]) GetElem() T

GetElem is getter of element of SES

func (*SesElem[T]) GetType

func (e *SesElem[T]) GetType() SesType

GetType is getter of manipulation type of SES

type SesType

type SesType int

SesType is manipulaton type

const (
	// SesDelete is manipulaton type of deleting element in SES
	SesDelete SesType = iota
	// SesCommon is manipulaton type of same element in SES
	SesCommon
	// SesAdd is manipulaton type of adding element in SES
	SesAdd
)

type UniHunk

type UniHunk[T Elem] struct {
	// contains filtered or unexported fields
}

UniHunk is an element of unified format difference

func (*UniHunk[T]) GetChanges

func (uniHunk *UniHunk[T]) GetChanges() []SesElem[T]

GetChanges is getter of changes in UniHunk

func (*UniHunk[T]) SprintDiffRange

func (uniHunk *UniHunk[T]) SprintDiffRange() string

SprintDiffRange returns formatted string represents difference range