wails-epic/internal/optimizer/optimizer.go

package optimizer

import (
	"container/heap"
	"context"
	"encoding/json"
	"fmt"
	"log"
	"math"
	"runtime"
	"sort"
	"sync"
	"sync/atomic"

	"equipment-analyzer/internal/model"
)

const (
	defaultMaxItemsPerSlot   = 300
	defaultMaxCombos         = 2000000
	defaultMaxResults        = 5000
	maxCollectedPerPass      = 5000
	maxCandidateItemsPerSlot = 5000
	maxParallelSearchPasses  = 4
	progressReportInterval   = 10000
	setCoverageSearchBonus   = 1000000
)

var gearSlots = []string{"Weapon", "Helmet", "Armor", "Necklace", "Ring", "Boots"}
var statKeys = []string{"atk", "def", "hp", "spd", "cr", "cd", "acc", "res"}

var fourPieceSets = map[string]bool{
	"AttackSet":      true,
	"SpeedSet":       true,
	"DestructionSet": true,
	"LifestealSet":   true,
	"ProtectionSet":  true,
	"CounterSet":     true,
	"RageSet":        true,
	"RevengeSet":     true,
	"InjurySet":      true,
	"ReversalSet":    true,
	"RiposteSet":     true,
	"WarfareSet":     true,
}

var twoPieceSets = map[string]bool{
	"HealthSet":      true,
	"DefenseSet":     true,
	"CriticalSet":    true,
	"HitSet":         true,
	"ResistSet":      true,
	"UnitySet":       true,
	"ImmunitySet":    true,
	"PenetrationSet": true,
	"TorrentSet":     true,
	"PursuitSet":     true,
}

type itemStats struct {
	atk    float64
	def    float64
	hp     float64
	spd    float64
	cr     float64
	cd     float64
	acc    float64
	res    float64
	atkPct float64
	defPct float64
	hpPct  float64
}

type baseStats struct {
	atk float64
	def float64
	hp  float64
	spd float64
	cr  float64
	cd  float64
	acc float64
	res float64
}

// ParseItems converts raw interface data to optimizer items.
func ParseItems(items []interface{}) ([]model.OptimizeItem, error) {
	if len(items) == 0 {
		return []model.OptimizeItem{}, nil
	}
	data, err := json.Marshal(items)
	if err != nil {
		return nil, err
	}
	var out []model.OptimizeItem
	if err := json.Unmarshal(data, &out); err != nil {
		return nil, err
	}
	for i := range out {
		if out[i].Set == "" && out[i].F != "" {
			if mapped, ok := ingameSetMap[out[i].F]; ok {
				out[i].Set = mapped
			}
		}
	}
	return out, nil
}

type ProgressCallback func(checked int, total int, matched int)

type scoredOptimizeItem struct {
	item  model.OptimizeItem
	stats itemStats
	score float64
}

type searchSlotItem struct {
	item             model.OptimizeItem
	stats            itemStats
	score            float64
	requiredSetIndex int
}

type optimizeCandidateItem struct {
	item  model.OptimizeItem
	stats itemStats
	score float64
}

type optimizeSearchPass struct {
	objective      string
	req            model.OptimizeRequest
	topItemsByGear [][]scoredOptimizeItem
	maxCombos      int
}

type optimizePassExecutionResult struct {
	results []model.OptimizeResult
	checked int
	matched int
	err     error
}

// ParseHeroes converts raw interface data to optimizer heroes.
func ParseHeroes(heroes []interface{}) ([]model.OptimizeHero, error) {
	if len(heroes) == 0 {
		return []model.OptimizeHero{}, nil
	}
	data, err := json.Marshal(heroes)
	if err != nil {
		return nil, err
	}
	var out []model.OptimizeHero
	if err := json.Unmarshal(data, &out); err != nil {
		return nil, err
	}
	return out, nil
}

func Optimize(items []model.OptimizeItem, heroes []model.OptimizeHero, req model.OptimizeRequest) (*model.OptimizeResponse, error) {
	return OptimizeWithContext(context.Background(), items, heroes, req, nil)
}

func OptimizeWithContext(ctx context.Context, items []model.OptimizeItem, heroes []model.OptimizeHero, req model.OptimizeRequest, progress ProgressCallback) (*model.OptimizeResponse, error) {
	if ctx == nil {
		ctx = context.Background()
	}
	if req.HeroID == "" {
		return nil, fmt.Errorf("hero code is required")
	}

	hero := findHeroByCode(heroes, req.HeroID)
	if hero == nil {
		return nil, fmt.Errorf("hero not found")
	}

	maxItems := req.MaxItemsPerSlot
	if maxItems <= 0 {
		maxItems = defaultMaxItemsPerSlot
	}
	maxCombos := req.MaxCombos
	if maxCombos <= 0 {
		maxCombos = defaultMaxCombos
	}
	maxResults := req.MaxResults
	if maxResults <= 0 {
		maxResults = defaultMaxResults
	}

	base := buildBaseStats(hero)
	bonus := req.BonusStats

	setRequirements, requiredSetPieces, validSetFilters := buildSetRequirements(req.SetFilters)
	if !validSetFilters {
		return nil, fmt.Errorf("invalid set filter combination: selected set effects require more than 6 gear pieces")
	}
	if len(setRequirements) == 0 {
		return nil, fmt.Errorf("set filter is required")
	}
	if !hasAnyWeightPreference(req.WeightValues) {
		return nil, fmt.Errorf("attribute preference is required")
	}
	restrictToSelectedSets := len(setRequirements) > 0 && requiredSetPieces == len(gearSlots)

	itemsByGear := map[string][]model.OptimizeItem{}
	for _, slot := range gearSlots {
		itemsByGear[slot] = []model.OptimizeItem{}
	}
	for _, item := range items {
		if item.Gear == "" {
			continue
		}
		if !itemPassesMainStatFilter(item, req.MainStatFilters) {
			continue
		}
		if restrictToSelectedSets {
			if item.Set == "" {
				continue
			}
			if _, ok := setRequirements[item.Set]; !ok {
				continue
			}
		}
		if _, ok := itemsByGear[item.Gear]; ok {
			itemsByGear[item.Gear] = append(itemsByGear[item.Gear], item)
		}
	}

	statsCache := buildStatsCache(itemsByGear)
	searchObjectives := buildSearchObjectives(req)
	searchPasses := buildOptimizeSearchPasses(itemsByGear, statsCache, base, req, maxItems, maxCombos, setRequirements, !restrictToSelectedSets, searchObjectives)
	totalExpectedCombos := 0
	for _, pass := range searchPasses {
		totalExpectedCombos += estimatePassCombos(pass.topItemsByGear, pass.maxCombos)
	}
	if progress != nil {
		progress(0, totalExpectedCombos, 0)
	}

	passResults, checkedCount, matchedCount, uniqueMatchedCount, err := collectOptimizeSearchPasses(
		ctx,
		searchPasses,
		statsCache,
		base,
		bonus,
		req,
		setRequirements,
		totalExpectedCombos,
		progress,
	)
	if err != nil {
		return nil, err
	}

	resultByKey := map[string]model.OptimizeResult{}
	for _, passResult := range passResults {
		for _, result := range passResult.results {
			resultByKey[result.Key] = result
		}
	}

	results := make([]model.OptimizeResult, 0, len(resultByKey))
	for _, result := range resultByKey {
		results = append(results, result)
	}

	results = selectOptimizeResults(results, maxResults, searchObjectives)

	log.Printf("[optimizer] checked=%d matched=%d unique=%d retained=%d returned=%d", checkedCount, matchedCount, uniqueMatchedCount, len(resultByKey), len(results))
	if progress != nil {
		progress(totalExpectedCombos, totalExpectedCombos, uniqueMatchedCount)
	}

	totalCombos := uniqueMatchedCount
	return &model.OptimizeResponse{
		TotalCombos: totalCombos,
		Results:     results,
	}, nil
}

