Fuzzy matching:

1) Handle localized and English searches as equivalent.
2) Search the whole section : group : label string, still give
   precedence to just the label.

4 files changed, 124 insertions, 115 deletions

diff --git a/src/slic3r/GUI/Preset.hpp b/src/slic3r/GUI/Preset.hpp
index 9c2cebd50..dc0078091 100644
--- a/src/slic3r/GUI/Preset.hpp
+++ b/src/slic3r/GUI/Preset.hpp
@@ -125,6 +125,7 @@ public:
         TYPE_FILAMENT,
         TYPE_SLA_MATERIAL,
         TYPE_PRINTER,
+        TYPE_COUNT,
     };
 
     Preset(Type type, const std::string &name, bool is_default = false) : type(type), is_default(is_default), name(name) {}
diff --git a/src/slic3r/GUI/Search.cpp b/src/slic3r/GUI/Search.cpp
index c6894bc5b..844d2244c 100644
--- a/src/slic3r/GUI/Search.cpp
+++ b/src/slic3r/GUI/Search.cpp
@@ -25,41 +25,18 @@ using GUI::into_u8;
 
 namespace Search {
 
-static std::map<Preset::Type, std::string> NameByType = {
-    { Preset::TYPE_PRINT,           L("Print")     },
-    { Preset::TYPE_FILAMENT,        L("Filament")  },
-    { Preset::TYPE_SLA_MATERIAL,    L("Material")  },
-    { Preset::TYPE_SLA_PRINT,       L("Print")     },
-    { Preset::TYPE_PRINTER,         L("Printer")   }
-};
-
-FMFlag Option::fuzzy_match(wchar_t const* search_pattern, int& outScore, std::vector<uint16_t> &out_matches) const
+static const std::vector<std::wstring>& NameByType()
 {
-    FMFlag flag = fmUndef;
-    int score;
-
-    uint16_t matches[fts::max_matches + 1]; // +1 for the stopper
-    auto save_matches = [&matches, &out_matches]() {
-        size_t cnt = 0;
-        for (; matches[cnt] != fts::stopper; ++cnt);
-        out_matches.assign(matches, matches + cnt);
-    };
-    if (fts::fuzzy_match(search_pattern, label_local.c_str(),    score, matches) && outScore < score) {
-        outScore = score; flag = fmLabelLocal   ; save_matches(); }
-    if (fts::fuzzy_match(search_pattern, group_local.c_str(),    score, matches) && outScore < score) {
-        outScore = score; flag = fmGroupLocal   ; save_matches(); }
-    if (fts::fuzzy_match(search_pattern, category_local.c_str(), score, matches) && outScore < score) {
-        outScore = score; flag = fmCategoryLocal; save_matches(); }
-    if (fts::fuzzy_match(search_pattern, opt_key.c_str(),        score, matches) && outScore < score) {
-        outScore = score; flag = fmOptKey       ; save_matches(); }
-    if (fts::fuzzy_match(search_pattern, label.c_str(),          score, matches) && outScore < score) {
-        outScore = score; flag = fmLabel        ; save_matches(); }
-    if (fts::fuzzy_match(search_pattern, group.c_str(),          score, matches) && outScore < score) {
-        outScore = score; flag = fmGroup        ; save_matches(); }
-    if (fts::fuzzy_match(search_pattern, category.c_str(),       score, matches) && outScore < score) {
-        outScore = score; flag = fmCategory     ; save_matches(); }
-
-    return flag;
+    static std::vector<std::wstring> data;
+    if (data.empty()) {
+        data.assign(Preset::TYPE_COUNT, std::wstring());
+        data[Preset::TYPE_PRINT         ] = _L("Print"      ).ToStdWstring();
+        data[Preset::TYPE_FILAMENT      ] = _L("Filament"   ).ToStdWstring();
+        data[Preset::TYPE_SLA_MATERIAL  ] = _L("Material"   ).ToStdWstring();
+        data[Preset::TYPE_SLA_PRINT     ] = _L("Print"      ).ToStdWstring();
+        data[Preset::TYPE_PRINTER       ] = _L("Printer"    ).ToStdWstring();
+	};
+	return data;
 }
 
 void FoundOption::get_marked_label_and_tooltip(const char** label_, const char** tooltip_) const
@@ -89,12 +66,16 @@ void OptionsSearcher::append_options(DynamicPrintConfig* config, Preset::Type ty
             return;
 
         wxString suffix;
-        if (gc.category == "Machine limits")
+        wxString suffix_local;
+        if (gc.category == "Machine limits") {
             suffix = opt_key.back()=='1' ? L("Stealth") : L("Normal");
+            suffix_local = " " + _(suffix);
+            suffix = " " + suffix;
+        }
 
         if (!label.IsEmpty())
             options.emplace_back(Option{ boost::nowide::widen(opt_key), type,
-                                        (label+ " " + suffix).ToStdWstring(), (_(label)+ " " + _(suffix)).ToStdWstring(),
+                                        (label + suffix).ToStdWstring(), (_(label) + suffix_local).ToStdWstring(),
                                         gc.group.ToStdWstring(), _(gc.group).ToStdWstring(),
                                         gc.category.ToStdWstring(), _(gc.category).ToStdWstring() });
     };
@@ -125,7 +106,7 @@ void OptionsSearcher::append_options(DynamicPrintConfig* config, Preset::Type ty
             emplace(opt_key, label);
         else
             for (int i = 0; i < cnt; ++i)
-                emplace(opt_key + "#" + std::to_string(i), label);
+                emplace(opt_key + "[" + std::to_string(i) + "]", label);
 
         /*const GroupAndCategory& gc = groups_and_categories[opt_key];
         if (gc.group.IsEmpty() || gc.category.IsEmpty())
@@ -179,6 +160,20 @@ bool OptionsSearcher::search()
     return search(search_line, true);
 }
 
+static bool fuzzy_match(const std::wstring &search_pattern, const std::wstring &label, int& out_score, std::vector<uint16_t> &out_matches)
+{
+    uint16_t matches[fts::max_matches + 1]; // +1 for the stopper
+    int score;
+    if (fts::fuzzy_match(search_pattern.c_str(), label.c_str(), score, matches)) {
+	    size_t cnt = 0;
+	    for (; matches[cnt] != fts::stopper; ++cnt);
+	    out_matches.assign(matches, matches + cnt);
+		out_score = score;
+		return true;
+	} else
+		return false;
+}
+
 bool OptionsSearcher::search(const std::string& search, bool force/* = false*/)
 {
     if (search_line == search && !force)
@@ -187,78 +182,95 @@ bool OptionsSearcher::search(const std::string& search, bool force/* = false*/)
     found.clear();
 
     bool full_list = search.empty();
-    wxString sep = " : ";
+    std::wstring sep = L" : ";
+    const std::vector<std::wstring>& name_by_type = NameByType();
 
-    auto get_label = [this, sep](const Option& opt)
+    auto get_label = [this, &name_by_type, &sep](const Option& opt)
     {
-        wxString label;
-        if (view_params.type)
-            label += _(NameByType[opt.type]) + sep;
-        if (view_params.category)
-            label += opt.category_local + sep;
-        if (view_params.group)
-            label += opt.group_local + sep;
-        label += opt.label_local;
-        return label;
+        std::wstring out;
+    	const std::wstring *prev = nullptr;
+    	for (const std::wstring * const s : {
+	        view_params.type 		? &(name_by_type[opt.type]) : nullptr,
+	        view_params.category 	? &opt.category_local 		: nullptr,
+	        view_params.group 		? &opt.group_local			: nullptr,
+	        &opt.label_local })
+    		if (s != nullptr && (prev == nullptr || *prev != *s)) {
+    			if (! out.empty())
+    				out += sep;
+    			out += *s;
+    			prev = s;
+    		}
+        return out;
     };
 
-    auto get_tooltip = [this, sep](const Option& opt)
+    auto get_label_english = [this, &name_by_type, &sep](const Option& opt)
     {
-        return  _(NameByType[opt.type]) + sep +
+        std::wstring out;
+    	const std::wstring*prev = nullptr;
+    	for (const std::wstring * const s : {
+	        view_params.type 		? &name_by_type[opt.type] 	: nullptr,
+	        view_params.category 	? &opt.category 			: nullptr,
+	        view_params.group 		? &opt.group				: nullptr,
+	        &opt.label })
+    		if (s != nullptr && (prev == nullptr || *prev != *s)) {
+    			if (! out.empty())
+    				out += sep;
+    			out += *s;
+    			prev = s;
+    		}
+        return out;
+    };
+
+    auto get_tooltip = [this, &name_by_type, &sep](const Option& opt)
+    {
+        return  name_by_type[opt.type] + sep +
                 opt.category_local + sep +
                 opt.group_local + sep + opt.label_local;
     };
 
-    std::vector<uint16_t> matches;
+    std::vector<uint16_t> matches, matches2;
     for (size_t i=0; i < options.size(); i++)
     {
         const Option &opt = options[i];
         if (full_list) {
             std::string label = into_u8(get_label(opt));
-            found.emplace_back(FoundOption{ label, label, into_u8(get_tooltip(opt)), i, fmUndef, 0 });
+            found.emplace_back(FoundOption{ label, label, boost::nowide::narrow(get_tooltip(opt)), i, 0 });
             continue;
         }
 
-        int score = 0;
-        FMFlag fuzzy_match_flag = opt.fuzzy_match(boost::nowide::widen(search).c_str(), score, matches);
-        if (fuzzy_match_flag != fmUndef)
-        {
-            wxString label;
-
-	        if (view_params.type)
-	            label += _(NameByType[opt.type]) + sep;
-	        if (fuzzy_match_flag == fmCategoryLocal)
-	            label += mark_string(opt.category_local, matches) + sep;
-	        else if (view_params.category)
-			    label += opt.category_local + sep;
-			if (fuzzy_match_flag == fmGroupLocal)
-	            label += mark_string(opt.group_local, matches) + sep;
-	        else if (view_params.group)
-	            label += opt.group_local + sep;
-            label += ((fuzzy_match_flag == fmLabelLocal) ? mark_string(opt.label_local, matches) : opt.label_local) + sep;
-
-            switch (fuzzy_match_flag) {
-            	case fmLabelLocal:
-			    case fmGroupLocal:
-			    case fmCategoryLocal:
-			        break;
-            	case fmLabel: 		label = get_label(opt) + "(" + mark_string(opt.label,    matches) + ")"; break;
-            	case fmGroup:		label = get_label(opt) + "(" + mark_string(opt.group,    matches) + ")"; break;
-            	case fmCategory:	label = get_label(opt) + "(" + mark_string(opt.category, matches) + ")"; break;
-            	case fmOptKey:		label = get_label(opt) + "(" + mark_string(opt.opt_key,  matches) + ")"; break;
-            	case fmUndef: 		assert(false); break;
-            }
-
-		    std::string label_plain = into_u8(label);
-		    boost::erase_all(label_plain, std::wstring(1, wchar_t(ImGui::ColorMarkerStart)));
-		    boost::erase_all(label_plain, std::wstring(1, wchar_t(ImGui::ColorMarkerEnd)));
-            found.emplace_back(FoundOption{ label_plain, into_u8(label), into_u8(get_tooltip(opt)), i, fuzzy_match_flag, score });
+        std::wstring wsearch       = boost::nowide::widen(search);
+        boost::trim_left(wsearch);
+        std::wstring label         = get_label(opt);
+        std::wstring label_english = get_label_english(opt);
+        int score = std::numeric_limits<int>::min();
+        int score2;
+        matches.clear();
+        fuzzy_match(wsearch, label, score, matches);
+        if (fuzzy_match(wsearch, opt.opt_key, score2, matches2) && score2 > score) {
+        	for (fts::pos_type &pos : matches2)
+        		pos += label.size() + 1;
+        	label += L"(" + opt.opt_key + L")";
+        	append(matches, matches2);
+        	score = score2;
+        }
+        if (fuzzy_match(wsearch, label_english, score2, matches2) && score2 > score) {
+        	label   = std::move(label_english);
+        	matches = std::move(matches2);
+        	score   = score2;
+        }
+        if (score > std::numeric_limits<int>::min()) {
+		    label = mark_string(label, matches);
+	        std::string label_u8 = into_u8(label);
+	        std::string label_plain = label_u8;
+	        boost::erase_all(label_plain, std::string(1, char(ImGui::ColorMarkerStart)));
+	        boost::erase_all(label_plain, std::string(1, char(ImGui::ColorMarkerEnd)));
+            found.emplace_back(FoundOption{ label_plain, label_u8, boost::nowide::narrow(get_tooltip(opt)), i, score });
         }
     }
 
     if (!full_list)
         sort_found();
-
+ 
     if (search_line != search)
         search_line = search;
 
diff --git a/src/slic3r/GUI/Search.hpp b/src/slic3r/GUI/Search.hpp
index 1c24248ac..5fcb58f1e 100644
--- a/src/slic3r/GUI/Search.hpp
+++ b/src/slic3r/GUI/Search.hpp
@@ -36,20 +36,6 @@ struct GroupAndCategory {
     wxString        category;
 };
 
-// fuzzy_match flag
-// Sorted by the order of importance. The outputs will be sorted by the importance if the match value given by fuzzy_match is equal.
-enum FMFlag
-{
-    fmUndef = 0, // didn't find 
-    fmOptKey,
-    fmLabel,
-    fmLabelLocal,
-    fmGroup,
-    fmGroupLocal,
-    fmCategory,
-    fmCategoryLocal
-};
-
 struct Option {
     bool operator<(const Option& other) const { return other.label > this->label; }
     bool operator>(const Option& other) const { return other.label < this->label; }
@@ -64,8 +50,6 @@ struct Option {
     std::wstring    group_local;
     std::wstring    category;
     std::wstring    category_local;
-
-    FMFlag fuzzy_match(wchar_t const *search_pattern, int &outScore, std::vector<uint16_t> &out_matches) const;
 };
 
 struct FoundOption {
@@ -74,7 +58,6 @@ struct FoundOption {
     std::string     marked_label;
     std::string     tooltip;
     size_t          option_idx {0};
-    FMFlag 			category {fmUndef};
     int             outScore {0};
 
     // Returning pointers to contents of std::string members, to be used by ImGUI for rendering.
@@ -106,7 +89,7 @@ class OptionsSearcher
     }
     void sort_found() {
         std::sort(found.begin(), found.end(), [](const FoundOption& f1, const FoundOption& f2) {
-            return f1.outScore > f2.outScore || (f1.outScore == f2.outScore && int(f1.category) < int(f2.category)); });
+            return f1.outScore > f2.outScore || (f1.outScore == f2.outScore && f1.label < f2.label); });
     };
 
     size_t options_size() const { return options.size(); }
diff --git a/src/slic3r/GUI/fts_fuzzy_match.h b/src/slic3r/GUI/fts_fuzzy_match.h
index 6d26965a1..e692232cc 100644
--- a/src/slic3r/GUI/fts_fuzzy_match.h
+++ b/src/slic3r/GUI/fts_fuzzy_match.h
@@ -57,7 +57,7 @@ namespace fts {
     namespace fuzzy_internal {
         static bool fuzzy_match_recursive(const char_type * pattern, const char_type * str, int & outScore, const char_type * const strBegin,          
             pos_type const * srcMatches,  pos_type * newMatches, int nextMatch, 
-            int & recursionCount, int recursionLimit);
+            int recursionCount, const int recursionLimit);
         static void copy_matches(pos_type * dst, pos_type const* src);
     }
 
@@ -93,8 +93,8 @@ namespace fts {
         // Recursion count is input / output to track the maximum depth reached.
         // Was given by reference &recursionCount, see discussion in https://github.com/forrestthewoods/lib_fts/issues/21
 //        int & 					recursionCount, 
-        int 					recursionCount, 
-        int 					recursionLimit)
+        int				        recursionCount, 
+        const int				recursionLimit)
     {
         // Count recursions
         if (++ recursionCount >= recursionLimit)
@@ -183,28 +183,41 @@ namespace fts {
             // Initialize score
             outScore = 100;
 
+            // Start of the first group that contains matches[0].
+            const char_type *group_start = strBegin + matches[0];
+            for (const char_type *c = group_start; c >= strBegin && *c != ':'; -- c)
+            	if (*c != ' ' && *c != '\t')
+            		group_start = c;
+
             // Apply leading letter penalty or bonus.
-            outScore += matches[0] == 0 ?
+            outScore += matches[0] == int(group_start - strBegin) ?
             	first_letter_bonus :
-            	std::max(matches[0] * leading_letter_penalty, max_leading_letter_penalty);
+            	std::max((matches[0] - int(group_start - strBegin)) * leading_letter_penalty, max_leading_letter_penalty);
 
             // Apply unmatched letters after the end penalty
-//            outScore += (int(str - strBegin) - matches[nextMatch-1] + 1) * unmatched_letter_penalty;
+//            outScore += (int(str - group_start) - matches[nextMatch-1] + 1) * unmatched_letter_penalty;
             // Apply unmatched penalty
-            outScore += (int(str - strBegin) - nextMatch) * unmatched_letter_penalty;
+            outScore += (int(str - group_start) - nextMatch) * unmatched_letter_penalty;
 
             // Apply ordering bonuses
+            int sequential_state = sequential_bonus;
             for (int i = 0; i < nextMatch; ++i) {
                 pos_type currIdx = matches[i];
 
                 // Check for bonuses based on neighbor character value
                 if (currIdx > 0) {
-                    if (i > 0 && currIdx == matches[i - 1] + 1)
+                    if (i > 0 && currIdx == matches[i - 1] + 1) {
 	                    // Sequential
-                        outScore += sequential_bonus;
+                        outScore += sequential_state;
+                        // Exponential grow of the sequential bonus.
+                    	sequential_state = std::min(5 * sequential_bonus, sequential_state + sequential_state / 3);
+                    } else {
+                    	// Reset the sequential bonus exponential grow.
+                    	sequential_state = sequential_bonus;
+                    }
+					char_type prev = strBegin[currIdx - 1];
 /*
                     // Camel case
-					char_type prev = strBegin[currIdx - 1];
                     if (std::islower(prev) && std::isupper(strBegin[currIdx]))
                         outScore += camel_bonus;
 */