myers

Documentation

Overview

Package myers implements the Myers diff algorithm.

Index

• func Diff(ctx context.Context, ab Pair) edit.Script
• type Pair

Functions

func Diff

func Diff(ctx context.Context, ab Pair) edit.Script

Diff calculates an edit.Script for ab using the Myers diff algorithm. This implementation uses the algorithm described in the first half of Myers' paper, which requires quadratric space. (An implementation of the linear space version is forthcoming.)

Because diff calculation can be expensive, Myers supports cancellation via ctx.

Types

type Pair

type Pair interface {
	// LenA returns the number of initial elements.
	LenA() int
	// LenB returns the number of final elements.
	LenB() int
	// Equal reports whether the aᵢ'th element of A is equal to the bᵢ'th element of B.
	Equal(ai, bi int) bool
}

A Pair is two things that can be diffed using the Myers diff algorithm. A is the initial state; B is the final state.