func collectOptimizeSearchPasses(
	ctx context.Context,
	searchPasses []optimizeSearchPass,
	statsCache map[string]itemStats,
	base baseStats,
	bonus model.BonusStats,
	req model.OptimizeRequest,
	setRequirements map[string]int,
	totalExpectedCombos int,
	progress ProgressCallback,
) ([]optimizePassExecutionResult, int, int, int, error) {
	if len(searchPasses) == 0 {
		return nil, 0, 0, 0, nil
	}

	workerCtx, cancel := context.WithCancel(ctx)
	defer cancel()

	jobs := make(chan int, len(searchPasses))
	results := make(chan optimizePassExecutionResult, len(searchPasses))
	passChecked := make([]int64, len(searchPasses))
	uniqueMatched := map[string]struct{}{}
	var progressMu sync.Mutex
	lastProgressChecked := 0
	lastProgressMatched := 0

	reportProgress := func() {
		if progress == nil {
			return
		}
		checked := sumAtomicInts(passChecked)
		progressMu.Lock()
		matched := len(uniqueMatched)
		if checked < lastProgressChecked {
			checked = lastProgressChecked
		} else {
			lastProgressChecked = checked
		}
		if matched < lastProgressMatched {
			matched = lastProgressMatched
		} else {
			lastProgressMatched = matched
		}
		progress(checked, totalExpectedCombos, matched)
		progressMu.Unlock()
	}

	recordMatched := func(key string) {
		if key == "" {
			return
		}
		progressMu.Lock()
		uniqueMatched[key] = struct{}{}
		progressMu.Unlock()
	}

	for index := range searchPasses {
		jobs <- index
	}
	close(jobs)

	workerCount := optimizeWorkerCount(len(searchPasses))
	for worker := 0; worker < workerCount; worker++ {
		go func() {
			for index := range jobs {
				pass := searchPasses[index]
				passResults, checked, matched, err := collectOptimizeResults(
					workerCtx,
					pass.topItemsByGear,
					statsCache,
					base,
					bonus,
					pass.req,
					pass.objective,
					setRequirements,
					req.WeightValues,
					pass.maxCombos,
					func(checked int, _ int) {
						atomic.StoreInt64(&passChecked[index], int64(checked))
						reportProgress()
					},
					recordMatched,
				)
				atomic.StoreInt64(&passChecked[index], int64(checked))
				reportProgress()
				if err != nil {
					cancel()
				}
				results <- optimizePassExecutionResult{
					results: passResults,
					checked: checked,
					matched: matched,
					err:     err,
				}
			}
		}()
	}

	passResults := make([]optimizePassExecutionResult, 0, len(searchPasses))
	var firstErr error
	for range searchPasses {
		result := <-results
		passResults = append(passResults, result)
		if result.err != nil && firstErr == nil {
			firstErr = result.err
			cancel()
		}
	}

	checkedCount := 0
	matchedCount := 0
	for _, result := range passResults {
		checkedCount += result.checked
		matchedCount += result.matched
	}
	progressMu.Lock()
	uniqueMatchedCount := len(uniqueMatched)
	progressMu.Unlock()
	return passResults, checkedCount, matchedCount, uniqueMatchedCount, firstErr
}

func optimizeWorkerCount(passCount int) int {
	if passCount <= 1 {
		return passCount
	}
	workers := runtime.NumCPU()
	if workers > 1 {
		workers--
	}
	if workers < 1 {
		workers = 1
	}
	if workers > maxParallelSearchPasses {
		workers = maxParallelSearchPasses
	}
	if workers > passCount {
		workers = passCount
	}
	return workers
}

func sumAtomicInts(values []int64) int {
	total := 0
	for index := range values {
		total += int(atomic.LoadInt64(&values[index]))
	}
	return total
}

func buildOptimizeSearchPasses(
	itemsByGear map[string][]model.OptimizeItem,
	statsCache map[string]itemStats,
	base baseStats,
	req model.OptimizeRequest,
	maxItems int,
	maxCombos int,
	setRequirements map[string]int,
	preferSelectedSets bool,
	objectives []string,
) []optimizeSearchPass {
	if len(objectives) == 0 {
		objectives = []string{""}
	}

	passes := make([]optimizeSearchPass, len(objectives))
	jobs := make(chan int, len(objectives))
	for index := range objectives {
		jobs <- index
	}
	close(jobs)

	var wg sync.WaitGroup
	workerCount := optimizeWorkerCount(len(objectives))
	wg.Add(workerCount)
	for worker := 0; worker < workerCount; worker++ {
		go func() {
			defer wg.Done()
			for index := range jobs {
				objective := objectives[index]
				passReq := req
				passReq.WeightValues = weightsForObjective(req.WeightValues, objective)
				passes[index] = optimizeSearchPass{
					objective:      objective,
					req:            passReq,
					topItemsByGear: buildTopItemsByGear(itemsByGear, statsCache, base, passReq, maxItems, setRequirements, preferSelectedSets),
					maxCombos:      maxCombos,
				}
			}
		}()
	}
	wg.Wait()
	return passes
}

func estimatePassCombos(topItemsByGear [][]scoredOptimizeItem, maxCombos int) int {
	if len(topItemsByGear) != len(gearSlots) || maxCombos <= 0 {
		return 0
	}
	total := 1
	for _, slotItems := range topItemsByGear {
		if len(slotItems) == 0 {
			return 0
		}
		total *= len(slotItems)
		if total >= maxCombos {
			return maxCombos
		}
	}
	return total
}

func buildStatsCache(itemsByGear map[string][]model.OptimizeItem) map[string]itemStats {
	statsCache := map[string]itemStats{}
	for _, items := range itemsByGear {
		for _, item := range items {
			statsCache[itemKey(item)] = buildItemStats(item)
		}
	}
	return statsCache
}

func buildTopItemsByGear(
	itemsByGear map[string][]model.OptimizeItem,
	statsCache map[string]itemStats,
	base baseStats,
	req model.OptimizeRequest,
	maxItems int,
	setRequirements map[string]int,
	preferSelectedSets bool,
) [][]scoredOptimizeItem {
	focusKeys := buildCandidateFocusKeys(req)
	topItemsByGear := make([][]scoredOptimizeItem, 0, len(gearSlots))
	for _, slot := range gearSlots {
		slotItems := itemsByGear[slot]
		scored := make([]optimizeCandidateItem, 0, len(slotItems))
		for _, item := range slotItems {
			stats := statsCache[itemKey(item)]
			score := scoreCandidateItem(stats, base, req)
			scored = append(scored, optimizeCandidateItem{item: item, stats: stats, score: score})
		}
		sort.Slice(scored, func(i, j int) bool {
			if scored[i].score == scored[j].score {
				return itemKey(scored[i].item) < itemKey(scored[j].item)
			}
			return scored[i].score > scored[j].score
		})

		requestedLimit := maxItems
		if requestedLimit > len(scored) {
			requestedLimit = len(scored)
		}

		requiredSetKeys := sortedRequiredSetKeys(setRequirements)
		candidateLimit := candidateLimitForSlot(len(scored), requestedLimit, focusKeys, requiredSetKeys, preferSelectedSets)
		selected := buildCandidateUnion(scored, focusKeys, requiredSetKeys, base, requestedLimit, preferSelectedSets)
		selected = paretoPruneCandidates(selected, focusKeys, base, setRequirements)
		selected = capCandidatesByChannels(selected, focusKeys, requiredSetKeys, base, candidateLimit, preferSelectedSets)

		sort.Slice(selected, func(i, j int) bool {
			if selected[i].score == selected[j].score {
				return itemKey(selected[i].item) < itemKey(selected[j].item)
			}
			return selected[i].score > selected[j].score
		})
		if len(selected) > candidateLimit {
			selected = selected[:candidateLimit]
		}
		topItemsByGear = append(topItemsByGear, selected)
	}
	return topItemsByGear
}

