diff options
Diffstat (limited to 'src/emu/drivenum.cpp')
-rw-r--r-- | src/emu/drivenum.cpp | 123 |
1 files changed, 68 insertions, 55 deletions
diff --git a/src/emu/drivenum.cpp b/src/emu/drivenum.cpp index 989a9cc8f46..b3e9ce93d62 100644 --- a/src/emu/drivenum.cpp +++ b/src/emu/drivenum.cpp @@ -12,8 +12,6 @@ #include "drivenum.h" #include "softlist_dev.h" -#include <algorithm> - #include <ctype.h> @@ -66,6 +64,47 @@ bool driver_list::matches(const char *wildstring, const char *string) } +//------------------------------------------------- +// penalty_compare - compare two strings for +// closeness and assign a score. +//------------------------------------------------- + +int driver_list::penalty_compare(const char *source, const char *target) +{ + int gaps = 1; + bool last = true; + + // scan the strings + for ( ; *source && *target; target++) + { + // do a case insensitive match + bool const match(tolower(u8(*source)) == tolower(u8(*target))); + + // if we matched, advance the source + if (match) + source++; + + // if the match state changed, count gaps + if (match != last) + { + last = match; + if (!match) + gaps++; + } + } + + // penalty if short string does not completely fit in + for ( ; *source; source++) + gaps++; + + // if we matched perfectly, gaps == 0 + if (gaps == 1 && *source == 0 && *target == 0) + gaps = 0; + + return gaps; +} + + //************************************************************************** // DRIVER ENUMERATOR @@ -221,12 +260,12 @@ bool driver_enumerator::next_excluded() // an array of game_driver pointers //------------------------------------------------- -void driver_enumerator::find_approximate_matches(std::string const &string, std::size_t count, int *results) +void driver_enumerator::find_approximate_matches(const char *string, std::size_t count, int *results) { #undef rand // if no name, pick random entries - if (string.empty()) + if (!string || !string[0]) { // seed the RNG first srand(osd_ticks()); @@ -256,11 +295,14 @@ void driver_enumerator::find_approximate_matches(std::string const &string, std: else { // allocate memory to track the penalty value - std::vector<std::pair<double, int> > penalty; - penalty.reserve(count); - std::u32string const search(ustr_from_utf8(normalize_unicode(string, unicode_normalization_form::D, true))); - std::string composed; - std::u32string candidate; + std::vector<int> penalty(count); + + // initialize everyone's states + for (int matchnum = 0; matchnum < count; matchnum++) + { + penalty[matchnum] = 9999; + results[matchnum] = -1; + } // scan the entire drivers array for (int index = 0; index < s_driver_count; index++) @@ -268,58 +310,29 @@ void driver_enumerator::find_approximate_matches(std::string const &string, std: // skip things that can't run if (m_included[index]) { - // cheat on the shortname as it's always lowercase ASCII - game_driver const &drv(*s_drivers_sorted[index]); - std::size_t const namelen(std::strlen(drv.name)); - candidate.resize(namelen); - std::copy_n(drv.name, namelen, candidate.begin()); - double curpenalty(util::edit_distance(search, candidate)); - - // if it's not a perfect match, try the description - if (curpenalty) - { - candidate = ustr_from_utf8(normalize_unicode(drv.type.fullname(), unicode_normalization_form::D, true)); - double p(util::edit_distance(search, candidate)); - if (p < curpenalty) - curpenalty = p; - } - - // also check "<manufacturer> <description>" - if (curpenalty) - { - composed.assign(drv.manufacturer); - composed.append(1, ' '); - composed.append(drv.type.fullname()); - candidate = ustr_from_utf8(normalize_unicode(composed, unicode_normalization_form::D, true)); - double p(util::edit_distance(search, candidate)); - if (p < curpenalty) - curpenalty = p; - } + // pick the best match between driver name and description + int curpenalty = penalty_compare(string, s_drivers_sorted[index]->type.fullname()); + int tmp = penalty_compare(string, s_drivers_sorted[index]->name); + curpenalty = (std::min)(curpenalty, tmp); // insert into the sorted table of matches - auto const it(std::upper_bound(penalty.begin(), penalty.end(), std::make_pair(curpenalty, index))); - if (penalty.end() != it) + for (int matchnum = count - 1; matchnum >= 0; matchnum--) { - if (penalty.size() >= count) - penalty.resize(count - 1); - penalty.emplace(it, curpenalty, index); - } - else if (penalty.size() < count) - { - penalty.emplace(it, curpenalty, index); + // stop if we're worse than the current entry + if (curpenalty >= penalty[matchnum]) + break; + + // as long as this isn't the last entry, bump this one down + if (matchnum < count - 1) + { + penalty[matchnum + 1] = penalty[matchnum]; + results[matchnum + 1] = results[matchnum]; + } + results[matchnum] = index; + penalty[matchnum] = curpenalty; } } } - - // copy to output and pad with -1 - std::fill( - std::transform( - penalty.begin(), - penalty.end(), - results, - [] (std::pair<double, int> const &x) { return x.second; }), - results + count, - -1); } } |