DGtal 1.3.0
Loading...
Searching...
No Matches
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
44using namespace std;
45using namespace DGtal;
46
48// Functions for testing class LightSternBrocot.
50
51template <typename Quotient>
52bool
53equalCFrac( const std::vector<Quotient> & c1, const std::vector<Quotient> & c2 )
54{
55 unsigned int 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
71template <typename SB>
72bool 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 = NumberTraits<Integer>::castToInt64_t( p );
88 Quotient sq = 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 unsigned int depth = cf1.size();
104 for ( unsigned int 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
123template <typename SB>
124bool 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
153template <typename SB>
154bool 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
560template <typename Fraction>
561bool 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
615template <typename DSL>
616bool 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
652template <typename Fraction>
653bool 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
700bool 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
739template <typename SB>
740bool
741testAncestors()
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
760int 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
Aim: This class gathers several types and methods to make computation with integers.
Definition: IntegerComputer.h:83
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::Pattern
Aim: This class represents a pattern, i.e. the path between two consecutive upper leaning points on a...
Definition: Pattern.h:79
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.
Definition: ClosedIntegerHalfPlane.h:49
DGtal::trace
Trace trace
Definition: Common.h:154
DGtal::BigInteger
mpz_class BigInteger
Multi-precision integer with GMP implementation.
Definition: BasicTypes.h:79
std
STL namespace.
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:165
boost::InputIterator
Go to http://www.sgi.com/tech/stl/InputIterator.html.
Definition: Boost.dox:36
main
int main()
Definition: testBits.cpp:56
Point
MyPointD Point
Definition: testClone2.cpp:383
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
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
Generated on Sun Nov 27 2022 15:15:53 for DGtal by doxygen 1.9.5