func buildCandidateUnion(
	scored []optimizeCandidateItem,
	focusKeys []string,
	requiredSetKeys []string,
	base baseStats,
	limit int,
	preferSelectedSets bool,
) []scoredOptimizeItem {
	if len(scored) == 0 || limit <= 0 {
		return []scoredOptimizeItem{}
	}
	channelQuota := limit
	if len(focusKeys) > 0 {
		channelQuota = limit / 2
		if channelQuota < 1 {
			channelQuota = 1
		}
	}
	if channelQuota > len(scored) {
		channelQuota = len(scored)
	}

	selected := make([]scoredOptimizeItem, 0, minInt(len(scored), maxCandidateItemsPerSlot))
	selectedKeys := map[string]struct{}{}
	addCandidates := func(candidates []optimizeCandidateItem, quota int) {
		for _, candidate := range candidates {
			if len(selected) >= maxCandidateItemsPerSlot || quota <= 0 {
				return
			}
			key := itemKey(candidate.item)
			if _, ok := selectedKeys[key]; ok {
				continue
			}
			selectedKeys[key] = struct{}{}
			selected = append(selected, scoredOptimizeItem{
				item:  candidate.item,
				stats: candidate.stats,
				score: candidate.score,
			})
			quota--
		}
	}

	addCandidates(scored, channelQuota)
	for _, key := range focusKeys {
		addCandidates(rankCandidatesByStat(scored, base, key), channelQuota)
	}
	if preferSelectedSets {
		for _, setKey := range requiredSetKeys {
			setCandidates := filterCandidatesBySet(scored, setKey)
			addCandidates(setCandidates, channelQuota)
			for _, key := range focusKeys {
				addCandidates(rankCandidatesByStat(setCandidates, base, key), channelQuota)
			}
		}
	}
	return selected
}

func candidateLimitForSlot(
	totalItems int,
	requestedLimit int,
	focusKeys []string,
	requiredSetKeys []string,
	preferSelectedSets bool,
) int {
	if totalItems <= 0 || requestedLimit <= 0 {
		return 0
	}
	channelCount := 1 + len(focusKeys)
	if preferSelectedSets {
		channelCount += len(requiredSetKeys) * (1 + len(focusKeys))
	}
	limit := requestedLimit
	if channelCount > 1 {
		limit = requestedLimit * channelCount
	}
	if limit > maxCandidateItemsPerSlot {
		limit = maxCandidateItemsPerSlot
	}
	if limit > totalItems {
		limit = totalItems
	}
	return limit
}

func paretoPruneCandidates(
	selected []scoredOptimizeItem,
	focusKeys []string,
	base baseStats,
	setRequirements map[string]int,
) []scoredOptimizeItem {
	if len(selected) <= 1 || len(focusKeys) == 0 {
		return selected
	}
	bySet := map[string][]scoredOptimizeItem{}
	for _, candidate := range selected {
		bySet[candidate.item.Set] = append(bySet[candidate.item.Set], candidate)
	}
	out := make([]scoredOptimizeItem, 0, len(selected))
	for _, group := range bySet {
		for i, candidate := range group {
			dominated := false
			for j, other := range group {
				if i == j {
					continue
				}
				if dominatesCandidate(other, candidate, focusKeys, base, setRequirements) {
					dominated = true
					break
				}
			}
			if !dominated {
				out = append(out, candidate)
			}
		}
	}
	return out
}

func capCandidatesByChannels(
	selected []scoredOptimizeItem,
	focusKeys []string,
	requiredSetKeys []string,
	base baseStats,
	limit int,
	preferSelectedSets bool,
) []scoredOptimizeItem {
	if len(selected) <= limit || limit <= 0 {
		return selected
	}
	candidates := optimizeCandidatesFromScored(selected)
	sort.Slice(candidates, func(i, j int) bool {
		return compareCandidateScore(candidates[i], candidates[j])
	})

	channelCount := 1 + len(focusKeys)
	if preferSelectedSets {
		channelCount += len(requiredSetKeys) * (1 + len(focusKeys))
	}
	channelQuota := limit / channelCount
	if channelQuota < 1 {
		channelQuota = 1
	}

	out := make([]scoredOptimizeItem, 0, limit)
	outKeys := map[string]struct{}{}
	addScored := func(items []scoredOptimizeItem, quota int) {
		for _, item := range items {
			if len(out) >= limit || quota <= 0 {
				return
			}
			key := itemKey(item.item)
			if _, ok := outKeys[key]; ok {
				continue
			}
			outKeys[key] = struct{}{}
			out = append(out, item)
			quota--
		}
	}
	addCandidates := func(items []optimizeCandidateItem, quota int) {
		scoredItems := make([]scoredOptimizeItem, 0, len(items))
		for _, item := range items {
			scoredItems = append(scoredItems, scoredOptimizeItem{item: item.item, stats: item.stats, score: item.score})
		}
		addScored(scoredItems, quota)
	}

	addCandidates(candidates, channelQuota)
	for _, key := range focusKeys {
		addCandidates(rankCandidatesByStat(candidates, base, key), channelQuota)
	}
	if preferSelectedSets {
		for _, setKey := range requiredSetKeys {
			setCandidates := filterCandidatesBySet(candidates, setKey)
			addCandidates(setCandidates, channelQuota)
			for _, key := range focusKeys {
				addCandidates(rankCandidatesByStat(setCandidates, base, key), channelQuota)
			}
		}
	}
	if len(out) < limit {
		addCandidates(candidates, limit-len(out))
	}
	return out
}

func dominatesCandidate(
	left scoredOptimizeItem,
	right scoredOptimizeItem,
	focusKeys []string,
	base baseStats,
	setRequirements map[string]int,
) bool {
	if requiredSetRank(left.item.Set, setRequirements) < requiredSetRank(right.item.Set, setRequirements) {
		return false
	}
	strictlyBetter := left.score > right.score
	for _, key := range focusKeys {
		leftValue := itemStatContribution(left.stats, base, key)
		rightValue := itemStatContribution(right.stats, base, key)
		if leftValue < rightValue {
			return false
		}
		if leftValue > rightValue {
			strictlyBetter = true
		}
	}
	return strictlyBetter
}

func requiredSetRank(setName string, setRequirements map[string]int) int {
	if setName == "" {
		return 0
	}
	if _, ok := setRequirements[setName]; ok {
		return 1
	}
	return 0
}

