DGtal 1.4.0
Loading...
Searching...
No Matches
testUnorderedSetByBlock.cpp
Go to the documentation of this file.
1
31#include <iostream>
32#include <vector>
33#include <algorithm>
34#include <iterator>
35#include <unordered_set>
36#include "DGtal/kernel/PointVector.h"
37#include "DGtal/kernel/UnorderedSetByBlock.h"
38#include "DGtalCatch.h"
40
41using namespace std;
42using namespace DGtal;
43
44template < typename Point >
45Point randomPoint( int S )
46{
47 Point p;
48 for ( DGtal::Dimension i = 0; i < Point::dimension; i++ )
49 p[ i ] = (rand() % S) - S/2;
50 return p;
51}
52
53
55// Functions for testing class UnorderedSetByBlock.
57
58SCENARIO( "UnorderedSetByBlock< PointVector< 2, int > unit tests with 32 bits blocks", "[unorderedsetbyblock][2d]" )
59{
60 typedef PointVector< 2, int32_t > Point;
61 typedef std::unordered_set< Point > StdUnorderedSet;
62 typedef UnorderedSetByBlock< Point > BlockUnorderedSet;
63
64 const size_t nb_inserted = 100;
65 const size_t nb_sought = 200;
66 const size_t nb_erased = 100;
67
68 StdUnorderedSet stdSet;
69 BlockUnorderedSet blkSet;
70 for ( size_t i = 0; i < nb_inserted; i++ )
71 {
72 Point p = randomPoint<Point>( 10 );
73 stdSet.insert( p );
74 blkSet.insert( p );
75 }
76 WHEN( "Inserting identical elements in std::unordered_set<> and in UnorderedSetByBlock<>, they contains the same number of elements" ) {
77 REQUIRE( blkSet.size() <= nb_inserted );
78 REQUIRE( blkSet.size() == stdSet.size() );
79 }
80 WHEN( "Cloning identical std::unordered_set<> and UnorderedSetByBlock<>, they contains the same number of elements" ) {
81 StdUnorderedSet stdSet2( stdSet );
82 BlockUnorderedSet blkSet2( blkSet );
83 REQUIRE( blkSet2.size() == blkSet.size() );
84 REQUIRE( blkSet2.size() == stdSet2.size() );
85 }
86 WHEN( "Traversing identical std::unordered_set<> and UnorderedSetByBlock<>, they traverse the same elements" ) {
87 std::vector< Point > stdTrv;
88 std::vector< Point > blkTrv;
89 for ( auto&& p : stdSet ) stdTrv.push_back( p );
90 for ( auto&& p : blkSet ) blkTrv.push_back( p );
91 REQUIRE( blkTrv.size() == stdTrv.size() );
92 std::sort( stdTrv.begin(), stdTrv.end() );
93 std::sort( blkTrv.begin(), blkTrv.end() );
94 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
95 }
96 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `count`" ) {
97 std::vector< Point > stdFound, stdNotFound;
98 std::vector< Point > blkFound, blkNotFound;
99 for ( size_t i = 0; i < nb_sought; i++ )
100 {
101 Point p = randomPoint<Point>( 10 );
102 if ( stdSet.count( p ) != 0 ) stdFound.push_back( p );
103 else stdNotFound.push_back( p );
104 if ( blkSet.count( p ) != 0 ) blkFound.push_back( p );
105 else blkNotFound.push_back( p );
106 }
107 REQUIRE( blkFound .size() == stdFound .size() );
108 REQUIRE( blkNotFound.size() == stdNotFound.size() );
109 std::sort( stdFound .begin(), stdFound .end() );
110 std::sort( stdNotFound.begin(), stdNotFound.end() );
111 std::sort( blkFound .begin(), blkFound .end() );
112 std::sort( blkNotFound.begin(), blkNotFound.end() );
113 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
114 blkFound.cbegin() ) );
115 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
116 blkNotFound.cbegin() ) );
117 }
118 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `find`" ) {
119 std::vector< Point > stdFound, stdNotFound;
120 std::vector< Point > blkFound, blkNotFound;
121 size_t std_nb_value_ok = 0;
122 size_t blk_nb_value_ok = 0;
123 for ( size_t i = 0; i < nb_sought; i++ )
124 {
125 Point p = randomPoint<Point>( 10 );
126 const auto stdIt = stdSet.find( p );
127 if ( stdIt != stdSet.end() )
128 {
129 stdFound.push_back( p );
130 std_nb_value_ok += ( *stdIt == p ) ? 1 : 0;
131 }
132 else stdNotFound.push_back( p );
133 const auto blkIt = blkSet.find( p );
134 if ( blkIt != blkSet.end() )
135 {
136 blkFound.push_back( p );
137 blk_nb_value_ok += ( *blkIt == p ) ? 1 : 0;
138 }
139 else blkNotFound.push_back( p );
140 }
141 REQUIRE( blkFound .size() == stdFound .size() );
142 REQUIRE( blkNotFound.size() == stdNotFound.size() );
143 std::sort( stdFound .begin(), stdFound .end() );
144 std::sort( stdNotFound.begin(), stdNotFound.end() );
145 std::sort( blkFound .begin(), blkFound .end() );
146 std::sort( blkNotFound.begin(), blkNotFound.end() );
147 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
148 blkFound.cbegin() ) );
149 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
150 blkNotFound.cbegin() ) );
151 REQUIRE( std_nb_value_ok == stdFound.size() );
152 REQUIRE( blk_nb_value_ok == std_nb_value_ok );
153 REQUIRE( blk_nb_value_ok == blkFound.size() );
154 }
155 WHEN( "Erasing elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are left" ) {
156 std::vector< Point > stdErase;
157 std::vector< Point > blkErase;
158 size_t std_nb_erase_ok = 0;
159 size_t blk_nb_erase_ok = 0;
160 for ( size_t i = 0; i < nb_erased; i++ )
161 {
162 Point p = randomPoint<Point>( 10 );
163 auto stdFindIt = stdSet.find ( p );
164 auto stdIsErased = stdSet.erase( p );
165 if ( stdFindIt != stdSet.cend() )
166 {
167 std_nb_erase_ok += ( stdIsErased != 0 ) ? 1 : 0;
168 stdErase.push_back( p );
169 }
170 else std_nb_erase_ok += ( stdIsErased == 0 ) ? 1 : 0;
171 auto blkFindIt = blkSet.find ( p );
172 auto blkIsErased = blkSet.erase( p );
173 if ( blkFindIt != blkSet.cend() )
174 {
175 blk_nb_erase_ok += ( blkIsErased != 0 ) ? 1 : 0;
176 blkErase.push_back( p );
177 }
178 else blk_nb_erase_ok += ( blkIsErased == 0 ) ? 1 : 0;
179 }
180 REQUIRE( blkSet .size() == stdSet .size() );
181 REQUIRE( blkErase.size() == stdErase.size() );
182 REQUIRE( blk_nb_erase_ok == std_nb_erase_ok );
183 std::vector< Point > stdTrv;
184 std::vector< Point > blkTrv;
185 for ( auto&& p : stdSet ) stdTrv.push_back( p );
186 for ( auto&& p : blkSet ) blkTrv.push_back( p );
187 REQUIRE( blkTrv.size() == stdTrv.size() );
188 std::sort( stdTrv.begin(), stdTrv.end() );
189 std::sort( blkTrv.begin(), blkTrv.end() );
190 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
191 }
192 WHEN( "Erasing a range in identical std::unordered_set<> and UnorderedSetByBlock<>, the same number of elements is left" ) {
193 auto nb_std_before = stdSet.size();
194 auto nb_blk_before = blkSet.size();
195 auto stdItB = stdSet.begin(); std::advance( stdItB, 10 );
196 auto blkItB = blkSet.begin(); std::advance( blkItB, 10 );
197 auto stdItE = stdItB; std::advance( stdItE, 20 );
198 auto blkItE = blkItB; std::advance( blkItE, 20 );
199 stdSet.erase( stdItB, stdItE );
200 blkSet.erase( blkItB, blkItE );
201 size_t nb_std = std::distance(stdSet.begin(), stdSet.end());
202 size_t nb_blk = std::distance(blkSet.begin(), blkSet.end());
203 REQUIRE( stdSet.size() == nb_std );
204 REQUIRE( stdSet.size() == nb_std_before - 20 );
205 REQUIRE( blkSet.size() == nb_blk );
206 REQUIRE( blkSet.size() == nb_blk_before - 20 );
207 REQUIRE( blkSet.size() == stdSet.size() );
208 }
209 THEN( "The memory usage of UnorderedSetByBlock<> is inferior to the one of std::unordered_set<>" ) {
210 const auto stdMem = blkSet.memory_usage_unordered_set();
211 const auto blkMem = blkSet.memory_usage();
212 REQUIRE( blkMem <= stdMem );
213 }
214
215
216 THEN( "Conparisons and valid assignments between iterator and const_iterator should be seamless for the user" ) {
217 BlockUnorderedSet::iterator itB = blkSet.begin();
218 BlockUnorderedSet::const_iterator citB = blkSet.begin();
219 BlockUnorderedSet::const_iterator citBp = blkSet.cbegin();
220 BlockUnorderedSet::iterator itE = blkSet.end();
221 BlockUnorderedSet::const_iterator citE = blkSet.end();
222 BlockUnorderedSet::const_iterator citEp = blkSet.cend();
223 REQUIRE( itB == blkSet.begin() );
224 REQUIRE( itB == blkSet.cbegin() );
225 REQUIRE( citB == blkSet.begin() );
226 REQUIRE( citB == blkSet.cbegin() );
227 REQUIRE( citBp == blkSet.cbegin() );
228 REQUIRE( itE == blkSet.end() );
229 REQUIRE( itE == blkSet.cend() );
230 REQUIRE( citE == blkSet.end() );
231 REQUIRE( citE == blkSet.cend() );
232 REQUIRE( citEp == blkSet.cend() );
233 REQUIRE( itB != itE );
234 REQUIRE( itB != citE );
235 REQUIRE( itB != citEp );
236 REQUIRE( citB != itE );
237 REQUIRE( citB != citE );
238 REQUIRE( citB != citEp );
239 REQUIRE( citBp != itE );
240 REQUIRE( citBp != citE );
241 REQUIRE( citBp != citEp );
242 }
243}
244
245
246SCENARIO( "UnorderedSetByBlock< PointVector< 3, int64 > unit tests with 32 bits blocks", "[unorderedsetbyblock][3d]" )
247{
248 typedef PointVector< 3, int64_t > Point;
249 typedef std::unordered_set< Point > StdUnorderedSet;
250 typedef UnorderedSetByBlock< Point > BlockUnorderedSet;
251
252 const size_t nb_inserted = 1000;
253 const size_t nb_sought = 2000;
254 const size_t nb_erased = 1000;
255
256 StdUnorderedSet stdSet;
257 BlockUnorderedSet blkSet;
258 for ( size_t i = 0; i < nb_inserted; i++ )
259 {
260 Point p = randomPoint<Point>( 10 );
261 stdSet.insert( p );
262 blkSet.insert( p );
263 }
264 WHEN( "Inserting identical elements in std::unordered_set<> and in UnorderedSetByBlock<>, they contains the same number of elements" ) {
265 REQUIRE( blkSet.size() <= nb_inserted );
266 REQUIRE( blkSet.size() == stdSet.size() );
267 }
268 WHEN( "Cloning identical std::unordered_set<> and UnorderedSetByBlock<>, they contains the same number of elements" ) {
269 StdUnorderedSet stdSet2( stdSet );
270 BlockUnorderedSet blkSet2( blkSet );
271 REQUIRE( blkSet2.size() == blkSet.size() );
272 REQUIRE( blkSet2.size() == stdSet2.size() );
273 }
274 WHEN( "Traversing identical std::unordered_set<> and UnorderedSetByBlock<>, they traverse the same elements" ) {
275 std::vector< Point > stdTrv;
276 std::vector< Point > blkTrv;
277 for ( auto&& p : stdSet ) stdTrv.push_back( p );
278 for ( auto&& p : blkSet ) blkTrv.push_back( p );
279 REQUIRE( blkTrv.size() == stdTrv.size() );
280 std::sort( stdTrv.begin(), stdTrv.end() );
281 std::sort( blkTrv.begin(), blkTrv.end() );
282 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
283 }
284 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `count`" ) {
285 std::vector< Point > stdFound, stdNotFound;
286 std::vector< Point > blkFound, blkNotFound;
287 for ( size_t i = 0; i < nb_sought; i++ )
288 {
289 Point p = randomPoint<Point>( 10 );
290 if ( stdSet.count( p ) != 0 ) stdFound.push_back( p );
291 else stdNotFound.push_back( p );
292 if ( blkSet.count( p ) != 0 ) blkFound.push_back( p );
293 else blkNotFound.push_back( p );
294 }
295 REQUIRE( blkFound .size() == stdFound .size() );
296 REQUIRE( blkNotFound.size() == stdNotFound.size() );
297 std::sort( stdFound .begin(), stdFound .end() );
298 std::sort( stdNotFound.begin(), stdNotFound.end() );
299 std::sort( blkFound .begin(), blkFound .end() );
300 std::sort( blkNotFound.begin(), blkNotFound.end() );
301 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
302 blkFound.cbegin() ) );
303 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
304 blkNotFound.cbegin() ) );
305 }
306 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `find`" ) {
307 std::vector< Point > stdFound, stdNotFound;
308 std::vector< Point > blkFound, blkNotFound;
309 size_t std_nb_value_ok = 0;
310 size_t blk_nb_value_ok = 0;
311 for ( size_t i = 0; i < nb_sought; i++ )
312 {
313 Point p = randomPoint<Point>( 10 );
314 const auto stdIt = stdSet.find( p );
315 if ( stdIt != stdSet.end() )
316 {
317 stdFound.push_back( p );
318 std_nb_value_ok += ( *stdIt == p ) ? 1 : 0;
319 }
320 else stdNotFound.push_back( p );
321 const auto blkIt = blkSet.find( p );
322 if ( blkIt != blkSet.end() )
323 {
324 blkFound.push_back( p );
325 blk_nb_value_ok += ( *blkIt == p ) ? 1 : 0;
326 }
327 else blkNotFound.push_back( p );
328 }
329 REQUIRE( blkFound .size() == stdFound .size() );
330 REQUIRE( blkNotFound.size() == stdNotFound.size() );
331 std::sort( stdFound .begin(), stdFound .end() );
332 std::sort( stdNotFound.begin(), stdNotFound.end() );
333 std::sort( blkFound .begin(), blkFound .end() );
334 std::sort( blkNotFound.begin(), blkNotFound.end() );
335 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
336 blkFound.cbegin() ) );
337 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
338 blkNotFound.cbegin() ) );
339 REQUIRE( std_nb_value_ok == stdFound.size() );
340 REQUIRE( blk_nb_value_ok == std_nb_value_ok );
341 REQUIRE( blk_nb_value_ok == blkFound.size() );
342 }
343 WHEN( "Erasing elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are left" ) {
344 std::vector< Point > stdErase;
345 std::vector< Point > blkErase;
346 size_t std_nb_erase_ok = 0;
347 size_t blk_nb_erase_ok = 0;
348 for ( size_t i = 0; i < nb_erased; i++ )
349 {
350 Point p = randomPoint<Point>( 10 );
351 auto stdFindIt = stdSet.find ( p );
352 auto stdIsErased = stdSet.erase( p );
353 if ( stdFindIt != stdSet.cend() )
354 {
355 std_nb_erase_ok += ( stdIsErased != 0 ) ? 1 : 0;
356 stdErase.push_back( p );
357 }
358 else std_nb_erase_ok += ( stdIsErased == 0 ) ? 1 : 0;
359 auto blkFindIt = blkSet.find ( p );
360 auto blkIsErased = blkSet.erase( p );
361 if ( blkFindIt != blkSet.cend() )
362 {
363 blk_nb_erase_ok += ( blkIsErased != 0 ) ? 1 : 0;
364 blkErase.push_back( p );
365 }
366 else blk_nb_erase_ok += ( blkIsErased == 0 ) ? 1 : 0;
367 }
368 REQUIRE( blkSet .size() == stdSet .size() );
369 REQUIRE( blkErase.size() == stdErase.size() );
370 REQUIRE( blk_nb_erase_ok == std_nb_erase_ok );
371 std::vector< Point > stdTrv;
372 std::vector< Point > blkTrv;
373 for ( auto&& p : stdSet ) stdTrv.push_back( p );
374 for ( auto&& p : blkSet ) blkTrv.push_back( p );
375 REQUIRE( blkTrv.size() == stdTrv.size() );
376 std::sort( stdTrv.begin(), stdTrv.end() );
377 std::sort( blkTrv.begin(), blkTrv.end() );
378 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
379 }
380 WHEN( "Erasing a range in identical std::unordered_set<> and UnorderedSetByBlock<>, the same number of elements is left" ) {
381 auto nb_std_before = stdSet.size();
382 auto nb_blk_before = blkSet.size();
383 auto stdItB = stdSet.begin(); std::advance( stdItB, 10 );
384 auto blkItB = blkSet.begin(); std::advance( blkItB, 10 );
385 auto stdItE = stdItB; std::advance( stdItE, 20 );
386 auto blkItE = blkItB; std::advance( blkItE, 20 );
387 stdSet.erase( stdItB, stdItE );
388 blkSet.erase( blkItB, blkItE );
389 size_t nb_std = std::distance(stdSet.begin(), stdSet.end());
390 size_t nb_blk = std::distance(blkSet.begin(), blkSet.end());
391 REQUIRE( stdSet.size() == nb_std );
392 REQUIRE( stdSet.size() == nb_std_before - 20 );
393 REQUIRE( blkSet.size() == nb_blk );
394 REQUIRE( blkSet.size() == nb_blk_before - 20 );
395 REQUIRE( blkSet.size() == stdSet.size() );
396 }
397 THEN( "The memory usage of UnorderedSetByBlock<> is inferior to the one of std::unordered_set<>" ) {
398 const auto stdMem = blkSet.memory_usage_unordered_set();
399 const auto blkMem = blkSet.memory_usage();
400 REQUIRE( blkMem <= stdMem );
401 }
402
403
404 THEN( "Conparisons and valid assignments between iterator and const_iterator should be seamless for the user" ) {
405 BlockUnorderedSet::iterator itB = blkSet.begin();
406 BlockUnorderedSet::const_iterator citB = blkSet.begin();
407 BlockUnorderedSet::const_iterator citBp = blkSet.cbegin();
408 BlockUnorderedSet::iterator itE = blkSet.end();
409 BlockUnorderedSet::const_iterator citE = blkSet.end();
410 BlockUnorderedSet::const_iterator citEp = blkSet.cend();
411 REQUIRE( itB == blkSet.begin() );
412 REQUIRE( itB == blkSet.cbegin() );
413 REQUIRE( citB == blkSet.begin() );
414 REQUIRE( citB == blkSet.cbegin() );
415 REQUIRE( citBp == blkSet.cbegin() );
416 REQUIRE( itE == blkSet.end() );
417 REQUIRE( itE == blkSet.cend() );
418 REQUIRE( citE == blkSet.end() );
419 REQUIRE( citE == blkSet.cend() );
420 REQUIRE( citEp == blkSet.cend() );
421 REQUIRE( itB != itE );
422 REQUIRE( itB != citE );
423 REQUIRE( itB != citEp );
424 REQUIRE( citB != itE );
425 REQUIRE( citB != citE );
426 REQUIRE( citB != citEp );
427 REQUIRE( citBp != itE );
428 REQUIRE( citBp != citE );
429 REQUIRE( citBp != citEp );
430 }
431}
432
433SCENARIO( "UnorderedSetByBlock< PointVector< 2, int > unit tests with 64 bits blocks", "[unorderedsetbyblock][2d]" )
434{
435 typedef PointVector< 2, int32_t > Point;
436 typedef std::unordered_set< Point > StdUnorderedSet;
437 typedef Splitter< Point, DGtal::uint64_t > Splitter64;
438 typedef UnorderedSetByBlock< Point, Splitter64 > BlockUnorderedSet;
439
440 const size_t nb_inserted = 10000;
441 const size_t nb_sought = 200;
442 const size_t nb_erased = 100;
443
444 StdUnorderedSet stdSet;
445 BlockUnorderedSet blkSet;
446 for ( size_t i = 0; i < nb_inserted; i++ )
447 {
448 Point p = randomPoint<Point>( 200 );
449 stdSet.insert( p );
450 blkSet.insert( p );
451 }
452 WHEN( "Inserting identical elements in std::unordered_set<> and in UnorderedSetByBlock<>, they contains the same number of elements" ) {
453 REQUIRE( blkSet.size() <= nb_inserted );
454 REQUIRE( blkSet.size() == stdSet.size() );
455 }
456 WHEN( "Cloning identical std::unordered_set<> and UnorderedSetByBlock<>, they contains the same number of elements" ) {
457 StdUnorderedSet stdSet2( stdSet );
458 BlockUnorderedSet blkSet2( blkSet );
459 REQUIRE( blkSet2.size() == blkSet.size() );
460 REQUIRE( blkSet2.size() == stdSet2.size() );
461 }
462 WHEN( "Traversing identical std::unordered_set<> and UnorderedSetByBlock<>, they traverse the same elements" ) {
463 std::vector< Point > stdTrv;
464 std::vector< Point > blkTrv;
465 for ( auto&& p : stdSet ) stdTrv.push_back( p );
466 for ( auto&& p : blkSet ) blkTrv.push_back( p );
467 REQUIRE( blkTrv.size() == stdTrv.size() );
468 std::sort( stdTrv.begin(), stdTrv.end() );
469 std::sort( blkTrv.begin(), blkTrv.end() );
470 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
471 }
472 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `count`" ) {
473 std::vector< Point > stdFound, stdNotFound;
474 std::vector< Point > blkFound, blkNotFound;
475 for ( size_t i = 0; i < nb_sought; i++ )
476 {
477 Point p = randomPoint<Point>( 10 );
478 if ( stdSet.count( p ) != 0 ) stdFound.push_back( p );
479 else stdNotFound.push_back( p );
480 if ( blkSet.count( p ) != 0 ) blkFound.push_back( p );
481 else blkNotFound.push_back( p );
482 }
483 REQUIRE( blkFound .size() == stdFound .size() );
484 REQUIRE( blkNotFound.size() == stdNotFound.size() );
485 std::sort( stdFound .begin(), stdFound .end() );
486 std::sort( stdNotFound.begin(), stdNotFound.end() );
487 std::sort( blkFound .begin(), blkFound .end() );
488 std::sort( blkNotFound.begin(), blkNotFound.end() );
489 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
490 blkFound.cbegin() ) );
491 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
492 blkNotFound.cbegin() ) );
493 }
494 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `find`" ) {
495 std::vector< Point > stdFound, stdNotFound;
496 std::vector< Point > blkFound, blkNotFound;
497 size_t std_nb_value_ok = 0;
498 size_t blk_nb_value_ok = 0;
499 for ( size_t i = 0; i < nb_sought; i++ )
500 {
501 Point p = randomPoint<Point>( 10 );
502 const auto stdIt = stdSet.find( p );
503 if ( stdIt != stdSet.end() )
504 {
505 stdFound.push_back( p );
506 std_nb_value_ok += ( *stdIt == p ) ? 1 : 0;
507 }
508 else stdNotFound.push_back( p );
509 const auto blkIt = blkSet.find( p );
510 if ( blkIt != blkSet.end() )
511 {
512 blkFound.push_back( p );
513 blk_nb_value_ok += ( *blkIt == p ) ? 1 : 0;
514 }
515 else blkNotFound.push_back( p );
516 }
517 REQUIRE( blkFound .size() == stdFound .size() );
518 REQUIRE( blkNotFound.size() == stdNotFound.size() );
519 std::sort( stdFound .begin(), stdFound .end() );
520 std::sort( stdNotFound.begin(), stdNotFound.end() );
521 std::sort( blkFound .begin(), blkFound .end() );
522 std::sort( blkNotFound.begin(), blkNotFound.end() );
523 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
524 blkFound.cbegin() ) );
525 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
526 blkNotFound.cbegin() ) );
527 REQUIRE( std_nb_value_ok == stdFound.size() );
528 REQUIRE( blk_nb_value_ok == std_nb_value_ok );
529 REQUIRE( blk_nb_value_ok == blkFound.size() );
530 }
531 WHEN( "Erasing elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are left" ) {
532 std::vector< Point > stdErase;
533 std::vector< Point > blkErase;
534 size_t std_nb_erase_ok = 0;
535 size_t blk_nb_erase_ok = 0;
536 for ( size_t i = 0; i < nb_erased; i++ )
537 {
538 Point p = randomPoint<Point>( 10 );
539 auto stdFindIt = stdSet.find ( p );
540 auto stdIsErased = stdSet.erase( p );
541 if ( stdFindIt != stdSet.cend() )
542 {
543 std_nb_erase_ok += ( stdIsErased != 0 ) ? 1 : 0;
544 stdErase.push_back( p );
545 }
546 else std_nb_erase_ok += ( stdIsErased == 0 ) ? 1 : 0;
547 auto blkFindIt = blkSet.find ( p );
548 auto blkIsErased = blkSet.erase( p );
549 if ( blkFindIt != blkSet.cend() )
550 {
551 blk_nb_erase_ok += ( blkIsErased != 0 ) ? 1 : 0;
552 blkErase.push_back( p );
553 }
554 else blk_nb_erase_ok += ( blkIsErased == 0 ) ? 1 : 0;
555 }
556 REQUIRE( blkSet .size() == stdSet .size() );
557 REQUIRE( blkErase.size() == stdErase.size() );
558 REQUIRE( blk_nb_erase_ok == std_nb_erase_ok );
559 std::vector< Point > stdTrv;
560 std::vector< Point > blkTrv;
561 for ( auto&& p : stdSet ) stdTrv.push_back( p );
562 for ( auto&& p : blkSet ) blkTrv.push_back( p );
563 REQUIRE( blkTrv.size() == stdTrv.size() );
564 std::sort( stdTrv.begin(), stdTrv.end() );
565 std::sort( blkTrv.begin(), blkTrv.end() );
566 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
567 }
568 WHEN( "Erasing a range in identical std::unordered_set<> and UnorderedSetByBlock<>, the same number of elements is left" ) {
569 auto nb_std_before = stdSet.size();
570 auto nb_blk_before = blkSet.size();
571 auto stdItB = stdSet.begin(); std::advance( stdItB, 10 );
572 auto blkItB = blkSet.begin(); std::advance( blkItB, 10 );
573 auto stdItE = stdItB; std::advance( stdItE, 20 );
574 auto blkItE = blkItB; std::advance( blkItE, 20 );
575 stdSet.erase( stdItB, stdItE );
576 blkSet.erase( blkItB, blkItE );
577 size_t nb_std = std::distance(stdSet.begin(), stdSet.end());
578 size_t nb_blk = std::distance(blkSet.begin(), blkSet.end());
579 REQUIRE( stdSet.size() == nb_std );
580 REQUIRE( stdSet.size() == nb_std_before - 20 );
581 REQUIRE( blkSet.size() == nb_blk );
582 REQUIRE( blkSet.size() == nb_blk_before - 20 );
583 REQUIRE( blkSet.size() == stdSet.size() );
584 }
585 THEN( "The memory usage of UnorderedSetByBlock<> is inferior to the one of std::unordered_set<>" ) {
586 const auto stdMem = blkSet.memory_usage_unordered_set();
587 const auto blkMem = blkSet.memory_usage();
588 REQUIRE( blkMem <= stdMem );
589 }
590
591
592 THEN( "Conparisons and valid assignments between iterator and const_iterator should be seamless for the user" ) {
593 BlockUnorderedSet::iterator itB = blkSet.begin();
594 BlockUnorderedSet::const_iterator citB = blkSet.begin();
595 BlockUnorderedSet::const_iterator citBp = blkSet.cbegin();
596 BlockUnorderedSet::iterator itE = blkSet.end();
597 BlockUnorderedSet::const_iterator citE = blkSet.end();
598 BlockUnorderedSet::const_iterator citEp = blkSet.cend();
599 REQUIRE( itB == blkSet.begin() );
600 REQUIRE( itB == blkSet.cbegin() );
601 REQUIRE( citB == blkSet.begin() );
602 REQUIRE( citB == blkSet.cbegin() );
603 REQUIRE( citBp == blkSet.cbegin() );
604 REQUIRE( itE == blkSet.end() );
605 REQUIRE( itE == blkSet.cend() );
606 REQUIRE( citE == blkSet.end() );
607 REQUIRE( citE == blkSet.cend() );
608 REQUIRE( citEp == blkSet.cend() );
609 REQUIRE( itB != itE );
610 REQUIRE( itB != citE );
611 REQUIRE( itB != citEp );
612 REQUIRE( citB != itE );
613 REQUIRE( citB != citE );
614 REQUIRE( citB != citEp );
615 REQUIRE( citBp != itE );
616 REQUIRE( citBp != citE );
617 REQUIRE( citBp != citEp );
618 }
619}
620
621
622SCENARIO( "UnorderedSetByBlock< PointVector< 3, int64 > unit tests with 64 bits blocks", "[unorderedsetbyblock][3d]" )
623{
624 typedef PointVector< 3, int64_t > Point;
625 typedef std::unordered_set< Point > StdUnorderedSet;
626 typedef Splitter< Point, DGtal::uint64_t > Splitter64;
627 typedef UnorderedSetByBlock< Point, Splitter64 > BlockUnorderedSet;
628
629 const size_t nb_inserted = 40000;
630 const size_t nb_sought = 2000;
631 const size_t nb_erased = 1000;
632
633 StdUnorderedSet stdSet;
634 BlockUnorderedSet blkSet;
635 for ( size_t i = 0; i < nb_inserted; i++ )
636 {
637 Point p = randomPoint<Point>( 100 );
638 stdSet.insert( p );
639 blkSet.insert( p );
640 }
641 WHEN( "Inserting identical elements in std::unordered_set<> and in UnorderedSetByBlock<>, they contains the same number of elements" ) {
642 REQUIRE( blkSet.size() <= nb_inserted );
643 REQUIRE( blkSet.size() == stdSet.size() );
644 }
645 WHEN( "Cloning identical std::unordered_set<> and UnorderedSetByBlock<>, they contains the same number of elements" ) {
646 StdUnorderedSet stdSet2( stdSet );
647 BlockUnorderedSet blkSet2( blkSet );
648 REQUIRE( blkSet2.size() == blkSet.size() );
649 REQUIRE( blkSet2.size() == stdSet2.size() );
650 }
651 WHEN( "Traversing identical std::unordered_set<> and UnorderedSetByBlock<>, they traverse the same elements" ) {
652 std::vector< Point > stdTrv;
653 std::vector< Point > blkTrv;
654 for ( auto&& p : stdSet ) stdTrv.push_back( p );
655 for ( auto&& p : blkSet ) blkTrv.push_back( p );
656 REQUIRE( blkTrv.size() == stdTrv.size() );
657 std::sort( stdTrv.begin(), stdTrv.end() );
658 std::sort( blkTrv.begin(), blkTrv.end() );
659 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
660 }
661 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `count`" ) {
662 std::vector< Point > stdFound, stdNotFound;
663 std::vector< Point > blkFound, blkNotFound;
664 for ( size_t i = 0; i < nb_sought; i++ )
665 {
666 Point p = randomPoint<Point>( 10 );
667 if ( stdSet.count( p ) != 0 ) stdFound.push_back( p );
668 else stdNotFound.push_back( p );
669 if ( blkSet.count( p ) != 0 ) blkFound.push_back( p );
670 else blkNotFound.push_back( p );
671 }
672 REQUIRE( blkFound .size() == stdFound .size() );
673 REQUIRE( blkNotFound.size() == stdNotFound.size() );
674 std::sort( stdFound .begin(), stdFound .end() );
675 std::sort( stdNotFound.begin(), stdNotFound.end() );
676 std::sort( blkFound .begin(), blkFound .end() );
677 std::sort( blkNotFound.begin(), blkNotFound.end() );
678 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
679 blkFound.cbegin() ) );
680 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
681 blkNotFound.cbegin() ) );
682 }
683 WHEN( "Looking for elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are find with method `find`" ) {
684 std::vector< Point > stdFound, stdNotFound;
685 std::vector< Point > blkFound, blkNotFound;
686 size_t std_nb_value_ok = 0;
687 size_t blk_nb_value_ok = 0;
688 for ( size_t i = 0; i < nb_sought; i++ )
689 {
690 Point p = randomPoint<Point>( 10 );
691 const auto stdIt = stdSet.find( p );
692 if ( stdIt != stdSet.end() )
693 {
694 stdFound.push_back( p );
695 std_nb_value_ok += ( *stdIt == p ) ? 1 : 0;
696 }
697 else stdNotFound.push_back( p );
698 const auto blkIt = blkSet.find( p );
699 if ( blkIt != blkSet.end() )
700 {
701 blkFound.push_back( p );
702 blk_nb_value_ok += ( *blkIt == p ) ? 1 : 0;
703 }
704 else blkNotFound.push_back( p );
705 }
706 REQUIRE( blkFound .size() == stdFound .size() );
707 REQUIRE( blkNotFound.size() == stdNotFound.size() );
708 std::sort( stdFound .begin(), stdFound .end() );
709 std::sort( stdNotFound.begin(), stdNotFound.end() );
710 std::sort( blkFound .begin(), blkFound .end() );
711 std::sort( blkNotFound.begin(), blkNotFound.end() );
712 REQUIRE( std::equal( stdFound.cbegin(), stdFound.cend(),
713 blkFound.cbegin() ) );
714 REQUIRE( std::equal( stdNotFound.cbegin(), stdNotFound.cend(),
715 blkNotFound.cbegin() ) );
716 REQUIRE( std_nb_value_ok == stdFound.size() );
717 REQUIRE( blk_nb_value_ok == std_nb_value_ok );
718 REQUIRE( blk_nb_value_ok == blkFound.size() );
719 }
720 WHEN( "Erasing elements in identical std::unordered_set<> and UnorderedSetByBlock<>, the same elements are left" ) {
721 std::vector< Point > stdErase;
722 std::vector< Point > blkErase;
723 size_t std_nb_erase_ok = 0;
724 size_t blk_nb_erase_ok = 0;
725 for ( size_t i = 0; i < nb_erased; i++ )
726 {
727 Point p = randomPoint<Point>( 10 );
728 auto stdFindIt = stdSet.find ( p );
729 auto stdIsErased = stdSet.erase( p );
730 if ( stdFindIt != stdSet.cend() )
731 {
732 std_nb_erase_ok += ( stdIsErased != 0 ) ? 1 : 0;
733 stdErase.push_back( p );
734 }
735 else std_nb_erase_ok += ( stdIsErased == 0 ) ? 1 : 0;
736 auto blkFindIt = blkSet.find ( p );
737 auto blkIsErased = blkSet.erase( p );
738 if ( blkFindIt != blkSet.cend() )
739 {
740 blk_nb_erase_ok += ( blkIsErased != 0 ) ? 1 : 0;
741 blkErase.push_back( p );
742 }
743 else blk_nb_erase_ok += ( blkIsErased == 0 ) ? 1 : 0;
744 }
745 REQUIRE( blkSet .size() == stdSet .size() );
746 REQUIRE( blkErase.size() == stdErase.size() );
747 REQUIRE( blk_nb_erase_ok == std_nb_erase_ok );
748 std::vector< Point > stdTrv;
749 std::vector< Point > blkTrv;
750 for ( auto&& p : stdSet ) stdTrv.push_back( p );
751 for ( auto&& p : blkSet ) blkTrv.push_back( p );
752 REQUIRE( blkTrv.size() == stdTrv.size() );
753 std::sort( stdTrv.begin(), stdTrv.end() );
754 std::sort( blkTrv.begin(), blkTrv.end() );
755 REQUIRE( std::equal( stdTrv.cbegin(), stdTrv.cend(), blkTrv.cbegin() ) );
756 }
757 WHEN( "Erasing a range in identical std::unordered_set<> and UnorderedSetByBlock<>, the same number of elements is left" ) {
758 auto nb_std_before = stdSet.size();
759 auto nb_blk_before = blkSet.size();
760 auto stdItB = stdSet.begin(); std::advance( stdItB, 10 );
761 auto blkItB = blkSet.begin(); std::advance( blkItB, 10 );
762 auto stdItE = stdItB; std::advance( stdItE, 20 );
763 auto blkItE = blkItB; std::advance( blkItE, 20 );
764 stdSet.erase( stdItB, stdItE );
765 blkSet.erase( blkItB, blkItE );
766 size_t nb_std = std::distance(stdSet.begin(), stdSet.end());
767 size_t nb_blk = std::distance(blkSet.begin(), blkSet.end());
768 REQUIRE( stdSet.size() == nb_std );
769 REQUIRE( stdSet.size() == nb_std_before - 20 );
770 REQUIRE( blkSet.size() == nb_blk );
771 REQUIRE( blkSet.size() == nb_blk_before - 20 );
772 REQUIRE( blkSet.size() == stdSet.size() );
773 }
774 THEN( "The memory usage of UnorderedSetByBlock<> is inferior to the one of std::unordered_set<>" ) {
775 const auto stdMem = blkSet.memory_usage_unordered_set();
776 const auto blkMem = blkSet.memory_usage();
777 REQUIRE( blkMem <= stdMem );
778 }
779
780
781 THEN( "Conparisons and valid assignments between iterator and const_iterator should be seamless for the user" ) {
782 BlockUnorderedSet::iterator itB = blkSet.begin();
783 BlockUnorderedSet::const_iterator citB = blkSet.begin();
784 BlockUnorderedSet::const_iterator citBp = blkSet.cbegin();
785 BlockUnorderedSet::iterator itE = blkSet.end();
786 BlockUnorderedSet::const_iterator citE = blkSet.end();
787 BlockUnorderedSet::const_iterator citEp = blkSet.cend();
788 REQUIRE( itB == blkSet.begin() );
789 REQUIRE( itB == blkSet.cbegin() );
790 REQUIRE( citB == blkSet.begin() );
791 REQUIRE( citB == blkSet.cbegin() );
792 REQUIRE( citBp == blkSet.cbegin() );
793 REQUIRE( itE == blkSet.end() );
794 REQUIRE( itE == blkSet.cend() );
795 REQUIRE( citE == blkSet.end() );
796 REQUIRE( citE == blkSet.cend() );
797 REQUIRE( citEp == blkSet.cend() );
798 REQUIRE( itB != itE );
799 REQUIRE( itB != citE );
800 REQUIRE( itB != citEp );
801 REQUIRE( citB != itE );
802 REQUIRE( citB != citE );
803 REQUIRE( citB != citEp );
804 REQUIRE( citBp != itE );
805 REQUIRE( citBp != citE );
806 REQUIRE( citBp != citEp );
807 }
808}
809
810
811
812// //
DGtal::PointVector
Aim: Implements basic operations that will be used in Point and Vector classes.
Definition PointVector.h:593
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition ClosedIntegerHalfPlane.h:49
DGtal::Dimension
DGtal::uint32_t Dimension
Definition Common.h:136
std
STL namespace.
Point
MyPointD Point
Definition testClone2.cpp:383
REQUIRE
REQUIRE(domain.isInside(aPoint))
SCENARIO
SCENARIO("UnorderedSetByBlock< PointVector< 2, int > unit tests with 32 bits blocks", "[unorderedsetbyblock][2d]")
Definition testUnorderedSetByBlock.cpp:58
randomPoint
Point randomPoint(int S)
Definition testUnorderedSetByBlock.cpp:45