FuzzySearch.FuzzyMatch

Parameters

Returns

bool Returns true if a match was found.

Description

Performs a fuzzy search for a pattern on a string.

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEditor;
using UnityEditor.Search;
using UnityEngine;

static class Example_FuzzySearch_FuzzyMatch
{
    [MenuItem("Examples/FuzzySearch/FuzzyMatch")]
    public static void Run()
    {
        const string pattern = "exfsfm";
        const string toBeSearched = nameof(Example_FuzzySearch_FuzzyMatch);

        long score = 0;
        if (FuzzySearch.FuzzyMatch(pattern, toBeSearched, ref score))
            Debug.Assert(score == 309);

        // This allocated list can be reused for multiple calls to FuzzyMatch
        var matches = new List<int>();
        if (FuzzySearch.FuzzyMatch(pattern, toBeSearched, ref score, matches))
        {
            var formattedMatch = RichTextFormatter.FormatSuggestionTitle(toBeSearched, matches);
            Debug.Log($"Found fuzzy pattern <i>{pattern}</i> in {formattedMatch} with indices " +
                $"{string.Join(",", matches.Select(m => m.ToString()))} and got a score of <b>{score}</b>");
        }
    }

    static class RichTextFormatter
    {
        static readonly char[] cache_result = new char[1024];
        public static string HighlightColorTag = EditorGUIUtility.isProSkin ? "<color=#FF6100>" : "<color=#EE4400>";
        public static string HighlightColorTagSpecial = EditorGUIUtility.isProSkin ? "<color=#FF6100>" : "<color=#BB1100>";

        public static string FormatSuggestionTitle(string title, List<int> matches)
        {
            return FormatSuggestionTitle(title, matches, HighlightColorTag, HighlightColorTagSpecial);
        }

        public static string FormatSuggestionTitle(string title, List<int> matches, string selectedTextColorTag, string specialTextColorTag)
        {
            const string closingTag = "</color>";
            int openCharCount = specialTextColorTag.Length;
            int closingCharCount = closingTag.Length;

            var N = title.Length + matches.Count * (closingCharCount + openCharCount);
            var MN = matches.Count;

            var result = cache_result;
            if (N > cache_result.Length)
                result = new char[N];

            int t_i = 0;
            int t_j = 0;
            int t_k = 0;
            string tag = null;
            var needToClose = false;

            for (int guard = 0; guard < N; ++guard)
            {
                if (tag == null && needToClose == false && t_k < MN)
                {
                    var indx = matches[t_k];
                    if (indx == t_i || indx == -t_i)
                    {
                        tag = (indx < 0) ? specialTextColorTag : selectedTextColorTag;
                        ++t_k;
                    }
                }

                if (tag != null)
                {
                    result[guard] = tag[t_j++];

                    if (t_j >= tag.Length)
                    {
                        if (tag != closingTag)
                            needToClose = true;

                        tag = null;
                        t_j = 0;
                    }
                }
                else
                {
                    result[guard] = title[Math.Min(t_i++, title.Length - 1)];

                    if (needToClose)
                    {
                        tag = closingTag;
                        needToClose = false;
                    }
                }
            }

            return new string(result, 0, N);
        }
    }
}