// Myers diff 算法实现 -- An O(ND) Difference Algorithm (Myers, 1986).
//
// 核心思想:在编辑图(edit graph)中寻找最短编辑路径.
// 编辑图的 x 轴是旧文本行号,y 轴是新文本行号.
// 每一步可以向右(删除),向下(插入),或对角线(相同行跳过).
// Myers 算法贪心地按编辑距离 d = 0, 1, 2, ... 扩展,找到最短路径.
//
// 精妙之处(CLEVER): 算法复杂度 O(ND),其中 N 是两文本长度之和,
// D 是最小编辑距离.对于相似文件(D 很小),速度远快于 O(N^2).
//
// 大文件降级策略:如果两文本行数之和 > 10000,降级到简单的首尾匹配 + 中间全替换.
// 这是实用主义的妥协 -- 万行级别的完整 Myers diff 既慢又无意义
// (人类根本看不懂那么长的 diff).
package diff

// EditType 表示编辑操作的类型.
type EditType int

const (
	EditEqual  EditType = iota // 相同行(无变更)
	EditDelete                 // 删除行(旧文本中有,新文本中无)
	EditInsert                 // 插入行(旧文本中无,新文本中有)
)

// Edit 表示单个编辑操作.
type Edit struct {
	Type    EditType // 操作类型:相同 / 删除 / 插入
	Content string   // 行内容(不含换行符)
	OldLine int      // 在旧文本中的行号(从 1 开始,插入行为 0)
	NewLine int      // 在新文本中的行号(从 1 开始,删除行为 0)
}

// largeDiffThreshold 是触发降级策略的行数差异阈值.
// 超过此阈值,Myers 算法的 O(ND) 复杂度中 D 可能很大,
// 降级到简单的首尾匹配 + 中间全替换.
const largeDiffThreshold = 10000

// Diff 计算两个字符串切片之间的编辑脚本.
// 返回的 []Edit 序列按文本顺序排列,可以直接用于生成 diff 输出.
//
// 精妙之处(CLEVER): 两个空切片之间 diff 返回空切片(不是 nil),
// 保证消费方无需做 nil 检查.
func Diff(oldLines, newLines []string) []Edit {
	oldLen := len(oldLines)
	newLen := len(newLines)

	// 边界:两者都为空
	if oldLen == 0 && newLen == 0 {
		return []Edit{}
	}

	// 边界:旧文本为空 → 全部插入
	if oldLen == 0 {
		edits := make([]Edit, newLen)
		for i, line := range newLines {
			edits[i] = Edit{Type: EditInsert, Content: line, OldLine: 0, NewLine: i + 1}
		}
		return edits
	}

	// 边界:新文本为空 → 全部删除
	if newLen == 0 {
		edits := make([]Edit, oldLen)
		for i, line := range oldLines {
			edits[i] = Edit{Type: EditDelete, Content: line, OldLine: i + 1, NewLine: 0}
		}
		return edits
	}

	// 升华改进(ELEVATED): 大文件降级策略.如果两文本行数之和超过阈值,
	// 跳过完整 Myers 算法,改用首尾匹配 + 中间全替换.
	// 替代方案:无条件跑 Myers(可能在极端情况下卡住几十秒).
	totalLines := oldLen + newLen
	if totalLines > largeDiffThreshold {
		return fallbackDiff(oldLines, newLines)
	}

	return myersDiff(oldLines, newLines)
}

