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