5 files changed, 641 insertions, 18 deletions
diff --git a/Swift/Controllers/Roster/LeastCommonSubsequence.h b/Swift/Controllers/Roster/LeastCommonSubsequence.h
new file mode 100644
index 0000000..dd3c95a
--- /dev/null
+++ b/Swift/Controllers/Roster/LeastCommonSubsequence.h
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2011 Remko Tronçon
+ * Licensed under the GNU General Public License v3.
+ * See Documentation/Licenses/GPLv3.txt for more information.
+ */
+
+#pragma once
+
+#include <vector>
+
+namespace Swift {
+	using std::equal_to;
+
+	namespace Detail {
+		template<typename XIt, typename YIt, typename Length, typename Predicate>
+		void computeLeastCommonSubsequenceMatrix(XIt xBegin, XIt xEnd, YIt yBegin, YIt yEnd, std::vector<Length>& result) {
+			size_t width = std::distance(xBegin, xEnd) + 1;
+			size_t height = std::distance(yBegin, yEnd)  + 1;
+			result.resize(width * height);
+
+			// Initialize first row & column
+			for (size_t i = 0; i < width; ++i) {
+				result[i] = 0;
+			}
+			for (size_t j = 0; j < height; ++j) {
+				result[j*width] = 0;
+			}
+
+			// Compute the LCS lengths for subsets
+			Predicate predicate;
+			for (size_t i = 1; i < width; ++i) {
+				for (size_t j = 1; j < height; ++j) {
+					result[i + j*width] = (predicate(*(xBegin + i-1), *(yBegin + j-1)) ? result[(i-1) + (j-1)*width] + 1 : std::max(result[i + (j-1)*width], result[i-1 + (j*width)]));
+				}
+			}
+		}
+	}
+
+	template<typename X, typename InsertRemovePredicate, typename UpdatePredicate>
+	void computeIndexDiff(const std::vector<X>& x, const std::vector<X>& y, std::vector<size_t>& updates, std::vector<size_t>& postUpdates, std::vector<size_t>& removes, std::vector<size_t>& inserts) {
+		InsertRemovePredicate insertRemovePredicate;
+		UpdatePredicate updatePredicate;
+
+		// Find & handle common prefix (Optimization to reduce LCS matrix size)
+		typename std::vector<X>::const_iterator xBegin = x.begin();
+		typename std::vector<X>::const_iterator yBegin = y.begin();
+		while (xBegin < x.end() && yBegin < y.end() && insertRemovePredicate(*xBegin, *yBegin)) {
+			if (updatePredicate(*xBegin, *yBegin)) {
+				updates.push_back(std::distance(x.begin(), xBegin));
+				postUpdates.push_back(std::distance(y.begin(), yBegin));
+			}
+			++xBegin;
+			++yBegin;
+		}
+		size_t prefixLength = std::distance(x.begin(), xBegin);
+
+		// Find & handle common suffix (Optimization to reduce LCS matrix size)
+		typename std::vector<X>::const_reverse_iterator xEnd = x.rbegin();
+		typename std::vector<X>::const_reverse_iterator yEnd = y.rbegin();
+		while (xEnd.base() > xBegin && yEnd.base() > yBegin && insertRemovePredicate(*xEnd, *yEnd)) {
+			if (updatePredicate(*xEnd, *yEnd)) {
+				updates.push_back(std::distance(x.begin(), xEnd.base()) - 1);
+				postUpdates.push_back(std::distance(y.begin(), yEnd.base()) - 1);
+			}
+			++xEnd;
+			++yEnd;
+		}
+
+		// Compute lengths
+		size_t xLength = std::distance(xBegin, xEnd.base());
+		size_t yLength = std::distance(yBegin, yEnd.base());
+
+		// Compute LCS matrix
+		std::vector<unsigned int> lcs;
+		Detail::computeLeastCommonSubsequenceMatrix<typename std::vector<X>::const_iterator, typename std::vector<X>::const_iterator, unsigned int, InsertRemovePredicate>(xBegin, xEnd.base(), yBegin, yEnd.base(), lcs);
+
+		// Process LCS matrix
+		size_t i = xLength;
+		size_t j = yLength;
+		const size_t width = xLength + 1;
+		while (true) {
+			if (i > 0 && j > 0 && insertRemovePredicate(x[prefixLength + i-1], y[prefixLength + j-1])) {
+				// x[i-1] same
+				if (updatePredicate(x[prefixLength + i - 1], y[prefixLength + j - 1])) {
+					updates.push_back(prefixLength + i-1);
+					postUpdates.push_back(prefixLength + j-1);
+				}
+				i -= 1;
+				j -= 1;
+			}
+			else if (j > 0 && (i == 0 || lcs[i + (j-1)*width] >= lcs[i-1 + j*width])) {
+				// y[j-1] added
+				inserts.push_back(prefixLength + j-1);
+				j -= 1;
+			}
+			else if (i > 0 && (j == 0 || lcs[i + (j-1)*width] < lcs[i-1 + j*width])) {
+				// x[i-1] removed
+				removes.push_back(prefixLength + i-1);
+				i -= 1;
+			}
+			else {
+				break;
+			}
+		}
+	}
+}
diff --git a/Swift/Controllers/Roster/TableRoster.cpp b/Swift/Controllers/Roster/TableRoster.cpp
index fda7de8..66e3a85 100644
--- a/Swift/Controllers/Roster/TableRoster.cpp
+++ b/Swift/Controllers/Roster/TableRoster.cpp
@@ -7,30 +7,137 @@
 #include <Swift/Controllers/Roster/TableRoster.h>
 
 #include <boost/cast.hpp>
