DGtal  1.3.beta
testSetFunctions.cpp
1 
30 #include <iostream>
32 #include <vector>
33 #include <set>
34 #include <random>
35 #include <unordered_set>
36 #include "DGtal/base/Common.h"
37 #include "DGtal/base/SetFunctions.h"
38 #include "DGtalCatch.h"
40 
41 using namespace DGtal;
42 using namespace DGtal::functions;
43 //using DGtal::functions::setops::operator|;
44 using DGtal::functions::setops::operator&;
45 using DGtal::functions::setops::operator-;
46 using DGtal::functions::setops::operator^;
47 
48 
50 TEMPLATE_TEST_CASE( "SetFunctions module unit tests", "[set_functions]",
51  std::vector<int>,
52  std::list<int>,
53  std::set<int>,
54  std::unordered_set<int> )
55 
56 {
57  int S1[ 10 ] = { 4, 15, 20, 17, 9, 7, 13, 12, 1, 3 };
58  int S2[ 6 ] = { 17, 14, 19, 2, 3, 4 };
59  TestType C1( S1, S1 + 10 );
60  TestType C2( S2, S2 + 6 );
61  TestType C1_minus_C2 = C1 - C2;
62  REQUIRE( C1_minus_C2.size() == 7 );
63  TestType C2_minus_C1 = C2 - C1;
64  REQUIRE( C2_minus_C1.size() == 3 );
65  REQUIRE( ( C1_minus_C2 - C1 ).size() == 0 );
66  REQUIRE( ( C2_minus_C1 - C2 ).size() == 0 );
67  REQUIRE( ( C1_minus_C2 - C2 ).size() == C1_minus_C2.size() );
68  REQUIRE( ( C2_minus_C1 - C1 ).size() == C2_minus_C1.size() );
69  TestType C1_union_C2 = DGtal::functions::setops::operator|(C1 , C2);
70  TestType C2_union_C1 = DGtal::functions::setops::operator|(C2 , C1);
71  REQUIRE( C1_union_C2.size() == 13 );
72  REQUIRE( C1_union_C2.size() == C2_union_C1.size() );
73  REQUIRE( ( DGtal::functions::setops::operator|(C1_minus_C2 , C2) ).size() == (DGtal::functions::setops::operator|(C2_minus_C1 , C1) ).size() );
74 
75  TestType C1_intersection_C2 = C1 & C2;
76  TestType C2_intersection_C1 = C2 & C1;
77  REQUIRE( C1_intersection_C2.size() == 3 );
78  REQUIRE( C1_intersection_C2.size() == C2_intersection_C1.size() );
79 
80  REQUIRE( ( DGtal::functions::setops::operator|(DGtal::functions::setops::operator|(C1_minus_C2 , C1_intersection_C2) , C2_minus_C1) ).size() == C1_union_C2.size() );
81 
82  TestType C1_symdiff_C2 = C1 ^ C2;
83  TestType C2_symdiff_C1 = C2 ^ C1;
84  REQUIRE( C1_symdiff_C2.size() == C2_symdiff_C1.size() );
85  REQUIRE( C1_symdiff_C2.size() == ( C1_union_C2 - C1_intersection_C2 ).size() );
86  REQUIRE( C1_symdiff_C2.size() == ( DGtal::functions::setops::operator|(C1_minus_C2 , C2_minus_C1) ).size() );
87 
88  REQUIRE( isEqual( C1_symdiff_C2, C1_union_C2 - C1_intersection_C2 ) );
89  REQUIRE( isEqual( C1_symdiff_C2, DGtal::functions::setops::operator|(C1_minus_C2 , C2_minus_C1) ) );
90  REQUIRE( isEqual( DGtal::functions::setops::operator|(DGtal::functions::setops::operator|(C1_minus_C2 , C1_intersection_C2) , C2_minus_C1), C1_union_C2 ) );
91  REQUIRE( isSubset( C1_minus_C2, C1 ) );
92  REQUIRE( ! isSubset( C1_minus_C2, C2 ) );
93  REQUIRE( isSubset( C2_minus_C1, C2 ) );
94  REQUIRE( ! isSubset( C2_minus_C1, C1 ) );
95  REQUIRE( isSubset( C1, C1_union_C2 ) );
96  REQUIRE( isSubset( C2, C1_union_C2 ) );
97  REQUIRE( isSubset( C1_intersection_C2, C1 ) );
98  REQUIRE( isSubset( C1_intersection_C2, C2 ) );
99  REQUIRE( isSubset( C1_symdiff_C2, C1_union_C2 ) );
100  REQUIRE( ! isSubset( C1, C1_symdiff_C2 ) );
101  REQUIRE( ! isSubset( C2, C1_symdiff_C2 ) );
102 }
103 
104 
105 static const int NB = 10000;
106 static std::default_random_engine generator;
107 static std::uniform_int_distribution<int> distribution(1,NB);
108 
109 int randomNB( )
110 {
111  return distribution(generator);
112 }
113 
115 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator | (sequences)", "[set_functions]",
116  std::vector<int> )
117 {
118  typedef typename TestType::size_type Size;
119  std::set<int> S1;
120  std::set<int> S2;
121  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
122  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
123  TestType A( S1.begin(), S1.end() );
124  TestType B( S2.begin(), S2.end() );
125  TestType AorB;
126  std::random_device rd;
127  std::mt19937 g(rd());
128 
129  std::shuffle( A.begin(), A.end(), g);
130  std::shuffle( B.begin(), B.end(), g);
131 
132  SECTION( " - benchmark set operators |" )
133  {
135  }
136  Size size_A = A.size();
137  Size size_B = B.size();
138  Size size_AorB = AorB.size();
139  REQUIRE( size_AorB >= std::max( size_A, size_B ) );
140 }
141 
142 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator | (sets)", "[set_functions]",
143  std::set<int>,
144  std::unordered_set<int> )
145 {
146  typedef typename TestType::size_type Size;
147  std::set<int> S1;
148  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
149  std::set<int> S2;
150  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
151  TestType A( S1.begin(), S1.end() );
152  TestType B( S2.begin(), S2.end() );
153  TestType AorB;
154 
155  SECTION( " - benchmark set operators |" )
156  {
158  }
159  Size size_A = A.size();
160  Size size_B = B.size();
161  Size size_AorB = AorB.size();
162  REQUIRE( size_AorB >= std::max( size_A, size_B ) );
163 }
164 
166 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator & (sequences)", "[set_functions]",
167  std::vector<int> )
168 {
169  typedef typename TestType::size_type Size;
170  std::set<int> S1;
171  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
172  std::set<int> S2;
173  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
174  TestType A( S1.begin(), S1.end() );
175  TestType B( S2.begin(), S2.end() );
176  TestType AandB;
177  std::random_device rd;
178  std::mt19937 g(rd());
179 
180  std::shuffle( A.begin(), A.end(), g );
181  std::shuffle( B.begin(), B.end(), g );
182 
183  SECTION( " - benchmark set operators &" )
184  {
185  AandB = A & B;
186  }
187  Size size_A = A.size();
188  Size size_B = B.size();
189  Size size_AandB = AandB.size();
190  REQUIRE( size_AandB <= std::min( size_A, size_B ) );
191 }
192 
193 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator & (sets)", "[set_functions]",
194  std::set<int>,
195  std::unordered_set<int> )
196 {
197  typedef typename TestType::size_type Size;
198  std::set<int> S1;
199  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
200  std::set<int> S2;
201  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
202  TestType A( S1.begin(), S1.end() );
203  TestType B( S2.begin(), S2.end() );
204  TestType AandB;
205 
206  SECTION( " - benchmark set operators &" )
207  {
208  AandB = A & B;
209  }
210  Size size_A = A.size();
211  Size size_B = B.size();
212  Size size_AandB = AandB.size();
213  REQUIRE( size_AandB <= std::min( size_A, size_B ) );
214 }
215 
216 
218 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator - (sequences)", "[set_functions]",
219  std::vector<int> )
220 {
221  typedef typename TestType::size_type Size;
222  std::set<int> S1;
223  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
224  std::set<int> S2;
225  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
226  TestType A( S1.begin(), S1.end() );
227  TestType B( S2.begin(), S2.end() );
228  TestType AminusB;
229  std::random_device rd;
230  std::mt19937 g(rd());
231 
232  std::shuffle( A.begin(), A.end(), g );
233  std::shuffle( B.begin(), B.end(), g );
234 
235  SECTION( " - benchmark set operators -" )
236  {
237  AminusB = A - B;
238  }
239  Size size_A = A.size();
240  Size size_B = B.size();
241  Size size_AminusB = AminusB.size();
242  REQUIRE( size_AminusB <= size_A );
243  boost::ignore_unused_variable_warning(size_B);
244 }
245 
246 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator - (sets)", "[set_functions]",
247  std::set<int>,
248  std::unordered_set<int> )
249 {
250  typedef typename TestType::size_type Size;
251  std::set<int> S1;
252  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
253  std::set<int> S2;
254  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
255  TestType A( S1.begin(), S1.end() );
256  TestType B( S2.begin(), S2.end() );
257  TestType AminusB;
258 
259  SECTION( " - benchmark set operators -" )
260  {
261  AminusB = A - B;
262  }
263  Size size_A = A.size();
264  Size size_B = B.size();
265  Size size_AminusB = AminusB.size();
266  REQUIRE( size_AminusB <= size_A );
267  boost::ignore_unused_variable_warning(size_B);
268 }
269 
270 
272 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator ^ (sequences)", "[set_functions]",
273  std::vector<int> )
274 {
275  typedef typename TestType::size_type Size;
276  std::set<int> S1;
277  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
278  std::set<int> S2;
279  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
280  TestType A( S1.begin(), S1.end() );
281  TestType B( S2.begin(), S2.end() );
282  TestType AxorB;
283  std::random_device rd;
284  std::mt19937 g(rd());
285 
286  std::shuffle( A.begin(), A.end(), g );
287  std::shuffle( B.begin(), B.end(), g );
288 
289  SECTION( " - benchmark set operators ^" )
290  {
291  AxorB = A ^ B;
292  }
293  Size size_A = A.size();
294  Size size_B = B.size();
295  Size size_AxorB = AxorB.size();
296  REQUIRE( size_AxorB <= std::max( size_A, size_B ) );
297 }
298 
299 TEMPLATE_TEST_CASE( "SetFunctions benchmark operator ^ (sets)", "[set_functions]",
300  std::set<int>,
301  std::unordered_set<int> )
302 {
303  typedef typename TestType::size_type Size;
304  std::set<int> S1;
305  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
306  std::set<int> S2;
307  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
308  TestType A( S1.begin(), S1.end() );
309  TestType B( S2.begin(), S2.end() );
310  TestType AxorB;
311 
312  SECTION( " - benchmark set operators ^" )
313  {
314  AxorB = A ^ B;
315  }
316  Size size_A = A.size();
317  Size size_B = B.size();
318  Size size_AxorB = AxorB.size();
319  REQUIRE( size_AxorB <= std::max( size_A, size_B ) );
320 }
321 
322 
323 
324 
max
int max(int a, int b)
Definition: testArithmeticalDSS.cpp:1108
REQUIRE
REQUIRE(domain.isInside(aPoint))
Size
HalfEdgeDataStructure::Size Size
Definition: testHalfEdgeDataStructure.cpp:50
DGtal::functions
functions namespace gathers all DGtal functionsxs.
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::functions::isSubset
bool isSubset(const Container &S1, const Container &S2)
Definition: SetFunctions.h:845
DGtal::functions::setops::operator|
Container operator|(const Container &S1, const Container &S2)
Definition: SetFunctions.h:1303
SECTION
SECTION("Testing constant forward iterators")
Definition: testSimpleRandomAccessRangeFromPoint.cpp:66
TEMPLATE_TEST_CASE
TEMPLATE_TEST_CASE("Star shapes", "move() method", AccFlower, Astroid, Ball, Ellipse, Flower, Lemniscate, NGon, BallImplicit, HyperCubeImplicit, Norm1BallImplicit, RoundedHyperCubeImplicit)
Definition: testShapeMoveCenter.cpp:141
DGtal::functions::isEqual
bool isEqual(const Container &S1, const Container &S2)
Definition: SetFunctions.h:789