package transcript

import (
	"sort"
	"strings"
	"unicode"
)

/*
Finding the advertising by subtraction.

A publisher's transcript describes the ad-free master. Speech recognition over the mirrored file
describes the copy the phone will play. The copy is the master with advertising stitched into
it, so the text present in the served copy and absent from the master *is* the advertising, with
its own boundaries.

This is a measurement rather than a guess, which makes it different in kind from everything else
in this project. The audio scan infers advertising from what several episodes share and checks
itself against the declared-versus-served length gap; the phrase spotter infers it from ad copy
and checks itself against nothing. This one derives the answer from two independent descriptions
of the same recording.

It needs both halves, which is why a declined publisher transcript is kept rather than thrown
away. Declined means "this copy carries inserted advertising the master does not describe" --
precisely the episode this works on.
*/

// SignalDifference marks a candidate found by subtracting the master from the served copy,
// rather than by reading ad copy. Carried so one episode's candidates can come from either
// detector and still be told apart.
const SignalDifference = "difference"

const (
	// anchorWords is how long a matching run must be to anchor the two texts together.
	// Five: long enough that an ordinary phrase does not match in several places, short enough
	// that it still fits between two recognition errors. Recognition is approximate -- whisper
	// writes "Bombus" for "Bombas" -- so a window containing a mistake simply fails to anchor
	// and its neighbours carry the alignment instead.
	anchorWords = 5
	// minInsertedWords is the shortest stretch worth calling an advertisement. A publisher who
	// trims a sentence, or recognition that drops a clause, leaves a gap of a few words;
	// skipping over one would clip the programme. Forty words is about fifteen seconds of
	// speech, the same floor the phrase spotter uses and the same ad unit the length-gap rule
	// uses.
	minInsertedWords = 40
)

// token is one word of a transcript and where it was said.
type token struct {
	word    string
	startMs int64
	endMs   int64
}

// Inserted reports the stretches of the served copy that the master does not contain.
//
// Returns nothing when either side is missing: there is nothing to subtract, which is a
// different answer from "no advertising" and the caller sees it as the absence of candidates
// either way. The episode record says which of the two it is.
func Inserted(master, served []Cue) []Candidate {
	masterWords := tokenise(master)
	servedWords := tokenise(served)
	if len(masterWords) < anchorWords || len(servedWords) < anchorWords {
		return nil
	}

	anchors := alignment(masterWords, servedWords)

	// Walk the gaps between consecutive anchors, including the ones at each end. A gap where
	// the served copy advanced a long way and the master did not is inserted content.
	// An anchor names the start of a run of [anchorWords] matching words, so the content
	// between two anchors begins after the first one's run ends, not after its first word.
	// Getting this wrong puts the start of every break one anchor-length early, which on a real
	// episode is a skip over the last sentence of the programme.
	var found []Candidate
	previous := anchor{master: -anchorWords, served: -anchorWords}
	for _, next := range append(anchors, anchor{master: len(masterWords), served: len(servedWords)}) {
		servedFrom := previous.served + anchorWords
		masterFrom := previous.master + anchorWords
		servedGap := next.served - servedFrom
		masterGap := next.master - masterFrom
		if servedGap-masterGap >= minInsertedWords && servedFrom < len(servedWords) {
			from := servedWords[servedFrom]
			to := servedWords[next.served-1]
			found = append(found, Candidate{
				StartMs: from.startMs,
				EndMs:   to.endMs,
				Signals: []string{SignalDifference},
			})
		}
		previous = next
	}
	// Every gap is then partitioned line by line against the master, which is what decides
	// where within it the advertising actually is. See [Trimmed].
	return trimmed(found, master, served)
}

// anchor ties a position in the master to the position in the served copy saying the same words.
type anchor struct{ master, served int }

/*
alignment finds where the two texts agree.

Anchored on runs of [anchorWords] words that occur exactly once in each text. Uniqueness is what
makes an anchor trustworthy: a phrase appearing twice in the master cannot say which occurrence
a served phrase matches, and a wrong anchor drags the alignment across a break. Inside an
advertisement there are no matching runs at all, which is what makes a pod show up as a gap.

The anchors are then reduced to the longest increasing run, because a handful will still be
spurious -- a stock phrase the publisher and an advertiser both used -- and those point
backwards.
*/
func alignment(masterWords, servedWords []token) []anchor {
	masterRuns := uniqueRuns(masterWords)
	servedRuns := uniqueRuns(servedWords)

	var anchors []anchor
	for run, servedAt := range servedRuns {
		if masterAt, ok := masterRuns[run]; ok {
			anchors = append(anchors, anchor{master: masterAt, served: servedAt})
		}
	}
	sort.Slice(anchors, func(i, j int) bool { return anchors[i].served < anchors[j].served })
	return longestIncreasing(anchors)
}

// uniqueRuns maps every run of [anchorWords] words that occurs exactly once to where it starts.
func uniqueRuns(words []token) map[string]int {
	seen := make(map[string]int, len(words))
	repeated := make(map[string]bool)
	for i := 0; i+anchorWords <= len(words); i++ {
		parts := make([]string, anchorWords)
		for j := 0; j < anchorWords; j++ {
			parts[j] = words[i+j].word
		}
		run := strings.Join(parts, " ")
		if _, ok := seen[run]; ok {
			repeated[run] = true
			continue
		}
		seen[run] = i
	}
	for run := range repeated {
		delete(seen, run)
	}
	return seen
}

// longestIncreasing keeps the longest run of anchors whose master positions increase, dropping
// the ones that would have the alignment going backwards.
func longestIncreasing(anchors []anchor) []anchor {
	if len(anchors) == 0 {
		return nil
	}
	// Patience sorting: tails[k] is the index of the anchor ending the best run of length k+1.
	var tails []int
	previous := make([]int, len(anchors))
	for i, a := range anchors {
		previous[i] = -1
		at := sort.Search(len(tails), func(k int) bool {
			return anchors[tails[k]].master >= a.master
		})
		if at > 0 {
			previous[i] = tails[at-1]
		}
		if at == len(tails) {
			tails = append(tails, i)
		} else {
			tails[at] = i
		}
	}

	out := make([]anchor, 0, len(tails))
	for i := tails[len(tails)-1]; i >= 0; i = previous[i] {
		out = append(out, anchors[i])
	}
	for left, right := 0, len(out)-1; left < right; left, right = left+1, right-1 {
		out[left], out[right] = out[right], out[left]
	}
	return out
}

// tokenise splits cues into comparable words, each carrying the time of the cue it came from.
//
// Case and punctuation are dropped because they are exactly what differs between a publisher's
// written transcript and a machine's reading of the same speech, and neither carries meaning
// for matching.
func tokenise(cues []Cue) []token {
	var out []token
	for _, cue := range cues {
		for _, word := range strings.FieldsFunc(strings.ToLower(cue.Text), notWord) {
			out = append(out, token{word: word, startMs: cue.StartMs, endMs: cue.EndMs})
		}
	}
	return out
}

func notWord(r rune) bool { return !unicode.IsLetter(r) && !unicode.IsDigit(r) }