tests/levenshtein.cpp

   1 #include <cppu.h>
   2 #include <vector>
   3 #include <iostream>
   4 #include "text.h"
   5 #include "levenshtein.h"
   6 using namespace std;
   7 void printTable(vector<vector<int> > &table)
   8 {
   9     int rows = table.size();
  10     int cols = table[0].size();
  11
  12     for (int i=0; i < rows; i++){
  13         for (int j=0; j < cols; j++){
  14             cout << table[i][j] << " ";
  15         }
  16         cout << endl;
  17     }
  18 }
  19 void printTrace(list<pair<int, int> > &trace)
  20 {
  21     list<pair<int, int> >::const_iterator it = trace.begin();
  22     list<pair<int, int> >::const_iterator it_end = trace.end();
  23     for (; it != it_end; it++){
  24         cout << "(" << (*it).first << ", " << (*it).second << ") ";
  25     }
  26     cout << endl;
  27 }
  28
  29 void printRanges(vector<range_t> &ranges)
  30 {
  31     int len = ranges.size();
  32     cout << "INSERTION: " << range_t::INSERTION << endl;
  33     cout << "SUBSTITUTION: " << range_t::SUBSTITUTION << endl;
  34     for (int i=0; i < len; i++){
  35         cout << "type: " << ranges[i].type << ", "
  36              << "original: " << ranges[i].original << ", "
  37              << "from: " << ranges[i].from << ", "
  38              << "length: " << ranges[i].length << endl;
  39     }
  40 }
  41
  42 TEST_CASE(TestCaseLevenshtein);
  43
  44 vector<vector<int> > table;
  45 list<pair<int, int> > trace;
  46 vector<range_t> ranges;
  47 QString original;
  48 QString modified;
  49
  50 void setUp()
  51 {
  52     original = "kitten";
  53     modified = "sitting";
  54
  55     table.resize(8);
  56     for (int i=0; i < 8; i++){
  57         table[i].resize(7);
  58         table[i][0] = i;
  59     }
  60     for (int i=0; i < 7; i++)
  61         table[0][i] = i;
  62
  63     table[1][1] = 1; table[1][2] = 2; table[1][3] = 3;
  64     table[1][4] = 4; table[1][5] = 5; table[1][6] = 6;
  65
  66     table[2][1] = 2; table[2][2] = 1; table[2][3] = 2;
  67     table[2][4] = 3; table[2][5] = 4; table[2][6] = 5;
  68
  69     table[3][1] = 3; table[3][2] = 2; table[3][3] = 1;
  70     table[3][4] = 2; table[3][5] = 3; table[3][6] = 4;
  71
  72     table[4][1] = 4; table[4][2] = 3; table[4][3] = 2;
  73     table[4][4] = 1; table[4][5] = 2; table[4][6] = 3;
  74
  75     table[5][1] = 5; table[5][2] = 4; table[5][3] = 3;
  76     table[5][4] = 2; table[5][5] = 2; table[5][6] = 3;
  77
  78     table[6][1] = 6; table[6][2] = 5; table[6][3] = 4;
  79     table[6][4] = 3; table[6][5] = 3; table[6][6] = 2;
  80
  81     table[7][1] = 7; table[7][2] = 6; table[7][3] = 5;
  82     table[7][4] = 4; table[7][5] = 4; table[7][6] = 3;
  83
  84     trace.push_front(pair<int, int>(7, 6));
  85     trace.push_front(pair<int, int>(6, 6));
  86     trace.push_front(pair<int, int>(5, 5));
  87     trace.push_front(pair<int, int>(4, 4));
  88     trace.push_front(pair<int, int>(3, 3));
  89     trace.push_front(pair<int, int>(2, 2));
  90     trace.push_front(pair<int, int>(1, 1));
  91
  92     range_t range;
  93
  94     range.type = range_t::SUBSTITUTION;
  95     range.original = true;
  96     range.from = 0;
  97     range.length = 1;
  98     ranges.push_back(range);
  99
 100     range.original = false;
 101     ranges.push_back(range);
 102
 103     range.original = true;
 104     range.from = 4;
 105     range.length = 1;
 106     ranges.push_back(range);
 107
 108     range.original = false;
 109     ranges.push_back(range);
 110
 111     range.type = range_t::INSERTION;
 112     range.original = false;
 113     range.from = 6;
 114     range.length = 1;
 115     ranges.push_back(range);
 116 }
 117
 118 void testTable()
 119 {
 120     LevenshteinTable l_table(original, modified);
 121     vector<vector<int> > table2;
 122     list<pair<int, int> > trace2;
 123     l_table.dumpTable(table2);
 124     l_table.dumpTrace(trace2);
 125
 126     assertEqualsM(table, table2, "Incorrect Levenshtein table.");
 127     assertEqualsM(trace, trace2, "Incorrect trace back.");
 128 }
 129
 130 void testRanges()
 131 {
 132     LevenshteinTable l_table(original, modified);
 133     vector<range_t> ranges2;
 134     l_table.fillRanges(ranges2);
 135
 136     //printRanges(ranges);
 137     //printRanges(ranges2);
 138
 139     assertEqualsM(ranges.size(), ranges2.size(), "Incorrect size of ranges.");
 140     int len = ranges.size();
 141     for (int i=0; i < len; i++){
 142         assertTrue(ranges2.end() != std::find(ranges2.begin(), ranges2.end(), ranges[i]));
 143     }
 144 }
 145
 146 TESTS{
 147     REG_TEST(testTable);
 148     REG_TEST(testRanges);
 149 }
 150 TEST_CASE_END;