func rankCandidatesByStat(candidates []optimizeCandidateItem, base baseStats, key string) []optimizeCandidateItem {
	ranked := append([]optimizeCandidateItem(nil), candidates...)
	sort.Slice(ranked, func(i, j int) bool {
		left := itemStatContribution(ranked[i].stats, base, key)
		right := itemStatContribution(ranked[j].stats, base, key)
		if left == right {
			return compareCandidateScore(ranked[i], ranked[j])
		}
		return left > right
	})
	return ranked
}

func filterCandidatesBySet(candidates []optimizeCandidateItem, setKey string) []optimizeCandidateItem {
	out := make([]optimizeCandidateItem, 0, len(candidates))
	for _, candidate := range candidates {
		if candidate.item.Set == setKey {
			out = append(out, candidate)
		}
	}
	return out
}

func optimizeCandidatesFromScored(items []scoredOptimizeItem) []optimizeCandidateItem {
	out := make([]optimizeCandidateItem, 0, len(items))
	for _, item := range items {
		out = append(out, optimizeCandidateItem{
			item:  item.item,
			stats: item.stats,
			score: item.score,
		})
	}
	return out
}

func compareCandidateScore(left optimizeCandidateItem, right optimizeCandidateItem) bool {
	if left.score == right.score {
		return itemKey(left.item) < itemKey(right.item)
	}
	return left.score > right.score
}

func minInt(left int, right int) int {
	if left < right {
		return left
	}
	return right
}

func buildCandidateFocusKeys(req model.OptimizeRequest) []string {
	focusKeys := make([]string, 0, len(statKeys))
	seen := map[string]struct{}{}
	addKey := func(key string) {
		if !isStatKey(key) {
			return
		}
		if _, ok := seen[key]; ok {
			return
		}
		seen[key] = struct{}{}
		focusKeys = append(focusKeys, key)
	}

	weightedKeys := make([]string, 0, len(statKeys))
	for _, key := range statKeys {
		if req.WeightValues[key] > 0 {
			weightedKeys = append(weightedKeys, key)
		}
	}
	sort.SliceStable(weightedKeys, func(i, j int) bool {
		left := req.WeightValues[weightedKeys[i]]
		right := req.WeightValues[weightedKeys[j]]
		if left == right {
			return weightedKeys[i] < weightedKeys[j]
		}
		return left > right
	})
	for _, key := range weightedKeys {
		addKey(key)
	}

	for _, key := range statKeys {
		if rangeVal, ok := req.StatFilters[key]; ok {
			if rangeVal.Min != nil || rangeVal.Max != nil {
				addKey(key)
			}
		}
	}

	return focusKeys
}

func buildSearchObjectives(req model.OptimizeRequest) []string {
	objectives := []string{""}
	weightedKeys := weightedStatKeys(req.WeightValues)
	if len(weightedKeys) > 0 {
		return append(objectives, weightedKeys...)
	}
	return append(objectives, statKeys...)
}

func weightedStatKeys(weights map[string]float64) []string {
	keys := make([]string, 0, len(statKeys))
	for _, key := range statKeys {
		if weights[key] > 0 {
			keys = append(keys, key)
		}
	}
	sort.SliceStable(keys, func(i, j int) bool {
		left := weights[keys[i]]
		right := weights[keys[j]]
		if left == right {
			return keys[i] < keys[j]
		}
		return left > right
	})
	return keys
}

func sortedRequiredSetKeys(setRequirements map[string]int) []string {
	keys := make([]string, 0, len(setRequirements))
	for key := range setRequirements {
		keys = append(keys, key)
	}
	sort.Strings(keys)
	return keys
}

func cloneWeights(weights map[string]float64) map[string]float64 {
	if len(weights) == 0 {
		return nil
	}
	out := make(map[string]float64, len(weights))
	for key, value := range weights {
		out[key] = value
	}
	return out
}

func weightsForObjective(weights map[string]float64, objective string) map[string]float64 {
	if objective == "" || !isStatKey(objective) {
		return cloneWeights(weights)
	}
	out := make(map[string]float64, len(statKeys))
	for _, key := range statKeys {
		out[key] = 0
	}
	if weights[objective] > 0 {
		out[objective] = weights[objective]
	} else {
		out[objective] = 1
	}
	return out
}

func hasAnyWeightPreference(weights map[string]float64) bool {
	for _, key := range statKeys {
		if weights[key] > 0 {
			return true
		}
	}
	return false
}

func isStatKey(key string) bool {
	switch key {
	case "atk", "def", "hp", "spd", "cr", "cd", "acc", "res":
		return true
	default:
		return false
	}
}

func collectOptimizeResults(
	ctx context.Context,
	topItemsByGear [][]scoredOptimizeItem,
	statsCache map[string]itemStats,
	base baseStats,
	bonus model.BonusStats,
	req model.OptimizeRequest,
	objective string,
	setRequirements map[string]int,
	scoreWeights map[string]float64,
	maxCombos int,
	onProgress func(checked int, matched int),
	onMatched func(key string),
) ([]model.OptimizeResult, int, int, error) {
	if len(topItemsByGear) != 6 {
		return []model.OptimizeResult{}, 0, 0, nil
	}
	searchItemsByGear, requiredPieces := buildSearchItemsByGear(topItemsByGear, setRequirements)
	if len(searchItemsByGear) != 6 {
		return []model.OptimizeResult{}, 0, 0, nil
	}

	checkedCount := 0
	reportedCount := 0
	matchedCount := 0
	retained := &resultHeap{objective: objective}
	heap.Init(retained)

	startIndices := [6]int{}
	startScore := 0.0
	for slot := 0; slot < len(searchItemsByGear); slot++ {
		if len(searchItemsByGear[slot]) == 0 {
			return retained.items, checkedCount, matchedCount, nil
		}
		startScore += searchItemsByGear[slot][0].score
	}
	startScore += setCoverageScoreForSearch(searchItemsByGear, startIndices, requiredPieces)
	startStates := []combinationState{{indices: startIndices, score: startScore}}
	for _, setSeed := range buildSetCoverageSeedStates(searchItemsByGear, requiredPieces) {
		if setSeed.indices == startIndices {
			continue
		}
		startStates = append(startStates, setSeed)
	}

	states := &combinationHeap{}
	heap.Init(states)
	visited := map[combinationVisitKey]struct{}{}
	for _, state := range startStates {
		visitKey := packCombinationVisitKey(state.indices)
		if _, ok := visited[visitKey]; ok {
			continue
		}
		visited[visitKey] = struct{}{}
		heap.Push(states, state)
	}

	for states.Len() > 0 && checkedCount < maxCombos {
		state := heap.Pop(states).(combinationState)
		checkedCount++
		if checkedCount-reportedCount >= progressReportInterval {
			if err := ctx.Err(); err != nil {
				if onProgress != nil {
					onProgress(checkedCount, matchedCount)
				}
				return retained.items, checkedCount, matchedCount, err
			}
			if onProgress != nil {
				onProgress(checkedCount, matchedCount)
			}
			reportedCount = checkedCount
		}

		setCounts := setCountsArrayForSearch(searchItemsByGear, state.indices, len(requiredPieces))
		currentCoverageScore := setCoverageScoreFromCountArray(setCounts, requiredPieces)

		if passesRequiredSetCountsArray(setCounts, requiredPieces) {
			totals := buildTotalStatsForSearch(searchItemsByGear, state.indices, base, bonus)
			if passesFilters(totals, req.StatFilters) {
				matchedCount++
				itemsList := buildItemsListForSearch(searchItemsByGear, state.indices)
				completed := getCompletedSets(itemsList)
				setName := "无套装"
				if len(completed) > 0 {
					setName = joinSets(completed)
				}
				key := buildKey(itemsList)
				if onMatched != nil {
					onMatched(key)
				}
				result := model.OptimizeResult{
					Key:   key,
					Sets:  setName,
					Atk:   panelWholeStat(totals.atk),
					Def:   panelWholeStat(totals.def),
					Hp:    panelWholeStat(totals.hp),
					Spd:   panelRoundedStat(totals.spd),
					Cr:    math.Round(totals.cr),
					Cd:    math.Round(totals.cd),
					Acc:   math.Round(totals.acc),
					Res:   math.Round(totals.res),
					Score: scoreTotals(totals, scoreWeights),
					Items: itemsList,
				}
				retainResult(retained, result, maxCollectedPerPass)
			}
		}

		for slot := 0; slot < len(searchItemsByGear); slot++ {
			nextIndices := state.indices
			nextIndices[slot]++
			if nextIndices[slot] >= len(searchItemsByGear[slot]) {
				continue
			}
			nextVisitKey := packCombinationVisitKey(nextIndices)
			if _, ok := visited[nextVisitKey]; ok {
				continue
			}
			visited[nextVisitKey] = struct{}{}
			nextScore := state.score -
				searchItemsByGear[slot][state.indices[slot]].score +
				searchItemsByGear[slot][nextIndices[slot]].score
			nextCounts := setCounts
			currentSetIndex := searchItemsByGear[slot][state.indices[slot]].requiredSetIndex
			if currentSetIndex >= 0 && currentSetIndex < len(requiredPieces) {
				nextCounts[currentSetIndex]--
			}
			nextSetIndex := searchItemsByGear[slot][nextIndices[slot]].requiredSetIndex
			if nextSetIndex >= 0 && nextSetIndex < len(requiredPieces) {
				nextCounts[nextSetIndex]++
			}
			nextScore += setCoverageScoreFromCountArray(nextCounts, requiredPieces) - currentCoverageScore
			heap.Push(states, combinationState{
				indices: nextIndices,
				score:   nextScore,
			})
		}
	}

	if onProgress != nil {
		onProgress(checkedCount, matchedCount)
	}

	return retained.items, checkedCount, matchedCount, nil
}

