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