1 // Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information.
2
3 #include <iostream>
4 #include <iomanip>
5 #include <vector>
6 #include <functional>
7 #include <algorithm>
8 #include <numeric>
9 #include <iterator>
10 #include <string>
11 #include <complex>
12
13 #include <ctime>
14 #include <cstddef>
15
16 #include <boost/lambda/core.hpp>
17 #include <boost/lambda/lambda.hpp>
18 #include <boost/iterator.hpp>
19
20 #include "cpplinq/linq.hpp"
21
22 #include "testbench.hpp"
23
24 using namespace std;
25 using namespace cpplinq;
26
27 struct int_iter
28 : std::iterator<std::random_access_iterator_tag, int, std::ptrdiff_t, int*, int>
29 {
int_iterint_iter30 int_iter(value_type i = 0, value_type step = 1) : value(i), step(step)
31 {}
32
operator *int_iter33 value_type operator*() const {
34 return value;
35 }
operator ++int_iter36 int_iter& operator++() {
37 value+=step; return *this;
38 }
operator --int_iter39 int_iter& operator--() {
40 value-=step; return *this;
41 }
operator +=int_iter42 int_iter& operator+=(std::ptrdiff_t offset) {
43 value += step*offset; return *this;
44 }
operator -=int_iter45 int_iter& operator-=(std::ptrdiff_t offset) {
46 value -= step*offset; return *this;
47 }
operator -int_iter48 std::ptrdiff_t operator-(int_iter rhs) const {
49 return std::ptrdiff_t((value - rhs.value)/step);
50 }
operator ==int_iter51 bool operator==(int_iter other) const {
52 return value == other.value;
53 }
operator !=int_iter54 bool operator!=(int_iter other) const {
55 return !(*this == other);
56 }
operator <int_iter57 bool operator<(int_iter other) const { return (*this - other) < 0; }
operator >int_iter58 bool operator>(int_iter other) const { return (*this - other) > 0; }
operator <=int_iter59 bool operator<=(int_iter other) const { return (*this - other) <= 0; }
operator >=int_iter60 bool operator>=(int_iter other) const { return (*this - other) >= 0; }
61
62 value_type value;
63 value_type step;
64 };
operator +(int_iter lhs,std::ptrdiff_t rhs)65 int_iter operator+(int_iter lhs, std::ptrdiff_t rhs) {
66 return lhs+=rhs;
67 }
operator +(std::ptrdiff_t lhs,int_iter rhs)68 int_iter operator+(std::ptrdiff_t lhs, int_iter rhs) {
69 return rhs+=lhs;
70 }
operator -(int_iter lhs,std::ptrdiff_t rhs)71 int_iter operator-(int_iter lhs, std::ptrdiff_t rhs) {
72 return lhs-=rhs;
73 }
74 struct int_range
75 {
76 typedef int_iter iterator;
77 typedef int_iter::value_type value_type;
int_rangeint_range78 int_range(value_type begin, value_type end, value_type step = 1)
79 : b(begin, step), e(end, step)
80 {
81 if (step == 0) {
82 throw std::logic_error("bad step");
83 }
84 if (abs(end - begin) % abs(step) != 0) {
85 end -= (end-begin)%abs(step);
86 }
87 }
beginint_range88 int_iter begin() const { return int_iter(b);}
endint_range89 int_iter end() const { return int_iter(e); }
90
91 iterator b, e;
92 };
93
vector_range(int start,int end)94 vector<int> vector_range(int start, int end)
95 {
96 vector<int> v;
97 for (int i = start; i < end; ++i)
98 v.push_back(i);
99 return v;
100 }
101
TEST(test_selection)102 TEST(test_selection)
103 {
104 vector<int> v = vector_range(0, 10);
105
106 auto v2 = from(v)
107 .select([](int x) { return x*2; });
108
109 auto result = accumulate(begin(v2), end(v2), int(0));
110
111 VERIFY_EQ(90, result);
112 }
113
TEST(test_where)114 TEST(test_where)
115 {
116 vector<int> v = vector_range(0, 10);
117 auto v2 = from(v)
118 .where([](int x) { return x % 2;});
119
120 VERIFY_EQ(1, *v2.begin());
121
122 auto result = accumulate(begin(v2), end(v2), int(0));
123
124 VERIFY_EQ(25, result);
125 }
126
127
is_prime(int x)128 bool is_prime(int x) {
129 if (x < 2) {return false;}
130 if (x == 2) {return true;}
131 for (int i = x/2; i >= 2; --i) {
132 if (x % i == 0) { return false;}
133 }
134 return true;
135 };
136
137 template <class It>
display(It start,It end)138 void display(It start, It end)
139 {
140 int i = 0;
141 for_each(start, end, [&](typename iterator_traits<It>::value_type x){
142 if (++i % 10 == 0) {
143 cout << endl;
144 }
145 cout << x << " ";
146 });
147 cout << endl;
148 }
149
TEST(test_whereselect)150 TEST(test_whereselect)
151 {
152 auto xs = int_range(0,100);
153 auto ys = from(xs)
154 .where(is_prime)
155 .select([](int x){ return x*x; });
156 auto result = accumulate(begin(ys), end(ys), int(0));
157
158 //display(begin(ys), end(ys));
159
160 // primes < 100
161 VERIFY_EQ(65796, result);
162 }
TEST(test_where_modification)163 TEST(test_where_modification)
164 {
165 vector<int> xs = vector_range(0, 100);
166
167 auto ys = from(xs)
168 .where(is_prime);
169 std::fill(begin(ys), end(ys), int(0));
170
171 auto result = accumulate(begin(xs), end(xs), int(0));
172
173 //display(begin(ys), end(ys));
174
175 // non-primes < 100
176 VERIFY_EQ(3890, result);
177 }
178
TEST(test_where_any)179 TEST(test_where_any)
180 {
181 using namespace boost::lambda;
182
183 vector<int> xs(200);
184 fill(begin(xs), end(xs), int(0));
185 auto it = xs.begin();
186 *it = 2;
187
188 for(;;) {
189 auto last = *it++;
190 auto primes = from(int_range(last+1, -1))
191 .where([&](int x){
192 return from(begin(xs), it)
193 //.all([&](int d){return x%d;});
194 .all(x % boost::lambda::_1);
195 });
196 *it = *primes.begin();
197 if ((*it)>=100) {
198 break;
199 }
200 };
201 xs.erase(it, xs.end());
202
203 auto result = accumulate(begin(xs), end(xs), int(0));
204
205 //display(begin(xs), end(xs));
206
207 // primes < 100
208 VERIFY_EQ(1060, result);
209 }
210
TEST(test_take)211 TEST(test_take)
212 {
213 auto zero_one = from(int_range(0, -1))
214 .take(2);
215
216 VERIFY_EQ(0, zero_one[0]);
217 VERIFY_EQ(1, zero_one[1]);
218
219 auto ten = from(int_range(0, -1))
220 .skip(10);
221
222 VERIFY_EQ(10, ten[0]);
223 VERIFY_EQ(11, ten[1]);
224 }
225
some_primes(std::size_t howMany)226 vector<int> some_primes(std::size_t howMany)
227 {
228 auto xs = from(int_range(0, -1))
229 .where(is_prime)
230 .take(howMany);
231 auto v = vector<int>(begin(xs), end(xs));
232 return v;
233 }
234
TEST(test_groupby)235 TEST(test_groupby)
236 {
237 auto xs = some_primes(40);
238 //display(begin(xs), end(xs));
239
240 auto grouped =
241 from(xs)
242 .groupby([](int i){return i % 10; });
243
244 VERIFY_EQ(6, from(grouped).count());
245 for(auto group = begin(grouped); group != end(grouped); ++group) {
246 //cout << "key = " << group->key << endl
247 // << "| ";
248 for (auto elem = group->begin(); elem != group->end(); ++elem) {
249 //cout << *elem << " ";
250 }
251 //cout << endl;
252
253 switch(group->key) {
254 case 2: VERIFY_EQ(1, from(*group).count()); break;
255 case 3: VERIFY_EQ(11, from(*group).count()); break;
256 case 5: VERIFY_EQ(1, from(*group).count()); break;
257 case 7: VERIFY_EQ(11, from(*group).count()); break;
258 case 1: VERIFY_EQ(8, from(*group).count()); break;
259 case 9: VERIFY_EQ(8, from(*group).count()); break;
260 }
261 }
262 }
263
TEST(test_symbolname)264 TEST(test_symbolname)
265 {
266 auto complexQuery =
267 from(int_range(0,100000))
268 .select([](int x){ return x*2;})
269 .where([](int x){ return x%7; })
270 .skip(20);
271
272 //cout << " type name: " << typeid(complexQuery1).name() << endl;
273
274
275 //auto complexQuery =
276 // complexQuery1.groupby([](int x) { return x%5; })
277 // .take(3)
278 // ;
279
280
281 cout << "type name: " << typeid(complexQuery).name() << endl;
282 cout << "type name length: " << strlen(typeid(complexQuery).name()) << endl;
283
284 auto iter = complexQuery.begin();
285 cout << "iterator name: " << typeid(iter).name() << endl;
286 cout << "iterator name length: " << strlen(typeid(iter).name()) << endl;
287 }
288
TEST(test_cast)289 TEST(test_cast)
290 {
291 auto q = from(int_range(0,10))
292 .cast<bool>();
293 VERIFY_EQ(false, q[0]);
294 VERIFY_EQ(true, q[1]);
295 VERIFY_EQ(true, q[2]);
296 VERIFY((std::is_same<decltype(q[0]), bool>::value));
297 }
298
TEST(test_contains)299 TEST(test_contains)
300 {
301 auto q = from(int_range(0,10))
302 .select([](int x){return x*2;});
303 VERIFY(q.contains(4));
304 VERIFY(!q.contains(5));
305 }
306
TEST(test_element_accessors)307 TEST(test_element_accessors)
308 {
309 vector<int> v(int_iter(0), int_iter(10));
310 auto q = from(v)
311 .where([](int x){return x%2==0;});
312
313 VERIFY_EQ(0, q.first());
314 VERIFY_EQ(8, q.last());
315 VERIFY_EQ(6, q.element_at(3));
316
317 bool thrown = false;
318 try { q.element_at(5); } catch (std::logic_error&) { thrown = true; }
319 VERIFY(thrown);
320
321 q.first() = 1;
322 q.last() = 42;
323
324 // note: because the vector now contains { 1, 1, 2, 3, ... 7, 8, 42 }, the first
325 // even number is now '2'
326 VERIFY_EQ(2, q.first());
327 VERIFY_EQ(42, q.last());
328 }
329
330 //////////////////// New style cursors ////////////////////
331
TEST(test_cursor_dynamic)332 TEST(test_cursor_dynamic)
333 {
334 dynamic_cursor<int> dc(int_iter(0), int_iter(2));
335
336 VERIFY(!dc.empty());
337 VERIFY_EQ(0, dc.get());
338 dc.inc();
339 VERIFY_EQ(1, dc.get());
340 dc.inc();
341 VERIFY(dc.empty());
342 }
343
TEST(test_selectmany)344 TEST(test_selectmany)
345 {
346 int_range range1(0, 3);
347 auto range2 =
348
349 from(range1)
350 .select_many(
351 [](int x)
352 {
353 return int_range(0, x+1);
354 });
355
356 auto cur = range2.get_cursor();
357
358 // expected: 0, 0, 1, 0, 1, 2.
359 VERIFY(!cur.empty());
360
361 VERIFY_EQ(0, cur.get());
362 cur.inc();
363 VERIFY(!cur.empty());
364
365 VERIFY_EQ(0, cur.get());
366 cur.inc();
367 VERIFY(!cur.empty());
368
369 VERIFY_EQ(1, cur.get());
370 cur.inc();
371 VERIFY(!cur.empty());
372
373 VERIFY_EQ(0, cur.get());
374 cur.inc();
375 VERIFY(!cur.empty());
376
377 VERIFY_EQ(1, cur.get());
378 cur.inc();
379 VERIFY(!cur.empty());
380
381 VERIFY_EQ(2, cur.get());
382 cur.inc();
383 VERIFY(cur.empty());
384 }
385
TEST(test_cursor_selectmany2)386 TEST(test_cursor_selectmany2)
387 {
388 int_range range1(0, 3);
389 auto range2 = from(range1)
390 .select_many(
391 [](int x)
392 {
393 return int_range(0, x+1);
394 });
395
396 // expected: 0, 0, 1, 0, 1, 2.
397 int expect[] = { 0, 0, 1, 0, 1, 2 };
398
399 VERIFY_EQ(_countof(expect), std::distance(range2.begin(), range2.end()));
400 VERIFY_EQ(_countof(expect), std::distance(range2.begin(), range2.end()));
401
402 auto result = std::mismatch(expect, expect + _countof(expect), range2.begin());
403 if (result.second != range2.end()) {
404 cout << "mismatch: " << *result.first << " != " << *result.second << endl;
405 }
406 VERIFY( result.second == range2.end());
407 }
408
TEST(test_late_bind)409 TEST(test_late_bind)
410 {
411 int_range range1(0, 100);
412 linq_driver<dynamic_collection<int>> range2 = from(range1).late_bind();
413
414 VERIFY_EQ(1, range2.element_at(1));
415
416 auto q1 = from(range1).select([](int x){ return x*2; }).where([](int x){ return x%10!=0; });
417
418 cout << "typeof q1 ==> " << typeid(q1).name() << endl;
419 cout << "typeof q1.late_bind() ==> " << typeid(q1.late_bind()).name() << endl;
420 }
421
422 struct stopwatch
423 {
424 time_t t0, t1;
startstopwatch425 void start() {
426 t1 = t0 = clock();
427 }
stopstopwatch428 void stop() {
429 t1 = clock();
430 }
valuestopwatch431 double value() const {
432 return double(t1-t0)/CLOCKS_PER_SEC;
433 }
434 };
435
436 template <class Fn>
test_perf(Fn fn)437 void test_perf(Fn fn)
438 {
439 // warmup
440 fn(10);
441
442 int n = 100;
443 stopwatch sw;
444 for(;;)
445 {
446 cout << "trying n=" << n << endl;
447 sw.start();
448 fn(n);
449 sw.stop();
450 if (sw.value() > 2.0) {
451 break;
452 }
453 n *= 2;
454 }
455 cout << "time = " << sw.value() << " s\n";
456 cout << "steps = " << n << "\n";
457 cout << "t/step = " << (sw.value() * 1e9 / n) << " ns\n";
458 cout << "step/t = " << (n / sw.value()) << " Hz\n";
459 }
460
TEST(test_performance)461 TEST(test_performance)
462 {
463 // http://projecteuler.net/problem=8
464 //
465 // Find the greatest product of five consecutive digits in the 1000-digit number.
466 //
467
468 static const char num[] =
469 "73167176531330624919225119674426574742355349194934"
470 "96983520312774506326239578318016984801869478851843"
471 "85861560789112949495459501737958331952853208805511"
472 "12540698747158523863050715693290963295227443043557"
473 "66896648950445244523161731856403098711121722383113"
474 "62229893423380308135336276614282806444486645238749"
475 "30358907296290491560440772390713810515859307960866"
476 "70172427121883998797908792274921901699720888093776"
477 "65727333001053367881220235421809751254540594752243"
478 "52584907711670556013604839586446706324415722155397"
479 "53697817977846174064955149290862569321978468622482"
480 "83972241375657056057490261407972968652414535100474"
481 "82166370484403199890008895243450658541227588666881"
482 "16427171479924442928230863465674813919123162824586"
483 "17866458359124566529476545682848912883142607690042"
484 "24219022671055626321111109370544217506941658960408"
485 "07198403850962455444362981230987879927244284909188"
486 "84580156166097919133875499200524063689912560717606"
487 "05886116467109405077541002256983155200055935729725"
488 "71636269561882670428252483600823257530420752963450";
489
490 auto task = [&](int n){
491 for (int i = 0; i < n; ++i) {
492 auto range1 = int_range(0, _countof(num)-5); // 5 digit numbers, plus null terminator
493
494 auto products = from(range1)
495 .select([&](int i){ return num+i;})
496 .where([&](const char* s){ return !from(s, s+5).contains('0'); })
497 .select([&](const char* s) { return from(s, s+5).select([](char c){ return c - '0'; })
498 .aggregate(std::multiplies<int>()); });
499
500 auto result = products.max();
501 if (n == 1) {
502 cout << "result = " << result << endl;
503 }
504 }
505 };
506 cout << "length of input: " << (_countof(num)-1) << endl;
507
508 task(1);
509 cout << endl;
510
511 #ifdef PERF
512 test_perf(task);
513 cout << endl;
514 #endif
515 }
516
517 // SUM TESTS
518
TEST(test_sum_ints)519 TEST(test_sum_ints)
520 {
521 vector<int> numbers{1, 2, 3, 4, 5};
522
523 auto result = cpplinq::from(numbers);
524 auto r2 = result.sum();
525
526 VERIFY_EQ(15, r2);
527 }
528
TEST(test_sum_ints_with_seed)529 TEST(test_sum_ints_with_seed)
530 {
531 vector<int> numbers{1, 2, 3, 4, 5};
532
533 auto result = cpplinq::from(numbers).sum(10);
534
535 VERIFY_EQ(25, result);
536 }
537
TEST(test_sum_floats)538 TEST(test_sum_floats) {
539 vector<float> numbers{ 1.0f,2.0f,3.0f,4.0f,5.0f };
540
541 auto result = cpplinq::from(numbers).sum();
542
543 VERIFY_EQ(15.0f, result);
544 }
545
TEST(test_sum_doubles)546 TEST(test_sum_doubles) {
547 vector<double> numbers { 1.0,2.0,3.0,4.0,5.0 };
548
549 auto result = cpplinq::from(numbers).sum();
550
551 VERIFY_EQ(15.0, result);
552 }
553
TEST(test_sum_complex)554 TEST(test_sum_complex) {
555 using namespace std::complex_literals;
556
557 vector<complex<double>> numbers{ 1i, 1.0 + 2i, 2.0 + 3i };
558
559 auto sum = cpplinq::from(numbers).sum();
560
561 VERIFY_EQ(3.0, sum.real());
562 VERIFY_EQ(6.0, sum.imag());
563 }
564
TEST(test_sum_with_projection_lambda)565 TEST(test_sum_with_projection_lambda) {
566 vector<tuple<int>> numbers { std::tuple<int>(0), std::tuple<int>(1), std::tuple<int>(2) };
567
568 auto result = cpplinq::from(numbers).sum([](std::tuple<int>& x){
569 return std::get<0>(x);
570 });
571
572 VERIFY_EQ(3.0, result);
573 }
574
TEST(test_sum_with_projection_lambda_and_seed)575 TEST(test_sum_with_projection_lambda_and_seed) {
576 vector<tuple<int>> numbers { std::tuple<int>(0), std::tuple<int>(1), std::tuple<int>(2) };
577
578 auto result = cpplinq::from(numbers).sum([](std::tuple<int>& x){
579 return std::get<0>(x);
580 }, 10);
581
582 VERIFY_EQ(13.0, result);
583 }
584
getValue(std::tuple<int> x)585 int getValue(std::tuple<int> x)
586 {
587 return std::get<0>(x);
588 }
589
TEST(test_sum_with_projection_function_pointer)590 TEST(test_sum_with_projection_function_pointer) {
591 vector<tuple<int>> numbers { std::tuple<int>(0), std::tuple<int>(1), std::tuple<int>(2) };
592
593 auto result = cpplinq::from(numbers).sum(getValue);
594
595 VERIFY_EQ(3.0, result);
596 }
597
main(int argc,char ** argv)598 int main(int argc, char** argv)
599 {
600 std::size_t pass = 0, fail = 0;
601 testrange<0,__LINE__>().run(pass, fail);
602
603
604 cout << "pass: " << pass << ", fail: " << fail << endl;
605 if (fail){
606 cerr << "ERRORS PRESENT." << endl;
607 } else if (!pass) {
608 cerr << "ERROR, no tests run" << endl;
609 }
610 }
611