func buildSearchItemsByGear(topItemsByGear [][]scoredOptimizeItem, setRequirements map[string]int) ([][]searchSlotItem, []int) {
	requiredSetKeys := sortedRequiredSetKeys(setRequirements)
	requiredIndex := map[string]int{}
	requiredPieces := make([]int, len(requiredSetKeys))
	for index, setName := range requiredSetKeys {
		requiredIndex[setName] = index
		requiredPieces[index] = setRequirements[setName]
	}

	out := make([][]searchSlotItem, 0, len(topItemsByGear))
	for _, slotItems := range topItemsByGear {
		items := make([]searchSlotItem, 0, len(slotItems))
		for _, candidate := range slotItems {
			setIndex := -1
			if index, ok := requiredIndex[candidate.item.Set]; ok {
				setIndex = index
			}
			items = append(items, searchSlotItem{
				item:             candidate.item,
				stats:            candidate.stats,
				score:            candidate.score,
				requiredSetIndex: setIndex,
			})
		}
		out = append(out, items)
	}
	return out, requiredPieces
}

func buildSetCoverageSeedStates(searchItemsByGear [][]searchSlotItem, requiredPieces []int) []combinationState {
	if len(requiredPieces) == 0 || len(searchItemsByGear) != len(gearSlots) {
		return nil
	}

	assignments := buildRequiredSetSlotAssignments(requiredPieces)
	seeds := make([]combinationState, 0, len(assignments))
	for _, assignment := range assignments {
		indices := [6]int{}
		valid := true
		for slot, setIndex := range assignment {
			index := firstCandidateIndexForRequiredSet(searchItemsByGear[slot], setIndex)
			if index < 0 {
				valid = false
				break
			}
			indices[slot] = index
		}
		if !valid {
			continue
		}
		seeds = append(seeds, combinationState{
			indices: indices,
			score:   combinationScoreForSearch(searchItemsByGear, indices) + setCoverageScoreForSearch(searchItemsByGear, indices, requiredPieces),
		})
	}
	return seeds
}

func buildRequiredSetSlotAssignments(requiredPieces []int) []map[int]int {
	assignments := []map[int]int{{}}
	for setIndex, pieces := range requiredPieces {
		if pieces <= 0 {
			continue
		}
		nextAssignments := make([]map[int]int, 0, len(assignments))
		for _, assignment := range assignments {
			availableSlots := make([]int, 0, len(gearSlots))
			for slot := range gearSlots {
				if _, used := assignment[slot]; !used {
					availableSlots = append(availableSlots, slot)
				}
			}
			for _, slots := range chooseSlotCombos(availableSlots, pieces) {
				next := cloneSlotAssignment(assignment)
				for _, slot := range slots {
					next[slot] = setIndex
				}
				nextAssignments = append(nextAssignments, next)
			}
		}
		assignments = nextAssignments
	}
	return assignments
}

func chooseSlotCombos(slots []int, count int) [][]int {
	if count <= 0 {
		return [][]int{{}}
	}
	if count > len(slots) {
		return nil
	}
	var out [][]int
	var current []int
	var walk func(start int)
	walk = func(start int) {
		if len(current) == count {
			combo := append([]int(nil), current...)
			out = append(out, combo)
			return
		}
		needed := count - len(current)
		for i := start; i <= len(slots)-needed; i++ {
			current = append(current, slots[i])
			walk(i + 1)
			current = current[:len(current)-1]
		}
	}
	walk(0)
	return out
}

func cloneSlotAssignment(assignment map[int]int) map[int]int {
	out := make(map[int]int, len(assignment))
	for slot, setIndex := range assignment {
		out[slot] = setIndex
	}
	return out
}

func firstCandidateIndexForRequiredSet(items []searchSlotItem, setIndex int) int {
	for index, candidate := range items {
		if candidate.requiredSetIndex == setIndex {
			return index
		}
	}
	return -1
}

func setCoverageScoreForSearch(searchItemsByGear [][]searchSlotItem, indices [6]int, requiredPieces []int) float64 {
	if len(requiredPieces) == 0 || len(searchItemsByGear) != len(gearSlots) {
		return 0
	}
	counts := setCountsArrayForSearch(searchItemsByGear, indices, len(requiredPieces))
	return setCoverageScoreFromCountArray(counts, requiredPieces)
}

func setCoverageScoreFromCountArray(counts [6]int, requiredPieces []int) float64 {
	score := 0.0
	for setIndex, required := range requiredPieces {
		if setIndex >= len(counts) {
			break
		}
		if required <= 0 {
			continue
		}
		covered := counts[setIndex]
		if covered > required {
			covered = required
		}
		score += float64(covered) * setCoverageSearchBonus
	}
	return score
}

func setCountsArrayForSearch(searchItemsByGear [][]searchSlotItem, indices [6]int, requiredSetCount int) [6]int {
	var counts [6]int
	if requiredSetCount <= 0 {
		return counts
	}
	if requiredSetCount > len(counts) {
		requiredSetCount = len(counts)
	}
	for slot := 0; slot < len(searchItemsByGear); slot++ {
		index := indices[slot]
		if index < 0 || index >= len(searchItemsByGear[slot]) {
			continue
		}
		setIndex := searchItemsByGear[slot][index].requiredSetIndex
		if setIndex >= 0 && setIndex < requiredSetCount {
			counts[setIndex]++
		}
	}
	return counts
}

