package tui

import (
	"sort"
	"strings"
)

// Fuzzy matching, for pickers whose list is long enough that scrolling it is
// slower than describing what you want. The rule is subsequence: every
// character typed has to appear, in order, somewhere in the candidate — so
// "dkmd" finds "dark-mode" — and the score decides which of the matches is
// offered first.
//
// The scoring is deliberately small. What people actually type is the start of
// a word or a run of letters from one, so those are what earn points; nothing
// here tries to be a ranking function, only to put the obvious answer on top.

// Scores for the three ways a character can land, and the cap on what skipping
// over characters costs. Consecutive beats a word start beats a stray hit.
const (
	fuzzyRun      = 10 // directly after the previous match
	fuzzyBoundary = 8  // the first character of a word
	fuzzyHit      = 1  // anywhere else
	fuzzyGapMax   = 3  // the most one gap can cost
	fuzzyLeadMax  = 4  // the most a late start can cost
)

// fuzzyMatch reports whether pattern appears in s as a subsequence, and how
// good a match it is — higher is better. Matching is case-insensitive, and an
// empty pattern matches everything, which is what an unfiltered picker wants.
func fuzzyMatch(pattern, s string) (int, bool) {
	if pattern == "" {
		return 0, true
	}
	p := []rune(strings.ToLower(pattern))
	t := []rune(strings.ToLower(s))

	score, pi, prev := 0, 0, -1
	for i := 0; i < len(t) && pi < len(p); i++ {
		if t[i] != p[pi] {
			continue
		}
		switch {
		case i == prev+1 && prev >= 0:
			score += fuzzyRun
		case i == 0 || isWordBoundary(t[i-1]):
			score += fuzzyBoundary
		default:
			score += fuzzyHit
		}
		// Skipping over characters to get here is what makes a loose match
		// loose, and the penalty is capped so one long gap does not sink a
		// candidate that is otherwise a good hit.
		if prev >= 0 {
			score -= minInt(fuzzyGapMax, i-prev-1)
		} else {
			// Where the match begins matters too: of two candidates that
			// contain "par" as a word, "parser-rewrite" is the one being asked
			// for and "old-parser" is the one that happens to contain it.
			score -= minInt(fuzzyLeadMax, i)
		}
		prev, pi = i, pi+1
	}
	if pi < len(p) {
		return 0, false
	}
	// Of two candidates matched equally well, the shorter one is the one
	// meant: "api" should offer "api" before "rapid-prototyping".
	return score - len(t)/8, true
}

// isWordBoundary says whether a character separates words, for the purpose of
// deciding that the next one starts a word. Worktree names are slugs and
// branches have slashes in them, so these are the separators that matter.
func isWordBoundary(r rune) bool {
	switch r {
	case '-', '_', '/', ' ', '.', ':', '@':
		return true
	}
	return false
}

// fuzzyRank narrows a list to what matches pattern, best first. Ties keep the
// order they came in, so a list already sorted the way the picker wants it
// stays that way under an empty or undiscriminating filter.
func fuzzyRank[T any](items []T, pattern string, text func(T) string) []T {
	type scored struct {
		item  T
		score int
		at    int
	}
	var hits []scored
	for i, it := range items {
		if score, ok := fuzzyMatch(pattern, text(it)); ok {
			hits = append(hits, scored{item: it, score: score, at: i})
		}
	}
	sort.SliceStable(hits, func(i, j int) bool {
		if hits[i].score != hits[j].score {
			return hits[i].score > hits[j].score
		}
		return hits[i].at < hits[j].at
	})
	out := make([]T, 0, len(hits))
	for _, h := range hits {
		out = append(out, h.item)
	}
	return out
}