diff

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

• type Change
  • func ByteStrings(a, b string) []Change
  • func Bytes(a, b []byte) []Change
  • func Diff(n, m int, data Data) []Change
  • func Granular(granularity int, changes []Change) []Change
  • func Ints(a, b []int) []Change
  • func Runes(a, b []rune) []Change
• type Data

Examples

• Diff
• Granular

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.