+#include <cassert>
+#include <algorithm>
+#include <Swiften/Base/foreach.h>
 
+#include <Swiften/Network/TimerFactory.h>
+#include <Swiften/Network/Timer.h>
 #include <Swift/Controllers/Roster/Roster.h>
 #include <Swift/Controllers/Roster/GroupRosterItem.h>
+#include <Swift/Controllers/Roster/LeastCommonSubsequence.h>
+
+namespace Swift {
+	struct SectionNameEquals {
+		bool operator()(const TableRoster::Section& s1, const TableRoster::Section& s2) const {
+			return s1.name == s2.name;
+		}
+	};
+
+	template<typename T>
+	struct True {
+		bool operator()(const T&, const T&) const {
+			return true;
+		}
+	};
+
+	struct ItemEquals {
+			bool operator()(const TableRoster::Item& i1, const TableRoster::Item& i2) const {
+				return i1.jid == i2.jid;
+			}
+	};
+
+
+	struct ItemNeedsUpdate {
+			bool operator()(const TableRoster::Item& i1, const TableRoster::Item& i2) const {
+				return i1.description != i2.description || i1.name != i2.name;
+			}
+	};
+
+	struct CreateIndexForSection {
+			CreateIndexForSection(size_t section) : section(section) {
+			}
+
+			TableRoster::Index operator()(size_t row) const {
+				return TableRoster::Index(section, row);
+			}
+
+			size_t section;
+	};
+}
 
 using namespace Swift;
 
