summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRichard Maudsley <richard.maudsley@isode.com>2014-04-14 09:46:23 (GMT)
committerRichard Maudsley <richard.maudsley@isode.com>2014-04-25 08:38:24 (GMT)
commitd5f701fdd6826421c0c83b8e299918065b6c99d1 (patch)
tree90d5c425b8dda4c293e3e902ad9cea4f7750430f
parente4704555946626980014d936dcfe6ede2710501b (diff)
downloadswift-contrib-d5f701fdd6826421c0c83b8e299918065b6c99d1.zip
swift-contrib-d5f701fdd6826421c0c83b8e299918065b6c99d1.tar.bz2
Sort ContactSuggester results using case-insensitive substring match, plus unit tests.
Change-Id: I806f696dac582ba2d818ceb22df3a10495ce0b16
-rw-r--r--Swift/Controllers/Contact.cpp45
-rw-r--r--Swift/Controllers/Contact.h4
-rw-r--r--Swift/Controllers/ContactSuggester.cpp26
-rw-r--r--Swift/Controllers/ContactSuggester.h7
-rw-r--r--Swift/Controllers/SConscript1
-rw-r--r--Swift/Controllers/UnitTest/ContactSuggesterTest.cpp128
6 files changed, 187 insertions, 24 deletions
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);