+/*

+ * 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;

+ }

+ }

+ }

+}

+#include <cassert>

+#include <algorithm>

+#include <Swiften/Base/foreach.h>

+#include <Swiften/Network/TimerFactory.h>

+#include <Swiften/Network/Timer.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;

+ };

+}

+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();

+ return sections.size();

+const std::string& TableRoster::getSectionTitle(size_t section) {

+ return sections[section].name;

+size_t TableRoster::getNumberOfRowsInSection(size_t section) const {

+ return sections[section].items.size();

+ 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();

+ }

+ class TimerFactory;

+ class Timer;

+ Item(const std::string& name, const std::string& description, const JID& jid) : name(name), description(description), jid(jid) {

+ }

+

+ Index(size_t section = 0, size_t row = 0) : section(section), row(row) {

+

+ bool operator==(const Index& o) const {

+ return o.section == section && o.row == row;

+ }

+ 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();

+ boost::signal<void (const Update&)> onUpdate;

+ void handleUpdateTimerTick();

+ void scheduleUpdate();

+

+ private:

+ friend class SectionNameEquals;

+ struct Section {

+ Section(const std::string& name) : name(name) {

+ }

+

+ std::string name;

+ std::vector<Item> items;

+ };

+

+ std::vector<Section> sections;

+ bool updatePending;

+ boost::shared_ptr<Timer> updateTimer;

+/*

+ * 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);

+/*

+ * 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);

+

+ File("Roster/UnitTest/LeastCommonSubsequenceTest.cpp"),

+ File("Roster/UnitTest/TableRosterTest.cpp"),