func passesRequiredSetCountsArray(counts [6]int, requiredPieces []int) bool {
	for index, required := range requiredPieces {
		if required <= 0 {
			continue
		}
		if index >= len(counts) || counts[index] < required {
			return false
		}
	}
	return true
}

func packCombinationVisitKey(indices [6]int) combinationVisitKey {
	return combinationVisitKey{
		lo: uint64(uint32(indices[0])) |
			uint64(uint32(indices[1]))<<32,
		hi: uint64(uint32(indices[2])) |
			uint64(uint32(indices[3]))<<16 |
			uint64(uint32(indices[4]))<<32 |
			uint64(uint32(indices[5]))<<48,
	}
}

func combinationScoreForSearch(searchItemsByGear [][]searchSlotItem, indices [6]int) float64 {
	score := 0.0
	for slot := 0; slot < len(searchItemsByGear); slot++ {
		score += searchItemsByGear[slot][indices[slot]].score
	}
	return score
}

func resultObjectiveValue(result model.OptimizeResult, objective string) float64 {
	switch objective {
	case "atk":
		return result.Atk
	case "def":
		return result.Def
	case "hp":
		return result.Hp
	case "spd":
		return result.Spd
	case "cr":
		return result.Cr
	case "cd":
		return result.Cd
	case "acc":
		return result.Acc
	case "res":
		return result.Res
	default:
		return result.Score
	}
}

func compareResultsForObjective(a model.OptimizeResult, b model.OptimizeResult, objective string) int {
	aPrimary := resultObjectiveValue(a, objective)
	bPrimary := resultObjectiveValue(b, objective)
	if aPrimary < bPrimary {
		return -1
	}
	if aPrimary > bPrimary {
		return 1
	}
	if a.Score < b.Score {
		return -1
	}
	if a.Score > b.Score {
		return 1
	}
	if a.Key < b.Key {
		return -1
	}
	if a.Key > b.Key {
		return 1
	}
	return 0
}

type resultHeap struct {
	objective string
	items     []model.OptimizeResult
}

type combinationState struct {
	indices [6]int
	score   float64
}

type combinationVisitKey struct {
	lo uint64
	hi uint64
}

type combinationHeap []combinationState

func (h combinationHeap) Len() int {
	return len(h)
}

func (h combinationHeap) Less(i int, j int) bool {
	return h[i].score > h[j].score
}

func (h combinationHeap) Swap(i int, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *combinationHeap) Push(x interface{}) {
	*h = append(*h, x.(combinationState))
}

