fixed test codes
test/test_edit.cc (diff) test/test_filter.cc (diff)
src/edit.java (diff) src/particle.cc (diff) src/edit.cc (diff) src/filter.cc (diff) src/particles.cc (diff)
src/edit.h (diff)| @@ -1,8 +1,8 @@ | ||
| 1 | 1 | #include <cppcutter.h> |
| 2 | 2 | #include <particle.h> |
| 3 | 3 | #include <iostream> |
| 4 | +#include <edit.cc> | |
| 4 | 5 | using namespace std; |
| 5 | -extern int edit(const string &,const string &); | |
| 6 | 6 | namespace test_edit |
| 7 | 7 | { |
| 8 | 8 |
| @@ -15,9 +15,9 @@ | ||
| 15 | 15 | |
| 16 | 16 | void test_edit(void) |
| 17 | 17 | { |
| 18 | - cut_assert_equal_int(3,edit("kitten","sitting")); | |
| 19 | - cut_assert_equal_int(1,edit("あかまきがみ","あおまきがみ")); | |
| 20 | - cut_assert_equal_int(3,edit("あかMAXがみ","あおMINがみ")); | |
| 21 | - cut_assert_equal_int(4,edit("情報工学","画像情報")); | |
| 18 | + cut_assert_equal_int(3,LevenshteinDistance::edit("kitten","sitting")); | |
| 19 | + cut_assert_equal_int(1,LevenshteinDistance::edit("あかまきがみ","あおまきがみ")); | |
| 20 | + cut_assert_equal_int(3,LevenshteinDistance::edit("あかMAXがみ","あおMINがみ")); | |
| 21 | + cut_assert_equal_int(4,LevenshteinDistance::edit("情報工学","画像情報")); | |
| 22 | 22 | } |
| 23 | 23 | } |
| @@ -69,4 +69,4 @@ | ||
| 69 | 69 | { |
| 70 | 70 | test_filter::test_construction(); |
| 71 | 71 | return(0); |
| 72 | -} | |
| \ No newline at end of file | ||
| 72 | +} |
| @@ -4,16 +4,17 @@ | ||
| 4 | 4 | |
| 5 | 5 | class LevenshteinDistance |
| 6 | 6 | { |
| 7 | - private int isutf8(String args) throws UnsupportedEncodingException | |
| 7 | + static int isutf8(String args) throws UnsupportedEncodingException | |
| 8 | 8 | { |
| 9 | 9 | int ret = -1; |
| 10 | 10 | byte[] c = args.getBytes("UTF-8"); |
| 11 | 11 | if((c[0]&0x80) == 0x00) ret = 1; |
| 12 | 12 | else if((c[0]&0xe0) == 0xc0 && (c[1]&0xc0) == 0x80) ret = 2; |
| 13 | - else if((c[0]&0xf0) == 0xe0 && (c[1]&0xc0) == 0x80 && (c[2]&0xc0) == 0x80 ) ret = 3; | |
| 13 | + else if((c[0]&0xf0) == 0xe0 && (c[1]&0xc0) == 0x80 | |
| 14 | + && (c[2]&0xc0) == 0x80 ) ret = 3; | |
| 14 | 15 | return(ret); |
| 15 | 16 | } |
| 16 | - Boolean equal(String s1, String s2) throws UnsupportedEncodingException | |
| 17 | + static Boolean equal(String s1, String s2) throws UnsupportedEncodingException | |
| 17 | 18 | { |
| 18 | 19 | Boolean ret = false; |
| 19 | 20 | if(isutf8(s1)==isutf8(s2)) |
| @@ -29,7 +30,7 @@ | ||
| 29 | 30 | } |
| 30 | 31 | return(ret); |
| 31 | 32 | } |
| 32 | - int edit(String px, String py) throws UnsupportedEncodingException | |
| 33 | + static int edit(String px, String py) throws UnsupportedEncodingException | |
| 33 | 34 | { |
| 34 | 35 | Vector<Vector> row = new Vector<Vector>(); |
| 35 | 36 | int len1=0,len2=0; |
| @@ -53,7 +54,8 @@ | ||
| 53 | 54 | for(j=1;j<=len2;++j) |
| 54 | 55 | { |
| 55 | 56 | row.get(i).set(j,Math.min(Math.min( |
| 56 | - (Integer)(row.get(i-1).get(j-1)) + (equal(px.substring(i-1),py.substring(j-1))?0:1) , // replace | |
| 57 | + (Integer)(row.get(i-1).get(j-1)) | |
| 58 | + + (equal(px.substring(i-1),py.substring(j-1))?0:1) , // replace | |
| 57 | 59 | (Integer)(row.get(i).get(j-1)) + 1), // delete |
| 58 | 60 | (Integer)(row.get(i-1).get(j)) + 1 )); // insert |
| 59 | 61 | } |
| @@ -65,7 +67,6 @@ | ||
| 65 | 67 | |
| 66 | 68 | public static void main(String[] args) throws UnsupportedEncodingException |
| 67 | 69 | { |
| 68 | - LevenshteinDistance ld = new LevenshteinDistance() ; | |
| 69 | - System.out.println(ld.edit("あい","あうう")); | |
| 70 | + System.out.println(LevenshteinDistance.edit("あい","あいう")); | |
| 70 | 71 | } |
| 71 | 72 | } |
| \ No newline at end of file |
| @@ -63,7 +63,7 @@ | ||
| 63 | 63 | s<<"("; |
| 64 | 64 | // for(vector<C>::iterator i=p.begin(); |
| 65 | 65 | // i!=p.end();++i) |
| 66 | - for(int i=0;i<p.size();++i) | |
| 66 | + for(unsigned int i=0;i<p.size();++i) | |
| 67 | 67 | { |
| 68 | 68 | // if(i!=p.begin()) s<<","; |
| 69 | 69 | if(i!=0) s<<","; |
| @@ -1,75 +1,72 @@ | ||
| 1 | 1 | #include <iostream> |
| 2 | -#include <algorithm> | |
| 3 | 2 | #include <vector> |
| 4 | 3 | using namespace std; |
| 5 | -int isutf8(const string &c) | |
| 4 | +class LevenshteinDistance | |
| 6 | 5 | { |
| 7 | - int ret; | |
| 8 | - if((c[0]&0x80) == 0x00) ret = 1; | |
| 9 | - else if((c[0]&0xe0) == 0xc0 && (c[1]&0xc0) == 0x80) ret = 2; | |
| 10 | - else if((c[0]&0xf0) == 0xe0 && (c[1]&0xc0) == 0x80 && (c[2]&0xc0) == 0x80 ) ret = 3; | |
| 11 | - return(ret); | |
| 12 | -} | |
| 13 | -bool equal(const string &s1, const string &s2) | |
| 14 | -{ | |
| 15 | - bool ret = false; | |
| 16 | - if(isutf8(s1)==isutf8(s2)) | |
| 6 | +public: | |
| 7 | + static int isutf8(const string &c) | |
| 17 | 8 | { |
| 18 | - int f=0; | |
| 19 | - for(int i=0;i<isutf8(s1);++i) | |
| 9 | + int ret; | |
| 10 | + if((c[0]&0x80) == 0x00) ret = 1; | |
| 11 | + else if((c[0]&0xe0) == 0xc0 && (c[1]&0xc0) == 0x80) ret = 2; | |
| 12 | + else if((c[0]&0xf0) == 0xe0 && (c[1]&0xc0) == 0x80 | |
| 13 | + && (c[2]&0xc0) == 0x80 ) ret = 3; | |
| 14 | + return(ret); | |
| 15 | + } | |
| 16 | + static bool equal(const string &s1, const string &s2) | |
| 17 | + { | |
| 18 | + bool ret = false; | |
| 19 | + if(isutf8(s1)==isutf8(s2)) | |
| 20 | 20 | { |
| 21 | - if(s1[i]==s2[i]) ++f; | |
| 21 | + int f=0; | |
| 22 | + for(int i=0;i<isutf8(s1);++i) | |
| 23 | + { | |
| 24 | + if(s1[i]==s2[i]) ++f; | |
| 25 | + } | |
| 26 | + if(f==isutf8(s1)) ret = true; | |
| 22 | 27 | } |
| 23 | - if(f==isutf8(s1)) ret = true; | |
| 28 | + return(ret); | |
| 24 | 29 | } |
| 25 | - return(ret); | |
| 26 | -} | |
| 27 | -int edit(const string &px, const string &py) | |
| 28 | -{ | |
| 29 | - vector<vector<int> > row; | |
| 30 | - int len1=0,len2=0; | |
| 31 | - int i,j; | |
| 32 | - int result; | |
| 33 | - // len1=(int)px.size(); len2=(int)py.size(); | |
| 34 | - for(i=0;i<px.size();) | |
| 30 | + static int edit(const string &px, const string &py) | |
| 35 | 31 | { |
| 36 | - i += isutf8(&px[i]); | |
| 37 | - ++len1; | |
| 38 | - } | |
| 39 | - for(i=0;i<py.size();) | |
| 40 | - { | |
| 41 | - i += isutf8(&py[i]); | |
| 42 | - ++len2; | |
| 43 | - } | |
| 44 | - row.resize(len1+1); | |
| 45 | - for(vector<vector<int> >::iterator i=row.begin(); i!=row.end(); ++i) | |
| 46 | - { | |
| 47 | - i->resize(len2+1); | |
| 48 | - } | |
| 32 | + int len1=0,len2=0; | |
| 33 | + int i,j; | |
| 34 | + int result; | |
| 35 | + for(unsigned i=0;i<px.size();) | |
| 36 | + { | |
| 37 | + i += isutf8(&px[i]); | |
| 38 | + ++len1; | |
| 39 | + } | |
| 40 | + for(unsigned i=0;i<py.size();) | |
| 41 | + { | |
| 42 | + i += isutf8(&py[i]); | |
| 43 | + ++len2; | |
| 44 | + } | |
| 45 | + vector<vector<int> > row(len1+1, vector<int>(len2+1)); | |
| 49 | 46 | |
| 50 | - for(i=0;i<len1+1;i++) row[i][0]=i; | |
| 51 | - for(i=0;i<len2+1;i++) row[0][i]=i; | |
| 52 | - int k=0,l=0; | |
| 53 | - for(i=1;i<=len1;++i) | |
| 54 | - { | |
| 55 | - l = 0; | |
| 56 | - for(j=1;j<=len2;++j) | |
| 47 | + for(i=0;i<len1+1;i++) row[i][0]=i; | |
| 48 | + for(i=0;i<len2+1;i++) row[0][i]=i; | |
| 49 | + int k=0,l=0; | |
| 50 | + for(i=1;i<=len1;++i) | |
| 57 | 51 | { |
| 58 | - row[i][j] = min(min( | |
| 59 | - row[i-1][j-1] + (equal(&px[k],&py[l])?0:1) , // replace | |
| 60 | - row[i][j-1] + 1), // delete | |
| 61 | - row[i-1][j] + 1 ); // insert | |
| 62 | - l += isutf8(&py[l]); | |
| 52 | + l = 0; | |
| 53 | + for(j=1;j<=len2;++j) | |
| 54 | + { | |
| 55 | + row[i][j] = min(min( | |
| 56 | + row[i-1][j-1] + (equal(&px[k],&py[l])?0:1) , // replace | |
| 57 | + row[i][j-1] + 1), // delete | |
| 58 | + row[i-1][j] + 1 ); // insert | |
| 59 | + l += isutf8(&py[l]); | |
| 60 | + } | |
| 61 | + k += isutf8(&px[k]); | |
| 63 | 62 | } |
| 64 | - k += isutf8(&px[k]); | |
| 63 | + result=row[i-1][j-1]; | |
| 64 | + | |
| 65 | + return result; | |
| 65 | 66 | } |
| 66 | - result=row[i-1][j-1]; | |
| 67 | - | |
| 68 | - return result; | |
| 69 | -} | |
| 67 | +}; | |
| 70 | 68 | int main() |
| 71 | 69 | { |
| 72 | -// cout<<edit("kitten","sitting")<<endl; | |
| 73 | - cout<<edit("あほb","bあ")<<endl; | |
| 70 | + cout<<LevenshteinDistance::edit("あい","あいう")<<endl; | |
| 74 | 71 | return(0); |
| 75 | -} | |
| \ No newline at end of file | ||
| 72 | +} |
| @@ -78,4 +78,4 @@ | ||
| 78 | 78 | { |
| 79 | 79 | y = p; |
| 80 | 80 | return(true); |
| 81 | -} | |
| \ No newline at end of file | ||
| 81 | +} |
| @@ -22,7 +22,7 @@ | ||
| 22 | 22 | typedef Particle<C> ParticleC; |
| 23 | 23 | // for(vector<ParticleC>::iterator i= p.begin(); |
| 24 | 24 | // i!=p.end();++i) |
| 25 | - for(int i=0;i<p.size();++i) | |
| 25 | + for(unsigned int i=0;i<p.size();++i) | |
| 26 | 26 | { |
| 27 | 27 | // i->resize(dimension); |
| 28 | 28 | p[i].resize(dimension); |
| @@ -49,7 +49,7 @@ | ||
| 49 | 49 | { |
| 50 | 50 | // for(vector<Particle<C> >::iterator i=p.begin(); |
| 51 | 51 | // i!=p.end();++i) |
| 52 | - for(int i=0;i<p.size();++i) | |
| 52 | + for(unsigned int i=0;i<p.size();++i) | |
| 53 | 53 | { |
| 54 | 54 | // i->dump(); |
| 55 | 55 | p[i].dump(); |
| @@ -58,4 +58,4 @@ | ||
| 58 | 58 | } |
| 59 | 59 | |
| 60 | 60 | template class Particles<int>; |
| 61 | -template class Particles<double>; | |
| \ No newline at end of file | ||
| 61 | +template class Particles<double>; |
Fork