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
@@ -1,17 +1,62 @@
 /*
  * Copyright (c) 2013 Tobias Markmann
  * Licensed under the simplified BSD license.
  * 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 {
 
 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
@@ -1,37 +1,41 @@
 /*
  * Copyright (c) 2013 Tobias Markmann
  * Licensed under the simplified BSD license.
  * See Documentation/Licenses/BSD-simplified.txt for more information.
  */
 
 /*
  * Copyright (c) 2014 Kevin Smith and Remko Tronçon
  * Licensed under the GNU General Public License v3.
  * See Documentation/Licenses/GPLv3.txt for more information.
  */
 
 #pragma once
 
 #include <boost/enable_shared_from_this.hpp>
 #include <boost/filesystem/path.hpp>
 
 #include <Swiften/Elements/StatusShow.h>
 #include <Swiften/JID/JID.h>
 
 namespace Swift {
 
 class Contact : public boost::enable_shared_from_this<Contact> {
 	public:
 		typedef boost::shared_ptr<Contact> ref;
 
 		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;
 		StatusShow::Type statusType;
 		boost::filesystem::path avatarPath;
 };
 
 }
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
@@ -1,91 +1,77 @@
 /*
  * Copyright (c) 2013 Tobias Markmann
  * Licensed under the simplified BSD license.
  * See Documentation/Licenses/BSD-simplified.txt for more information.
  */
 
 /*
  * Copyright (c) 2014 Kevin Smith and Remko Tronçon
  * Licensed under the GNU General Public License v3.
  * See Documentation/Licenses/GPLv3.txt for more information.
  */
 
 #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>
 
 #include <Swiften/Base/Algorithm.h>
 #include <Swiften/Base/foreach.h>
 #include <Swiften/JID/JID.h>
 
 #include <Swift/Controllers/ContactProvider.h>
 
 #include <algorithm>
 #include <vector>
 #include <set>
 
 namespace lambda = boost::lambda;
 
 namespace Swift {
 
 ContactSuggester::ContactSuggester() {
 }
 
 ContactSuggester::~ContactSuggester() {
 }
 
 void ContactSuggester::addContactProvider(ContactProvider* provider) {
 	contactProviders_.push_back(provider);
 }
 
 bool ContactSuggester::matchContact(const std::string& search, const Contact::ref& c) {
 	return fuzzyMatch(c->name, search) || fuzzyMatch(c->jid.toString(), search);
 }
 
 std::vector<Contact::ref> ContactSuggester::getSuggestions(const std::string& search) const {
 	std::vector<Contact::ref> results;
 
 	foreach(ContactProvider* provider, contactProviders_) {
 		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;
 }
 
 bool ContactSuggester::fuzzyMatch(std::string text, std::string match) {
 	for (std::string::iterator currentQueryChar = match.begin(); currentQueryChar != match.end(); currentQueryChar++) {
 		//size_t result = text.find(*currentQueryChar);
 		std::string::iterator result = boost::algorithm::ifind_first(text, std::string(currentQueryChar, currentQueryChar+1)).begin();
 		if (result == text.end()) {
 			return false;
 		}
 		text.erase(result);
 	}
 	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
@@ -1,44 +1,43 @@
 /*
  * Copyright (c) 2013 Tobias Markmann
  * Licensed under the simplified BSD license.
  * See Documentation/Licenses/BSD-simplified.txt for more information.
  */
 
 /*
  * Copyright (c) 2014 Kevin Smith and Remko Tronçon
  * Licensed under the GNU General Public License v3.
  * See Documentation/Licenses/GPLv3.txt for more information.
  */
 
 #pragma once
 
 #include <string>
 #include <vector>
 
 #include <Swift/Controllers/Contact.h>
 
+class ContactSuggesterTest;
+
 namespace Swift {
 	class ContactProvider;
 
 	class ContactSuggester {
 	public:
 		ContactSuggester();
 		~ContactSuggester();
 
 		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
@@ -73,36 +73,37 @@ if env["SCONS_STAGE"] == "build" :
 			"Storages/FileStorages.cpp",
 			"Storages/RosterFileStorage.cpp",
 			"Storages/CapsFileStorage.cpp",
 			"Storages/VCardFileStorage.cpp",
 			"StatusUtil.cpp",
 			"Translator.cpp",
 			"XMPPURIController.cpp",
 			"ChatMessageSummarizer.cpp",
 			"SettingConstants.cpp",
 			"WhiteboardManager.cpp",
 			"StatusCache.cpp",
 			"HighlightAction.cpp",
 			"HighlightEditorController.cpp",
 			"HighlightManager.cpp",
 			"HighlightRule.cpp",
 			"Highlighter.cpp",
 			"ContactsFromXMPPRoster.cpp",
 			"ContactProvider.cpp",
 			"Contact.cpp"
 		])
 
 	env.Append(UNITTEST_SOURCES = [
 			File("Roster/UnitTest/RosterControllerTest.cpp"),
 			File("Roster/UnitTest/RosterTest.cpp"),
 			File("Roster/UnitTest/LeastCommonSubsequenceTest.cpp"),
 			File("Roster/UnitTest/TableRosterTest.cpp"),	
 			File("UnitTest/PreviousStatusStoreTest.cpp"),
 			File("UnitTest/PresenceNotifierTest.cpp"),
 			File("Chat/UnitTest/ChatsManagerTest.cpp"),
 			File("Chat/UnitTest/MUCControllerTest.cpp"),
 			File("Chat/UnitTest/ChatMessageParserTest.cpp"),
 			File("UnitTest/MockChatWindow.cpp"),
 			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);