DGtal  1.5.beta
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 
41 using namespace std;
42 using namespace DGtal;
43 
44 template < typename Point >
45 Point 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 
58 SCENARIO( "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 
246 SCENARIO( "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 
433 SCENARIO( "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 
622 SCENARIO( "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.
DGtal::Dimension
DGtal::uint32_t Dimension
Definition: Common.h:136
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