func (h *combinationHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func (h resultHeap) Len() int {
	return len(h.items)
}

func (h resultHeap) Less(i int, j int) bool {
	return compareResultsForObjective(h.items[i], h.items[j], h.objective) < 0
}

func (h resultHeap) Swap(i int, j int) {
	h.items[i], h.items[j] = h.items[j], h.items[i]
}

func (h *resultHeap) Push(x interface{}) {
	h.items = append(h.items, x.(model.OptimizeResult))
}

func (h *resultHeap) Pop() interface{} {
	old := h.items
	n := len(old)
	item := old[n-1]
	h.items = old[:n-1]
	return item
}

func retainResult(h *resultHeap, result model.OptimizeResult, limit int) {
	if limit <= 0 {
		return
	}
	if h.Len() < limit {
		heap.Push(h, result)
		return
	}
	if compareResultsForObjective(result, h.items[0], h.objective) <= 0 {
		return
	}
	h.items[0] = result
	heap.Fix(h, 0)
}

func selectOptimizeResults(results []model.OptimizeResult, maxResults int, objectives []string) []model.OptimizeResult {
	if len(results) == 0 {
		return []model.OptimizeResult{}
	}
	if maxResults <= 0 {
		maxResults = defaultMaxResults
	}
	if len(objectives) <= 1 {
		out := append([]model.OptimizeResult(nil), results...)
		sort.Slice(out, func(i, j int) bool {
			if out[i].Score == out[j].Score {
				return out[i].Key < out[j].Key
			}
			return out[i].Score > out[j].Score
		})
		if len(out) > maxResults {
			out = out[:maxResults]
		}
		return out
	}

	selected := map[string]struct{}{}
	out := make([]model.OptimizeResult, 0, maxResults)
	addQuota := maxResults / len(objectives)
	if addQuota < 1 {
		addQuota = 1
	}
	addTop := func(value func(model.OptimizeResult) float64) {
		sorted := append([]model.OptimizeResult(nil), results...)
		sort.Slice(sorted, func(i, j int) bool {
			left := value(sorted[i])
			right := value(sorted[j])
			if left == right {
				return sorted[i].Score > sorted[j].Score
			}
			return left > right
		})
		limit := addQuota
		if limit > len(sorted) {
			limit = len(sorted)
		}
		added := 0
		for _, result := range sorted {
			if len(out) >= maxResults || added >= limit {
				return
			}
			if _, ok := selected[result.Key]; ok {
				continue
			}
			selected[result.Key] = struct{}{}
			out = append(out, result)
			added++
		}
	}

	for _, objective := range objectives {
		currentObjective := objective
		addTop(func(result model.OptimizeResult) float64 {
			return resultObjectiveValue(result, currentObjective)
		})
	}

	if len(selected) < maxResults {
		sorted := append([]model.OptimizeResult(nil), results...)
		sort.Slice(sorted, func(i, j int) bool {
			if sorted[i].Score == sorted[j].Score {
				return sorted[i].Key < sorted[j].Key
			}
			return sorted[i].Score > sorted[j].Score
		})
		for _, result := range sorted {
			if len(selected) >= maxResults {
				break
			}
			if _, ok := selected[result.Key]; ok {
				continue
			}
			selected[result.Key] = struct{}{}
			out = append(out, result)
		}
	}

	if len(out) > maxResults {
		out = out[:maxResults]
	}
	return out
}

func findHeroByCode(heroes []model.OptimizeHero, code string) *model.OptimizeHero {
	for i := range heroes {
		if heroes[i].Code == code {
			return &heroes[i]
		}
	}
	return nil
}

func buildBaseStats(hero *model.OptimizeHero) baseStats {
	atk := hero.BaseAtk
	if atk == 0 {
		atk = hero.Atk
	}
	def := hero.BaseDef
	if def == 0 {
		def = hero.Def
	}
	hp := hero.BaseHp
	if hp == 0 {
		hp = hero.Hp
	}
	spd := hero.BaseSpd
	if spd == 0 {
		spd = hero.Spd
	}
	cr := hero.BaseCr
	if cr == 0 {
		cr = hero.Cr
	}
	cd := hero.BaseCd
	if cd == 0 {
		cd = hero.Cd
	}
	acc := hero.BaseEff
	if acc == 0 {
		acc = hero.Eff
	}
	res := hero.BaseRes
	if res == 0 {
		res = hero.Res
	}
	return baseStats{
		atk: atk,
		def: def,
		hp:  hp,
		spd: spd,
		cr:  cr,
		cd:  cd,
		acc: acc,
		res: res,
	}
}

func buildItemStats(item model.OptimizeItem) itemStats {
	stats := itemStats{}
	apply := func(stat *model.OptimizeStat) {
		if stat == nil {
			return
		}
		switch stat.Type {
		case "Attack":
			stats.atk += stat.Value
		case "Defense":
			stats.def += stat.Value
		case "Health":
			stats.hp += stat.Value
		case "Speed":
			stats.spd += stat.Value
		case "CriticalHitChancePercent":
			stats.cr += stat.Value
		case "CriticalHitDamagePercent":
			stats.cd += stat.Value
		case "EffectivenessPercent":
			stats.acc += stat.Value
		case "EffectResistancePercent":
			stats.res += stat.Value
		case "AttackPercent":
			stats.atkPct += stat.Value
		case "DefensePercent":
			stats.defPct += stat.Value
		case "HealthPercent":
			stats.hpPct += stat.Value
		}
	}

	if item.Main != nil {
		apply(item.Main)
	}
	for i := range item.Substats {
		stat := item.Substats[i]
		apply(&stat)
	}

	return stats
}

func scoreCandidateItem(stats itemStats, base baseStats, req model.OptimizeRequest) float64 {
	return scoreItemWeights(stats, base, req.WeightValues)
}

func itemStatContribution(stats itemStats, base baseStats, key string) float64 {
	switch key {
	case "atk":
		return stats.atk + base.atk*(stats.atkPct/100)
	case "def":
		return stats.def + base.def*(stats.defPct/100)
	case "hp":
		return stats.hp + base.hp*(stats.hpPct/100)
	case "spd":
		return stats.spd
	case "cr":
		return stats.cr
	case "cd":
		return stats.cd
	case "acc":
		return stats.acc
	case "res":
		return stats.res
	default:
		return 0
	}
}

func scoreItemWeights(stats itemStats, base baseStats, weights map[string]float64) float64 {
	if len(weights) == 0 {
		return 0
	}
	w := func(key string) float64 {
		if val, ok := weights[key]; ok {
			if val <= 0 {
				return 0
			}
			return val
		}
		return 0
	}
	return (itemStatContribution(stats, base, "atk")/100)*w("atk") +
		(itemStatContribution(stats, base, "def")/100)*w("def") +
		(itemStatContribution(stats, base, "hp")/100)*w("hp") +
		stats.spd*2*w("spd") +
		stats.cr*w("cr") +
		stats.cd*w("cd") +
		stats.acc*w("acc") +
		stats.res*w("res")
}

type totalsStats struct {
	atk float64
	def float64
	hp  float64
	spd float64
	cr  float64
	cd  float64
	acc float64
	res float64
}

type setEffectCounts struct {
	attack      int
	health      int
	defense     int
	speed       int
	revenge     int
	reversal    int
	critical    int
	hit         int
	resist      int
	destruction int
	warfare     int
	torrent     int
}

func buildTotalStats(statsList []itemStats, base baseStats, bonus model.BonusStats, items []model.OptimizeItem) totalsStats {
	var totals itemStats
	for _, stats := range statsList {
		totals.atk += stats.atk
		totals.def += stats.def
		totals.hp += stats.hp
		totals.spd += stats.spd
		totals.cr += stats.cr
		totals.cd += stats.cd
		totals.acc += stats.acc
		totals.res += stats.res
		totals.atkPct += stats.atkPct
		totals.defPct += stats.defPct
		totals.hpPct += stats.hpPct
	}

	var counts setEffectCounts
	for _, item := range items {
		addSetEffectCount(&counts, item.Set)
	}

	return calculateTotalStats(totals, base, bonus, counts)
}

func buildTotalStatsForSearch(searchItemsByGear [][]searchSlotItem, indices [6]int, base baseStats, bonus model.BonusStats) totalsStats {
	var totals itemStats
	var counts setEffectCounts
	for slot := 0; slot < len(searchItemsByGear); slot++ {
		index := indices[slot]
		if index < 0 || index >= len(searchItemsByGear[slot]) {
			continue
		}
		candidate := searchItemsByGear[slot][index]
		stats := candidate.stats
		totals.atk += stats.atk
		totals.def += stats.def
		totals.hp += stats.hp
		totals.spd += stats.spd
		totals.cr += stats.cr
		totals.cd += stats.cd
		totals.acc += stats.acc
		totals.res += stats.res
		totals.atkPct += stats.atkPct
		totals.defPct += stats.defPct
		totals.hpPct += stats.hpPct
		addSetEffectCount(&counts, candidate.item.Set)
	}
	return calculateTotalStats(totals, base, bonus, counts)
}

func buildItemsListForSearch(searchItemsByGear [][]searchSlotItem, indices [6]int) []model.OptimizeItem {
	itemsList := make([]model.OptimizeItem, 0, len(searchItemsByGear))
	for slot := 0; slot < len(searchItemsByGear); slot++ {
		itemsList = append(itemsList, searchItemsByGear[slot][indices[slot]].item)
	}
	return itemsList
}

func addSetEffectCount(counts *setEffectCounts, setName string) {
	switch setName {
	case "AttackSet":
		counts.attack++
	case "HealthSet":
		counts.health++
	case "DefenseSet":
		counts.defense++
	case "SpeedSet":
		counts.speed++
	case "RevengeSet":
		counts.revenge++
	case "ReversalSet":
		counts.reversal++
	case "CriticalSet":
		counts.critical++
	case "HitSet":
		counts.hit++
	case "ResistSet":
		counts.resist++
	case "DestructionSet":
		counts.destruction++
	case "WarfareSet":
		counts.warfare++
	case "TorrentSet":
		counts.torrent++
	}
}

func calculateTotalStats(totals itemStats, base baseStats, bonus model.BonusStats, counts setEffectCounts) totalsStats {
	bonusBaseAtk := base.atk + base.atk*(bonus.AtkPct/100) + bonus.Atk
	bonusBaseDef := base.def + base.def*(bonus.DefPct/100) + bonus.Def
	bonusBaseHp := base.hp + base.hp*(bonus.HpPct/100) + bonus.Hp

	bonusMaxAtk := 1 + bonus.FinalAtkMultiplier/100
	bonusMaxDef := 1 + bonus.FinalDefMultiplier/100
	bonusMaxHp := 1 + bonus.FinalHpMultiplier/100

	attackSetBonus := 0.0
	if counts.attack >= 4 {
		attackSetBonus = 0.45 * base.atk
	}
	healthSetBonus := float64(counts.health/2) * 0.20 * base.hp
	defenseSetBonus := float64(counts.defense/2) * 0.20 * base.def
	speedSetBonus := 0.0
	if counts.speed >= 4 {
		speedSetBonus = 0.25 * base.spd
	}
	revengeSetBonus := 0.0
	if counts.revenge >= 4 {
		revengeSetBonus = 0.12 * base.spd
	}
	reversalSetBonus := 0.0
	if counts.reversal >= 4 {
		reversalSetBonus = 0.15 * base.spd
	}
	criticalSetBonus := float64(counts.critical/2) * 12
	hitSetBonus := float64(counts.hit/2) * 20
	resistSetBonus := float64(counts.resist/2) * 20
	destructionSetBonus := 0.0
	if counts.destruction >= 4 {
		destructionSetBonus = 60
	}
	warfareSetBonus := 0.0
	if counts.warfare >= 4 {
		warfareSetBonus = 0.20 * base.hp
	}
	torrentSetPenalty := float64(counts.torrent/2) * (-0.10 * base.hp)

	atkFlat := totals.atk + base.atk*(totals.atkPct/100)
	defFlat := totals.def + base.def*(totals.defPct/100)
	hpFlat := totals.hp + base.hp*(totals.hpPct/100)

	atk := (bonusBaseAtk + atkFlat + attackSetBonus) * bonusMaxAtk
	def := (bonusBaseDef + defFlat + defenseSetBonus) * bonusMaxDef
	hp := (bonusBaseHp + hpFlat + healthSetBonus + warfareSetBonus + torrentSetPenalty) * bonusMaxHp
	spd := base.spd + totals.spd + speedSetBonus + revengeSetBonus + reversalSetBonus + bonus.Spd
	cr := math.Min(100, base.cr+totals.cr+criticalSetBonus+bonus.Cr)
	cd := math.Min(350, base.cd+totals.cd+destructionSetBonus+bonus.Cd)
	acc := base.acc + totals.acc + hitSetBonus + bonus.Eff
	res := base.res + totals.res + resistSetBonus + bonus.Res

	return totalsStats{
		atk: atk,
		def: def,
		hp:  hp,
		spd: spd,
		cr:  cr,
		cd:  cd,
		acc: acc,
		res: res,
	}
}

func panelWholeStat(value float64) float64 {
	return math.Floor(value)
}

func panelRoundedStat(value float64) float64 {
	return math.Round(value)
}

func passesFilters(t totalsStats, filters map[string]model.StatRange) bool {
	if len(filters) == 0 {
		return true
	}
	for key, rangeVal := range filters {
		var value float64
		switch key {
		case "atk":
			value = panelWholeStat(t.atk)
		case "def":
			value = panelWholeStat(t.def)
		case "hp":
			value = panelWholeStat(t.hp)
		case "spd":
			value = panelRoundedStat(t.spd)
		case "cr":
			value = panelRoundedStat(t.cr)
		case "cd":
			value = panelRoundedStat(t.cd)
		case "acc":
			value = panelRoundedStat(t.acc)
		case "res":
			value = panelRoundedStat(t.res)
		default:
			continue
		}
		if rangeVal.Min != nil && value < *rangeVal.Min {
			return false
		}
		if rangeVal.Max != nil && value > *rangeVal.Max {
			return false
		}
	}
	return true
}

var ingameSetMap = map[string]string{
	"set_acc":       "HitSet",
	"set_att":       "AttackSet",
	"set_coop":      "UnitySet",
	"set_counter":   "CounterSet",
	"set_cri_dmg":   "DestructionSet",
	"set_cri":       "CriticalSet",
	"set_def":       "DefenseSet",
	"set_immune":    "ImmunitySet",
	"set_max_hp":    "HealthSet",
	"set_penetrate": "PenetrationSet",
	"set_rage":      "RageSet",
	"set_res":       "ResistSet",
	"set_revenge":   "RevengeSet",
	"set_scar":      "InjurySet",
	"set_speed":     "SpeedSet",
	"set_vampire":   "LifestealSet",
	"set_shield":    "ProtectionSet",
	"set_torrent":   "TorrentSet",
	"set_revenant":  "ReversalSet",
	"set_riposte":   "RiposteSet",
	"set_chase":     "PursuitSet",
	"set_opener":    "WarfareSet",
}

func itemPassesMainStatFilter(item model.OptimizeItem, filters map[string]string) bool {
	if len(filters) == 0 {
		return true
	}
	var key string
	switch item.Gear {
	case "Necklace":
		key = "necklace"
	case "Ring":
		key = "ring"
	case "Boots":
		key = "boots"
	default:
		return true
	}
	want, ok := filters[key]
	if !ok || want == "" || want == "All" {
		return true
	}
	return item.Main != nil && item.Main.Type == want
}

func passesMainStatFilter(items []model.OptimizeItem, filters map[string]string) bool {
	if len(filters) == 0 {
		return true
	}
	check := func(gear string, key string) bool {
		want, ok := filters[key]
		if !ok || want == "" || want == "All" {
			return true
		}
		for _, item := range items {
			if item.Gear != gear {
				continue
			}
			if item.Main == nil || item.Main.Type == "" {
				return false
			}
			return item.Main.Type == want
		}
		return true
	}

	if !check("Necklace", "necklace") {
		return false
	}
	if !check("Ring", "ring") {
		return false
	}
	if !check("Boots", "boots") {
		return false
	}
	return true
}

func passesSetFilter(items []model.OptimizeItem, filters model.SetFilters) bool {
	requiredCounts, _, ok := buildSetRequirements(filters)
	if !ok {
		return false
	}
	if len(requiredCounts) == 0 {
		return true
	}
	counts := map[string]int{}
	for _, item := range items {
		if item.Set == "" {
			continue
		}
		counts[item.Set]++
	}

	for setName, requiredPieces := range requiredCounts {
		if counts[setName] < requiredPieces {
			return false
		}
	}

	return true
}

func buildSetRequirements(filters model.SetFilters) (map[string]int, int, bool) {
	required := map[string]int{}
	totalPieces := 0

	for _, group := range [][]string{filters.Set1, filters.Set2, filters.Set3} {
		for _, setName := range group {
			if setName == "" || setName == "All" {
				continue
			}
			pieces := setPieceCount(setName)
			if pieces == 0 {
				return required, totalPieces, false
			}
			totalPieces += pieces
			if totalPieces > len(gearSlots) {
				return required, totalPieces, false
			}
			required[setName] += pieces
		}
	}

	return required, totalPieces, true
}

func setPieceCount(setName string) int {
	if isFourPieceSet(setName) {
		return 4
	}
	if isTwoPieceSet(setName) {
		return 2
	}
	return 0
}

func scoreTotals(t totalsStats, weights map[string]float64) float64 {
	if len(weights) == 0 {
		return 0
	}
	w := func(key string) float64 {
		if val, ok := weights[key]; ok {
			if val <= 0 {
				return 0
			}
			return val / 3
		}
		return 0
	}
	wAtk := w("atk")
	wDef := w("def")
	wHp := w("hp")
	wSpd := w("spd")
	wCr := w("cr")
	wCd := w("cd")
	wAcc := w("acc")
	wRes := w("res")

	return (t.atk/100)*wAtk +
		(t.def/100)*wDef +
		(t.hp/100)*wHp +
		t.spd*2*wSpd +
		t.cr*wCr +
		t.cd*wCd +
		t.acc*wAcc +
		t.res*wRes
}

func getCompletedSets(items []model.OptimizeItem) []string {
	counts := map[string]int{}
	for _, item := range items {
		if item.Set == "" {
			continue
		}
		counts[item.Set]++
	}

	var completed []string
	for setName, count := range counts {
		if isFourPieceSet(setName) && count >= 4 {
			completed = append(completed, setName)
			continue
		}
		if isTwoPieceSet(setName) && count >= 2 {
			stacks := count / 2
			for i := 0; i < stacks; i++ {
				completed = append(completed, setName)
			}
		}
	}
	return completed
}

func isFourPieceSet(setName string) bool {
	return fourPieceSets[setName]
}

func isTwoPieceSet(setName string) bool {
	return twoPieceSets[setName]
}

func joinSets(sets []string) string {
	if len(sets) == 0 {
		return ""
	}
	out := sets[0]
	for i := 1; i < len(sets); i++ {
		out += "/" + sets[i]
	}
	return out
}

func itemKey(item model.OptimizeItem) string {
	if item.ID == nil {
		return fmt.Sprintf("%s-%s", item.Gear, item.Set)
	}
	return fmt.Sprint(item.ID)
}

func buildKey(items []model.OptimizeItem) string {
	key := ""
	for i, item := range items {
		if i > 0 {
			key += "-"
		}
		key += itemKey(item)
	}
	return key
}