DGtal  0.9.4beta
testSternBrocot.cpp
1 
30 #include <cstdlib>
32 #include <iostream>
33 #include "DGtal/base/Common.h"
34 #include "DGtal/kernel/CPointPredicate.h"
35 #include "DGtal/arithmetic/CPositiveIrreducibleFraction.h"
36 #include "DGtal/arithmetic/IntegerComputer.h"
37 #include "DGtal/arithmetic/SternBrocot.h"
38 #include "DGtal/arithmetic/Pattern.h"
39 #include "DGtal/arithmetic/StandardDSLQ0.h"
40 #include "DGtal/geometry/curves/ArithmeticalDSSComputer.h"
42 
43 using namespace std;
44 using namespace DGtal;
45 
47 // Functions for testing class SternBrocot.
49 
50 template <typename Quotient>
51 bool
52 equalCFrac( const std::vector<Quotient> & c1, const std::vector<Quotient> & c2 )
53 {
54  unsigned int s = c1.size() < c2.size() ? c1.size() : c2.size();
55  if ( ( s != c1.size() ) && ( c1.back() != NumberTraits<Quotient>::ONE ) )
56  return false;
57  if ( ( s != c2.size() ) && ( c2.back() != NumberTraits<Quotient>::ONE ) )
58  return false;
59  for ( unsigned int i = 0; i < s; ++i )
60  {
61  Quotient q1 = c1[ i ];
62  if ( ( s != c1.size() ) && ( i == s - 1 ) ) q1 += c1.back();
63  Quotient q2 = c2[ i ];
64  if ( ( s != c2.size() ) && ( i == s - 1 ) ) q2 += c2.back();
65  if ( q1 != q2 ) return false;
66  }
67  return true;
68 }
69 
70 template <typename SB>
71 bool testReducedFraction()
72 {
73  typedef typename SB::Integer Integer;
74  typedef typename SB::Quotient Quotient;
75  typedef typename SB::Fraction Fraction;
76  unsigned int nbok = 0;
77  unsigned int nb = 0;
78  Integer p = rand() / 10000;
79  Integer q = rand() / 10000;
80  trace.beginBlock ( "Testing block: reduced fraction." );
82  Integer g = ic.gcd( p, q );
83  p /= g;
84  q /= g;
86  Quotient sp = NumberTraits<Integer>::castToInt64_t( p );
87  Quotient sq = NumberTraits<Integer>::castToInt64_t( q );
88  std::vector<Quotient> cf1;
89  ics.getCFrac( cf1, sp, sq );
90  Fraction f1 = SB::fraction( p, q );
91  std::vector<Quotient> cf1_bis;
92  f1.getCFrac( cf1_bis );
93  bool ok = equalCFrac<Quotient>( cf1, cf1_bis );
94  trace.info() << " - p / q = " << p << " / " << q << std::endl;
95  trace.info() << " - f1 = ";
96  SB::display( trace.info(), f1 );
97  trace.info() << std::endl;
98  ++nb, nbok += ok ? 1 : 0;
99  trace.info() << "(" << nbok << "/" << nb << ") "
100  << " cfrac"
101  << std::endl;
102  unsigned int depth = cf1.size();
103  for ( unsigned int k = 1; k < depth; ++k )
104  {
105  std::vector<Quotient> cf1_red;
106  Fraction fr = f1.reduced( k );
107  fr.getCFrac( cf1_red );
108  cf1.resize( depth - k );
109  ok = equalCFrac<Quotient>( cf1, cf1_red );
110  ++nb, nbok += ok ? 1 : 0;
111  trace.info() << "(" << nbok << "/" << nb << ") "
112  << "reduced(" << k << ")=";
113  SB::display( trace.info(), fr );
114  std::cerr << std::endl;
115  }
116 
117  //trace.info() << "- nbFractions = " << SB::instance().nbFractions << std::endl;
118  trace.endBlock();
119  return nbok == nb;
120 }
121 
122 template <typename SB>
123 bool testInitFraction()
124 {
125  typedef typename SB::Integer Integer;
126  typedef typename SB::Fraction Fraction;
127  unsigned int nbok = 0;
128  unsigned int nb = 0;
129  Integer p = rand() / 10000;
130  Integer q = rand() / 10000;
131  trace.beginBlock ( "Testing block: init fraction." );
133  Integer g = ic.gcd( p, q );
134  p /= g;
135  q /= g;
136  Fraction f1 = SB::fraction( p, q );
137  trace.info() << "p / q = " << p << " / " << q << std::endl;
138  trace.info() << "f1 = ";
139  SB::display( trace.info(), f1 );
140  trace.info() << std::endl;
141  nbok += ( ( p == f1.p() ) && ( q == f1.q() ) ) ? 1 : 0;
142  ++nb;
143  trace.info() << "(" << nbok << "/" << nb << ") "
144  << "( ( p == f1.p() ) && ( q == f1.q() ) )"
145  << std::endl;
146  trace.info() << "- nbFractions = " << SB::instance().nbFractions << std::endl;
147  trace.endBlock();
148 
149  return nbok == nb;
150 }
151 
152 template <typename SB>
153 bool testPattern()
154 {
155  typedef typename SB::Integer Integer;
156  typedef typename SB::Quotient Quotient;
157  typedef typename SB::Fraction Fraction;
158  typedef Pattern<Fraction> MyPattern;
159  typedef typename MyPattern::Vector2I Vector2I;
160  unsigned int nbok = 0;
161  unsigned int nb = 0;
162  Integer p = rand() / 10000;
163  Integer q = rand() / 10000;
164  MyPattern pattern( p*6, q*6 );
165  trace.info() << pattern << endl;
166 
167  // ODD PATTERN
168  trace.beginBlock ( "Testing block: Smallest covering subpatterns of ODD pattern." );
169  MyPattern pat_odd( 5, 12 );
170  trace.info() << "ODD " << pat_odd << " " << pat_odd.rE() << endl;
171  MyPattern sp;
172  Quotient np;
173  Vector2I start;
174 
175  // Left Subpatterns
176  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
177  0, 17 );
178  trace.info() << "sub(0,17) = " << sp << " " << sp.rE() << "^" << np << endl;
179  ++nb, nbok += sp.slope() == SB::fraction( 5, 12 ) ? 1 : 0;
180  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
181  1, 17 );
182  trace.info() << "sub(1,17) = " << sp << " " << sp.rE() << "^" << np << endl;
183  ++nb, nbok += sp.slope() == SB::fraction( 5, 12 ) ? 1 : 0;
184  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
185  7, 17 );
186  trace.info() << "sub(7,17) = " << sp << " " << sp.rE() << "^" << np << endl;
187  ++nb, nbok += sp.slope() == SB::fraction( 3, 7 ) ? 1 : 0;
188  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
189  8, 17 );
190  trace.info() << "sub(8,17) = " << sp << " " << sp.rE() << "^" << np << endl;
191  ++nb, nbok += sp.slope() == SB::fraction( 3, 7 ) ? 1 : 0;
192  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
193  13, 17 );
194  trace.info() << "sub(13,17) = " << sp << " " << sp.rE() << "^" << np << endl;
195  ++nb, nbok += sp.slope() == SB::fraction( 3, 7 ) ? 1 : 0;
196  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
197  14, 17 );
198  trace.info() << "sub(14,17) = " << sp << " " << sp.rE() << "^" << np << endl;
199  ++nb, nbok += sp.slope() == SB::fraction( 1, 2 ) ? 1 : 0;
200  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
201  15, 17 );
202  trace.info() << "sub(15,17) = " << sp << " " << sp.rE() << "^" << np << endl;
203  ++nb, nbok += sp.slope() == SB::fraction( 1, 2 ) ? 1 : 0;
204 
205  trace.info() << "(" << nbok << "/" << nb << ") covering left Subpatterns." << endl;
206 
207  // Right Subpatterns
208  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
209  0, 16 );
210  trace.info() << "sub(0,16) = " << sp << " " << sp.rE() << "^" << np << endl;
211  ++nb, nbok += sp.slope() == SB::fraction( 5, 12 ) ? 1 : 0;
212  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
213  0, 15 );
214  trace.info() << "sub(0,15) = " << sp << " " << sp.rE() << "^" << np << endl;
215  ++nb, nbok += sp.slope() == SB::fraction( 5, 12 ) ? 1 : 0;
216  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
217  0, 14 );
218  trace.info() << "sub(0,14) = " << sp << " " << sp.rE() << "^" << np << endl;
219  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 2 ? 1 : 0;
220  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
221  0, 8 );
222  trace.info() << "sub(0,8) = " << sp << " " << sp.rE() << "^" << np << endl;
223  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 2 ? 1 : 0;
224  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
225  0, 7 );
226  trace.info() << "sub(0,7) = " << sp << " " << sp.rE() << "^" << np << endl;
227  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
228  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
229  0, 1 );
230  trace.info() << "sub(0,1) = " << sp << " " << sp.rE() << "^" << np << endl;
231  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
232 
233  trace.info() << "(" << nbok << "/" << nb << ") covering right Subpatterns." << endl;
234 
235  // Middle Subpatterns
236  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
237  1, 16 );
238  trace.info() << "sub(1,16) = " << sp << " " << sp.rE() << "^" << np << endl;
239  ++nb, nbok += sp.slope() == SB::fraction( 5, 12 ) ? 1 : 0;
240  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
241  2, 14 );
242  trace.info() << "sub(2,14) = " << sp << " " << sp.rE() << "^" << np << endl;
243  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 2 ? 1 : 0;
244  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
245  7, 15 );
246  trace.info() << "sub(7,15) = " << sp << " " << sp.rE() << "^" << np << endl;
247  ++nb, nbok += sp.slope() == SB::fraction( 3, 7 ) && np == 1 ? 1 : 0;
248  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
249  7, 14 );
250  trace.info() << "sub(7,14) = " << sp << " " << sp.rE() << "^" << np << endl;
251  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
252  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
253  3, 6 );
254  trace.info() << "sub(3,6) = " << sp << " " << sp.rE() << "^" << np << endl;
255  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
256  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
257  6, 8 );
258  trace.info() << "sub(6,8) = " << sp << " " << sp.rE() << "^" << np << endl;
259  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 2 ? 1 : 0;
260  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
261  8, 12 );
262  trace.info() << "sub(8,12) = " << sp << " " << sp.rE() << "^" << np << endl;
263  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
264  pat_odd.getSmallestCoveringSubpattern( sp, np, start,
265  15, 16 );
266  trace.info() << "sub(15,16) = " << sp << " " << sp.rE() << "^" << np << endl;
267  ++nb, nbok += sp.slope() == SB::fraction( 1, 2 ) && np == 1 ? 1 : 0;
268 
269  trace.info() << "(" << nbok << "/" << nb << ") covering middle Subpatterns." << endl;
270  trace.endBlock();
271 
272  // EVEN PATTERN
273  trace.beginBlock ( "Testing block: Smallest covering subpatterns of EVEN pattern." );
274  MyPattern pat_even( 12, 17 );
275  trace.info() << "EVEN " << pat_even << " " << pat_even.rE() << endl;
276 
277  // Left Subpatterns
278  pat_even.getSmallestCoveringSubpattern( sp, np, start,
279  0, 29 );
280  trace.info() << "sub(0,29) = " << sp << " " << sp.rE() << "^" << np << endl;
281  ++nb, nbok += sp.slope() == SB::fraction( 12, 17 ) ? 1 : 0;
282  pat_even.getSmallestCoveringSubpattern( sp, np, start,
283  0, 25 );
284  trace.info() << "sub(0,25) = " << sp << " " << sp.rE() << "^" << np << endl;
285  ++nb, nbok += sp.slope() == SB::fraction( 12, 17 ) ? 1 : 0;
286  pat_even.getSmallestCoveringSubpattern( sp, np, start,
287  0, 17 );
288  trace.info() << "sub(0,17) = " << sp << " " << sp.rE() << "^" << np << endl;
289  ++nb, nbok += sp.slope() == SB::fraction( 7, 10 ) ? 1 : 0;
290  pat_even.getSmallestCoveringSubpattern( sp, np, start,
291  0, 6 );
292  trace.info() << "sub(0,6) = " << sp << " " << sp.rE() << "^" << np << endl;
293  ++nb, nbok += sp.slope() == SB::fraction( 7, 10 ) ? 1 : 0;
294  pat_even.getSmallestCoveringSubpattern( sp, np, start,
295  0, 5 );
296  trace.info() << "sub(0,5) = " << sp << " " << sp.rE() << "^" << np << endl;
297  ++nb, nbok += sp.slope() == SB::fraction( 2, 3 ) ? 1 : 0;
298  trace.info() << "(" << nbok << "/" << nb << ") covering left Subpatterns." << endl;
299 
300  // Right Subpatterns
301  pat_even.getSmallestCoveringSubpattern( sp, np, start,
302  4, 29 );
303  trace.info() << "sub(4,29) = " << sp << " " << sp.rE() << "^" << np << endl;
304  ++nb, nbok += sp.slope() == SB::fraction( 12, 17 ) ? 1 : 0;
305  pat_even.getSmallestCoveringSubpattern( sp, np, start,
306  5, 29 );
307  trace.info() << "sub(5,29) = " << sp << " " << sp.rE() << "^" << np << endl;
308  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 2 ? 1 : 0;
309  pat_even.getSmallestCoveringSubpattern( sp, np, start,
310  16, 29 );
311  trace.info() << "sub(16,29) = " << sp << " " << sp.rE() << "^" << np << endl;
312  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 2 ? 1 : 0;
313  pat_even.getSmallestCoveringSubpattern( sp, np, start,
314  17, 29 );
315  trace.info() << "sub(17,29) = " << sp << " " << sp.rE() << "^" << np << endl;
316  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
317  trace.info() << "(" << nbok << "/" << nb << ") covering right Subpatterns." << endl;
318 
319  // Middle Subpatterns
320  pat_even.getSmallestCoveringSubpattern( sp, np, start,
321  1, 27 );
322  trace.info() << "sub(1,27) = " << sp << " " << sp.rE() << "^" << np << endl;
323  ++nb, nbok += sp.slope() == SB::fraction( 12, 17 ) ? 1 : 0;
324  pat_even.getSmallestCoveringSubpattern( sp, np, start,
325  5, 24 );
326  trace.info() << "sub(5,24) = " << sp << " " << sp.rE() << "^" << np << endl;
327  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 2 ? 1 : 0;
328  pat_even.getSmallestCoveringSubpattern( sp, np, start,
329  4, 17 );
330  trace.info() << "sub(4,17) = " << sp << " " << sp.rE() << "^" << np << endl;
331  ++nb, nbok += sp.slope() == SB::fraction( 7, 10 ) && np == 1 ? 1 : 0;
332  pat_even.getSmallestCoveringSubpattern( sp, np, start,
333  5, 17 );
334  trace.info() << "sub(5,17) = " << sp << " " << sp.rE() << "^" << np << endl;
335  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
336  pat_even.getSmallestCoveringSubpattern( sp, np, start,
337  7, 12 );
338  trace.info() << "sub(7,12) = " << sp << " " << sp.rE() << "^" << np << endl;
339  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
340  pat_even.getSmallestCoveringSubpattern( sp, np, start,
341  1, 4 );
342  trace.info() << "sub(1,4) = " << sp << " " << sp.rE() << "^" << np << endl;
343  ++nb, nbok += sp.slope() == SB::fraction( 2, 3 ) && np == 1 ? 1 : 0;
344  pat_even.getSmallestCoveringSubpattern( sp, np, start,
345  18, 25 );
346  trace.info() << "sub(18,20) = " << sp << " " << sp.rE() << "^" << np << endl;
347  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
348  trace.info() << "(" << nbok << "/" << nb << ") covering middle Subpatterns." << endl;
349  trace.endBlock();
350 
351 
352  // GREATEST INCLUDED SUBPATTERN
353  // ODD PATTERN
354  trace.beginBlock ( "Testing block: greatest included subpatterns of ODD pattern." );
355  trace.info() << "ODD " << pat_odd << " " << pat_odd.rE() << endl;
356 
357  // Left Subpatterns
358  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
359  0, 17 );
360  trace.info() << "sub(0,17) = " << sp << " " << sp.rE() << "^" << np << endl;
361  ++nb, nbok += sp.slope() == SB::fraction( 5, 12 ) ? 1 : 0;
362  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
363  1, 17 );
364  trace.info() << "sub(1,17) = " << sp << " " << sp.rE() << "^" << np << endl;
365  ++nb, nbok += sp.slope() == SB::fraction( 3, 7 ) ? 1 : 0;
366  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
367  7, 17 );
368  trace.info() << "sub(7,17) = " << sp << " " << sp.rE() << "^" << np << endl;
369  ++nb, nbok += sp.slope() == SB::fraction( 3, 7 ) ? 1 : 0;
370  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
371  8, 17 );
372  trace.info() << "sub(8,17) = " << sp << " " << sp.rE() << "^" << np << endl;
373  ++nb, nbok += sp.slope() == SB::fraction( 1, 2 ) ? 1 : 0;
374  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
375  13, 17 );
376  trace.info() << "sub(13,17) = " << sp << " " << sp.rE() << "^" << np << endl;
377  ++nb, nbok += sp.slope() == SB::fraction( 1, 2 ) ? 1 : 0;
378  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
379  14, 17 );
380  trace.info() << "sub(14,17) = " << sp << " " << sp.rE() << "^" << np << endl;
381  ++nb, nbok += sp.slope() == SB::fraction( 1, 2 ) ? 1 : 0;
382  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
383  15, 17 );
384  trace.info() << "sub(15,17) = " << sp << " " << sp.rE() << "^" << np << endl;
385  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
386 
387  trace.info() << "(" << nbok << "/" << nb << ") covering left Subpatterns." << endl;
388 
389  // Right Subpatterns
390  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
391  0, 15 );
392  trace.info() << "sub(0,15) = " << sp << " " << sp.rE() << "^" << np << endl;
393  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 2 ? 1 : 0;
394  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
395  0, 14 );
396  trace.info() << "sub(0,14) = " << sp << " " << sp.rE() << "^" << np << endl;
397  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 2 ? 1 : 0;
398  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
399  0, 13 );
400  trace.info() << "sub(0,13) = " << sp << " " << sp.rE() << "^" << np << endl;
401  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
402  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
403  0, 7 );
404  trace.info() << "sub(0,7) = " << sp << " " << sp.rE() << "^" << np << endl;
405  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
406  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
407  0, 6 );
408  trace.info() << "sub(0,6) = " << sp << " " << sp.rE() << "^" << np << endl;
409  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
410  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
411  0, 1 );
412  trace.info() << "sub(0,1) = " << sp << " " << sp.rE() << "^" << np << endl;
413  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
414 
415  trace.info() << "(" << nbok << "/" << nb << ") covering right Subpatterns." << endl;
416 
417  // Middle Subpatterns
418  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
419  1, 16 );
420  trace.info() << "sub(1,16) = " << sp << " " << sp.rE() << "^" << np << endl;
421  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) ? 1 : 0;
422  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
423  2, 14 );
424  trace.info() << "sub(2,14) = " << sp << " " << sp.rE() << "^" << np << endl;
425  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
426  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
427  7, 15 );
428  trace.info() << "sub(7,15) = " << sp << " " << sp.rE() << "^" << np << endl;
429  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
430  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
431  7, 14 );
432  trace.info() << "sub(7,14) = " << sp << " " << sp.rE() << "^" << np << endl;
433  ++nb, nbok += sp.slope() == SB::fraction( 2, 5 ) && np == 1 ? 1 : 0;
434  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
435  3, 6 );
436  trace.info() << "sub(3,6) = " << sp << " " << sp.rE() << "^" << np << endl;
437  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
438  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
439  6, 8 );
440  trace.info() << "sub(6,8) = " << sp << " " << sp.rE() << "^" << np << endl;
441  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
442  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
443  8, 12 );
444  trace.info() << "sub(8,12) = " << sp << " " << sp.rE() << "^" << np << endl;
445  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
446  pat_odd.getGreatestIncludedSubpattern( sp, np, start,
447  15, 16 );
448  trace.info() << "sub(15,16) = " << sp << " " << sp.rE() << "^" << np << endl;
449  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
450 
451  trace.info() << "(" << nbok << "/" << nb << ") covering middle Subpatterns." << endl;
452  trace.endBlock();
453 
454  // EVEN PATTERN
455  trace.beginBlock ( "Testing block: Greatest included subpatterns of EVEN pattern." );
456  trace.info() << "EVEN " << pat_even << " " << pat_even.rE() << endl;
457 
458  // Left Subpatterns
459  pat_even.getGreatestIncludedSubpattern( sp, np, start,
460  0, 29 );
461  trace.info() << "sub(0,29) = " << sp << " " << sp.rE() << "^" << np << endl;
462  ++nb, nbok += sp.slope() == SB::fraction( 12, 17 ) ? 1 : 0;
463  pat_even.getGreatestIncludedSubpattern( sp, np, start,
464  0, 25 );
465  trace.info() << "sub(0,25) = " << sp << " " << sp.rE() << "^" << np << endl;
466  ++nb, nbok += sp.slope() == SB::fraction( 7, 10 ) ? 1 : 0;
467  pat_even.getGreatestIncludedSubpattern( sp, np, start,
468  0, 17 );
469  trace.info() << "sub(0,17) = " << sp << " " << sp.rE() << "^" << np << endl;
470  ++nb, nbok += sp.slope() == SB::fraction( 7, 10 ) ? 1 : 0;
471  pat_even.getGreatestIncludedSubpattern( sp, np, start,
472  0, 16 );
473  trace.info() << "sub(0,16) = " << sp << " " << sp.rE() << "^" << np << endl;
474  ++nb, nbok += sp.slope() == SB::fraction( 2, 3 ) ? 1 : 0;
475  pat_even.getGreatestIncludedSubpattern( sp, np, start,
476  0, 6 );
477  trace.info() << "sub(0,6) = " << sp << " " << sp.rE() << "^" << np << endl;
478  ++nb, nbok += sp.slope() == SB::fraction( 2, 3 ) ? 1 : 0;
479  pat_even.getGreatestIncludedSubpattern( sp, np, start,
480  0, 5 );
481  trace.info() << "sub(0,5) = " << sp << " " << sp.rE() << "^" << np << endl;
482  ++nb, nbok += sp.slope() == SB::fraction( 2, 3 ) ? 1 : 0;
483  pat_even.getGreatestIncludedSubpattern( sp, np, start,
484  0, 4 );
485  trace.info() << "sub(0,4) = " << sp << " " << sp.rE() << "^" << np << endl;
486  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
487  trace.info() << "(" << nbok << "/" << nb << ") covering left Subpatterns." << endl;
488 
489  // Right Subpatterns
490  pat_even.getGreatestIncludedSubpattern( sp, np, start,
491  4, 29 );
492  trace.info() << "sub(4,29) = " << sp << " " << sp.rE() << "^" << np << endl;
493  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 2 ? 1 : 0;
494  pat_even.getGreatestIncludedSubpattern( sp, np, start,
495  5, 29 );
496  trace.info() << "sub(5,29) = " << sp << " " << sp.rE() << "^" << np << endl;
497  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 2 ? 1 : 0;
498  pat_even.getGreatestIncludedSubpattern( sp, np, start,
499  16, 29 );
500  trace.info() << "sub(16,29) = " << sp << " " << sp.rE() << "^" << np << endl;
501  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
502  pat_even.getGreatestIncludedSubpattern( sp, np, start,
503  17, 29 );
504  trace.info() << "sub(17,29) = " << sp << " " << sp.rE() << "^" << np << endl;
505  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
506  pat_even.getGreatestIncludedSubpattern( sp, np, start,
507  18, 29 );
508  trace.info() << "sub(18,29) = " << sp << " " << sp.rE() << "^" << np << endl;
509  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
510  trace.info() << "(" << nbok << "/" << nb << ") covering right Subpatterns." << endl;
511 
512  // Middle Subpatterns
513  pat_even.getGreatestIncludedSubpattern( sp, np, start,
514  1, 27 );
515  trace.info() << "sub(1,27) = " << sp << " " << sp.rE() << "^" << np << endl;
516  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
517  pat_even.getGreatestIncludedSubpattern( sp, np, start,
518  5, 24 );
519  trace.info() << "sub(5,24) = " << sp << " " << sp.rE() << "^" << np << endl;
520  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
521  pat_even.getGreatestIncludedSubpattern( sp, np, start,
522  4, 17 );
523  trace.info() << "sub(4,17) = " << sp << " " << sp.rE() << "^" << np << endl;
524  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
525  pat_even.getGreatestIncludedSubpattern( sp, np, start,
526  5, 17 );
527  trace.info() << "sub(5,17) = " << sp << " " << sp.rE() << "^" << np << endl;
528  ++nb, nbok += sp.slope() == SB::fraction( 5, 7 ) && np == 1 ? 1 : 0;
529  pat_even.getGreatestIncludedSubpattern( sp, np, start,
530  7, 16 );
531  trace.info() << "sub(5,16) = " << sp << " " << sp.rE() << "^" << np << endl;
532  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
533  pat_even.getGreatestIncludedSubpattern( sp, np, start,
534  1, 4 );
535  trace.info() << "sub(1,4) = " << sp << " " << sp.rE() << "^" << np << endl;
536  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
537  pat_even.getGreatestIncludedSubpattern( sp, np, start,
538  18, 25 );
539  trace.info() << "sub(18,20) = " << sp << " " << sp.rE() << "^" << np << endl;
540  ++nb, nbok += sp.slope() == Fraction() ? 1 : 0;
541  trace.info() << "(" << nbok << "/" << nb << ") covering middle Subpatterns." << endl;
542  trace.endBlock();
543 
544  trace.info() << "Odd pattern " << pat_odd << endl;
545  trace.info() << " U(0)=" << pat_odd.U( 0 )
546  << " L(0)=" << pat_odd.L( 0 )
547  << " U(1)=" << pat_odd.U( 1 )
548  << " L(1)=" << pat_odd.L( 1 ) << endl;
549 
550  trace.info() << "Even pattern " << pat_even << endl;
551  trace.info() << " U(0)=" << pat_even.U( 0 )
552  << " L(0)=" << pat_even.L( 0 )
553  << " U(1)=" << pat_even.U( 1 )
554  << " L(1)=" << pat_even.L( 1 ) << endl;
555 
556  return nbok == nb;
557 }
558 
559 template <typename Fraction>
560 bool testStandardDSLQ0()
561 {
562  typedef StandardDSLQ0<Fraction> DSL;
563  typedef typename Fraction::Integer Integer;
564  typedef typename DSL::Point Point;
565  typedef typename DSL::Vector2I Vector2I;
566 
567  BOOST_CONCEPT_ASSERT(( concepts::CPointPredicate< DSL > ));
568  unsigned int nbok = 0;
569  unsigned int nb = 0;
570 
571  for ( Integer mu = -5; mu < 30; ++mu )
572  {
573  DSL D1( 5, 12, mu );
574  trace.info() << "DSL D1=" << D1 << endl;
575  Point U = D1.U();
576  Point L = D1.L();
577  trace.info() << "- U=" << U << " r(U)=" << D1.r( U )
578  << ", L=" << L << " r(L)=" << D1.r( L ) << endl;
579  ++nb, nbok += D1.r( U ) == D1.mu() ? 1 : 0;
580  ++nb, nbok += D1.r( L ) == D1.mup() ? 1 : 0;
581  }
582 
583  DSL D2( 12, 17, 5 );
584  for ( Integer x = -5; x < 30; ++x )
585  {
586  Point P = D2.lowestY( x );
587  ++nb, nbok += D2( P ) && ( ! D2( P - Vector2I(0,1) ) ) ? 1 : 0;
588  trace.info() << "(" << nbok << "/" << nb << ") "
589  << "D2(P) && ! D2(P-y) P=" << P << " r(P)=" << D2.r( P )
590  << endl;
591  P = D2.uppermostY( x );
592  ++nb, nbok += D2( P ) && ( ! D2( P + Vector2I(0,1) ) ) ? 1 : 0;
593  trace.info() << "(" << nbok << "/" << nb << ") "
594  << "D2(P) && ! D2(P+y) P=" << P << " r(P)=" << D2.r( P )
595  << endl;
596  }
597  for ( Integer y = -5; y < 30; ++y )
598  {
599  Point P = D2.lowestX( y );
600  ++nb, nbok += D2( P ) && ( ! D2( P - Vector2I(1,0) ) ) ? 1 : 0;
601  trace.info() << "(" << nbok << "/" << nb << ") "
602  << "D2(P) && ! D2(P-x) P=" << P << " r(P)=" << D2.r( P )
603  << endl;
604  P = D2.uppermostX( y );
605  ++nb, nbok += D2( P ) && ( ! D2( P + Vector2I(1,0) ) ) ? 1 : 0;
606  trace.info() << "(" << nbok << "/" << nb << ") "
607  << "D2(P) && ! D2(P+x) P=" << P << " r(P)=" << D2.r( P )
608  << endl;
609  }
610 
611  return nbok == nb;
612 }
613 
614 template <typename DSL>
615 bool checkSubStandardDSLQ0( const DSL & D,
616  const typename DSL::Point & A,
617  const typename DSL::Point & B )
618 {
619  typedef typename DSL::Integer Integer;
620  typedef typename DSL::ConstIterator ConstIterator;
622 
623  DSL S = D.reversedSmartDSS( A, B );
624  ConstIterator it = D.begin( A );
625  ConstIterator it_end = D.end( B );
626  ADSS dss;
627  dss.init( it );
628  while ( ( dss.end() != it_end )
629  && ( dss.extendFront() ) ) {}
630  bool ok = S.a() == dss.a()
631  && S.b() == dss.b()
632  && S.mu() == dss.mu();
633  if ( ! ok )
634  {
635  trace.info() << "-------------------------------------------------------"
636  << std::endl;
637  trace.info() << "D = " << D // << " U1=" << U1 << " U2=" << U2
638  << " " << D.pattern().rE() << endl;
639  trace.info() << "S(" << A << "," << B << ") = "
640  << S << " " << S.pattern() << endl;
641  trace.info() << "ArithDSS = " << dss << std::endl;
642  }
643  // if ( ok )
644  // trace.info() << "========================== OK =========================";
645  // else
646  // trace.info() << "eeeeeeeeeeeeeeeeeeeeeeeeee KO eeeeeeeeeeeeeeeeeeeeeeeee";
647  // std::cerr << std::endl;
648  return ok;
649 }
650 
651 template <typename Fraction>
652 bool testSubStandardDSLQ0()
653 {
654  typedef StandardDSLQ0<Fraction> DSL;
655  typedef typename Fraction::Integer Integer;
656  typedef typename DSL::Point Point;
658  unsigned int nbok = 0;
659  unsigned int nb = 0;
660 
661  trace.beginBlock( "Check ReversedSmartDSS == ArithmeticDSS" );
662  for ( unsigned int i = 0; i < 100; ++i )
663  {
664  Integer a( rand() % 12000 + 1 );
665  Integer b( rand() % 12000 + 1 );
666  if ( ic.gcd( a, b ) == 1 )
667  {
668  trace.info() << "(" << i << ")"
669  << " Test DSL has slope " << a << "/" << b << std::endl;
670  for ( Integer mu = 0; mu < 5; ++mu )
671  {
672  DSL D( a, b, rand() % 10000 );
673  for ( Integer x = 0; x < 10; ++x )
674  {
675  Integer x1 = rand() % 1000;
676  Integer x2 = x1 + 1 + ( rand() % 1000 );
677  Point A = D.lowestY( x1 );
678  Point B = D.lowestY( x2 );
679  ++nb, nbok += checkSubStandardDSLQ0<DSL>( D, A, B ) ? 1 : 0;
680  if ( nb != nbok )
681  trace.info() << "(" << nbok << "/" << nb << ") correct reversedSmartDSS."
682  << std::endl;
683  if ( nbok != nb ) assert(false);
684  }
685  }
686  }
687  }
688  trace.info() << "(" << nbok << "/" << nb << ") correct reversedSmartDSS."
689  << std::endl;
690  trace.endBlock();
691  return nbok == nb;
692 }
693 
694 
699 bool testSternBrocot()
700 {
701  unsigned int nbtests = 10;
702  unsigned int nbok = 0;
703  unsigned int nb = 0;
704  typedef DGtal::BigInteger Integer;
706  trace.beginBlock ( "Testing block: init fractions." );
707  for ( unsigned int i = 0; i < nbtests; ++i )
708  {
709  nbok += testInitFraction<SB>() ? 1 : 0;
710  nb++;
711  }
712  trace.info() << "(" << nbok << "/" << nb << ") init fractions." << endl;
713  trace.endBlock();
714  trace.beginBlock ( "Testing block: reduced fractions." );
715  for ( unsigned int i = 0; i < nbtests; ++i )
716  {
717  nbok += testReducedFraction<SB>() ? 1 : 0;
718  nb++;
719  }
720  trace.info() << "(" << nbok << "/" << nb << ") reduced fractions." << endl;
721  trace.endBlock();
722 
723  trace.beginBlock ( "Testing block: number of fractions." );
724  trace.info() << "- nbFractions = " << SB::instance().nbFractions << endl;
725  trace.endBlock();
726 
727  return nbok == nb;
728 }
729 
730 template <typename SB>
731 bool testContinuedFraction()
732 {
733  typedef typename SB::Quotient Quotient;
734  typedef typename SB::Fraction Fraction;
735  typedef typename SB::Fraction::ConstIterator ConstIterator;
736 
737  Fraction f;
738  std::vector<Quotient> quotients;
739  std::vector<Quotient> qcfrac;
740  std::back_insert_iterator< Fraction > itout =
741  std::back_inserter( f );
742  unsigned int size = ( rand() % 20 ) + 10;
743  for ( unsigned int i = 0; i < size; ++i )
744  {
745  Quotient q = ( i == 0 )
746  ? ( rand() % 5 )
747  : ( rand() % 5 ) + 1;
748  *itout++ = std::make_pair( q, (Quotient) i );
749  quotients.push_back( q );
750  }
751  for ( ConstIterator it = f.begin(), it_end = f.end();
752  it != it_end; ++it )
753  qcfrac.push_back( (*it).first );
754  // f.getCFrac( qcfrac );
755  bool ok = equalCFrac( quotients, qcfrac );
756 
757  trace.info() << ( ok ? "(OK)" : "(ERR)" );
758  for ( unsigned int i = 0; i < quotients.size(); ++i )
759  std::cerr << " " << quotients[ i ];
760  trace.info() << std::endl;
761  trace.info() << " f=";
762  f.selfDisplay( std::cerr );
763  trace.info() << std::endl;
764  return ok;
765 }
766 
767 template <typename SB>
768 bool testContinuedFractions()
769 {
770  unsigned int nbtests = 1000;
771  unsigned int nbok = 0;
772  unsigned int nb = 0;
773  trace.beginBlock ( "Testing block: continued fraction." );
774  for ( unsigned int i = 0; i < nbtests; ++i )
775  {
776  ++nb, nbok += testContinuedFraction<SB>() ? 1 : 0;
777  trace.info() << "(" << nbok << "/" << nb << ")"
778  << " continued fractions." << std::endl;
779  }
780  trace.endBlock();
781  return nbok == nb;
782 }
783 
787 template <typename SB>
788 bool
789 testAncestors()
790 {
791  typedef typename SB::Fraction Fraction;
792  typedef StandardDSLQ0<Fraction> DSL;
793  typedef typename DSL::Point Point;
794 
795  // Instanciation d'un DSL
796  DSL D(1077,1495,6081);
797 
798  // Definition du sous-segment [AB] et calcul des caractéristiques
799  Point A(3,-3);
800  Point B(4,-2);
801  ASSERT( D( A ) && "Point A belongs to D." );
802  ASSERT( D( B ) && "Point A belongs to D." );
803  DSL D1 = D.reversedSmartDSS(A,B); // may raise an assert.
804  std::cerr << D1 << std::endl;
805  return D1.slope() == Fraction( 1, 1 );
806 }
807 
808 
809 //-------------------------------------------
810 template <typename SB>
811 bool
812 testSimplestFractionInBetween()
813 {
814  typedef typename SB::Fraction Fraction;
815  Fraction f,g;
816  unsigned int nb = 0;
817  unsigned int nbok = 0;
818 
819  trace.beginBlock("Testing block: simplest fraction between two fractions");
820  // When the two fractions are not ancestors of one other
821  f = Fraction(1,5); g = Fraction(3,4);
822  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(1,2) ? 1 : 0;
823  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
824 
825  f = Fraction(4,7); g = Fraction(5,7);
826  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(2,3) ? 1 : 0;
827  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
828 
829  f = Fraction(3,8); g = Fraction(7,4);
830  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(1,1) ? 1 : 0;
831  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
832 
833  f = Fraction(11,7); g = Fraction(7,4);
834  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(5,3) ? 1 : 0;
835  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
836 
837  f = Fraction(8,13); g = Fraction(7,11);
838  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(5,8) ? 1 : 0;
839  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
840 
841  // When f is an ancestor of g or conversely
842  f = Fraction(2,5); g = Fraction(4,9);
843  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(3,7) ? 1 : 0;
844  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
845 
846  f = Fraction(2,3); g = Fraction(8,11);
847  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(5,7) ? 1 : 0;
848  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
849 
850  f = Fraction(1,2); g = Fraction(5,9);
851  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(6,11) ? 1 : 0;
852  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
853 
854  f = Fraction(5,9); g = Fraction(2,3);
855  ++nb, nbok += f.simplestFractionInBetween(g) == Fraction(3,5) ? 1 : 0;
856  trace.info() << "(" << nbok << "/" << nb << ")" << std::endl;
857 
858  trace.endBlock();
859  return nbok == nb;
860 }
861 
862 
863 
865 // Standard services - public :
866 
867 int main( int , char** )
868 {
870  typedef SB::Fraction Fraction;
871  typedef Fraction::ConstIterator ConstIterator;
872 
873  BOOST_CONCEPT_ASSERT(( concepts::CPositiveIrreducibleFraction< Fraction > ));
874  BOOST_CONCEPT_ASSERT(( boost::InputIterator< ConstIterator > ));
875 
876  trace.beginBlock ( "Testing class SternBrocot" );
877  bool res = testSternBrocot()
878  && testPattern<SB>()
879  && testSubStandardDSLQ0<Fraction>()
880  && testContinuedFractions<SB>()
881  && testAncestors<SB>()
882  && testSimplestFractionInBetween<SB>();
883  trace.emphase() << ( res ? "Passed." : "Error." ) << endl;
884  trace.endBlock();
885  return res ? 0 : 1;
886 }
887 // //
void beginBlock(const std::string &keyword="")
DGtal::int32_t Integer
Definition: StdDefs.h:74
Aim: Represents a digital straight line with slope in the first quadrant (Q0: x >= 0...
Definition: StandardDSLQ0.h:79
Trace trace
Definition: Common.h:137
Integer getCFrac(std::vector< Integer > &quotients, IntegerParamType a, IntegerParamType b) const
STL namespace.
double endBlock()
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition: BasicTypes.h:79
Aim: This class is a wrapper around ArithmeticalDSS that is devoted to the dynamic recognition of dig...
Aim: Defines positive irreducible fractions, i.e. fraction p/q, p and q non-negative integers...
Aim: Defines a predicate on a point.
std::ostream & emphase()
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:69
DGtal is the top-level namespace which contains all DGtal functions and types.
Go to http://www.sgi.com/tech/stl/InputIterator.html.
Definition: Boost.dox:36
std::ostream & info()
Integer gcd(IntegerParamType a, IntegerParamType b) const
ConstIterator begin() const
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition: SternBrocot.h:77