-TableRoster::TableRoster(Roster* model) : model(model) {
+TableRoster::TableRoster(Roster* model, TimerFactory* timerFactory, int updateDelay) : model(model) {
+	updateTimer = timerFactory->createTimer(updateDelay);
+	model->onChildrenChanged.connect(boost::bind(&TableRoster::scheduleUpdate, this));
+	model->onGroupAdded.connect(boost::bind(&TableRoster::scheduleUpdate, this));
+	model->onDataChanged.connect(boost::bind(&TableRoster::scheduleUpdate, this));
+}
+
+TableRoster::~TableRoster() {
+	model->onDataChanged.disconnect(boost::bind(&TableRoster::scheduleUpdate, this));
+	model->onGroupAdded.disconnect(boost::bind(&TableRoster::scheduleUpdate, this));
+	model->onChildrenChanged.disconnect(boost::bind(&TableRoster::scheduleUpdate, this));
+	updateTimer->stop();
 }
 			
 size_t TableRoster::getNumberOfSections() const {
-	return model ? model->getRoot()->getDisplayedChildren().size() : 0;
+	return sections.size();
 }
 
-size_t TableRoster::getNumberOfRowsInSection(size_t section) const {
-	return boost::polymorphic_downcast<Swift::GroupRosterItem*>(model->getRoot()->getDisplayedChildren()[section])->getDisplayedChildren().size();
+const std::string& TableRoster::getSectionTitle(size_t section) {
+	return sections[section].name;
 }
 
-const std::string& TableRoster::getSectionTitle(size_t section) {
-	return model->getRoot()->getDisplayedChildren()[section]->getDisplayName();
+size_t TableRoster::getNumberOfRowsInSection(size_t section) const {
+	return sections[section].items.size();
 }
 
 TableRoster::Item TableRoster::getItem(const Index& index) const {
-	Item item;
-	item.name = boost::polymorphic_downcast<Swift::GroupRosterItem*>(model->getRoot()->getDisplayedChildren().at(index.section))->getDisplayedChildren().at(index.row)->getDisplayName();
-	item.description = "My Status";
-	return item;
+	return sections[index.section].items[index.row];
+}
+			
+void TableRoster::handleUpdateTimerTick() {
+	updateTimer->stop();
+	updatePending = false;
+
+	// Get a model for the new roster
+	std::vector<Section> newSections;
+	foreach(RosterItem* item, model->getRoot()->getDisplayedChildren()) {
+		if (GroupRosterItem* groupItem = boost::polymorphic_downcast<GroupRosterItem*>(item)) {
+			Section section(groupItem->getDisplayName());
+			foreach(RosterItem* groupChildItem, groupItem->getDisplayedChildren()) {
+				if (ContactRosterItem* contact = boost::polymorphic_downcast<ContactRosterItem*>(groupChildItem)) {
+					section.items.push_back(Item(contact->getDisplayName(), contact->getStatusText(), contact->getDisplayJID()));
+				}
+			}
+			newSections.push_back(section);
+		}
+	}
+
+	// Do a diff with the previous roster
+	Update update;
+	std::vector<size_t> sectionUpdates;
+	std::vector<size_t> sectionPostUpdates;
+	computeIndexDiff<Section,SectionNameEquals,True<Section> >(sections, newSections, sectionUpdates, sectionPostUpdates, update.deletedSections, update.insertedSections);
+	assert(sectionUpdates.size() == sectionPostUpdates.size());
+	for (size_t i = 0; i < sectionUpdates.size(); ++i) {
+		assert(sectionUpdates[i] < sections.size());
+		assert(sectionPostUpdates[i] < newSections.size());
+		std::vector<size_t> itemUpdates;
+		std::vector<size_t> itemPostUpdates;
+		std::vector<size_t> itemRemoves;
+		std::vector<size_t> itemInserts;
+		computeIndexDiff<Item, ItemEquals, ItemNeedsUpdate >(sections[sectionUpdates[i]].items, newSections[sectionPostUpdates[i]].items, itemUpdates, itemPostUpdates, itemRemoves, itemInserts);
+		update.insertedRows.resize(itemInserts.size());
+		std::transform(itemInserts.begin(), itemInserts.end(), update.insertedRows.begin(), CreateIndexForSection(sectionPostUpdates[i]));
+		update.deletedRows.resize(itemRemoves.size());
+		std::transform(itemRemoves.begin(), itemRemoves.end(), update.deletedRows.begin(), CreateIndexForSection(sectionPostUpdates[i]));
+		update.updatedRows.resize(itemUpdates.size());
+		std::transform(itemUpdates.begin(), itemUpdates.end(), update.updatedRows.begin(), CreateIndexForSection(sectionPostUpdates[i]));
+	}
+	
+	// Switch the old model with the new
+	sections.swap(newSections);
+
+	// Emit the update
+	onUpdate(update);
+}
+
+void TableRoster::scheduleUpdate() {
+	if (!updatePending) {
+		updatePending = true;
+		updateTimer->start();
+	}
 }
diff --git a/Swift/Controllers/Roster/TableRoster.h b/Swift/Controllers/Roster/TableRoster.h
index 7d92995..7360d20 100644
--- a/Swift/Controllers/Roster/TableRoster.h
+++ b/Swift/Controllers/Roster/TableRoster.h
@@ -14,22 +14,40 @@
 
 namespace Swift {
 	class Roster;
+	class TimerFactory;
+	class Timer;
 
 	class TableRoster {
 		public:
 			struct Item {
+				Item(const std::string& name, const std::string& description, const JID& jid) : name(name), description(description), jid(jid) {
+				}
 				std::string name;
 				std::string description;
 				JID jid;
 			};
+
 			struct Index {
-				Index(size_t section, size_t row) : section(section), row(row) { 
+				Index(size_t section = 0, size_t row = 0) : section(section), row(row) {
 				}
 				size_t section;
 				size_t row;
+
+				bool operator==(const Index& o) const {
+					return o.section == section && o.row == row;
+				}
 			};
 
-			TableRoster(Roster* model);
+			struct Update {
+				std::vector<Index> updatedRows;
+				std::vector<Index> insertedRows;
+				std::vector<Index> deletedRows;
+				std::vector<size_t> insertedSections;
+				std::vector<size_t> deletedSections;
+			};
+
+			TableRoster(Roster* model, TimerFactory* timerFactory, int updateDelay);
+			~TableRoster();
 			
 			size_t getNumberOfSections() const;
 			size_t getNumberOfRowsInSection(size_t section) const;
@@ -38,14 +56,25 @@ namespace Swift {
 
 			Item getItem(const Index&) const;
 
-			boost::signal<void ()> onBeginUpdates;
-			boost::signal<void (const std::vector<Index>&)> onRowsInserted;
-			boost::signal<void (const std::vector<Index>&)> onRowsDeleted;
-			boost::signal<void (const std::vector<size_t>&)> onSectionsInserted;
-			boost::signal<void (const std::vector<size_t>&)> onSectionsDeleted;
-			boost::signal<void ()> onEndUpdates;
+			boost::signal<void (const Update&)> onUpdate;
 
 		private:
+			void handleUpdateTimerTick();
+			void scheduleUpdate();
+
+		private:
+			friend class SectionNameEquals;
+			struct Section {
+				Section(const std::string& name) : name(name) {
+				}
+
+				std::string name;
+				std::vector<Item> items;
+			};
+
 			Roster* model;
+			std::vector<Section> sections;
+			bool updatePending;
+			boost::shared_ptr<Timer> updateTimer;
 	};
 }
diff --git a/Swift/Controllers/Roster/UnitTest/LeastCommonSubsequenceTest.cpp b/Swift/Controllers/Roster/UnitTest/LeastCommonSubsequenceTest.cpp
new file mode 100644
index 0000000..97b5406
--- /dev/null
+++ b/Swift/Controllers/Roster/UnitTest/LeastCommonSubsequenceTest.cpp
@@ -0,0 +1,290 @@
+/*
+ * 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_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_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/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);
+