+ bool operator()(char c, char c2) const {

+ CPPUNIT_ASSERT_EQUAL(c, c2);

+ return c == 'b' || c == 'c';

+ }

+ bool operator()(char c, char c2) const {

+ CPPUNIT_ASSERT_EQUAL(c, c2);

+ return c == 'x' || c == 'y';

+ }

+ bool operator()(const std::string& s, const std::string& s2) const {

+ CPPUNIT_ASSERT_EQUAL(s, s2);

+ return s == "Arizona" || s == "New Jersey";

+ }

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

+ }