package entry

import "strings"

// DiffOp sagt, was mit einer Zeile im Vergleich zweier Fassungen passiert ist.
type DiffOp int

const (
	DiffEqual DiffOp = iota
	DiffRemove
	DiffAdd
)

// DiffLine ist eine Zeile im Ergebnis von DiffLines.
type DiffLine struct {
	Op   DiffOp
	Text string
}

// maxDiffCells begrenzt die Größe der Vergleichstabelle (Zeilen_alt ×
// Zeilen_neu). Jenseits davon bräuchte eine genaue Zeilenzuordnung mehr
// Speicher, als für eine einzelne Vergleichsseite sinnvoll ist — dann liefert
// DiffLines nur noch "alles Alte weg, alles Neue dazu" statt einer
// Zeile-für-Zeile-Zuordnung. Bei zwei mittelgroßen Wiki-Einträgen (je ein paar
// hundert Zeilen) wird diese Grenze nicht erreicht.
const maxDiffCells = 4_000_000

// DiffLines vergleicht zwei Fassungen eines Eintrags zeilenweise.
//
// Klassischer Ansatz über die längste gemeinsame Teilfolge (LCS): Zeilen, die
// in beiden Fassungen in derselben Reihenfolge vorkommen, gelten als
// unverändert; alles dazwischen als entfernt bzw. hinzugefügt. Ein
// verschobener, aber unveränderter Absatz wird dabei nicht zwingend als
// "gleich" erkannt, wenn sich in seiner Umgebung etwas geändert hat — für die
// Frage "was hat sich bei diesem Schreibvorgang geändert" reicht das.
func DiffLines(old, newer string) []DiffLine {
	oldLines := splitLines(old)
	newLines := splitLines(newer)

	if len(oldLines)*len(newLines) > maxDiffCells {
		return coarseDiff(oldLines, newLines)
	}
	return lcsDiff(oldLines, newLines)
}

func splitLines(s string) []string {
	if s == "" {
		return nil
	}
	return strings.Split(s, "\n")
}

// coarseDiff dient als Rückfallebene für außergewöhnlich lange Einträge: keine
// Zeilenzuordnung, nur der komplette alte Text als entfernt und der
// komplette neue als hinzugefügt.
func coarseDiff(oldLines, newLines []string) []DiffLine {
	lines := make([]DiffLine, 0, len(oldLines)+len(newLines))
	for _, z := range oldLines {
		lines = append(lines, DiffLine{Op: DiffRemove, Text: z})
	}
	for _, z := range newLines {
		lines = append(lines, DiffLine{Op: DiffAdd, Text: z})
	}
	return lines
}

// lcsDiff berechnet die Zeilenzuordnung über eine klassische LCS-Tabelle.
//
// dp[i][j] ist die Länge der längsten gemeinsamen Teilfolge von a[i:] und
// b[j:], rückwärts aufgebaut. Der anschließende Vorwärtslauf liest daraus die
// eigentliche Zuordnung ab: Stimmen die Zeilen überein, sind sie Teil der
// gemeinsamen Folge; sonst wird der Seite gefolgt, die die längere
// Teilfolge verspricht.
func lcsDiff(a, b []string) []DiffLine {
	n, m := len(a), len(b)

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
	}
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			switch {
			case a[i] == b[j]:
				dp[i][j] = dp[i+1][j+1] + 1
			case dp[i+1][j] >= dp[i][j+1]:
				dp[i][j] = dp[i+1][j]
			default:
				dp[i][j] = dp[i][j+1]
			}
		}
	}

	var lines []DiffLine
	i, j := 0, 0
	for i < n && j < m {
		switch {
		case a[i] == b[j]:
			lines = append(lines, DiffLine{Op: DiffEqual, Text: a[i]})
			i++
			j++
		case dp[i+1][j] >= dp[i][j+1]:
			lines = append(lines, DiffLine{Op: DiffRemove, Text: a[i]})
			i++
		default:
			lines = append(lines, DiffLine{Op: DiffAdd, Text: b[j]})
			j++
		}
	}
	for ; i < n; i++ {
		lines = append(lines, DiffLine{Op: DiffRemove, Text: a[i]})
	}
	for ; j < m; j++ {
		lines = append(lines, DiffLine{Op: DiffAdd, Text: b[j]})
	}
	return lines
}