Sort ContactSuggester results using case-insensitive substring match, plus unit tests.

Change-Id: I806f696dac582ba2d818ceb22df3a10495ce0b16
author: Richard Maudsley <richard.maudsley@isode.com> 2014-04-14 09:46:23 (GMT)
committer: Richard Maudsley <richard.maudsley@isode.com> 2014-04-25 08:38:24 (GMT)
commit: d5f701fdd6826421c0c83b8e299918065b6c99d1 (patch)
tree: 90d5c425b8dda4c293e3e902ad9cea4f7750430f
parent: e4704555946626980014d936dcfe6ede2710501b (diff)
download: swift-d5f701fdd6826421c0c83b8e299918065b6c99d1.zip
swift-d5f701fdd6826421c0c83b8e299918065b6c99d1.tar.bz2
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);
author	Richard Maudsley <richard.maudsley@isode.com>	2014-04-14 09:46:23 (GMT)
committer	Richard Maudsley <richard.maudsley@isode.com>	2014-04-25 08:38:24 (GMT)
commit	d5f701fdd6826421c0c83b8e299918065b6c99d1 (patch)
tree	90d5c425b8dda4c293e3e902ad9cea4f7750430f
parent	e4704555946626980014d936dcfe6ede2710501b (diff)
download	swift-d5f701fdd6826421c0c83b8e299918065b6c99d1.zip swift-d5f701fdd6826421c0c83b8e299918065b6c99d1.tar.bz2