4 files changed, 417 insertions, 0 deletions
diff --git a/Swift/Controllers/Roster/UnitTest/LeastCommonSubsequenceTest.cpp b/Swift/Controllers/Roster/UnitTest/LeastCommonSubsequenceTest.cpp
new file mode 100644
index 0000000..3acab12
--- /dev/null
+++ b/Swift/Controllers/Roster/UnitTest/LeastCommonSubsequenceTest.cpp
@@ -0,0 +1,308 @@
+/*
+ * Copyright (c) 2011 Remko Tronçon
+ * 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/assign/list_of.hpp>
+#include <functional>
+
+#include <QA/Checker/IO.h>
+#include <Swift/Controllers/Roster/LeastCommonSubsequence.h>
+
+using namespace Swift;
+
+struct IsBOrC {
+	bool operator()(char c, char c2) const {
+		CPPUNIT_ASSERT_EQUAL(c, c2);
+		return c == 'b' || c == 'c';
+	}
+};
+
+struct IsXOrY {
+	bool operator()(char c, char c2) const {
+		CPPUNIT_ASSERT_EQUAL(c, c2);
+		return c == 'x' || c == 'y';
+	}
+};
+
+struct IsArizonaOrNewJersey {
+	bool operator()(const std::string& s, const std::string& s2) const {
+		CPPUNIT_ASSERT_EQUAL(s, s2);
+		return s == "Arizona" || s == "New Jersey";
+	}
+};
+
+class LeastCommonSubsequenceTest : public CppUnit::TestFixture {
+		CPPUNIT_TEST_SUITE(LeastCommonSubsequenceTest);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_1);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_2);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_Sequence1Empty);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_Sequence2Empty);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_BothSequencesEmpty);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_NoCommonSequence);
+		CPPUNIT_TEST(testComputeLeastCommonSubsequenceMatrix_SameSequences);
+		CPPUNIT_TEST(testComputeIndexDiff_1);
+		CPPUNIT_TEST(testComputeIndexDiff_2);
+		CPPUNIT_TEST(testComputeIndexDiff_Sequence1Empty);
+		CPPUNIT_TEST(testComputeIndexDiff_Sequence2Empty);
+		CPPUNIT_TEST(testComputeIndexDiff_BothSequencesEmpty);
+		CPPUNIT_TEST(testComputeIndexDiff_NoCommonSequence);
+		CPPUNIT_TEST(testComputeIndexDiff_SameSequences);
+		CPPUNIT_TEST(testComputeIndexDiff_CommonPrefixAndSuffix);
+		CPPUNIT_TEST_SUITE_END();
+
+	public:
+		void testComputeLeastCommonSubsequenceMatrix_1() {
+			std::vector<char> x = boost::assign::list_of('x')('m')('j')('y')('a')('u')('z');
+			std::vector<char> y = boost::assign::list_of('m')('z')('j')('a')('w')('x')('u');
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of
+				(0)(0)(0)(0)(0)(0)(0)(0)
+				(0)(0)(1)(1)(1)(1)(1)(1)
+				(0)(0)(1)(1)(1)(1)(1)(2)
+				(0)(0)(1)(2)(2)(2)(2)(2)
+				(0)(0)(1)(2)(2)(3)(3)(3)
+				(0)(0)(1)(2)(2)(3)(3)(3)
+				(0)(1)(1)(2)(2)(3)(3)(3)
+				(0)(1)(1)(2)(2)(3)(4)(4);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeLeastCommonSubsequenceMatrix_2() {
+			std::vector<char> x = boost::assign::list_of('x')('x')('x')('m')('j')('y')('a')('u')('z');
+			std::vector<char> y = boost::assign::list_of('m')('z')('j')('a')('w')('x')('u');
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of
+				(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)
+				(0)(0)(0)(0)(1)(1)(1)(1)(1)(1)
+				(0)(0)(0)(0)(1)(1)(1)(1)(1)(2)
+				(0)(0)(0)(0)(1)(2)(2)(2)(2)(2)
+				(0)(0)(0)(0)(1)(2)(2)(3)(3)(3)
+				(0)(0)(0)(0)(1)(2)(2)(3)(3)(3)
+				(0)(1)(1)(1)(1)(2)(2)(3)(3)(3)
+				(0)(1)(1)(1)(1)(2)(2)(3)(4)(4);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeLeastCommonSubsequenceMatrix_Sequence1Empty() {
+			std::vector<char> x;
+			std::vector<char> y = boost::assign::list_of('a')('b')('c');
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of
+				(0)
+				(0)
+				(0)
+				(0);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeLeastCommonSubsequenceMatrix_Sequence2Empty() {
+			std::vector<char> x = boost::assign::list_of('a')('b')('c');
+			std::vector<char> y;
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of
+				(0)(0)(0)(0);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeLeastCommonSubsequenceMatrix_BothSequencesEmpty() {
+			std::vector<char> x;
+			std::vector<char> y;
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of(0);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeLeastCommonSubsequenceMatrix_NoCommonSequence() {
+			std::vector<char> x = boost::assign::list_of('a')('b')('c');
+			std::vector<char> y = boost::assign::list_of('d')('e')('f')('g');
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of
+				(0)(0)(0)(0)
+				(0)(0)(0)(0)
+				(0)(0)(0)(0)
+				(0)(0)(0)(0)
+				(0)(0)(0)(0);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeLeastCommonSubsequenceMatrix_SameSequences() {
+			std::vector<char> x = boost::assign::list_of('a')('b')('c');
+			std::vector<char> y = boost::assign::list_of('a')('b')('c');
+
+			std::vector<int> result;
+			Detail::computeLeastCommonSubsequenceMatrix<std::vector<char>::const_iterator, std::vector<char>::const_iterator, int, std::equal_to<char> >(x.begin(), x.end(), y.begin(), y.end(), result);
+
+			std::vector<int> expected = boost::assign::list_of
+				(0)(0)(0)(0)
+				(0)(1)(1)(1)
+				(0)(1)(2)(2)
+				(0)(1)(2)(3);
+			CPPUNIT_ASSERT_EQUAL(expected, result);
+		}
+
+		void testComputeIndexDiff_1() {
+			std::vector<std::string> x = boost::assign::list_of("Arizona")("California")("Delaware")("New Jersey")("Washington");
+			std::vector<std::string> y = boost::assign::list_of("Alaska")("Arizona")("California")("Georgia")("New Jersey")("Virginia");
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<std::string, std::equal_to<std::string>, IsArizonaOrNewJersey >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedUpdates = boost::assign::list_of(3)(0);
+			std::vector<size_t> expectedPostUpdates = boost::assign::list_of(4)(1);
+			std::vector<size_t> expectedRemoves = boost::assign::list_of(4)(2);
+			std::vector<size_t> expectedInserts = boost::assign::list_of(5)(3)(0);
+			CPPUNIT_ASSERT_EQUAL(expectedUpdates, updates);
+			CPPUNIT_ASSERT_EQUAL(expectedPostUpdates, postUpdates);
+			CPPUNIT_ASSERT_EQUAL(expectedRemoves, removes);
+			CPPUNIT_ASSERT_EQUAL(expectedInserts, inserts);
+		}
+
+		void testComputeIndexDiff_2() {
+			std::vector<char> x = boost::assign::list_of('x')('y');
+			std::vector<char> y = boost::assign::list_of('x');
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsBOrC >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedRemoves = boost::assign::list_of(1);
+			CPPUNIT_ASSERT(updates.empty());
+			CPPUNIT_ASSERT(postUpdates.empty());
+			CPPUNIT_ASSERT(inserts.empty());
+			CPPUNIT_ASSERT_EQUAL(expectedRemoves, removes);
+		}
+
+		void testComputeIndexDiff_Sequence1Empty() {
+			std::vector<char> x;
+			std::vector<char> y = boost::assign::list_of('a')('b')('c');
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsBOrC >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedInserts = boost::assign::list_of(2)(1)(0);
+			CPPUNIT_ASSERT(updates.empty());
+			CPPUNIT_ASSERT(postUpdates.empty());
+			CPPUNIT_ASSERT(removes.empty());
+			CPPUNIT_ASSERT_EQUAL(expectedInserts, inserts);
+		}
+
+		void testComputeIndexDiff_Sequence2Empty() {
+			std::vector<char> x = boost::assign::list_of('a')('b')('c');
+			std::vector<char> y;
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsBOrC >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedRemoves = boost::assign::list_of(2)(1)(0);
+			CPPUNIT_ASSERT(updates.empty());
+			CPPUNIT_ASSERT(postUpdates.empty());
+			CPPUNIT_ASSERT_EQUAL(expectedRemoves, removes);
+			CPPUNIT_ASSERT(inserts.empty());
+		}
+
+		void testComputeIndexDiff_BothSequencesEmpty() {
+			std::vector<char> x;
+			std::vector<char> y;
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsBOrC >(x, y, updates, postUpdates, removes, inserts);
+			
+			CPPUNIT_ASSERT(updates.empty());
+			CPPUNIT_ASSERT(postUpdates.empty());
+			CPPUNIT_ASSERT(removes.empty());
+			CPPUNIT_ASSERT(inserts.empty());
+		}
+
+		void testComputeIndexDiff_NoCommonSequence() {
+			std::vector<char> x = boost::assign::list_of('a')('b')('c');
+			std::vector<char> y = boost::assign::list_of('d')('e')('f')('g');
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsBOrC >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedRemoves = boost::assign::list_of(2)(1)(0);
+			std::vector<size_t> expectedInserts = boost::assign::list_of(3)(2)(1)(0);
+			CPPUNIT_ASSERT(updates.empty());
+			CPPUNIT_ASSERT(postUpdates.empty());
+			CPPUNIT_ASSERT_EQUAL(expectedRemoves, removes);
+			CPPUNIT_ASSERT_EQUAL(expectedInserts, inserts);
+		}
+
+		void testComputeIndexDiff_SameSequences() {
+			std::vector<char> x = boost::assign::list_of('a')('b')('c');
+			std::vector<char> y = boost::assign::list_of('a')('b')('c');
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsBOrC >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedUpdates = boost::assign::list_of(1)(2);
+			CPPUNIT_ASSERT_EQUAL(expectedUpdates, updates);
+			CPPUNIT_ASSERT_EQUAL(expectedUpdates, postUpdates);
+			CPPUNIT_ASSERT(removes.empty());
+			CPPUNIT_ASSERT(inserts.empty());
+		}
+
+		void testComputeIndexDiff_CommonPrefixAndSuffix() {
+			std::vector<char> x = boost::assign::list_of('x')('x')('x')('x')('a')('b')('c')('d')('e')('y')('y')('y');
+			std::vector<char> y = boost::assign::list_of('x')('x')('x')('x')('e')('a')('b')('f')('d')('g')('y')('y')('y');
+
+			std::vector<size_t> updates;
+			std::vector<size_t> postUpdates;
+			std::vector<size_t> removes;
+			std::vector<size_t> inserts;
+			computeIndexDiff<char, std::equal_to<char>, IsXOrY >(x, y, updates, postUpdates, removes, inserts);
+			
+			std::vector<size_t> expectedUpdates = boost::assign::list_of(0)(1)(2)(3)(11)(10)(9);
+			std::vector<size_t> expectedPostUpdates = boost::assign::list_of(0)(1)(2)(3)(12)(11)(10);
+			std::vector<size_t> expectedRemoves = boost::assign::list_of(8)(6);
+			std::vector<size_t> expectedInserts = boost::assign::list_of(9)(7)(4);
+			CPPUNIT_ASSERT_EQUAL(expectedUpdates, updates);
+			CPPUNIT_ASSERT_EQUAL(expectedPostUpdates, postUpdates);
+			CPPUNIT_ASSERT_EQUAL(expectedRemoves, removes);
+			CPPUNIT_ASSERT_EQUAL(expectedInserts, inserts);
+		}
+};
+
+CPPUNIT_TEST_SUITE_REGISTRATION(LeastCommonSubsequenceTest);
diff --git a/Swift/Controllers/Roster/UnitTest/RosterControllerTest.cpp b/Swift/Controllers/Roster/UnitTest/RosterControllerTest.cpp
index 16f2745..ca74dbb 100644
--- a/Swift/Controllers/Roster/UnitTest/RosterControllerTest.cpp
+++ b/Swift/Controllers/Roster/UnitTest/RosterControllerTest.cpp
@@ -8,6 +8,7 @@
 #include <cppunit/extensions/HelperMacros.h>
 #include <cppunit/extensions/TestFactoryRegistry.h>
 
+#include <Swiften/Base/foreach.h>
 #include "Swift/Controllers/Roster/RosterController.h"
 #include "Swift/Controllers/UnitTest/MockMainWindowFactory.h"
 // #include "Swiften/Elements/Payload.h"
diff --git a/Swift/Controllers/Roster/UnitTest/RosterTest.cpp b/Swift/Controllers/Roster/UnitTest/RosterTest.cpp
index cbef787..4444e8a 100644
--- a/Swift/Controllers/Roster/UnitTest/RosterTest.cpp
+++ b/Swift/Controllers/Roster/UnitTest/RosterTest.cpp
@@ -21,6 +21,7 @@ class RosterTest : public CppUnit::TestFixture {
 		CPPUNIT_TEST(testRemoveSecondContact);
 		CPPUNIT_TEST(testRemoveSecondContactSameBare);
 		CPPUNIT_TEST(testApplyPresenceLikeMUC);
+		CPPUNIT_TEST(testReSortLikeMUC);
 		CPPUNIT_TEST_SUITE_END();
 
 	public:
@@ -117,6 +118,22 @@ class RosterTest : public CppUnit::TestFixture {
 
 		}
 
+		void testReSortLikeMUC() {
+			JID jid4a("a@b/c");
+			JID jid4b("a@b/d");
+			JID jid4c("a@b/e");
+			roster_->addContact(jid4a, JID(), "Bird", "group1", "");
+			roster_->addContact(jid4b, JID(), "Cookie", "group2", "");
+			roster_->addContact(jid4b, JID(), "Ernie", "group1", "");
+			roster_->getGroup("group1")->setManualSort("2");
+			roster_->getGroup("group2")->setManualSort("1");
+			GroupRosterItem* root = roster_->getRoot();
+			const std::vector<RosterItem*> kids = root->getDisplayedChildren();
+			CPPUNIT_ASSERT_EQUAL(static_cast<size_t>(2), kids.size());
+			CPPUNIT_ASSERT_EQUAL(std::string("group2"), kids[0]->getDisplayName());
+			CPPUNIT_ASSERT_EQUAL(std::string("group1"), kids[1]->getDisplayName());
+		}
+
 	private:
 		Roster *roster_;
 		JID jid1_;
diff --git a/Swift/Controllers/Roster/UnitTest/TableRosterTest.cpp b/Swift/Controllers/Roster/UnitTest/TableRosterTest.cpp
new file mode 100644
index 0000000..e433b50
--- /dev/null
+++ b/Swift/Controllers/Roster/UnitTest/TableRosterTest.cpp
@@ -0,0 +1,91 @@
+/*
+ * Copyright (c) 2010 Remko Tronçon
+ * Licensed under the GNU General Public License v3.
+ * See Documentation/Licenses/GPLv3.txt for more information.
+ */
+
+#include <Swift/Controllers/Roster/TableRoster.h>
+
+std::ostream& operator<<(std::ostream& os, const Swift::TableRoster::Index& i) {
+	os << "(" << i.section << ", " << i.row << ")";
+	return os;
+}
+
+#include <cppunit/extensions/HelperMacros.h>
+#include <cppunit/extensions/TestFactoryRegistry.h>
+#include <boost/shared_ptr.hpp>
+#include <boost/variant.hpp>
+
+#include <Swiften/Network/DummyTimerFactory.h>
+#include <Swift/Controllers/Roster/Roster.h>
+#include <Swift/Controllers/Roster/GroupRosterItem.h>
+#include <Swift/Controllers/Roster/SetPresence.h>
+
+using namespace Swift;
+
+class TableRosterTest : public CppUnit::TestFixture {
+		CPPUNIT_TEST_SUITE(TableRosterTest);
+		CPPUNIT_TEST(testAddContact_EmptyRoster);
+		CPPUNIT_TEST_SUITE_END();
+
+	public:
+		void setUp() {
+			timerFactory = new DummyTimerFactory();
+			roster = new Roster();
+			jid1 = JID("jid1@example.com");
+			jid2 = JID("jid2@example.com");
+		}
+
+		void tearDown() {
+			delete roster;
+			delete timerFactory;
+		}
+
+		void testAddContact_EmptyRoster() {
+			/*
+			boost::shared_ptr<TableRoster> tableRoster(createTestling());
+
+			addContact(jid1, "1", "group1");
+
+			CPPUNIT_ASSERT_EQUAL(4, static_cast<int>(events.size()));
+			CPPUNIT_ASSERT(boost::get<BeginUpdatesEvent>(&events[0]));
+			CPPUNIT_ASSERT(boost::get<SectionsInsertedEvent>(&events[1]));
+			CPPUNIT_ASSERT_EQUAL(1, static_cast<int>(boost::get<SectionsInsertedEvent>(events[1]).sections.size()));
+			CPPUNIT_ASSERT_EQUAL(0, static_cast<int>(boost::get<SectionsInsertedEvent>(events[1]).sections[0]));
+			CPPUNIT_ASSERT(boost::get<RowsInsertedEvent>(&events[2]));
+			CPPUNIT_ASSERT_EQUAL(1, static_cast<int>(boost::get<RowsInsertedEvent>(events[2]).rows.size()));
+			CPPUNIT_ASSERT_EQUAL(TableRoster::Index(0, 0), boost::get<RowsInsertedEvent>(events[2]).rows[0]);
+			CPPUNIT_ASSERT(boost::get<EndUpdatesEvent>(&events[3]));
+
+			CPPUNIT_ASSERT_EQUAL(1, static_cast<int>(tableRoster->getNumberOfSections()));
+			CPPUNIT_ASSERT_EQUAL(std::string("group1"), tableRoster->getSectionTitle(0));
+			CPPUNIT_ASSERT_EQUAL(1, static_cast<int>(tableRoster->getNumberOfRowsInSection(0)));
+			CPPUNIT_ASSERT_EQUAL(jid1, tableRoster->getItem(TableRoster::Index(0, 0)).jid);
+			*/
+		}
+
+	private:
+		void addContact(const JID& jid, const std::string& name, const std::string& group) {
+			roster->addContact(jid, JID(), name, group, "");
+		}
+
+		TableRoster* createTestling() {
+			TableRoster* result = new TableRoster(roster, timerFactory, 10);
+			result->onUpdate.connect(boost::bind(&TableRosterTest::handleUpdate, this, _1));
+			return result;
+		}
+
+		void handleUpdate(const TableRoster::Update& update) {
+			updates.push_back(update);
+		}
+
+	private:
+		DummyTimerFactory* timerFactory;
+		Roster* roster;
+		JID jid1;
+		JID jid2;
+		std::vector<TableRoster::Update> updates;
+};
+
+CPPUNIT_TEST_SUITE_REGISTRATION(TableRosterTest);
+