DGtal  0.9.3
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_4( "SetFunctions module unit tests", "[set_functions]",
51  Container,
52  std::vector<int>,
53  std::list<int>,
54  std::set<int>,
55  std::unordered_set<int> )
56 
57 {
58  int S1[ 10 ] = { 4, 15, 20, 17, 9, 7, 13, 12, 1, 3 };
59  int S2[ 6 ] = { 17, 14, 19, 2, 3, 4 };
60  Container C1( S1, S1 + 10 );
61  Container C2( S2, S2 + 6 );
62  Container C1_minus_C2 = C1 - C2;
63  REQUIRE( C1_minus_C2.size() == 7 );
64  Container C2_minus_C1 = C2 - C1;
65  REQUIRE( C2_minus_C1.size() == 3 );
66  REQUIRE( ( C1_minus_C2 - C1 ).size() == 0 );
67  REQUIRE( ( C2_minus_C1 - C2 ).size() == 0 );
68  REQUIRE( ( C1_minus_C2 - C2 ).size() == C1_minus_C2.size() );
69  REQUIRE( ( C2_minus_C1 - C1 ).size() == C2_minus_C1.size() );
70  Container C1_union_C2 = DGtal::functions::setops::operator|(C1 , C2);
71  Container C2_union_C1 = DGtal::functions::setops::operator|(C2 , C1);
72  REQUIRE( C1_union_C2.size() == 13 );
73  REQUIRE( C1_union_C2.size() == C2_union_C1.size() );
74  REQUIRE( ( DGtal::functions::setops::operator|(C1_minus_C2 , C2) ).size() == (DGtal::functions::setops::operator|(C2_minus_C1 , C1) ).size() );
75 
76  Container C1_intersection_C2 = C1 & C2;
77  Container C2_intersection_C1 = C2 & C1;
78  REQUIRE( C1_intersection_C2.size() == 3 );
79  REQUIRE( C1_intersection_C2.size() == C2_intersection_C1.size() );
80 
81  REQUIRE( ( DGtal::functions::setops::operator|(DGtal::functions::setops::operator|(C1_minus_C2 , C1_intersection_C2) , C2_minus_C1) ).size() == C1_union_C2.size() );
82 
83  Container C1_symdiff_C2 = C1 ^ C2;
84  Container C2_symdiff_C1 = C2 ^ C1;
85  REQUIRE( C1_symdiff_C2.size() == C2_symdiff_C1.size() );
86  REQUIRE( C1_symdiff_C2.size() == ( C1_union_C2 - C1_intersection_C2 ).size() );
87  REQUIRE( C1_symdiff_C2.size() == ( DGtal::functions::setops::operator|(C1_minus_C2 , C2_minus_C1) ).size() );
88 
89  REQUIRE( isEqual( C1_symdiff_C2, C1_union_C2 - C1_intersection_C2 ) );
90  REQUIRE( isEqual( C1_symdiff_C2, DGtal::functions::setops::operator|(C1_minus_C2 , C2_minus_C1) ) );
91  REQUIRE( isEqual( DGtal::functions::setops::operator|(DGtal::functions::setops::operator|(C1_minus_C2 , C1_intersection_C2) , C2_minus_C1), C1_union_C2 ) );
92  REQUIRE( isSubset( C1_minus_C2, C1 ) );
93  REQUIRE( ! isSubset( C1_minus_C2, C2 ) );
94  REQUIRE( isSubset( C2_minus_C1, C2 ) );
95  REQUIRE( ! isSubset( C2_minus_C1, C1 ) );
96  REQUIRE( isSubset( C1, C1_union_C2 ) );
97  REQUIRE( isSubset( C2, C1_union_C2 ) );
98  REQUIRE( isSubset( C1_intersection_C2, C1 ) );
99  REQUIRE( isSubset( C1_intersection_C2, C2 ) );
100  REQUIRE( isSubset( C1_symdiff_C2, C1_union_C2 ) );
101  REQUIRE( ! isSubset( C1, C1_symdiff_C2 ) );
102  REQUIRE( ! isSubset( C2, C1_symdiff_C2 ) );
103 }
104 
105 
106 static const int NB = 10000;
107 static std::default_random_engine generator;
108 static std::uniform_int_distribution<int> distribution(1,NB);
109 
110 int randomNB( )
111 {
112  return distribution(generator);
113 }
114 
116 TEMPLATE_TEST_CASE_1( "SetFunctions benchmark operator | (sequences)", "[set_functions]",
117  Container,
118  std::vector<int> )
119 {
120  typedef typename Container::size_type Size;
121  std::set<int> S1;
122  std::set<int> S2;
123  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
124  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
125  Container A( S1.begin(), S1.end() );
126  Container B( S2.begin(), S2.end() );
127  Container AorB;
128 
129  std::random_shuffle( A.begin(), A.end() );
130  std::random_shuffle( B.begin(), B.end() );
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_2( "SetFunctions benchmark operator | (sets)", "[set_functions]",
143  Container,
144  std::set<int>,
145  std::unordered_set<int> )
146 {
147  typedef typename Container::size_type Size;
148  std::set<int> S1;
149  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
150  std::set<int> S2;
151  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
152  Container A( S1.begin(), S1.end() );
153  Container B( S2.begin(), S2.end() );
154  Container AorB;
155 
156  SECTION( " - benchmark set operators |" )
157  {
159  }
160  Size size_A = A.size();
161  Size size_B = B.size();
162  Size size_AorB = AorB.size();
163  REQUIRE( size_AorB >= std::max( size_A, size_B ) );
164 }
165 
167 TEMPLATE_TEST_CASE_1( "SetFunctions benchmark operator & (sequences)", "[set_functions]",
168  Container,
169  std::vector<int> )
170 {
171  typedef typename Container::size_type Size;
172  std::set<int> S1;
173  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
174  std::set<int> S2;
175  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
176  Container A( S1.begin(), S1.end() );
177  Container B( S2.begin(), S2.end() );
178  Container AandB;
179 
180  std::random_shuffle( A.begin(), A.end() );
181  std::random_shuffle( B.begin(), B.end() );
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_2( "SetFunctions benchmark operator & (sets)", "[set_functions]",
194  Container,
195  std::set<int>,
196  std::unordered_set<int> )
197 {
198  typedef typename Container::size_type Size;
199  std::set<int> S1;
200  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
201  std::set<int> S2;
202  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
203  Container A( S1.begin(), S1.end() );
204  Container B( S2.begin(), S2.end() );
205  Container AandB;
206 
207  SECTION( " - benchmark set operators &" )
208  {
209  AandB = A & B;
210  }
211  Size size_A = A.size();
212  Size size_B = B.size();
213  Size size_AandB = AandB.size();
214  REQUIRE( size_AandB <= std::min( size_A, size_B ) );
215 }
216 
217 
219 TEMPLATE_TEST_CASE_1( "SetFunctions benchmark operator - (sequences)", "[set_functions]",
220  Container,
221  std::vector<int> )
222 {
223  typedef typename Container::size_type Size;
224  std::set<int> S1;
225  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
226  std::set<int> S2;
227  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
228  Container A( S1.begin(), S1.end() );
229  Container B( S2.begin(), S2.end() );
230  Container AminusB;
231 
232  std::random_shuffle( A.begin(), A.end() );
233  std::random_shuffle( B.begin(), B.end() );
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 }
244 
245 TEMPLATE_TEST_CASE_2( "SetFunctions benchmark operator - (sets)", "[set_functions]",
246  Container,
247  std::set<int>,
248  std::unordered_set<int> )
249 {
250  typedef typename Container::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  Container A( S1.begin(), S1.end() );
256  Container B( S2.begin(), S2.end() );
257  Container 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 }
268 
269 
271 TEMPLATE_TEST_CASE_1( "SetFunctions benchmark operator ^ (sequences)", "[set_functions]",
272  Container,
273  std::vector<int> )
274 {
275  typedef typename Container::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  Container A( S1.begin(), S1.end() );
281  Container B( S2.begin(), S2.end() );
282  Container AxorB;
283 
284  std::random_shuffle( A.begin(), A.end() );
285  std::random_shuffle( B.begin(), B.end() );
286 
287  SECTION( " - benchmark set operators ^" )
288  {
289  AxorB = A ^ B;
290  }
291  Size size_A = A.size();
292  Size size_B = B.size();
293  Size size_AxorB = AxorB.size();
294  REQUIRE( size_AxorB <= std::max( size_A, size_B ) );
295 }
296 
297 TEMPLATE_TEST_CASE_2( "SetFunctions benchmark operator ^ (sets)", "[set_functions]",
298  Container,
299  std::set<int>,
300  std::unordered_set<int> )
301 {
302  typedef typename Container::size_type Size;
303  std::set<int> S1;
304  for ( int i = 0; i < NB; ++i ) S1.insert( randomNB( ) );
305  std::set<int> S2;
306  for ( int i = 0; i < NB; ++i ) S2.insert( randomNB( ) );
307  Container A( S1.begin(), S1.end() );
308  Container B( S2.begin(), S2.end() );
309  Container AxorB;
310 
311  SECTION( " - benchmark set operators ^" )
312  {
313  AxorB = A ^ B;
314  }
315  Size size_A = A.size();
316  Size size_B = B.size();
317  Size size_AxorB = AxorB.size();
318  REQUIRE( size_AxorB <= std::max( size_A, size_B ) );
319 }
320 
321 
322 
323 
REQUIRE(domain.isInside(aPoint))
bool isEqual(const Container &S1, const Container &S2)
Definition: SetFunctions.h:789
DGtal is the top-level namespace which contains all DGtal functions and types.
int max(int a, int b)
bool isSubset(const Container &S1, const Container &S2)
Definition: SetFunctions.h:845
functions namespace gathers all DGtal functionsxs.
Definition: SetFunctions.h:768
Container operator|(const Container &S1, const Container &S2)
SECTION("Testing constant forward iterators")