MusicServer/cmd/web/search.go

package web

import (
	"log"
	"music-server/internal/backend"
	"net/http"
	"regexp"
	"sort"
	"strings"
	"sync"
	"unicode"
)

var soundtracks_added []string

// Precomputed data for optimization
type SoundtrackData struct {
	Original     string
	Cleaned      string
	Abbreviation string
}

var (
	precomputedSoundtracks []SoundtrackData
	precomputedOnce        sync.Once
	regexCache             = make(map[string]*regexp.Regexp)
	regexCacheMutex        sync.Mutex
)

func FindSoundtrackWebHandler(w http.ResponseWriter, r *http.Request) {
	err := r.ParseForm()
	if err != nil {
		http.Error(w, "Bad Request", http.StatusBadRequest)
	}

	search_term := r.FormValue("search_term")

	search(search_term)

	component := FoundSoundtracks(soundtracks_added)
	err = component.Render(r.Context(), w)
	if err != nil {
		http.Error(w, err.Error(), http.StatusBadRequest)
		log.Fatalf("Error rendering in FindSoundtrackWebHandler: %e", err)
	}
}

func search(searchText string) {
	soundtracks_added = nil

	// Precompute cleaned search term once
	cleanedSearchTerm := clean_term(searchText)

	// Use precomputed data for efficiency
	soundtrackData := getPrecomputedSoundtracks()
	seen := make(map[string]bool) // O(1) duplicate checking

	for _, data := range soundtrackData {
		// Check exact match (case-insensitive contains)
		if is_match_exact(searchText, data.Original) && !seen[data.Original] {
			soundtracks_added = append(soundtracks_added, data.Original)
			seen[data.Original] = true
		}
	}

	for _, data := range soundtrackData {
		// Check contains match with cleaned terms
		if !seen[data.Original] && is_match_contains(cleanedSearchTerm, data.Cleaned) {
			soundtracks_added = append(soundtracks_added, data.Original)
			seen[data.Original] = true
		}
	}

	for _, data := range soundtrackData {
		// Check regex match with cleaned terms
		if !seen[data.Original] && is_match_regex_cached(cleanedSearchTerm, data.Cleaned) {
			soundtracks_added = append(soundtracks_added, data.Original)
			seen[data.Original] = true
		}
	}
}

func is_match_exact(search_term string, soundtrack_name string) bool {
	search_term = strings.ToLower(search_term)
	soundtrack_name = strings.ToLower(soundtrack_name)

	if search_term == "" {
		return true
	} else if strings.Contains(soundtrack_name, search_term) {
		return true
	} else {
		return false
	}
}

func is_match_contains(search_term string, soundtrack_name string) bool {
	if search_term == "" {
		return true
	} else if strings.Contains(soundtrack_name, search_term) {
		return true
	} else {
		return false
	}
}

func is_match_regex(search_term string, soundtrack_name string) bool {
	if search_term == "" {
		return true
	} else if compile_regex(search_term).MatchString(soundtrack_name) {
		return true
	} else {
		return false
	}
}

func compile_regex(search_term string) *regexp.Regexp {
	regText := ".*"
	for _, letter := range search_term {
		regText += string(letter) + ".*"
	}
	r, _ := regexp.Compile(regText)

	return r
}

// is_match_regex_cached uses cached compiled regex patterns for better performance
func is_match_regex_cached(search_term string, soundtrack_name string) bool {
	if search_term == "" {
		return true
	}

	// Check cache first
	regexCacheMutex.Lock()
	re, exists := regexCache[search_term]
	if !exists {
		re = compile_regex(search_term)
		regexCache[search_term] = re
	}
	regexCacheMutex.Unlock()

	return re.MatchString(soundtrack_name)
}

func clean_term(term string) string {
	term = strings.ReplaceAll(term, " ", "")
	term = strings.ReplaceAll(term, "é", "e")
	term = strings.ReplaceAll(term, "+", "plus")
	term = strings.ReplaceAll(term, "&", "and")
	term = strings.ReplaceAll(term, "'n", "and")
	return strings.ToLower(term)
}

// toLower converts a string to lowercase.
func toLower(s string) string {
	return strings.Map(unicode.ToLower, s)
}

// levenshteinWithThreshold calculates Levenshtein distance with early termination and space optimization.
// Uses O(min(n,m)) space instead of O(n*m) and stops early if threshold is exceeded.
func levenshteinWithThreshold(s, t string, threshold int) int {
	if threshold < 0 {
		threshold = 2 // default threshold
	}

	m, n := len(s), len(t)

	// Quick checks for early termination
	if m == 0 {
		return n
	}
	if n == 0 {
		return m
	}
	if abs(m-n) > threshold {
		return threshold + 1 // Can't be within threshold
	}

	// Use the shorter string for the row to minimize space
	if m < n {
		s, t = t, s
		m, n = n, m
	}

	// Space optimization: only store two rows
	prevRow := make([]int, n+1)
	currRow := make([]int, n+1)

	// Initialize first row
	for j := 0; j <= n; j++ {
		prevRow[j] = j
	}

	for i := 1; i <= m; i++ {
		currRow[0] = i
		minInRow := currRow[0]

		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] {
				currRow[j] = prevRow[j-1]
			} else {
				currRow[j] = min3(prevRow[j], currRow[j-1], prevRow[j-1]) + 1
			}
			if currRow[j] < minInRow {
				minInRow = currRow[j]
			}
		}

		// Early termination: if minimum in current row exceeds threshold
		if minInRow > threshold {
			return threshold + 1
		}

		// Swap rows for next iteration
		prevRow, currRow = currRow, prevRow
	}

	return prevRow[n]
}

