summaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
author Vas Crabb <vas@vastheman.com>2019-01-14 00:44:46 +1100
committer Vas Crabb <vas@vastheman.com>2019-01-14 00:44:46 +1100
commit3d84943f72df5d69db5e5cff1d71887fcc23c422 (patch)
tree893bbfe9575c70b5b95311642937bc92bfb633ba
parent9d7b4d0faa64f42665b1c19b28b5eb15c0f40d29 (diff)
Make search not suck as badly (use algorithm derived from Jaro-Winkler similarity to match search strings, match on more useful stuff)
-rw-r--r--src/emu/drivenum.cpp123
-rw-r--r--src/emu/drivenum.h3
-rw-r--r--src/emu/softlist_dev.cpp11
-rw-r--r--src/frontend/mame/clifront.cpp16
-rw-r--r--src/frontend/mame/ui/auditmenu.cpp11
-rw-r--r--src/frontend/mame/ui/selector.cpp13
-rw-r--r--src/frontend/mame/ui/selector.h16
-rw-r--r--src/frontend/mame/ui/selgame.cpp331
-rw-r--r--src/frontend/mame/ui/selgame.h16
-rw-r--r--src/frontend/mame/ui/selsoft.cpp19
-rw-r--r--src/frontend/mame/ui/simpleselgame.cpp2
-rw-r--r--src/frontend/mame/ui/utils.cpp184
-rw-r--r--src/frontend/mame/ui/utils.h43
-rw-r--r--src/lib/util/corestr.cpp95
-rw-r--r--src/lib/util/corestr.h7
-rw-r--r--src/lib/util/unicode.cpp170
-rw-r--r--src/lib/util/unicode.h17
17 files changed, 692 insertions, 385 deletions
diff --git a/src/emu/drivenum.cpp b/src/emu/drivenum.cpp
index b3e9ce93d62..989a9cc8f46 100644
--- a/src/emu/drivenum.cpp
+++ b/src/emu/drivenum.cpp
@@ -12,6 +12,8 @@
#include "drivenum.h"
#include "softlist_dev.h"
+#include <algorithm>
+
#include <ctype.h>
@@ -64,47 +66,6 @@ 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
@@ -260,12 +221,12 @@ bool driver_enumerator::next_excluded()
// an array of game_driver pointers
//-------------------------------------------------
-void driver_enumerator::find_approximate_matches(const char *string, std::size_t count, int *results)
+void driver_enumerator::find_approximate_matches(std::string const &string, std::size_t count, int *results)
{
#undef rand
// if no name, pick random entries
- if (!string || !string[0])
+ if (string.empty())
{
// seed the RNG first
srand(osd_ticks());
@@ -295,14 +256,11 @@ void driver_enumerator::find_approximate_matches(const char *string, std::size_t
else
{
// allocate memory to track the penalty value
- std::vector<int> penalty(count);
-
- // initialize everyone's states
- for (int matchnum = 0; matchnum < count; matchnum++)
- {
- penalty[matchnum] = 9999;
- results[matchnum] = -1;
- }
+ 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;
// scan the entire drivers array
for (int index = 0; index < s_driver_count; index++)
@@ -310,29 +268,58 @@ void driver_enumerator::find_approximate_matches(const char *string, std::size_t
// skip things that can't run
if (m_included[index])
{
- // 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);
+ // 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;
+ }
// insert into the sorted table of matches
- for (int matchnum = count - 1; matchnum >= 0; matchnum--)
+ auto const it(std::upper_bound(penalty.begin(), penalty.end(), std::make_pair(curpenalty, index)));
+ if (penalty.end() != it)
{
- // 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;
+ if (penalty.size() >= count)
+ penalty.resize(count - 1);
+ penalty.emplace(it, curpenalty, index);
+ }
+ else if (penalty.size() < count)
+ {
+ penalty.emplace(it, curpenalty, index);
}
}
}
+
+ // 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);
}
}
diff --git a/src/emu/drivenum.h b/src/emu/drivenum.h
index 8db4fa9766c..8c0f12b832f 100644
--- a/src/emu/drivenum.h
+++ b/src/emu/drivenum.h
@@ -61,7 +61,6 @@ public:
// static helpers
static bool matches(const char *wildstring, const char *string);
- static int penalty_compare(const char *source, const char *target);
protected:
static std::size_t const s_driver_count;
@@ -120,7 +119,7 @@ public:
// general helpers
void set_current(std::size_t index) { assert(index < s_driver_count); m_current = index; }
- void find_approximate_matches(const char *string, std::size_t count, int *results);
+ void find_approximate_matches(std::string const &string, std::size_t count, int *results);
private:
static constexpr std::size_t CONFIG_CACHE_COUNT = 100;
diff --git a/src/emu/softlist_dev.cpp b/src/emu/softlist_dev.cpp
index 21dfb45ba09..e1539523dcb 100644
--- a/src/emu/softlist_dev.cpp
+++ b/src/emu/softlist_dev.cpp
@@ -113,14 +113,15 @@ void software_list_device::find_approx_matches(const std::string &name, int matc
return;
// initialize everyone's states
- std::vector<int> penalty(matches);
+ std::vector<double> penalty(matches);
for (int matchnum = 0; matchnum < matches; matchnum++)
{
- penalty[matchnum] = 9999;
+ penalty[matchnum] = 1.0;
list[matchnum] = nullptr;
}
// iterate over our info (will cause a parse if needed)
+ std::u32string const search(ustr_from_utf8(normalize_unicode(name, unicode_normalization_form::D, true)));
for (const software_info &swinfo : get_info())
{
for (const software_part &swpart : swinfo.parts())
@@ -128,9 +129,9 @@ void software_list_device::find_approx_matches(const std::string &name, int matc
if ((interface == nullptr || swpart.matches_interface(interface)) && is_compatible(swpart) == SOFTWARE_IS_COMPATIBLE)
{
// pick the best match between driver name and description
- int longpenalty = driver_list::penalty_compare(name.c_str(), swinfo.longname().c_str());
- int shortpenalty = driver_list::penalty_compare(name.c_str(), swinfo.shortname().c_str());
- int curpenalty = std::min(longpenalty, shortpenalty);
+ double const longpenalty = util::edit_distance(search, ustr_from_utf8(normalize_unicode(swinfo.longname(), unicode_normalization_form::D, true)));
+ double const shortpenalty = util::edit_distance(search, ustr_from_utf8(normalize_unicode(swinfo.shortname(), unicode_normalization_form::D, true)));
+ double const curpenalty = std::min(longpenalty, shortpenalty);
// make sure it isn't already in the table
bool skip = false;
diff --git a/src/frontend/mame/clifront.cpp b/src/frontend/mame/clifront.cpp
index 97147c76dc9..276c73f0e63 100644
--- a/src/frontend/mame/clifront.cpp
+++ b/src/frontend/mame/clifront.cpp
@@ -295,14 +295,22 @@ int cli_frontend::execute(std::vector<std::string> &args)
// get the top 16 approximate matches
driver_enumerator drivlist(m_options);
int matches[16];
- drivlist.find_approximate_matches(m_options.attempted_system_name().c_str(), ARRAY_LENGTH(matches), matches);
+ drivlist.find_approximate_matches(m_options.attempted_system_name(), ARRAY_LENGTH(matches), matches);
+
+ // work out how wide the titles need to be
+ int titlelen(0);
+ for (int match : matches)
+ titlelen = std::max(titlelen, int(strlen(drivlist.driver(match).type.fullname())));
// print them out
osd_printf_error("\n\"%s\" approximately matches the following\n"
"supported machines (best match first):\n\n", m_options.attempted_system_name().c_str());
- for (auto & matche : matches)
- if (matche != -1)
- osd_printf_error("%-18s%s\n", drivlist.driver(matche).name, drivlist.driver(matche).type.fullname());
+ for (int match : matches)
+ {
+ game_driver const &drv(drivlist.driver(match));
+ if (match != -1)
+ osd_printf_error("%s", util::string_format("%-18s%-*s(%s, %s)\n", drv.name, titlelen + 2, drv.type.fullname(), drv.manufacturer, drv.year).c_str());
+ }
}
}
catch (emu_exception &)
diff --git a/src/frontend/mame/ui/auditmenu.cpp b/src/frontend/mame/ui/auditmenu.cpp
index 0349e1c2949..7d5cbfd7305 100644
--- a/src/frontend/mame/ui/auditmenu.cpp
+++ b/src/frontend/mame/ui/auditmenu.cpp
@@ -207,24 +207,21 @@ void menu_audit::audit_fast()
void menu_audit::audit_all()
{
- m_availablesorted.clear();
driver_enumerator enumerator(machine().options());
media_auditor auditor(enumerator);
+ std::vector<bool> available(driver_list::total(), false);
while (enumerator.next())
{
m_current.store(&enumerator.driver());
media_auditor::summary const summary(auditor.audit_media(AUDIT_VALIDATE_FAST));
// if everything looks good, include the driver
- m_availablesorted.emplace_back(enumerator.driver(), (summary == media_auditor::CORRECT) || (summary == media_auditor::BEST_AVAILABLE) || (summary == media_auditor::NONE_NEEDED));
+ available[enumerator.current()] = (summary == media_auditor::CORRECT) || (summary == media_auditor::BEST_AVAILABLE) || (summary == media_auditor::NONE_NEEDED);
++m_audited;
}
- // sort
- std::stable_sort(
- m_availablesorted.begin(),
- m_availablesorted.end(),
- [] (ui_system_info const &a, ui_system_info const &b) { return sorted_game_list(a.driver, b.driver); });
+ for (ui_system_info &info : m_availablesorted)
+ info.available = available[info.index];
}
void menu_audit::save_available_machines()
diff --git a/src/frontend/mame/ui/selector.cpp b/src/frontend/mame/ui/selector.cpp
index 59aa51f9d13..7f5441afc2c 100644
--- a/src/frontend/mame/ui/selector.cpp
+++ b/src/frontend/mame/ui/selector.cpp
@@ -136,12 +136,17 @@ void menu_selector::custom_render(void *selectedref, float top, float bottom, fl
void menu_selector::find_matches(const char *str)
{
// allocate memory to track the penalty value
- std::vector<int> penalty(VISIBLE_GAMES_IN_SEARCH, 9999);
- int index = 0;
+ m_ucs_items.reserve(m_str_items.size());
+ std::vector<double> penalty(VISIBLE_GAMES_IN_SEARCH, 1.0);
+ std::u32string const search(ustr_from_utf8(normalize_unicode(str, unicode_normalization_form::D, true)));
- for (; index < m_str_items.size(); ++index)
+ int index = 0;
+ for ( ; index < m_str_items.size(); ++index)
{
- int curpenalty = fuzzy_substring(str, m_str_items[index]);
+ assert(m_ucs_items.size() >= index);
+ if (m_ucs_items.size() == index)
+ m_ucs_items.emplace_back(ustr_from_utf8(normalize_unicode(m_str_items[index], unicode_normalization_form::D, true)));
+ double const curpenalty(util::edit_distance(search, m_ucs_items[index]));
// insert into the sorted table of matches
for (int matchnum = VISIBLE_GAMES_IN_SEARCH - 1; matchnum >= 0; --matchnum)
diff --git a/src/frontend/mame/ui/selector.h b/src/frontend/mame/ui/selector.h
index bd6a87c4ef9..f3921536267 100644
--- a/src/frontend/mame/ui/selector.h
+++ b/src/frontend/mame/ui/selector.h
@@ -7,14 +7,15 @@
Internal UI user interface.
***************************************************************************/
+#ifndef MAME_FRONTEND_UI_SELECTOR_H
+#define MAME_FRONTEND_UI_SELECTOR_H
#pragma once
-#ifndef MAME_FRONTEND_UI_SELECTOR_H
-#define MAME_FRONTEND_UI_SELECTOR_H
#include "ui/menu.h"
+
namespace ui {
//-------------------------------------------------
@@ -44,11 +45,12 @@ private:
void find_matches(const char *str);
- std::string m_search;
- std::vector<std::string> m_str_items;
- std::function<void (int)> m_handler;
- int m_initial;
- std::string *m_searchlist[VISIBLE_GAMES_IN_SEARCH + 1];
+ std::string m_search;
+ std::vector<std::string> m_str_items;
+ std::function<void (int)> m_handler;
+ std::vector<std::u32string> m_ucs_items;
+ int m_initial;
+ std::string *m_searchlist[VISIBLE_GAMES_IN_SEARCH + 1];
};
} // namespace ui
diff --git a/src/frontend/mame/ui/selgame.cpp b/src/frontend/mame/ui/selgame.cpp
index 0b47fa1d7d1..acc9dd666b1 100644
--- a/src/frontend/mame/ui/selgame.cpp
+++ b/src/frontend/mame/ui/selgame.cpp
@@ -31,17 +31,168 @@
#include "uiinput.h"
#include "luaengine.h"
+#include <atomic>
+#include <condition_variable>
#include <cstring>
#include <iterator>
+#include <memory>
+#include <mutex>
+#include <thread>
extern const char UI_VERSION_TAG[];
namespace ui {
-bool menu_select_game::first_start = true;
-std::vector<const game_driver *> menu_select_game::m_sortedlist;
-int menu_select_game::m_isabios = 0;
+class menu_select_game::persistent_data
+{
+public:
+ enum available : unsigned
+ {
+ AVAIL_NONE = 0,
+ AVAIL_SORTED_LIST = 1 << 0,
+ AVAIL_BIOS_COUNT = 1 << 1,
+ AVAIL_UCS_SHORTNAME = 1 << 2,
+ AVAIL_UCS_DESCRIPTION = 1 << 3,
+ AVAIL_UCS_MANUF_DESC = 1 << 4
+ };
+
+ persistent_data()
+ : m_started(false)
+ , m_available(AVAIL_NONE)
+ , m_bios_count(0)
+ {
+ }
+
+ ~persistent_data()
+ {
+ if (m_thread)
+ m_thread->join();
+ }
+
+ void cache_data()
+ {
+ std::unique_lock<std::mutex> lock(m_mutex);
+ do_start_caching();
+ }
+
+ bool is_available(available desired)
+ {
+ return (m_available.load(std::memory_order_acquire) & desired) == desired;
+ }
+
+ void wait_available(available desired)
+ {
+ if (!is_available(desired))
+ {
+ std::unique_lock<std::mutex> lock(m_mutex);
+ do_start_caching();
+ m_condition.wait(lock, [this, desired] () { return is_available(desired); });
+ }
+ }
+
+ std::vector<ui_system_info> &sorted_list()
+ {
+ wait_available(AVAIL_SORTED_LIST);
+ return m_sorted_list;
+ }
+
+ int bios_count()
+ {
+ wait_available(AVAIL_BIOS_COUNT);
+ return m_bios_count;
+ }
+
+ bool unavailable_systems()
+ {
+ wait_available(AVAIL_SORTED_LIST);
+ return std::find_if(m_sorted_list.begin(), m_sorted_list.end(), [] (ui_system_info const &info) { return !info.available; }) != m_sorted_list.end();
+ }
+
+private:
+ void notify_available(available value)
+ {
+ std::unique_lock<std::mutex> lock(m_mutex);
+ m_available.fetch_or(value, std::memory_order_release);
+ m_condition.notify_all();
+ }
+
+ void do_start_caching()
+ {
+ if (!m_started)
+ {
+ m_started = true;
+ m_thread = std::make_unique<std::thread>([this] { do_cache_data(); });
+ }
+ }
+
+ void do_cache_data()
+ {
+ // generate full list
+ m_sorted_list.reserve(driver_list::total());
+ std::unordered_set<std::string> manufacturers, years;
+ for (int x = 0; x < driver_list::total(); ++x)
+ {
+ game_driver const &driver(driver_list::driver(x));
+ if (&driver != &GAME_NAME(___empty))
+ {
+ if (driver.flags & machine_flags::IS_BIOS_ROOT)
+ ++m_bios_count;
+
+ m_sorted_list.emplace_back(driver, x, false);
+ c_mnfct::add(driver.manufacturer);
+ c_year::add(driver.year);
+ }
+ }
+
+ // notify that BIOS count is valie
+ notify_available(AVAIL_BIOS_COUNT);
+
+ // sort drivers and notify
+ std::stable_sort(
+ m_sorted_list.begin(),
+ m_sorted_list.end(),
+ [] (ui_system_info const &lhs, ui_system_info const &rhs) { return sorted_game_list(lhs.driver, rhs.driver); });
+ notify_available(AVAIL_SORTED_LIST);
+
+ // convert shortnames to UCS-4
+ for (ui_system_info &info : m_sorted_list)
+ info.ucs_shortname = ustr_from_utf8(normalize_unicode(info.driver->name, unicode_normalization_form::D, true));
+ notify_available(AVAIL_UCS_SHORTNAME);
+
+ // convert descriptions to UCS-4
+ for (ui_system_info &info : m_sorted_list)
+ info.ucs_description = ustr_from_utf8(normalize_unicode(info.driver->type.fullname(), unicode_normalization_form::D, true));
+ notify_available(AVAIL_UCS_DESCRIPTION);
+
+ // convert "<manufacturer> <description>" to UCS-4
+ std::string buf;
+ for (ui_system_info &info : m_sorted_list)
+ {
+ buf.assign(info.driver->manufacturer);
+ buf.append(1, ' ');
+ buf.append(info.driver->type.fullname());
+ info.ucs_manufacturer_description = ustr_from_utf8(normalize_unicode(buf, unicode_normalization_form::D, true));
+ }
+ notify_available(AVAIL_UCS_MANUF_DESC);
+
+ // sort manufacturers and years
+ c_mnfct::finalise();
+ c_year::finalise();
+ }
+
+ std::mutex m_mutex;
+ std::condition_variable m_condition;
+ std::unique_ptr<std::thread> m_thread;
+ std::atomic<bool> m_started;
+ std::atomic<unsigned> m_available;
+ std::vector<ui_system_info> m_sorted_list;
+ int m_bios_count;
+};
+
+menu_select_game::persistent_data menu_select_game::s_persistent_data;
+bool menu_select_game::s_first_start = true;
+
//-------------------------------------------------
// ctor
@@ -54,7 +205,7 @@ menu_select_game::menu_select_game(mame_ui_manager &mui, render_container &conta
ui_options &moptions = mui.options();
// load drivers cache
- init_sorted_list();
+ s_persistent_data.cache_data();
// check if there are available icons
ui_globals::has_icons = false;
@@ -74,8 +225,9 @@ menu_select_game::menu_select_game(mame_ui_manager &mui, render_container &conta
if (!load_available_machines())
build_available_list();
- if (first_start)
+ if (s_first_start)
{
+ //s_first_start = false; TODO: why wansn't it ever clearing the first start flag?
reselect_last::set_driver(moptions.last_used_machine());
ui_globals::rpanel = std::min<int>(std::max<int>(moptions.last_right_panel(), RP_FIRST), RP_LAST);
@@ -121,7 +273,6 @@ menu_select_game::menu_select_game(mame_ui_manager &mui, render_container &conta
ui_globals::default_image = true;
ui_globals::panels_status = moptions.hide_panels();
ui_globals::curdats_total = 1;
- m_searchlist[0] = nullptr;
}
//-------------------------------------------------
@@ -326,12 +477,12 @@ void menu_select_game::handle()
break;
case IPT_UI_AUDIT_FAST:
- if (std::find_if(m_availsortedlist.begin(), m_availsortedlist.end(), [] (ui_system_info const &info) { return !info.available; }) != m_availsortedlist.end())
- menu::stack_push<menu_audit>(ui(), container(), m_availsortedlist, menu_audit::mode::FAST);
+ if (s_persistent_data.unavailable_systems())
+ menu::stack_push<menu_audit>(ui(), container(), s_persistent_data.sorted_list(), menu_audit::mode::FAST);
break;
case IPT_UI_AUDIT_ALL:
- menu::stack_push<menu_audit>(ui(), container(), m_availsortedlist, menu_audit::mode::ALL);
+ menu::stack_push<menu_audit>(ui(), container(), s_persistent_data.sorted_list(), menu_audit::mode::ALL);
break;
}
}
@@ -368,10 +519,11 @@ void menu_select_game::populate(float &customtop, float &custombottom)
// if filter is set on category, build category list
auto const it(main_filters::filters.find(main_filters::actual));
+ std::vector<ui_system_info> const &sorted(s_persistent_data.sorted_list());
if (main_filters::filters.end() == it)
- m_displaylist = m_availsortedlist;
+ std::copy(sorted.begin(), sorted.end(), std::back_inserter(m_displaylist));
else
- it->second->apply(m_availsortedlist.begin(), m_availsortedlist.end(), std::back_inserter(m_displaylist));
+ it->second->apply(sorted.begin(), sorted.end(), std::back_inserter(m_displaylist));
// iterate over entries
int curitem = 0;
@@ -400,7 +552,7 @@ void menu_select_game::populate(float &customtop, float &custombottom)
int curitem = 0;
// iterate over entries
- for (auto & favmap : mame_machine_manager::instance()->favorite().m_list)
+ for (auto &favmap : mame_machine_manager::instance()->favorite().m_list)
{
auto flags = flags_ui | FLAG_UI_FAVORITE;
if (favmap.second.startempty == 1)
@@ -562,18 +714,9 @@ void menu_select_game::build_available_list()
}
}
- // sort
- m_availsortedlist.reserve(total);
- for (std::size_t x = 0; total > x; ++x)
- {
- game_driver const &driver(driver_list::driver(x));
- if (&driver != &GAME_NAME(___empty))
- m_availsortedlist.emplace_back(driver, included[x]);
- }
- std::stable_sort(
- m_availsortedlist.begin(),
- m_availsortedlist.end(),
- [] (ui_system_info const &a, ui_system_info const &b) { return sorted_game_list(a.driver, b.driver); });
+ // copy into the persistent sorted list
+ for (ui_system_info &info : s_persistent_data.sorted_list())
+ info.available = included[info.index];
}
@@ -791,48 +934,72 @@ void menu_select_game::change_info_pane(int delta)
void menu_select_game::populate_search()
{
- // allocate memory to track the penalty value
- std::vector<int> penalty(VISIBLE_GAMES_IN_SEARCH, 9999);
- int index = 0;
- for (; index < m_displaylist.size(); ++index)
+ // ensure search list is populated
+ if (m_searchlist.empty())
{
- // pick the best match between driver name and description
- int curpenalty = fuzzy_substring(m_search, m_displaylist[index].driver->type.fullname());
- int tmp = fuzzy_substring(m_search, m_displaylist[index].driver->name);
- curpenalty = std::min(curpenalty, tmp);
+ std::vector<ui_system_info> const &sorted(s_persistent_data.sorted_list());
+ m_searchlist.reserve(sorted.size());
+ for (ui_system_info const &info : sorted)
+ m_searchlist.emplace_back(1.0, std::ref(info));
+ }
- // insert into the sorted table of matches
- for (int matchnum = VISIBLE_GAMES_IN_SEARCH - 1; matchnum >= 0; --matchnum)
- {
- // stop if we're worse than the current entry
- if (curpenalty >= penalty[matchnum])
- break;
+ // keep track of what we matched against
+ const std::u32string ucs_search(ustr_from_utf8(normalize_unicode(m_search, unicode_normalization_form::D, true)));
+ unsigned matched(0);
+
+ // match shortnames
+ if (s_persistent_data.is_available(persistent_data::AVAIL_UCS_SHORTNAME))
+ {
+ matched |= persistent_data::AVAIL_UCS_SHORTNAME;
+ for (std::pair<double, std::reference_wrapper<ui_system_info const> > &info : m_searchlist)
+ info.first = util::edit_distance(ucs_search, info.second.get().ucs_shortname);
+ }
- // as long as this isn't the last entry, bump this one down
- if (matchnum < VISIBLE_GAMES_IN_SEARCH - 1)
+ // match descriptions
+ if (s_persistent_data.is_available(persistent_data::AVAIL_UCS_DESCRIPTION))
+ {
+ matched |= persistent_data::AVAIL_UCS_DESCRIPTION;
+ for (std::pair<double, std::reference_wrapper<ui_system_info const> > &info : m_searchlist)
+ {
+ if (info.first)
{
- penalty[matchnum + 1] = penalty[matchnum];
- m_searchlist[matchnum + 1] = m_searchlist[matchnum];
+ double const penalty(util::edit_distance(ucs_search, info.second.get().ucs_description));
+ info.first = (std::min)(penalty, info.first);
}
+ }
+ }
- m_searchlist[matchnum] = m_displaylist[index].driver;
- penalty[matchnum] = curpenalty;
+ // match "<manufacturer> <description>"
+ if (s_persistent_data.is_available(persistent_data::AVAIL_UCS_MANUF_DESC))
+ {
+ matched |= persistent_data::AVAIL_UCS_MANUF_DESC;
+ for (std::pair<double, std::reference_wrapper<ui_system_info const> > &info : m_searchlist)
+ {
+ if (info.first)
+ {
+ double const penalty(util::edit_distance(ucs_search, info.second.get().ucs_manufacturer_description));
+ info.first = (std::min)(penalty, info.first);
+ }
}
}
- (index < VISIBLE_GAMES_IN_SEARCH) ? m_searchlist[index] = nullptr : m_searchlist[VISIBLE_GAMES_IN_SEARCH] = nullptr;
+ // sort according to edit distance and put up to 200 in the menu
+ std::stable_sort(
+ m_searchlist.begin(),
+ m_searchlist.end(),
+ [] (auto const &lhs, auto const &rhs) { return lhs.first < rhs.first; });
uint32_t flags_ui = FLAG_LEFT_ARROW | FLAG_RIGHT_ARROW;
- for (int curitem = 0; m_searchlist[curitem]; ++curitem)
+ for (int curitem = 0; (std::min)(m_searchlist.size(), std::size_t(200)) > curitem; ++curitem)
{
- bool cloneof = strcmp(m_searchlist[curitem]->parent, "0");
+ game_driver const &drv(*m_searchlist[curitem].second.get().driver);
+ bool cloneof = strcmp(drv.parent, "0") != 0;
if (cloneof)
{
- int cx = driver_list::find(m_searchlist[curitem]->parent);
+ int const cx = driver_list::find(drv.parent);
if (cx != -1 && ((driver_list::driver(cx).flags & machine_flags::IS_BIOS_ROOT) != 0))
cloneof = false;
}
- item_append(m_searchlist[curitem]->type.fullname(), "", (!cloneof) ? flags_ui : (FLAG_INVERT | flags_ui),
- (void *)m_searchlist[curitem]);
+ item_append(drv.type.fullname(), "", !cloneof ? flags_ui : (FLAG_INVERT | flags_ui), (void *)&drv);
}
}
@@ -992,8 +1159,8 @@ void menu_select_game::inkey_export()
std::vector<game_driver const *> list;
if (!m_search.empty())
{
- for (int curitem = 0; m_searchlist[curitem]; ++curitem)
- list.push_back(m_searchlist[curitem]);
+ for (int curitem = 0; (std::min)(m_searchlist.size(), std::size_t(200)); ++curitem)
+ list.push_back(m_searchlist[curitem].second.get().driver);
}
else
{
@@ -1020,41 +1187,6 @@ void menu_select_game::inkey_export()
}
//-------------------------------------------------
-// save drivers infos to file
-//-------------------------------------------------
-
-void menu_select_game::init_sorted_list()
-{
- if (!m_sortedlist.empty())
- return;
-
- // generate full list
- std::unordered_set<std::string> manufacturers, years;
- for (int x = 0; x < driver_list::total(); ++x)
- {
- game_driver const &driver(driver_list::driver(x));
- if (&driver != &GAME_NAME(___empty))
- {
- if (driver.flags & machine_flags::IS_BIOS_ROOT)
- m_isabios++;
-
- m_sortedlist.push_back(&driver);
- manufacturers.emplace(c_mnfct::getname(driver.manufacturer));
- years.emplace(driver.year);
- }
- }
-
- // sort manufacturers - years and driver
- for (auto it = manufacturers.begin(); manufacturers.end() != it; it = manufacturers.erase(it))
- c_mnfct::ui.emplace_back(*it);
- std::sort(c_mnfct::ui.begin(), c_mnfct::ui.end(), [] (std::string const &x, std::string const &y) { return 0 > core_stricmp(x.c_str(), y.c_str()); });
- for (auto it = years.begin(); years.end() != it; it = years.erase(it))
- c_year::ui.emplace_back(*it);
- std::stable_sort(c_year::ui.begin(), c_year::ui.end());
- std::stable_sort(m_sortedlist.begin(), m_sortedlist.end(), sorted_game_list);
-}
-
-//-------------------------------------------------
// load drivers infos from file
//-------------------------------------------------
@@ -1093,27 +1225,18 @@ bool menu_select_game::load_available_machines()
else
available.emplace(std::move(readbuf));
}
+ file.close();
// turn it into the sorted system list we all love
- m_availsortedlist.reserve(driver_list::total());
- for (std::size_t x = 0; driver_list::total() > x; ++x)
+ for (ui_system_info &info : s_persistent_data.sorted_list())
{
- game_driver const &driver(driver_list::driver(x));
- if (&driver != &GAME_NAME(___empty))
- {
- std::unordered_set<std::string>::iterator const it(available.find(&driver.name[0]));
- bool const found(available.end() != it);
- m_availsortedlist.emplace_back(driver, found);
- if (found)
- available.erase(it);
- }
+ std::unordered_set<std::string>::iterator const it(available.find(&info.driver->name[0]));
+ bool const found(available.end() != it);
+ info.available = found;
+ if (found)
+ available.erase(it);
}
- std::stable_sort(
- m_availsortedlist.begin(),
- m_availsortedlist.end(),
- [] (ui_system_info const &a, ui_system_info const &b) { return sorted_game_list(a.driver, b.driver); });
- file.close();
return true;
}
@@ -1170,7 +1293,7 @@ void menu_select_game::make_topbox_text(std::string &line0, std::string &line1,
bare_build_version,
visible_items,
(driver_list::total() - 1),
- m_isabios);
+ s_persistent_data.bios_count());
if (isfavorite())
{
diff --git a/src/frontend/mame/ui/selgame.h b/src/frontend/mame/ui/selgame.h
index 5778b2c544c..d3ab264ed50 100644
--- a/src/frontend/mame/ui/selgame.h
+++ b/src/frontend/mame/ui/selgame.h
@@ -15,6 +15,8 @@
#include "ui/selmenu.h"
#include "ui/utils.h"
+#include <functional>
+
class media_auditor;
@@ -37,15 +39,14 @@ private:
CONF_PLUGINS,
};
- enum { VISIBLE_GAMES_IN_SEARCH = 200 };
- static bool first_start;
- static int m_isabios;
+ class persistent_data;
+
+ std::vector<std::reference_wrapper<ui_system_info const> > m_displaylist;
- static std::vector<const game_driver *> m_sortedlist;
- std::vector<ui_system_info> m_availsortedlist;
- std::vector<ui_system_info> m_displaylist;
+ static persistent_data s_persistent_data;
+ static bool s_first_start;
- const game_driver *m_searchlist[VISIBLE_GAMES_IN_SEARCH + 1];
+ std::vector<std::pair<double, std::reference_wrapper<ui_system_info const> > > m_searchlist;
virtual void populate(float &customtop, float &custombottom) override;
virtual void handle() override;
@@ -75,7 +76,6 @@ private:
bool isfavorite() const;
void populate_search();
- void init_sorted_list();
bool load_available_machines();
void load_custom_filters();
diff --git a/src/frontend/mame/ui/selsoft.cpp b/src/frontend/mame/ui/selsoft.cpp
index e7ebc3effa2..e1eb1f75c33 100644
--- a/src/frontend/mame/ui/selsoft.cpp
+++ b/src/frontend/mame/ui/selsoft.cpp
@@ -490,15 +490,20 @@ void menu_select_software::load_sw_custom_filters()
void menu_select_software::find_matches(const char *str, int count)
{
// allocate memory to track the penalty value
- std::vector<int> penalty(count, 9999);
- int index = 0;
+ std::vector<double> penalty(count, 1.0);
+ std::u32string const search(ustr_from_utf8(normalize_unicode(str, unicode_normalization_form::D, true)));
- for (; index < m_displaylist.size(); ++index)
+ int index = 0;
+ for ( ; index < m_displaylist.size(); ++index)
{
- // pick the best match between driver name and description
- int curpenalty = fuzzy_substring(str, m_displaylist[index]->longname);
- int tmp = fuzzy_substring(str, m_displaylist[index]->shortname);
- curpenalty = std::min(curpenalty, tmp);
+ // pick the best match between shortname and longname
+ // TODO: search alternate title as well
+ double curpenalty(util::edit_distance(search, ustr_from_utf8(normalize_unicode(m_displaylist[index]->shortname, unicode_normalization_form::D, true))));
+ if (curpenalty)
+ {
+ double const tmp(util::edit_distance(search, ustr_from_utf8(normalize_unicode(m_displaylist[index]->longname, unicode_normalization_form::D, true))));
+ curpenalty = (std::min)(curpenalty, tmp);
+ }
// insert into the sorted table of matches
for (int matchnum = count - 1; matchnum >= 0; --matchnum)
diff --git a/src/frontend/mame/ui/simpleselgame.cpp b/src/frontend/mame/ui/simpleselgame.cpp
index f81b161dac1..604c2b32d41 100644
--- a/src/frontend/mame/ui/simpleselgame.cpp
+++ b/src/frontend/mame/ui/simpleselgame.cpp
@@ -250,7 +250,7 @@ void simple_menu_select_game::populate(float &customtop, float &custombottom)
// otherwise, rebuild the match list
assert(m_drivlist != nullptr);
if (!m_search.empty() || m_matchlist[0] == -1 || m_rerandomize)
- m_drivlist->find_approximate_matches(m_search.c_str(), matchcount, m_matchlist);
+ m_drivlist->find_approximate_matches(m_search, matchcount, m_matchlist);
m_rerandomize = false;
// iterate over entries
diff --git a/src/frontend/mame/ui/utils.cpp b/src/frontend/mame/ui/utils.cpp
index 1a8ff0ba476..f82435d3864 100644
--- a/src/frontend/mame/ui/utils.cpp
+++ b/src/frontend/mame/ui/utils.cpp
@@ -22,7 +22,9 @@
#include "romload.h"
#include "softlist.h"
+#include <atomic>
#include <bitset>
+#include <condition_variable>
#include <cstdlib>
#include <cstring>
#include <iterator>
@@ -97,6 +99,26 @@ constexpr char const *SOFTWARE_FILTER_NAMES[software_filter::COUNT] = {
//-------------------------------------------------
+// static filter data
+//-------------------------------------------------
+
+std::mutex f_filter_data_mutex;
+std::condition_variable f_filter_data_condition;
+std::atomic<bool> f_mnfct_finalised(false), f_year_finalised(false);
+std::vector<std::string> f_mnfct_ui, f_year_ui;
+std::unordered_set<std::string> f_mnfct_tmp, f_year_tmp;
+
+std::string trim_manufacturer(std::string const &mfg)
+{
+ size_t const found(mfg.find('('));
+ if ((found != std::string::npos) && (found > 0))
+ return mfg.substr(0, found - 1);
+ else
+ return mfg;
+}
+
+
+//-------------------------------------------------
// base implementation for simple filters
//-------------------------------------------------
@@ -740,7 +762,7 @@ class manufacturer_machine_filter : public choice_filter_impl_base<machine_filte
{
public:
manufacturer_machine_filter(char const *value, emu_file *file, unsigned indent)
- : choice_filter_impl_base<machine_filter, machine_filter::MANUFACTURER>(c_mnfct::ui, value)
+ : choice_filter_impl_base<machine_filter, machine_filter::MANUFACTURER>(c_mnfct::ui(), value)
{
}
@@ -751,7 +773,7 @@ public:
else if (!selection_valid())
return false;
- std::string const name(c_mnfct::getname(system.driver->manufacturer));
+ std::string const name(trim_manufacturer(system.driver->manufacturer));
return !name.empty() && (selection_text() == name);
}
};
@@ -761,7 +783,7 @@ class year_machine_filter : public choice_filter_impl_base<machine_filter, machi
{
public:
year_machine_filter(char const *value, emu_file *file, unsigned indent)
- : choice_filter_impl_base<machine_filter, machine_filter::YEAR>(c_year::ui, value)
+ : choice_filter_impl_base<machine_filter, machine_filter::YEAR>(c_year::ui(), value)
{
}
@@ -1709,18 +1731,96 @@ software_filter::ptr software_filter::create(emu_file &file, software_filter_dat
return nullptr;
}
+
+//-------------------------------------------------
+// set manufacturers
+//-------------------------------------------------
+
+void c_mnfct::add(std::string &&mfg)
+{
+ assert(!f_mnfct_finalised.load(std::memory_order_acquire));
+
+ size_t const found(mfg.find('('));
+ if ((found != std::string::npos) && (found > 0))
+ mfg.resize(found - 1);
+
+ f_mnfct_tmp.emplace(std::move(mfg));
+}
+
+void c_mnfct::finalise()
+{
+ assert(!f_mnfct_finalised.load(std::memory_order_acquire));
+
+ f_mnfct_ui.reserve(f_mnfct_tmp.size());
+ for (auto it = f_mnfct_tmp.begin(); f_mnfct_tmp.end() != it; it = f_mnfct_tmp.erase(it))
+ f_mnfct_ui.emplace_back(*it);
+ std::sort(
+ f_mnfct_ui.begin(),
+ f_mnfct_ui.end(),
+ [] (std::string const &x, std::string const &y) { return 0 > core_stricmp(x.c_str(), y.c_str()); });
+
+ std::unique_lock<std::mutex> lock(f_filter_data_mutex);
+ f_mnfct_finalised.store(true, std::memory_order_release);
+ f_filter_data_condition.notify_all();
+}
+
+std::vector<std::string> const &c_mnfct::ui()
+{
+ if (!f_mnfct_finalised.load(std::memory_order_acquire))
+ {
+ std::unique_lock<std::mutex> lock(f_filter_data_mutex);
+ f_filter_data_condition.wait(lock, [] () { return f_mnfct_finalised.load(std::memory_order_acquire); });
+ }
+
+ return f_mnfct_ui;
+}
+
+
+//-------------------------------------------------
+// set years
+//-------------------------------------------------
+
+void c_year::add(std::string &&year)
+{
+ assert(!f_year_finalised.load(std::memory_order_acquire));
+
+ f_year_tmp.emplace(std::move(year));
+}
+
+void c_year::finalise()
+{
+ assert(!f_year_finalised.load(std::memory_order_acquire));
+
+ f_year_ui.reserve(f_year_tmp.size());
+ for (auto it = f_year_tmp.begin(); f_year_tmp.end() != it; it = f_year_tmp.erase(it))
+ f_year_ui.emplace_back(*it);
+ std::sort(
+ f_year_ui.begin(),
+ f_year_ui.end(),
+ [] (std::string const &x, std::string const &y) { return 0 > core_stricmp(x.c_str(), y.c_str()); });
+
+ std::unique_lock<std::mutex> lock(f_filter_data_mutex);
+ f_year_finalised.store(true, std::memory_order_release);
+ f_filter_data_condition.notify_all();
+}
+
+std::vector<std::string> const &c_year::ui()
+{
+ if (!f_year_finalised.load(std::memory_order_acquire))
+ {
+ std::unique_lock<std::mutex> lock(f_filter_data_mutex);
+ f_filter_data_condition.wait(lock, [] () { return f_year_finalised.load(std::memory_order_acquire); });
+ }
+
+ return f_year_ui;
+}
+
} // namesapce ui
extern const char UI_VERSION_TAG[];
const char UI_VERSION_TAG[] = "# UI INFO ";
-// Years index
-std::vector<std::string> c_year::ui;
-
-// Manufacturers index
-std::vector<std::string> c_mnfct::ui;
-
// Main filters
ui::machine_filter::type main_filters::actual = ui::machine_filter::ALL;
std::map<ui::machine_filter::type, ui::machine_filter::ptr> main_filters::filters;
@@ -1782,72 +1882,6 @@ std::vector<std::string> tokenize(const std::string &text, char sep)
return tokens;
}
-//-------------------------------------------------
-// search a substring with even partial matching
-//-------------------------------------------------
-
-int fuzzy_substring(std::string s_needle, std::string s_haystack)
-{
- if (s_needle.empty())
- return s_haystack.size();
- if (s_haystack.empty())
- return s_needle.size();
-
- strmakelower(s_needle);
- strmakelower(s_haystack);
-
- if (s_needle == s_haystack)
- return 0;
- if (s_haystack.find(s_needle) != std::string::npos)
- return 0;
-
- auto *row1 = global_alloc_array_clear<int>(s_haystack.size() + 2);
- auto *row2 = global_alloc_array_clear<int>(s_haystack.size() + 2);
-
- for (int i = 0; i < s_needle.size(); ++i)
- {
- row2[0] = i + 1;
- for (int j = 0; j < s_haystack.size(); ++j)
- {
- int cost = (s_needle[i] == s_haystack[j]) ? 0 : 1;
- row2[j + 1] = std::min(row1[j + 1] + 1, std::min(row2[j] + 1, row1[j] + cost));
- }
-
- int *tmp = row1;
- row1 = row2;
- row2 = tmp;
- }
-
- int *first, *smallest;
- first = smallest = row1;
- int *last = row1 + s_haystack.size();
-
- while (++first != last)
- if (*first < *smallest)
- smallest = first;
-
- int rv = *smallest;
- global_free_array(row1);
- global_free_array(row2);
-
- return rv;
-}
-
-//-------------------------------------------------
-// set manufacturers
-//-------------------------------------------------
-
-std::string c_mnfct::getname(const char *str)
-{
- std::string name(str);
- size_t found = name.find("(");
-
- if (found != std::string::npos)
- return (name.substr(0, found - 1));
- else
- return name;
-}
-
ui_software_info::ui_software_info(
software_info const &info,
diff --git a/src/frontend/mame/ui/utils.h b/src/frontend/mame/ui/utils.h
index aaedd75854e..b7dbbb255b2 100644
--- a/src/frontend/mame/ui/utils.h
+++ b/src/frontend/mame/ui/utils.h
@@ -31,10 +31,15 @@ class render_container;
struct ui_system_info
{
ui_system_info() { }
- ui_system_info(game_driver const &d, bool a) : driver(&d), available(a) { }
+ ui_system_info(game_driver const &d, int index, bool a) : driver(&d), available(a) { }
game_driver const *driver = nullptr;
+ int index;
bool available = false;
+
+ std::u32string ucs_shortname;
+ std::u32string ucs_description;
+ std::u32string ucs_manufacturer_description;
};
struct ui_software_info
@@ -259,6 +264,24 @@ protected:
DECLARE_ENUM_INCDEC_OPERATORS(software_filter::type)
+// Manufacturers
+struct c_mnfct
+{
+ static void add(std::string &&mfg);
+ static void finalise();
+
+ static std::vector<std::string> const &ui();
+};
+
+// Years
+struct c_year
+{
+ static void add(std::string &&year);
+ static void finalise();
+
+ static std::vector<std::string> const &ui();
+};
+
} // namespace ui
#define MAX_CHAR_INFO 256
@@ -326,26 +349,13 @@ enum
// GLOBAL CLASS
struct ui_globals
{
- static uint8_t curimage_view, curdats_view, curdats_total, cur_sw_dats_view, cur_sw_dats_total, rpanel;
+ static uint8_t curimage_view, curdats_view, curdats_total, cur_sw_dats_view, cur_sw_dats_total, rpanel;
static bool switch_image, redraw_icon, default_image, reset;
static int visible_main_lines, visible_sw_lines;
- static uint16_t panels_status;
+ static uint16_t panels_status;
static bool has_icons;
};
-// Manufacturers
-struct c_mnfct
-{
- static std::string getname(const char *str);
- static std::vector<std::string> ui;
-};
-
-// Years
-struct c_year
-{
- static std::vector<std::string> ui;
-};
-
struct main_filters
{
static ui::machine_filter::type actual;
@@ -353,7 +363,6 @@ struct main_filters
};
// GLOBAL FUNCTIONS
-int fuzzy_substring(std::string needle, std::string haystack);
char* chartrimcarriage(char str[]);
const char* strensure(const char* s);
int getprecisionchr(const char* s);
diff --git a/src/lib/util/corestr.cpp b/src/lib/util/corestr.cpp
index a2fef33a87a..5add3ed302f 100644
--- a/src/lib/util/corestr.cpp
+++ b/src/lib/util/corestr.cpp
@@ -10,6 +10,10 @@
#include "corestr.h"
#include "osdcore.h"
+
+#include <algorithm>
+#include <memory>
+
#include <ctype.h>
#include <stdlib.h>
@@ -236,3 +240,94 @@ int strreplace(std::string &str, const std::string& search, const std::string& r
}
return matches;
}
+
+namespace util {
+
+/**
+ * @fn double edit_distance(std::u32string const &lhs, std::u32string const &rhs)
+ *
+ * @brief Compares strings and returns prefix-weighted similarity score (smaller is more similar).
+ *
+ * @param lhs First input.
+ * @param rhs Second input.
+ *
+ * @return Similarity score ranging from 0.0 (totally dissimilar) to 1.0 (identical).
+ */
+
+double edit_distance(std::u32string const &lhs, std::u32string const &rhs)
+{
+ // based on Jaro-Winkler distance
+ // TODO: this breaks if the lengths don't fit in a long int, but that's not a big limitation
+ constexpr long MAX_PREFIX(4);
+ constexpr double PREFIX_WEIGHT(0.1);
+ constexpr double PREFIX_THRESHOLD(0.7);
+
+ std::u32string const &longer((lhs.length() >= rhs.length()) ? lhs : rhs);
+ std::u32string const &shorter((lhs.length() < rhs.length()) ? lhs : rhs);
+
+ // find matches
+ long const range((std::max)(long(longer.length() / 2) - 1, 0L));
+ std::unique_ptr<long []> match_idx(std::make_unique<long []>(shorter.length()));
+ std::unique_ptr<bool []> match_flg(std::make_unique<bool []>(longer.length()));
+ std::fill_n(match_idx.get(), shorter.length(), -1);
+ std::fill_n(match_flg.get(), longer.length(), false);
+ long match_cnt(0);
+ for (long i = 0; shorter.length() > i; ++i)
+ {
+ char32_t const ch(shorter[i]);
+ long const n((std::min)(i + range + 1L, long(longer.length())));
+ for (long j = (std::max)(i - range, 0L); n > j; ++j)
+ {
+ if (!match_flg[j] && (ch == longer[j]))
+ {
+ match_idx[i] = j;
+ match_flg[j] = true;
+ ++match_cnt;
+ break;
+ }
+ }
+ }
+
+ // early exit if strings are very dissimilar
+ if (!match_cnt)
+ return 1.0;
+
+ // now find transpositions
+ std::unique_ptr<char32_t []> ms(std::make_unique<char32_t []>(2 * match_cnt));
+ std::fill_n(ms.get(), 2 * match_cnt, char32_t(0));
+ char32_t *const ms1(&ms[0]);
+ char32_t *const ms2(&ms[match_cnt]);
+ for (long i = 0, j = 0; shorter.length() > i; ++i)
+ {
+ if (0 <= match_idx[i])
+ ms1[j++] = shorter[i];
+ }
+ match_idx.reset();
+ for (long i = 0, j = 0; longer.length() > i; ++i)
+ {
+ if (match_flg[i])
+ ms2[j++] = longer[i];
+ }
+ match_flg.reset();
+ long halftrans_cnt(0);
+ for (long i = 0; match_cnt > i; ++i)
+ {
+ if (ms1[i] != ms2[i])
+ ++halftrans_cnt;
+ }
+ ms.reset();
+
+ // simple prefix detection
+ long prefix_len(0);
+ for (long i = 0; ((std::min)(long(shorter.length()), MAX_PREFIX) > i) && (lhs[i] == rhs[i]); ++i)
+ ++prefix_len;
+
+ // do the weighting
+ double const m(match_cnt);
+ double const t(double(halftrans_cnt) / 2);
+ double const jaro(((m / lhs.length()) + (m / rhs.length()) + ((m - t) / m)) / 3);
+ double const jaro_winkler((PREFIX_THRESHOLD > jaro) ? jaro : (jaro + (PREFIX_WEIGHT * prefix_len * (1.0 - jaro))));
+ return 1.0 - jaro_winkler;
+}
+
+} // namespace util
diff --git a/src/lib/util/corestr.h b/src/lib/util/corestr.h
index d7734d50b29..c0bf4ef16d5 100644
--- a/src/lib/util/corestr.h
+++ b/src/lib/util/corestr.h
@@ -64,4 +64,11 @@ std::string &strmakeupper(std::string& str);
std::string &strmakelower(std::string& str);
int strreplace(std::string &str, const std::string& search, const std::string& replace);
+namespace util {
+
+// based on Jaro-Winkler distance - returns value from 0.0 (totally dissimilar) to 1.0 (identical)
+double edit_distance(std::u32string const &lhs, std::u32string const &rhs);
+
+} // namespace util
+
#endif // MAME_UTIL_CORESTR_H
diff --git a/src/lib/util/unicode.cpp b/src/lib/util/unicode.cpp
index 5151a1e101d..8e6478beee3 100644
--- a/src/lib/util/unicode.cpp
+++ b/src/lib/util/unicode.cpp
@@ -21,6 +21,67 @@
#include <locale>
+namespace {
+
+//-------------------------------------------------
+// internal_normalize_unicode - uses utf8proc to
+// normalize unicode
+//-------------------------------------------------
+
+std::string internal_normalize_unicode(
+ char const *s,
+ size_t length,
+ unicode_normalization_form normalization_form,
+ bool fold_case,
+ bool null_terminated)
+{
+ // convert the normalization form
+ int options;
+ switch (normalization_form)
+ {
+ case unicode_normalization_form::C:
+ options = UTF8PROC_STABLE | UTF8PROC_COMPOSE;
+ break;
+ case unicode_normalization_form::D:
+ options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE;
+ break;
+ case unicode_normalization_form::KC:
+ options = UTF8PROC_STABLE | UTF8PROC_COMPOSE | UTF8PROC_COMPAT;
+ break;
+ case unicode_normalization_form::KD:
+ options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE | UTF8PROC_COMPAT;
+ break;
+ default:
+ throw false;
+ }
+
+ // perform case folding?
+ if (fold_case)
+ options |= UTF8PROC_CASEFOLD;
+
+ // use NUL terminator to determine length?
+ if (null_terminated)
+ options |= UTF8PROC_NULLTERM;
+
+ // invoke utf8proc
+ utf8proc_uint8_t *utf8proc_result(nullptr);
+ utf8proc_ssize_t const utf8proc_result_length(utf8proc_map(reinterpret_cast<utf8proc_uint8_t const *>(s), length, &utf8proc_result, utf8proc_option_t(options)));
+
+ // conver the result
+ std::string result;
+ if (utf8proc_result)
+ {
+ if (utf8proc_result_length > 0)
+ result.assign(reinterpret_cast<char const *>(utf8proc_result), utf8proc_result_length);
+ free(utf8proc_result);
+ }
+
+ return result;
+}
+
+} // anonymous namespace
+
+
//-------------------------------------------------
// uchar_isvalid - return true if a given
// character is a legitimate unicode character
@@ -66,56 +127,53 @@ bool uchar_is_digit(char32_t uchar)
int uchar_from_utf8(char32_t *uchar, const char *utf8char, size_t count)
{
- char32_t c, minchar;
- int auxlen, i;
- char auxchar;
-
// validate parameters
- if (utf8char == nullptr || count == 0)
+ if (!utf8char || !count)
return 0;
// start with the first byte
- c = (unsigned char) *utf8char;
+ char32_t c = (unsigned char)*utf8char;
count--;
utf8char++;
// based on that, determine how many additional bytes we need
- if (c < 0x80)
+ char32_t minchar;
+ int auxlen;
+ if ((c & 0x80) == 0x00)
{
// unicode char 0x00000000 - 0x0000007F
- c &= 0x7f;
auxlen = 0;
minchar = 0x00000000;
}
- else if (c >= 0xc0 && c < 0xe0)
+ else if ((c & 0xe0) == 0xc0)
{
// unicode char 0x00000080 - 0x000007FF
c &= 0x1f;
auxlen = 1;
minchar = 0x00000080;
}
- else if (c >= 0xe0 && c < 0xf0)
+ else if ((c & 0xf0) == 0xe0)
{
// unicode char 0x00000800 - 0x0000FFFF
c &= 0x0f;
auxlen = 2;
minchar = 0x00000800;
}
- else if (c >= 0xf0 && c < 0xf8)
+ else if ((c & 0xf8) == 0xf0)
{
// unicode char 0x00010000 - 0x001FFFFF
c &= 0x07;
auxlen = 3;
minchar = 0x00010000;
}
- else if (c >= 0xf8 && c < 0xfc)
+ else if ((c & 0xfc) == 0xf8)
{
// unicode char 0x00200000 - 0x03FFFFFF
c &= 0x03;
auxlen = 4;
minchar = 0x00200000;
}
- else if (c >= 0xfc && c < 0xfe)
+ else if ((c & 0xfe) == 0xfc)
{
// unicode char 0x04000000 - 0x7FFFFFFF
c &= 0x01;
@@ -133,9 +191,9 @@ int uchar_from_utf8(char32_t *uchar, const char *utf8char, size_t count)
return -1;
// we now know how long the char is, now compute it
- for (i = 0; i < auxlen; i++)
+ for (int i = 0; i < auxlen; i++)
{
- auxchar = utf8char[i];
+ char32_t const auxchar = (unsigned char)utf8char[i];
// all auxillary chars must be between 0x80-0xbf
if ((auxchar & 0xc0) != 0x80)
@@ -206,6 +264,28 @@ int uchar_from_utf16f(char32_t *uchar, const char16_t *utf16char, size_t count)
//-------------------------------------------------
+// ustr_from_utf8 - convert a UTF-8 sequence into
+// into a Unicode string
+//-------------------------------------------------
+
+std::u32string ustr_from_utf8(const std::string &utf8str)
+{
+ std::u32string result;
+ char const *utf8char(utf8str.c_str());
+ size_t remaining(utf8str.length());
+ while (remaining)
+ {
+ char32_t ch;
+ int const consumed(uchar_from_utf8(&ch, utf8char, remaining));
+ result.append(1, (consumed > 0) ? ch : char32_t(0x00fffdU));
+ utf8char += (consumed > 0) ? consumed : 1;
+ remaining -= (consumed > 0) ? consumed : 1;
+ }
+ return result;
+}
+
+
+//-------------------------------------------------
// utf8_from_uchar - convert a unicode character
// into a UTF-8 sequence
//-------------------------------------------------
@@ -388,61 +468,13 @@ std::string utf8_from_wstring(const std::wstring &string)
//-------------------------------------------------
-// internal_normalize_unicode - uses utf8proc to
-// normalize unicode
-//-------------------------------------------------
-
-static std::string internal_normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form, bool null_terminated)
-{
- // convert the normalization form
- int options;
- switch (normalization_form)
- {
- case unicode_normalization_form::C:
- options = UTF8PROC_STABLE | UTF8PROC_COMPOSE;
- break;
- case unicode_normalization_form::D:
- options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE;
- break;
- case unicode_normalization_form::KC:
- options = UTF8PROC_STABLE | UTF8PROC_COMPOSE | UTF8PROC_COMPAT;
- break;
- case unicode_normalization_form::KD:
- options = UTF8PROC_STABLE | UTF8PROC_DECOMPOSE | UTF8PROC_COMPAT;
- break;
- default:
- throw false;
- }
-
- // was this null terminated?
- if (null_terminated)
- options |= UTF8PROC_NULLTERM;
-
- // invoke utf8proc
- utf8proc_uint8_t *utf8proc_result;
- utf8proc_ssize_t utf8proc_result_length = utf8proc_map((utf8proc_uint8_t *) s, length, &utf8proc_result, (utf8proc_option_t)options);
-
- // conver the result
- std::string result;
- if (utf8proc_result)
- {
- if (utf8proc_result_length > 0)
- result = std::string((const char *)utf8proc_result, utf8proc_result_length);
- free(utf8proc_result);
- }
-
- return result;
-}
-
-
-//-------------------------------------------------
// normalize_unicode - uses utf8proc to normalize
// unicode
//-------------------------------------------------
-std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form)
+std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form, bool fold_case)
{
- return internal_normalize_unicode(s.c_str(), s.length(), normalization_form, false);
+ return internal_normalize_unicode(s.c_str(), s.length(), normalization_form, fold_case, false);
}
@@ -451,9 +483,9 @@ std::string normalize_unicode(const std::string &s, unicode_normalization_form n
// unicode
//-------------------------------------------------
-std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form)
+std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form, bool fold_case)
{
- return internal_normalize_unicode(s, 0, normalization_form, true);
+ return internal_normalize_unicode(s, 0, normalization_form, fold_case, true);
}
@@ -462,9 +494,9 @@ std::string normalize_unicode(const char *s, unicode_normalization_form normaliz
// unicode
//-------------------------------------------------
-std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form)
+std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form, bool fold_case)
{
- return internal_normalize_unicode(s, length, normalization_form, false);
+ return internal_normalize_unicode(s, length, normalization_form, fold_case, false);
}
diff --git a/src/lib/util/unicode.h b/src/lib/util/unicode.h
index 5e30a74916e..46e1aec3496 100644
--- a/src/lib/util/unicode.h
+++ b/src/lib/util/unicode.h
@@ -14,14 +14,16 @@
singular 32-bit Unicode chars.
***************************************************************************/
+#ifndef MAME_LIB_UTIL_UNICODE_H
+#define MAME_LIB_UTIL_UNICODE_H
#pragma once
-#ifndef UNICODE_H
-#define UNICODE_H
+#include "osdcore.h"
+
+#include <string>
#include <stdlib.h>
-#include "osdcore.h"
@@ -95,6 +97,7 @@ bool uchar_is_digit(char32_t uchar);
int uchar_from_utf8(char32_t *uchar, const char *utf8char, size_t count);
int uchar_from_utf16(char32_t *uchar, const char16_t *utf16char, size_t count);
int uchar_from_utf16f(char32_t *uchar, const char16_t *utf16char, size_t count);
+std::u32string ustr_from_utf8(const std::string &utf8str);
// converting 32-bit Unicode chars to strings
int utf8_from_uchar(char *utf8string, size_t count, char32_t uchar);
@@ -107,9 +110,9 @@ std::wstring wstring_from_utf8(const std::string &utf8string);
std::string utf8_from_wstring(const std::wstring &string);
// unicode normalization
-std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form);
-std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form);
-std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form);
+std::string normalize_unicode(const std::string &s, unicode_normalization_form normalization_form, bool fold_case = false);
+std::string normalize_unicode(const char *s, unicode_normalization_form normalization_form, bool fold_case = false);
+std::string normalize_unicode(const char *s, size_t length, unicode_normalization_form normalization_form, bool fold_case = false);
// upper and lower case
char32_t uchar_toupper(char32_t ch);
@@ -137,4 +140,4 @@ bool utf8_is_valid_string(const char *utf8string);
#define utf16le_from_uchar utf16f_from_uchar
#endif
-#endif /* UNICODE_H */
+#endif // MAME_LIB_UTIL_UNICODE_H