### 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.

### 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 ¶

`func ByteStrings(a, b string) []Change`

ByteStrings returns the differences of two strings in bytes.

#### func Bytes ¶

`func Bytes(a, b []byte) []Change`

Bytes returns the difference of two byte slices

#### func Diff ¶

`func Diff(n, m int, data Data) []Change`

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 ¶

`func Granular(granularity int, changes []Change) []Change`

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!
```

#### func Ints ¶

`func Ints(a, b []int) []Change`

Ints returns the difference of two int slices

#### func Runes ¶

`func Runes(a, b []rune) []Change`

Runes returns the difference of two rune slices

#### type Data ¶

```type Data interface {
// Equal returns whether the elements at i and j are considered equal.
Equal(i, j int) bool
}```

A type that satisfies diff.Data can be diffed by this package. It typically has two sequences A and B of comparable elements.