// Helper functions for optimized Levenshtein
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min3(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
		return c
	}
	if b < c {
		return b
	}
	return c
}

// precomputeSoundtrackData initializes cleaned terms and abbreviations for all soundtracks
func precomputeSoundtrackData() {
	precomputedOnce.Do(func() {
		soundtracks := backend.GetAllSoundtracks()
		precomputedSoundtracks = make([]SoundtrackData, len(soundtracks))

		for i, soundtrack := range soundtracks {
			cleaned := clean_term(soundtrack)
			precomputedSoundtracks[i] = SoundtrackData{
				Original:     soundtrack,
				Cleaned:      cleaned,
				Abbreviation: extractAbbreviation(soundtrack),
			}
		}
	})
}

// getPrecomputedSoundtracks ensures precomputed data is available and returns it
func getPrecomputedSoundtracks() []SoundtrackData {
	precomputeSoundtrackData()
	return precomputedSoundtracks
}

// levenshtein maintains backward compatibility by calling the optimized version
func levenshtein(s, t string) int {
	return levenshteinWithThreshold(s, t, -1) // -1 uses default threshold
}

// extractAbbreviation extracts the first letters of each word in a string.
func extractAbbreviation(s string) string {
	words := strings.Fields(s)
	abbr := ""
	for _, word := range words {
		if len(word) > 0 {
			abbr += string(word[0])
		}
	}
	return toLower(abbr)
}

// fuzzyFindSubstring checks if the query fuzzy-matches any substring of the item.
func fuzzyFindSubstring(query, item string, threshold int) (bool, int) {
	query = toLower(query)
	item = toLower(item)
	queryLen := len(query)
	itemLen := len(item)
	if queryLen > itemLen {
		return false, 0
	}

	// Check for exact substring match first (weight: 100)
	if strings.Contains(item, query) {
		return true, 100
	}

	// Check for fuzzy substring match using optimized Levenshtein
	for i := 0; i <= itemLen-queryLen; i++ {
		substring := item[i : i+queryLen]
		distance := levenshteinWithThreshold(query, substring, threshold)
		if distance <= threshold {
			// Weight: higher for matches at the start of the string
			weight := 50 - i // Higher weight for earlier matches
			return true, weight
		}
	}
	return false, 0
}

// fuzzyFind checks if the query matches the item (substring or abbreviation).
func fuzzyFind(query string, item string, threshold int) (bool, int) {
	query = toLower(query)
	item = toLower(item)

	// Check for substring fuzzy match
	if matched, weight := fuzzyFindSubstring(query, item, threshold); matched {
		return true, weight
	}

	// Check for abbreviation match using optimized Levenshtein
	abbr := extractAbbreviation(item)
	distance := levenshteinWithThreshold(query, abbr, threshold)
	if distance <= threshold {
		// Weight: higher for exact abbreviation matches
		weight := 100 - distance*10 // Higher weight for exact matches
		return true, weight
	}

	return false, 0
}

// getAdaptiveThreshold returns a threshold based on query length
func getAdaptiveThreshold(query string) int {
	threshold := 2 // Base threshold for minor typos
	queryLen := len(query)
	if queryLen > 6 {
		// For longer queries, allow more tolerance
		threshold = queryLen / 3
		if threshold < 2 {
			threshold = 2
		} else if threshold > 4 {
			threshold = 4 // Cap at 4 for very long queries
		}
	}
	return threshold
}

// fuzzySearch performs fuzzy search on soundtracks using the cleaned terms for consistency
func fuzzySearch(searchText string) []string {
	query := clean_term(searchText)
	threshold := getAdaptiveThreshold(query)

	// Use precomputed data for efficiency
	soundtrackData := getPrecomputedSoundtracks()

	type match struct {
		item   string
		weight int
	}
	var matches []match
	seen := make(map[string]bool) // O(1) duplicate checking

	for _, data := range soundtrackData {
		if matched, weight := fuzzyFind(query, data.Cleaned, threshold); matched {
			if !seen[data.Original] {
				matches = append(matches, match{data.Original, weight})
				seen[data.Original] = true
			}
		}
	}

	// Sort matches by weight (descending)
	sort.Slice(matches, func(i, j int) bool {
		return matches[i].weight > matches[j].weight
	})

	// Extract just the soundtrack names in order
	result := make([]string, len(matches))
	for i, m := range matches {
		result[i] = m.item
	}

	return result
}

// FindSoundtrackFuzzyWebHandler handles fuzzy search requests
func FindSoundtrackFuzzyWebHandler(w http.ResponseWriter, r *http.Request) {
	err := r.ParseForm()
	if err != nil {
		http.Error(w, "Bad Request", http.StatusBadRequest)
		return
	}

	search_term := r.FormValue("search_term")

	results := fuzzySearch(search_term)

	component := FoundSoundtracks(results)
	err = component.Render(r.Context(), w)
	if err != nil {
		http.Error(w, err.Error(), http.StatusBadRequest)
		log.Fatalf("Error rendering in FindSoundtrackFuzzyWebHandler: %e", err)
	}
}