From d5f701fdd6826421c0c83b8e299918065b6c99d1 Mon Sep 17 00:00:00 2001 From: Richard Maudsley <richard.maudsley@isode.com> Date: Mon, 14 Apr 2014 10:46:23 +0100 Subject: Sort ContactSuggester results using case-insensitive substring match, plus unit tests. Change-Id: I806f696dac582ba2d818ceb22df3a10495ce0b16 diff --git a/Swift/Controllers/Contact.cpp b/Swift/Controllers/Contact.cpp index 7eb446c..198443d 100644 --- a/Swift/Controllers/Contact.cpp +++ b/Swift/Controllers/Contact.cpp @@ -4,6 +4,8 @@ * See Documentation/Licenses/BSD-simplified.txt for more information. */ +#include <boost/algorithm/string.hpp> +#include <boost/algorithm/string/find.hpp> #include <Swift/Controllers/Contact.h> namespace Swift { @@ -14,4 +16,47 @@ Contact::Contact() { Contact::Contact(const std::string& name, const JID& jid, StatusShow::Type statusType, const boost::filesystem::path& path) : name(name), jid(jid), statusType(statusType), avatarPath(path) { } +bool Contact::lexicographicalSortPredicate(const Contact::ref& a, const Contact::ref& b) { + return a->jid < b->jid; +} + +bool Contact::equalityPredicate(const Contact::ref& a, const Contact::ref& b) { + return a->jid == b->jid; +} + +bool Contact::sortPredicate(const Contact::ref& a, const Contact::ref& b, const std::string& search) { + /* perform case insensitive comparisons */ + std::string aLower = a->name; + boost::to_lower(aLower); + std::string bLower = b->name; + boost::to_lower(bLower); + std::string searchLower = search; + boost::to_lower(searchLower); + + /* name starts with the search term */ + if (aLower.find(searchLower) == 0 && bLower.find(searchLower) != 0) { + return true; + } else if (bLower.find(searchLower) == 0 && aLower.find(searchLower) != 0) { + return false; + } + + /* name contains search term */ + if (aLower.find(searchLower) != std::string::npos && bLower.find(searchLower) == std::string::npos) { + return true; + } else if (bLower.find(searchLower) != std::string::npos && aLower.find(searchLower) == std::string::npos) { + return false; + } + + /* Levenshtein should be done here */ + /* if edit distances are equal, fall through to the tests below */ + + /* lexicographical sort */ + if (a->statusType == b->statusType) { + return aLower.compare(bLower) < 0; + } + + /* online status */ + return a->statusType < b->statusType; +} + } diff --git a/Swift/Controllers/Contact.h b/Swift/Controllers/Contact.h index ceba152..f83230f 100644 --- a/Swift/Controllers/Contact.h +++ b/Swift/Controllers/Contact.h @@ -27,6 +27,10 @@ class Contact : public boost::enable_shared_from_this<Contact> { Contact(); Contact(const std::string& name, const JID& jid, StatusShow::Type statusType, const boost::filesystem::path& path); + static bool lexicographicalSortPredicate(const Contact::ref& a, const Contact::ref& b); + static bool equalityPredicate(const Contact::ref& a, const Contact::ref& b); + static bool sortPredicate(const Contact::ref& a, const Contact::ref& b, const std::string& search); + public: std::string name; JID jid; diff --git a/Swift/Controllers/ContactSuggester.cpp b/Swift/Controllers/ContactSuggester.cpp index 41e0261..09a1567 100644 --- a/Swift/Controllers/ContactSuggester.cpp +++ b/Swift/Controllers/ContactSuggester.cpp @@ -12,7 +12,9 @@ #include <Swift/Controllers/ContactSuggester.h> +#include <boost/algorithm/string.hpp> #include <boost/algorithm/string/find.hpp> +#include <boost/bind.hpp> #include <boost/lambda/lambda.hpp> #include <boost/lambda/bind.hpp> @@ -51,11 +53,11 @@ std::vector<Contact::ref> ContactSuggester::getSuggestions(const std::string& se append(results, provider->getContacts()); } - std::sort(results.begin(), results.end(), ContactSuggester::contactLexicographicalSortPredicate); - results.erase(std::unique(results.begin(), results.end(), ContactSuggester::contactEqualityPredicate), results.end()); - results.erase(std::remove_if(results.begin(), results.end(), !lambda::bind(&ContactSuggester::matchContact, search, lambda::_1)), + std::sort(results.begin(), results.end(), Contact::lexicographicalSortPredicate); + results.erase(std::unique(results.begin(), results.end(), Contact::equalityPredicate), results.end()); + results.erase(std::remove_if(results.begin(), results.end(), !lambda::bind(&matchContact, search, lambda::_1)), results.end()); - std::sort(results.begin(), results.end(), ContactSuggester::contactSmartSortPredicate); + std::sort(results.begin(), results.end(), boost::bind(&Contact::sortPredicate, _1, _2, search)); return results; } @@ -72,20 +74,4 @@ bool ContactSuggester::fuzzyMatch(std::string text, std::string match) { return true; } -bool ContactSuggester::contactLexicographicalSortPredicate(const Contact::ref& a, const Contact::ref& b) { - return a->jid < b->jid; -} - -bool ContactSuggester::contactEqualityPredicate(const Contact::ref& a, const Contact::ref& b) { - return a->jid == b->jid; -} - -bool ContactSuggester::contactSmartSortPredicate(const Contact::ref& a, const Contact::ref& b) { - if (a->statusType == b->statusType) { - return a->name.compare(b->name) < 0; - } else { - return a->statusType < b->statusType; - } -} - } diff --git a/Swift/Controllers/ContactSuggester.h b/Swift/Controllers/ContactSuggester.h index 67b912c..1c796c9 100644 --- a/Swift/Controllers/ContactSuggester.h +++ b/Swift/Controllers/ContactSuggester.h @@ -17,6 +17,8 @@ #include <Swift/Controllers/Contact.h> +class ContactSuggesterTest; + namespace Swift { class ContactProvider; @@ -28,15 +30,12 @@ namespace Swift { void addContactProvider(ContactProvider* provider); std::vector<Contact::ref> getSuggestions(const std::string& search) const; - private: + public: static bool matchContact(const std::string& search, const Contact::ref& c); /** * Performs fuzzy matching on the string text. Matches when each character of match string is present in sequence in text string. */ static bool fuzzyMatch(std::string text, std::string match); - static bool contactLexicographicalSortPredicate(const Contact::ref& a, const Contact::ref& b); - static bool contactEqualityPredicate(const Contact::ref& a, const Contact::ref& b); - static bool contactSmartSortPredicate(const Contact::ref& a, const Contact::ref& b); private: std::vector<ContactProvider*> contactProviders_; diff --git a/Swift/Controllers/SConscript b/Swift/Controllers/SConscript index e0fa508..e911a3a 100644 --- a/Swift/Controllers/SConscript +++ b/Swift/Controllers/SConscript @@ -105,4 +105,5 @@ if env["SCONS_STAGE"] == "build" : File("UnitTest/ChatMessageSummarizerTest.cpp"), File("Settings/UnitTest/SettingsProviderHierachyTest.cpp"), File("UnitTest/HighlightRuleTest.cpp"), + File("UnitTest/ContactSuggesterTest.cpp") ]) diff --git a/Swift/Controllers/UnitTest/ContactSuggesterTest.cpp b/Swift/Controllers/UnitTest/ContactSuggesterTest.cpp new file mode 100644 index 0000000..222491b --- /dev/null +++ b/Swift/Controllers/UnitTest/ContactSuggesterTest.cpp @@ -0,0 +1,128 @@ +/* + * Copyright (c) 2014 Kevin Smith + * Licensed under the GNU General Public License v3. + * See Documentation/Licenses/GPLv3.txt for more information. + */ + +#include <cppunit/extensions/HelperMacros.h> +#include <cppunit/extensions/TestFactoryRegistry.h> + +#include <boost/bind.hpp> +#include <boost/function.hpp> +#include <boost/smart_ptr/make_shared.hpp> + +#include <Swiften/Base/foreach.h> +#include "Swift/Controllers/ContactSuggester.h" + +using namespace Swift; + +class ContactSuggesterTest : public CppUnit::TestFixture { + CPPUNIT_TEST_SUITE(ContactSuggesterTest); + CPPUNIT_TEST(equalityTest); + CPPUNIT_TEST(lexicographicalSortTest); + CPPUNIT_TEST(sortTest); + CPPUNIT_TEST_SUITE_END(); + +public: + + std::vector<std::string> wordList() { + const std::string words[] = { + "abc", + "ab", + "bc", + "d" + }; + + return std::vector<std::string>(words, words+sizeof(words)/sizeof(*words)); + } + + std::vector<StatusShow::Type> statusList() { + StatusShow::Type types[] = { + StatusShow::Online, + StatusShow::Away, + StatusShow::FFC, + StatusShow::XA, + StatusShow::DND, + StatusShow::None + }; + + return std::vector<StatusShow::Type>(types, types+sizeof(types)/sizeof(*types)); + } + + std::vector<Contact::ref> contactList() { + std::vector<Contact::ref> contacts; + std::vector<std::string> words = wordList(); + std::vector<StatusShow::Type> statuses = statusList(); + foreach (const std::string& name, words) { + foreach (const std::string& jid, words) { + foreach (const StatusShow::Type& status, statuses) { + contacts.push_back(boost::make_shared<Contact>(name, jid, status, "")); + } + } + } + return contacts; + } + + /* a = a */ + bool isReflexive(const boost::function<bool (const Contact::ref&, const Contact::ref&)>& comparitor) { + std::vector<Contact::ref> contacts = contactList(); + foreach (const Contact::ref& a, contacts) { + if (!comparitor(a, a)) { + return false; + } + } + return true; + } + + /* a = b -> b = a */ + bool isSymmetric(const boost::function<bool (const Contact::ref&, const Contact::ref&)>& comparitor) { + std::vector<Contact::ref> contacts = contactList(); + foreach (const Contact::ref& a, contacts) { + foreach (const Contact::ref& b, contacts) { + if (comparitor(a, b)) { + if (!comparitor(b, a)) { + return false; + } + } + } + } + return true; + } + + /* a = b && b = c -> a = c */ + bool isTransitive(const boost::function<bool (const Contact::ref&, const Contact::ref&)>& comparitor) { + std::vector<Contact::ref> contacts = contactList(); + foreach (const Contact::ref& a, contacts) { + foreach (const Contact::ref& b, contacts) { + foreach (const Contact::ref& c, contacts) { + if (comparitor(a, b) && comparitor(b, c)) { + if (!comparitor(a, c)) { + return false; + } + } + } + } + } + return true; + } + + void equalityTest() { + CPPUNIT_ASSERT(isReflexive(Contact::equalityPredicate)); + CPPUNIT_ASSERT(isSymmetric(Contact::equalityPredicate)); + CPPUNIT_ASSERT(isTransitive(Contact::equalityPredicate)); + } + + void lexicographicalSortTest() { + CPPUNIT_ASSERT(isTransitive(Contact::lexicographicalSortPredicate)); + } + + void sortTest() { + std::vector<std::string> words = wordList(); + foreach (const std::string& word, words) { + CPPUNIT_ASSERT(isTransitive(boost::bind(Contact::sortPredicate, _1, _2, word))); + } + } + +}; + +CPPUNIT_TEST_SUITE_REGISTRATION(ContactSuggesterTest); -- cgit v0.10.2-6-g49f6