package prosediff

// Myers O(ND) sequence diff, used at three levels: blocks, words and code
// lines. Sequences are always interned to []int first, so equality is exact
// integer equality and there is no hash-collision risk.

// Op is the role of a run in an edit script.
type Op uint8

const (
	// OpEqual marks content present, unchanged, in both revisions.
	OpEqual Op = iota
	// OpDelete marks content present only in the old revision.
	OpDelete
	// OpInsert marks content present only in the new revision.
	OpInsert
)

func (o Op) String() string {
	switch o {
	case OpEqual:
		return "equal"
	case OpDelete:
		return "delete"
	case OpInsert:
		return "insert"
	}
	return "unknown"
}

// edit is one run of an edit script: n consecutive elements sharing an Op.
type edit struct {
	op Op
	n  int
}

// interner maps arbitrary strings to dense ints so sequence comparison is
// integer equality.
type interner struct {
	ids map[string]int
}

func newInterner() *interner { return &interner{ids: make(map[string]int)} }

func (in *interner) id(s string) int {
	if v, ok := in.ids[s]; ok {
		return v
	}
	v := len(in.ids) + 1
	in.ids[s] = v
	return v
}

func (in *interner) all(ss []string) []int {
	out := make([]int, len(ss))
	for i, s := range ss {
		out[i] = in.id(s)
	}
	return out
}

// diffInts returns the edit script turning a into b, as a coalesced run list.
// The script is a minimal edit script (Myers), with common prefix and suffix
// trimmed first so the expensive part only runs over the changed middle.
func diffInts(a, b []int) []edit {
	pre := 0
	for pre < len(a) && pre < len(b) && a[pre] == b[pre] {
		pre++
	}
	suf := 0
	for suf < len(a)-pre && suf < len(b)-pre && a[len(a)-1-suf] == b[len(b)-1-suf] {
		suf++
	}
	var out []edit
	if pre > 0 {
		out = append(out, edit{OpEqual, pre})
	}
	out = append(out, myers(a[pre:len(a)-suf], b[pre:len(b)-suf])...)
	if suf > 0 {
		out = append(out, edit{OpEqual, suf})
	}
	return coalesce(out)
}

// vsnap is the V array of one Myers iteration, stored only over the diagonals
// [-d, d] that iteration can reach.
type vsnap struct {
	d    int
	vals []int32
}

func (s vsnap) get(k int) int { return int(s.vals[k+s.d]) }

func myers(a, b []int) []edit {
	n, m := len(a), len(b)
	switch {
	case n == 0 && m == 0:
		return nil
	case n == 0:
		return []edit{{OpInsert, m}}
	case m == 0:
		return []edit{{OpDelete, n}}
	}

	maxD := n + m
	v := make([]int32, 2*maxD+1)
	off := maxD
	trace := make([]vsnap, 0, 16)

	for d := 0; d <= maxD; d++ {
		done := false
		for k := -d; k <= d; k += 2 {
			var x int
			if k == -d || (k != d && v[off+k-1] < v[off+k+1]) {
				x = int(v[off+k+1]) // move down: consume one element of b
			} else {
				x = int(v[off+k-1]) + 1 // move right: consume one element of a
			}
			y := x - k
			for x < n && y < m && a[x] == b[y] {
				x++
				y++
			}
			v[off+k] = int32(x)
			if x >= n && y >= m {
				done = true
				break
			}
		}
		snap := vsnap{d: d, vals: make([]int32, 2*d+1)}
		for k := -d; k <= d; k += 2 {
			snap.vals[k+d] = v[off+k]
		}
		trace = append(trace, snap)
		if done {
			return backtrack(trace, n, m)
		}
	}
	panic("prosediff: myers did not converge")
}

// backtrack walks the saved V arrays from the end point back to the origin,
// emitting the edit script in reverse and then flipping it.
func backtrack(trace []vsnap, n, m int) []edit {
	var rev []edit
	push := func(op Op) {
		if len(rev) > 0 && rev[len(rev)-1].op == op {
			rev[len(rev)-1].n++
			return
		}
		rev = append(rev, edit{op, 1})
	}

	x, y := n, m
	for d := len(trace) - 1; d > 0; d-- {
		prev := trace[d-1]
		k := x - y
		var prevK int
		if k == -d || (k != d && prev.get(k-1) < prev.get(k+1)) {
			prevK = k + 1
		} else {
			prevK = k - 1
		}
		prevX := prev.get(prevK)
		prevY := prevX - prevK
		for x > prevX && y > prevY {
			push(OpEqual)
			x--
			y--
		}
		if x == prevX {
			push(OpInsert)
			y--
		} else {
			push(OpDelete)
			x--
		}
		x, y = prevX, prevY
	}
	for x > 0 && y > 0 {
		push(OpEqual)
		x--
		y--
	}
	// d == 0 leaves at most one of x, y non-zero only when the other
	// sequence was fully consumed on the diagonal, which the prefix trim
	// already handled; keep the guard rather than assume.
	for ; x > 0; x-- {
		push(OpDelete)
	}
	for ; y > 0; y-- {
		push(OpInsert)
	}

	out := make([]edit, 0, len(rev))
	for i := len(rev) - 1; i >= 0; i-- {
		out = append(out, rev[i])
	}
	return coalesce(out)
}

func coalesce(in []edit) []edit {
	out := in[:0:0]
	for _, e := range in {
		if e.n == 0 {
			continue
		}
		if len(out) > 0 && out[len(out)-1].op == e.op {
			out[len(out)-1].n += e.n
			continue
		}
		out = append(out, e)
	}
	return out
}

// commonCount reports how many elements the edit script keeps equal.
func commonCount(script []edit) int {
	n := 0
	for _, e := range script {
		if e.op == OpEqual {
			n += e.n
		}
	}
	return n
}

// ratio is the classic 2*common/(len(a)+len(b)) similarity in [0,1].
func ratio(a, b []int) float64 {
	if len(a) == 0 && len(b) == 0 {
		return 1
	}
	return 2 * float64(commonCount(diffInts(a, b))) / float64(len(a)+len(b))
}