class_name SoundtrackSearch
extends RefCounted
## Finds soundtrack names matching a search text. Matches ignore case, spaces and
## special characters. Searches of at least [code]Settings.LETTERS_FOR_LOOSE_SEARCH[/code]
## letters also find the letters in order with others in between.
##
## Used by the Search popup and the statistics view, so both find the same soundtracks.
##
## A soundtrack is also found by its alternative names, e.g. "FF7" for "Final Fantasy
## VII". The results are always the real names; [method matched_alternative] tells which
## alternative name matched.

## Each searchable name as a Dictionary: the soundtrack's real name ("original"), the name
## searched in ("text"), and its lowercase and cleaned forms.
var _names: Array[Dictionary] = []
# The alternative name that matched in the last search, by real name
var _matched_alternatives: Dictionary = {}

## Compiled patterns for the letters-in-order search, by cleaned search term.
var _regex_cache: Dictionary = {}


## Replaces the names to search in. [param alternatives] has the other names of a
## soundtrack, by its real name.
func set_names(names: Array, alternatives: Dictionary = {}) -> void:
	_names.clear()
	_matched_alternatives.clear()
	for soundtrack: String in names:
		_add_name(soundtrack, soundtrack)
		for alternative: String in alternatives.get(soundtrack, []):
			_add_name(soundtrack, alternative)


## The alternative name of [param soundtrack_name] that matched in the last
## [method find_matches], or an empty String when its real name matched.
func matched_alternative(soundtrack_name: String) -> String:
	return _matched_alternatives.get(soundtrack_name, "")


## Returns the names matching [param search_text], best matches first: plain
## case-insensitive matches, then matches ignoring spaces and special characters,
## then matches with the letters in order but not next to each other.
func find_matches(search_text: String) -> Array[String]:
	var seen: Dictionary = {}
	var search_text_lower: String = search_text.to_lower()
	var clean_search_text: String = clean_term(search_text)
	var passes: Array[Callable] = [
		func(entry: Dictionary) -> bool: return entry.lowercase.contains(search_text_lower),
		func(entry: Dictionary) -> bool: return entry.cleaned.contains(clean_search_text),
	]
	if clean_search_text.length() >= Settings.LETTERS_FOR_LOOSE_SEARCH:
		var regex: RegEx = _compile_regex_cached(clean_search_text)
		passes.append(
				func(entry: Dictionary) -> bool: return regex.search(entry.cleaned) != null)

	var matches: Array[String] = []
	_matched_alternatives.clear()
	for matches_pass: Callable in passes:
		for entry: Dictionary in _names:
			if !seen.has(entry.original) && matches_pass.call(entry):
				seen[entry.original] = true
				matches.append(entry.original)
				if entry.text != entry.original:
					_matched_alternatives[entry.original] = entry.text
	return matches


## The positions of the letters in [param soundtrack_name] that [param search_text]
## matched, for highlighting them: the text itself if the name contains it, otherwise the
## letters found in order the way [method find_matches] finds them. Empty if it does not
## match.
static func matched_letters(soundtrack_name: String, search_text: String) -> Array[int]:
	var positions: Array[int] = []
	if search_text.is_empty():
		return positions
	var start: int = soundtrack_name.to_lower().find(search_text.to_lower())
	if start >= 0:
		for i: int in search_text.length():
			positions.append(start + i)
		return positions

	# Clean the name piece by piece, remembering which letter each cleaned letter came from
	var cleaned: String = ""
	var source: Array[int] = []
	var i: int = 0
	while i < soundtrack_name.length():
		var piece: String
		var length: int = 1
		if soundtrack_name.substr(i, 2).to_lower() == "'n":
			piece = "and"
			length = 2
		else:
			piece = clean_term(soundtrack_name[i])
		for letter: String in piece:
			cleaned += letter
			source.append(i)
		i += length

	var clean_search_text: String = clean_term(search_text)
	var found: int = cleaned.find(clean_search_text)
	var cleaned_positions: Array[int] = []
	if found >= 0:
		for j: int in clean_search_text.length():
			cleaned_positions.append(found + j)
	elif clean_search_text.length() >= Settings.LETTERS_FOR_LOOSE_SEARCH:
		var at: int = 0
		for letter: String in clean_search_text:
			at = cleaned.find(letter, at)
			if at < 0:
				return positions
			cleaned_positions.append(at)
			at += 1
	for cleaned_position: int in cleaned_positions:
		if !positions.has(source[cleaned_position]):
			positions.append(source[cleaned_position])
	return positions


## Cleans a term by removing spaces and replacing special characters.
## Matches MusicServer's clean_term() function.
static func clean_term(term: String) -> String:
	return term.replace(" ", "").replace("é", "e").replace("+", "plus").replace("&", "and") \
			.replace("'n", "and").to_lower()


func _add_name(soundtrack: String, text: String) -> void:
	_names.append({
		"original": soundtrack,
		"text": text,
		"lowercase": text.to_lower(),
		"cleaned": clean_term(text),
	})


# Compiles the letters-in-order pattern for [param search_term], once per term
func _compile_regex_cached(search_term: String) -> RegEx:
	if not search_term in _regex_cache:
		var regex: RegEx = RegEx.new()
		var regex_text: String = ".*"
		for letter: String in search_term:
			# Escape regex metacharacters so searches like "Q*bert" or "(Remix)" work
			if "\\^$.|?*+()[]{}".contains(letter):
				regex_text += "\\"
			regex_text += letter + ".*"
		regex.compile(regex_text)
		_regex_cache[search_term] = regex
	return _regex_cache[search_term]