gotools/internal/diff/lcs/common.go

type lcs …

type diag …

// sort sorts in place, by lowest X, and if tied, inversely by Len
func (l lcs) sort() lcs { … }

// validate that the elements of the lcs do not overlap
// (can only happen when the two-sided algorithm ends early)
// expects the lcs to be sorted
func (l lcs) valid() bool { … }

// repair overlapping lcs
// only called if two-sided stops early
func (l lcs) fix() lcs { … }

type direction …

const empty …

const leftdown …

const rightup …

const bad …

// overlap trims the proposed diag prop  so it doesn't overlap with
// the existing diag that has already been added to the lcs.
func overlap(exist, prop diag) (direction, diag) { … }

// prepend a diagonal (x,y)-(x+1,y+1) segment either to an empty lcs
// or to its first Diag. prepend is only called to extend diagonals
// the backward direction.
func (lcs lcs) prepend(x, y int) lcs { … }

// append appends a diagonal, or extends the existing one.
// by adding the edge (x,y)-(x+1.y+1). append is only called
// to extend diagonals in the forward direction.
func (lcs lcs) append(x, y int) lcs { … }

// enforce constraint on d, k
func ok(d, k int) bool { … }