DGtal  1.5.beta
testOrderedAlphabet.cpp
Go to the documentation of this file.
1 
31 #include <iostream>
32 #include <sstream>
33 #include "DGtal/base/Common.h"
34 #include "DGtal/base/OrderedAlphabet.h"
36 
37 using namespace std;
38 using namespace DGtal;
39 
41 // Functions for testing class OrderedAlphabet.
43 
51 bool testFLF( const OrderedAlphabet & alphabet,
52  const string & output,
53  const string & input)
54 {
55  string w1 = input;
56  string a1 = output;
57  stringstream s1;
58  unsigned int len;
59  unsigned int nb;
60  unsigned int s = 0;
61  unsigned int e = (unsigned int)w1.size();
62  do
63  {
64  alphabet.firstLyndonFactor( len, nb, w1, s, e );
65  s1 << "(" << w1.substr( s, len ) << ")^" << nb;
66  s += len*nb;
67  }
68  while ( s < e );
69 
70  trace.beginBlock ( "Test Lyndon factorization" );
71  trace.info() << " input = " << input << endl;
72  trace.info() << "expected = " << output << endl;
73  trace.info() << "computed = " << s1.str() << endl;
74  trace.endBlock();
75 
76  return s1.str() == a1;
77 }
78 
79 
88 bool testDuvalPP( const OrderedAlphabet & alphabet,
89  const string & output,
90  const string & input)
91 {
94  bool christoffel = alphabet.duvalPP( len, nb, input, 0, (DGtal::OrderedAlphabet::index_t)input.size() );
95  stringstream s1;
96  if ( christoffel )
97  s1 << "C(" << input.substr( 0, len ) << ")^" << nb;
98  else s1 << "NC(" << len << ")";
99 
100  trace.beginBlock ( "Test Duval++" );
101  trace.info() << " input = " << input << endl;
102  trace.info() << "expected = " << output << endl;
103  trace.info() << "computed = " << s1.str() << endl;
104  trace.endBlock();
105 
106  return s1.str() == output;
107 }
108 
109 
119 bool testDuvalPPMod( const OrderedAlphabet & alphabet,
120  const string & output,
121  const string & input,
123 {
126  bool christoffel = alphabet.duvalPPMod( len, nb, input, s, s );
127  stringstream s1;
128  if ( christoffel )
129  {
130  s1 << "C(";
131  for ( unsigned int i = 0; i < len; ++i )
132  {
133  s1 << input[ s ];
134  s = s + 1 % input.size();
135  }
136  s1 << ")^" << nb;
137  }
138  else s1 << "NC(" << len << ")";
139 
140  trace.beginBlock ( "Test Duval++ modulo" );
141  trace.info() << " input = " << input << endl;
142  trace.info() << "expected = " << output << endl;
143  trace.info() << "computed = " << s1.str() << endl;
144  trace.endBlock();
145 
146  return s1.str() == output;
147 }
148 
149 
155 {
156  unsigned int nb_ok = 0;
157  unsigned int nb_ko = 0;
158  OrderedAlphabet A( '0', 4 );
159  string w1 = "01101010100101001010001";
160  string a1= "(011)^1(01)^3(00101)^2(0001)^1";
161  if ( testFLF( A, a1, w1 ) ) nb_ok++;
162  else nb_ko++;
163  w1 = "01232112232232103220123210120";
164  a1 = "(0123211223223210322)^1(012321)^1(012)^1(0)^1";
165  if ( testFLF( A, a1, w1 ) ) nb_ok++;
166  else nb_ko++;
167  w1 = "1112111211211121121112111211211121121111";
168  a1 = "C(111211121121112112)^2";
169  if ( testDuvalPP( A, a1, w1 ) ) nb_ok++;
170  else nb_ko++;
171  w1 = "1112111211211121121121111211211121121111";
172  a1 = "NC(20)";
173  if ( testDuvalPP( A, a1, w1 ) ) nb_ok++;
174  else nb_ko++;
175  w1 = "2111211211121121111111211121121112112111";
176  a1 = "C(111211121121112112)^2";
177  if ( testDuvalPPMod( A, a1, w1, 19 ) ) nb_ok++;
178  else nb_ko++;
179 
180  trace.info() << "Tests passed: " << nb_ok << "/"
181  << ( nb_ok + nb_ko ) << endl;
182 
183  return !nb_ko;
184 }
185 
186 
188 int main( int argc, char** argv )
189 {
190  trace.beginBlock ( "Testing class OrderedAlphabet" );
191  trace.info() << "Args:";
192  for ( int i = 0; i < argc; ++i )
193  trace.info() << " " << argv[ i ];
194  trace.info() << endl;
195 
196  bool res = testOrderedAlphabet(); // && ... other tests
197  trace.emphase() << ( res ? "Passed." : "Error." ) << endl;
198  trace.endBlock();
199 
200  return res ? 0 : 1;
201 }
Aim: Describes an alphabet over an interval of (ascii) letters, where the lexicographic order can be ...
bool duvalPP(size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const
void firstLyndonFactor(size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const
bool duvalPPMod(size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const
void beginBlock(const std::string &keyword="")
std::ostream & emphase()
std::ostream & info()
double endBlock()
DGtal is the top-level namespace which contains all DGtal functions and types.
Trace trace
Definition: Common.h:153
bool testOrderedAlphabet()
bool testFLF(const OrderedAlphabet &alphabet, const string &output, const string &input)
int main(int argc, char **argv)
bool testDuvalPP(const OrderedAlphabet &alphabet, const string &output, const string &input)
bool testDuvalPPMod(const OrderedAlphabet &alphabet, const string &output, const string &input, OrderedAlphabet::index_t s)