// myersDiff 实现完整的 Myers diff 算法.
//
// 算法步骤:
// 1. 前向搜索:按编辑距离 d = 0, 1, 2, ... 扩展最远到达点
// 2. 记录每步的 V 数组(最远到达点的 x 坐标)
// 3. 反向追踪:从终点回溯到起点,重建编辑路径
//
// 精妙之处(CLEVER): 前向搜索 + 反向追踪是 Myers 算法的经典两阶段.
// 前向搜索找到最短编辑距离 D,反向追踪重建具体的编辑操作序列.
func myersDiff(oldLines, newLines []string) []Edit {
	oldLen := len(oldLines)
	newLen := len(newLines)
	maxD := oldLen + newLen

	if maxD == 0 {
		return []Edit{}
	}

	// 精妙之处(CLEVER): V[k] 记录对角线 k 上能到达的最远 x 坐标.
	// 对角线 k = x - y,其中 x 是旧文本位置,y 是新文本位置.
	// 使用 offset 让数组索引非负:实际 k 值范围 [-maxD, maxD],
	// 存储时加 maxD 偏移.
	offset := maxD + 1
	vSize := 2*maxD + 3

	// trace 记录每一步(d=0,1,...)结束后的 V 数组快照,用于反向追踪.
	// trace[d] 是步骤 d 结束后 V 的状态.
	trace := make([][]int, 0, maxD+1)

	v := make([]int, vSize)

	// 前向搜索:按编辑距离 d 递增
	var finalD int

	for d := 0; d <= maxD; d++ {
		// 遍历所有可能的对角线 k(步长 2)
		for k := -d; k <= d; k += 2 {
			var x int
			if k == -d || (k != d && v[k-1+offset] < v[k+1+offset]) {
				x = v[k+1+offset]
			} else {
				x = v[k-1+offset] + 1
			}

			y := x - k

			// 沿对角线贪心延伸(跳过相同行)
			for x < oldLen && y < newLen && oldLines[x] == newLines[y] {
				x++
				y++
			}

			v[k+offset] = x

			// 到达终点
			if x >= oldLen && y >= newLen {
				finalD = d
				// 保存最终快照并跳转到反向追踪
				snapshot := make([]int, vSize)
				copy(snapshot, v)
				trace = append(trace, snapshot)
				goto backtrack
			}
		}

		// 精妙之处(CLEVER): 在步骤 d 的所有 k 处理完后保存快照.
		// trace[d] 是步骤 d 结束后(所有对角线都已更新)的 V 状态.
		snapshot := make([]int, vSize)
		copy(snapshot, v)
		trace = append(trace, snapshot)
	}

backtrack:
	// 反向追踪:从终点重建编辑路径
	// 精妙之处(CLEVER): 从 (oldLen, newLen) 回溯到 (0, 0).
	// 在步骤 d 中,我们从步骤 d-1 的某条对角线 prevK 出发,
	// 做一步非对角线移动到达对角线 k,然后沿对角线延伸.
	// trace[d-1] 记录了步骤 d-1 结束后的状态.
	edits := make([]Edit, 0, oldLen+newLen)

	x := oldLen
	y := newLen

	for d := finalD; d > 0; d-- {
		k := x - y

		// 判断步骤 d 中是从哪条对角线做非对角线移动过来的
		// 使用 trace[d-1](步骤 d-1 结束后的 V 状态)来判断
		prevV := trace[d-1]
		var prevK int
		if k == -d || (k != d && prevV[k-1+offset] < prevV[k+1+offset]) {
			prevK = k + 1 // 从 k+1 向下(插入)
		} else {
			prevK = k - 1 // 从 k-1 向右(删除)
		}

		// prevX 是步骤 d-1 结束时对角线 prevK 上的最远 x
		prevX := prevV[prevK+offset]
		prevY := prevX - prevK

		// 对角线延伸产生的 Equal 行(逆序收集)
		// 步骤 d 中,非对角线移动后到达 (midX, midY),然后沿对角线延伸到 (x, y)
		// midX, midY 就是非对角线移动的终点
		var midX, midY int
		if prevK < k {
			// 向右移动(删除): x+1, y 不变
			midX = prevX + 1
			midY = prevY
		} else {
			// 向下移动(插入): x 不变, y+1
			midX = prevX
			midY = prevY + 1
		}

		// 对角线上的 Equal 行
		for x > midX && y > midY {
			x--
			y--
			edits = append(edits, Edit{
				Type:    EditEqual,
				Content: oldLines[x],
				OldLine: x + 1,
				NewLine: y + 1,
			})
		}

		// 非对角线移动
		if prevK < k {
			// 向右:删除
			edits = append(edits, Edit{
				Type:    EditDelete,
				Content: oldLines[prevX],
				OldLine: prevX + 1,
				NewLine: 0,
			})
		} else {
			// 向下:插入
			edits = append(edits, Edit{
				Type:    EditInsert,
				Content: newLines[prevY],
				OldLine: 0,
				NewLine: prevY + 1,
			})
		}

		x = prevX
		y = prevY
	}

	// d=0 阶段:只有对角线延伸(从 (0,0) 开始的相同行)
	for x > 0 && y > 0 {
		x--
		y--
		edits = append(edits, Edit{
			Type:    EditEqual,
			Content: oldLines[x],
			OldLine: x + 1,
			NewLine: y + 1,
		})
	}

	// 反转(因为是逆序收集的)
	for i, j := 0, len(edits)-1; i < j; i, j = i+1, j-1 {
		edits[i], edits[j] = edits[j], edits[i]
	}

	return edits
}

// fallbackDiff 是大文件的降级 diff 策略.
// 首尾匹配公共前缀和后缀,中间部分全部标记为删除+插入.
//
// 历史包袱(LEGACY): 理想情况下应该用分块 Myers 或 patience diff,
// 但对于万行级别的文件,用户通常也不会逐行审查 diff,
// 简单的首尾匹配已经足够实用.
func fallbackDiff(oldLines, newLines []string) []Edit {
	oldLen := len(oldLines)
	newLen := len(newLines)

	// 找公共前缀
	prefixLen := 0
	maxPrefix := oldLen
	if newLen < maxPrefix {
		maxPrefix = newLen
	}
	for prefixLen < maxPrefix && oldLines[prefixLen] == newLines[prefixLen] {
		prefixLen++
	}

	// 找公共后缀(不与前缀重叠)
	suffixLen := 0
	maxSuffix := oldLen - prefixLen
	if newLen-prefixLen < maxSuffix {
		maxSuffix = newLen - prefixLen
	}
	for suffixLen < maxSuffix && oldLines[oldLen-1-suffixLen] == newLines[newLen-1-suffixLen] {
		suffixLen++
	}

	// 构建编辑脚本
	edits := make([]Edit, 0, oldLen+newLen)

	// 公共前缀
	for i := 0; i < prefixLen; i++ {
		edits = append(edits, Edit{
			Type:    EditEqual,
			Content: oldLines[i],
			OldLine: i + 1,
			NewLine: i + 1,
		})
	}

	// 中间差异部分:旧文本的行全部标记为删除
	for i := prefixLen; i < oldLen-suffixLen; i++ {
		edits = append(edits, Edit{
			Type:    EditDelete,
			Content: oldLines[i],
			OldLine: i + 1,
			NewLine: 0,
		})
	}

	// 中间差异部分:新文本的行全部标记为插入
	for i := prefixLen; i < newLen-suffixLen; i++ {
		edits = append(edits, Edit{
			Type:    EditInsert,
			Content: newLines[i],
			OldLine: 0,
			NewLine: i + 1,
		})
	}

	// 公共后缀
	for i := 0; i < suffixLen; i++ {
		oldIdx := oldLen - suffixLen + i
		newIdx := newLen - suffixLen + i
		edits = append(edits, Edit{
			Type:    EditEqual,
			Content: oldLines[oldIdx],
			OldLine: oldIdx + 1,
			NewLine: newIdx + 1,
		})
	}

	return edits
}