using System;

namespace Crux.Editor.Common
{
	// https://gist.github.com/CDillinger/2aa02128f840bdca90340ce08ee71bc2
	public static class FuzzyMatcher
	{
		// Score constants — tune these for your use case
		const int SequentialBonus = 15; // bonus for adjacent matches
		const int SeparatorBonus = 30; // bonus if match occurs after a separator
		const int CamelBonus = 30; // bonus if match is uppercase and prev is lower
		const int FirstLetterBonus = 15; // bonus if the first letter is matched

		const int LeadingLetterPenalty = -5; // penalty applied for every letter in str before the first match
		const int MaxLeadingLetterPenalty = -15; // maximum penalty for leading letters
		const int UnmatchedLetterPenalty = -1; // penalty for every letter that doesn't matter

		const int MaxRecursion = 10;
		const int MaxMatches = 256;

		/// <summary>
		/// Simple fuzzy match — no scoring. Returns true if each character in pattern
		/// is found sequentially within str.
		/// </summary>
		public static bool FuzzyMatchSimple( string pattern, string str )
		{
			int patternIdx = 0;
			int strIdx = 0;

			while ( patternIdx < pattern.Length && strIdx < str.Length )
			{
				if ( char.ToLower( pattern[patternIdx] ) == char.ToLower( str[strIdx] ) )
					patternIdx++;
				strIdx++;
			}

			return patternIdx == pattern.Length;
		}

		/// <summary>
		/// Scored fuzzy match. Performs exhaustive search via recursion to find
		/// the match with the highest score. Returns true if pattern was matched.
		/// </summary>
		public static bool FuzzyMatch( string pattern, string str, out int outScore )
		{
			int recursionCount = 0;
			int[] matches = new int[MaxMatches];
			return FuzzyMatchRecursive( pattern, str, 0, 0, null, matches, MaxMatches, 0, ref recursionCount,
				out outScore );
		}

		/// <summary>
		/// Scored fuzzy match with match index output. The matches array will contain
		/// the indices of matched characters in str.
		/// </summary>
		public static bool FuzzyMatch( string pattern, string str, out int outScore, out int[] matchIndices )
		{
			int recursionCount = 0;
			int[] matches = new int[MaxMatches];
			bool result = FuzzyMatchRecursive( pattern, str, 0, 0, null, matches, MaxMatches, 0, ref recursionCount,
				out outScore );

			if ( result )
			{
				int count = pattern.Length;
				matchIndices = new int[count];
				Array.Copy( matches, matchIndices, count );
			}
			else
			{
				matchIndices = Array.Empty<int>();
			}

			return result;
		}

		static bool FuzzyMatchRecursive(
			string pattern,
			string str,
			int patternIndex,
			int strIndex,
			int[] srcMatches,
			int[] matches,
			int maxMatches,
			int nextMatch,
			ref int recursionCount,
			out int outScore )
		{
			outScore = 0;

			// Count recursions
			recursionCount++;
			if ( recursionCount >= MaxRecursion )
				return false;

			// Detect end of strings
			if ( patternIndex == pattern.Length || strIndex == str.Length )
				return false;

			// Recursion params
			bool recursiveMatch = false;
			int[] bestRecursiveMatches = new int[MaxMatches];
			int bestRecursiveScore = 0;

			// Loop through pattern and str looking for a match
			bool firstMatch = true;

			while ( patternIndex < pattern.Length && strIndex < str.Length )
			{
				// Found match
				if ( char.ToLower( pattern[patternIndex] ) == char.ToLower( str[strIndex] ) )
				{
					// Supplied matches buffer was too short
					if ( nextMatch >= maxMatches )
						return false;

					// "Copy-on-Write" srcMatches into matches
					if ( firstMatch && srcMatches != null )
					{
						Array.Copy( srcMatches, matches, nextMatch );
						firstMatch = false;
					}

					// Recursive call that "skips" this match
					int[] recursiveMatches = new int[MaxMatches];
					if ( FuzzyMatchRecursive( pattern, str, patternIndex, strIndex + 1, matches, recursiveMatches,
						    MaxMatches, nextMatch, ref recursionCount, out int recursiveScore ) )
					{
						// Pick best recursive score
						if ( !recursiveMatch || recursiveScore > bestRecursiveScore )
						{
							Array.Copy( recursiveMatches, bestRecursiveMatches, MaxMatches );
							bestRecursiveScore = recursiveScore;
						}

						recursiveMatch = true;
					}

					// Advance
					matches[nextMatch++] = strIndex;
					patternIndex++;
				}

				strIndex++;
			}

			// Determine if full pattern was matched
			bool matched = patternIndex == pattern.Length;

			// Calculate score
			if ( matched )
			{
				// Initialize score
				outScore = 100;

				// Apply leading letter penalty
				int penalty = LeadingLetterPenalty * matches[0];
				if ( penalty < MaxLeadingLetterPenalty )
					penalty = MaxLeadingLetterPenalty;
				outScore += penalty;

				// Apply unmatched penalty
				int unmatched = str.Length - nextMatch;
				outScore += UnmatchedLetterPenalty * unmatched;

				// Apply ordering bonuses
				for ( int i = 0; i < nextMatch; i++ )
				{
					int currIdx = matches[i];

					if ( i > 0 )
					{
						int prevIdx = matches[i - 1];

						// Sequential
						if ( currIdx == prevIdx + 1 )
							outScore += SequentialBonus;
					}

					// Check for bonuses based on neighbor character value
					if ( currIdx > 0 )
					{
						// Camel case
						char neighbor = str[currIdx - 1];
						char curr = str[currIdx];
						if ( char.IsLower( neighbor ) && char.IsUpper( curr ) )
							outScore += CamelBonus;

						// Separator
						if ( neighbor == '_' || neighbor == ' ' || neighbor == '/' || neighbor == '\\' ||
						     neighbor == '.' )
							outScore += SeparatorBonus;
					}
					else
					{
						// First letter
						outScore += FirstLetterBonus;
					}
				}
			}

			// Return best result
			if ( recursiveMatch && (!matched || bestRecursiveScore > outScore) )
			{
				// Recursive score is better than "this"
				Array.Copy( bestRecursiveMatches, matches, maxMatches );
				outScore = bestRecursiveScore;
				return true;
			}
			else if ( matched )
			{
				// "this" score is better than recursive
				return true;
			}

			return false;
		}
	}
}