DGtal 1.4.0
Loading...
Searching...
No Matches
testLighterSternBrocot.cpp
Go to the documentation of this file.
1
31#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
47using namespace std;
48using namespace DGtal;
49
51// Functions for testing class LighterSternBrocot.
53
54template <typename Quotient>
55bool
56equalCFrac( const std::vector<Quotient> & c1, const std::vector<Quotient> & c2 )
57{
58 auto 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
74template <typename SB>
75bool 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." );
85 IntegerComputer<Integer> ic;
86 Integer g = ic.gcd( p, q );
87 p /= g;
88 q /= g;
89 IntegerComputer<Quotient> ics;
90 Quotient sp = (Quotient)NumberTraits<Integer>::castToInt64_t( p );
91 Quotient sq = (Quotient)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 const auto 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
126template <typename SB>
127bool 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." );
136 IntegerComputer<Integer> ic;
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
156template <typename SB>
157bool 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
563template <typename Fraction>
564bool 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
618template <typename DSL>
619bool 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;
625 typedef ArithmeticalDSSComputer<ConstIterator, Integer, 4> ADSS;
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
655template <typename Fraction>
656bool testSubStandardDSLQ0()
657{
658 typedef StandardDSLQ0<Fraction> DSL;
659 typedef typename Fraction::Integer Integer;
660 typedef typename DSL::Point Point;
661 IntegerComputer<Integer> ic;
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
702bool testLighterSternBrocot()
703{
704 unsigned int nbtests = 10;
705 unsigned int nbok = 0;
706 unsigned int nb = 0;
707 typedef DGtal::BigInteger Integer;
708 typedef LighterSternBrocot<Integer, DGtal::int32_t, DGtal::StdMapRebinder> SB;
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
735template <typename SB>
736bool 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
772template <typename SB>
773bool 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
789template <typename LSB>
790bool
791testTrivial( 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
825template <typename SB>
826bool
827testAncestors()
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
849int main( int , char** )
850{
851 typedef LighterSternBrocot< DGtal::int64_t,DGtal::int32_t,
852 DGtal::StdMapRebinder > SB;
853 typedef LightSternBrocot<DGtal::int64_t,DGtal::int32_t> SB2;
854 typedef SternBrocot<DGtal::int64_t,DGtal::int32_t> SB3;
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// //
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::LighterSternBrocot
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition LighterSternBrocot.h:109
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::Pattern::slope
Fraction slope() const
DGtal::Pattern::previousPattern
Pattern previousPattern() const
DGtal::Pattern::rE
std::string rE() const
DGtal::StandardDSLQ0
Aim: Represents a digital straight line with slope in the first quadrant (Q0: x >= 0,...
Definition StandardDSLQ0.h:80
DGtal::SternBrocot
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition SternBrocot.h:78
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::int64_t
boost::int64_t int64_t
signed 94-bit integer.
Definition BasicTypes.h:74
DGtal::trace
Trace trace
Definition Common.h:153
DGtal::int32_t
boost::int32_t int32_t
signed 32-bit integer.
Definition BasicTypes.h:72
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:164
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 testLighterSternBrocot.cpp:656
testReducedFraction
bool testReducedFraction()
Definition testLighterSternBrocot.cpp:75
checkSubStandardDSLQ0
bool checkSubStandardDSLQ0(const DSL &D, const typename DSL::Point &A, const typename DSL::Point &B)
Definition testLighterSternBrocot.cpp:619
testPattern
bool testPattern()
Definition testLighterSternBrocot.cpp:157
testStandardDSLQ0
bool testStandardDSLQ0()
Definition testLighterSternBrocot.cpp:564
testAncestors
bool testAncestors()
Definition testLighterSternBrocot.cpp:827
testInitFraction
bool testInitFraction()
Definition testLighterSternBrocot.cpp:127
testLighterSternBrocot
bool testLighterSternBrocot()
Definition testLighterSternBrocot.cpp:702
testContinuedFraction
bool testContinuedFraction()
Definition testLighterSternBrocot.cpp:736
testContinuedFractions
bool testContinuedFractions()
Definition testLighterSternBrocot.cpp:773
testTrivial
bool testTrivial(const string &lsb)
Definition testLighterSternBrocot.cpp:791
equalCFrac
bool equalCFrac(const std::vector< Quotient > &c1, const std::vector< Quotient > &c2)
Definition testLighterSternBrocot.cpp:56