Lumiera  0.pre.03
»edit your freedom«
iter-explorer-test.cpp
Go to the documentation of this file.
1 /*
2  IterExplorer(Test) - verify tree expanding and backtracking iterator
3 
4  Copyright (C)
5  2017, Hermann Vosseler <Ichthyostega@web.de>
6 
7   **Lumiera** is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 2 of the License, or (at your
10   option) any later version. See the file COPYING for further details.
11 
12 * *****************************************************************/
13 
44 #include "lib/test/run.hpp"
45 #include "lib/test/test-helper.hpp"
46 #include "lib/iter-adapter-stl.hpp"
47 #include "lib/format-string.hpp"
48 #include "lib/format-cout.hpp"
49 #include "lib/format-util.hpp"
50 #include "lib/itertools.hpp"
51 #include "lib/util.hpp"
52 
53 #include "lib/iter-explorer.hpp"
54 #include "lib/meta/trait.hpp"
55 
56 #include <utility>
57 #include <vector>
58 #include <limits>
59 #include <string>
60 #include <tuple>
61 #include <cmath>
62 #include <set>
63 
64 
65 namespace lib {
66 namespace test{
67 
68  using ::Test;
69  using util::_Fmt;
70  using util::isnil;
71  using util::isSameObject;
73  using LERR_(ITER_EXHAUST);
74  using std::vector;
75  using std::string;
76 
77 
78  namespace { // test substrate: simple number sequence iterator
79 
84  struct CountDown
85  {
86  uint p,e;
87 
88  CountDown(uint start =0, uint end =0)
89  : p(start)
90  , e(end)
91  { }
92 
93  bool
94  checkPoint () const
95  {
96  return p > e;
97  }
98 
99  uint&
100  yield () const
101  {
102  return util::unConst (checkPoint()? p : e);
103  }
104 
105  void
106  iterNext ()
107  {
108  if (not checkPoint()) return;
109  --p;
110  }
111 
112  bool
113  operator== (CountDown const& o) const
114  {
115  return e == o.e
116  and p == o.p;
117  }
118  };
119 
120 
127  : public IterStateWrapper<CountDown>
128  {
129 
130  public:
131  explicit
132  NumberSequence(uint start = 0)
133  : IterStateWrapper{CountDown{start}}
134  { }
135  NumberSequence(uint start, uint end)
136  : IterStateWrapper{CountDown(start,end)}
137  { }
138  };
139 
140 
141 
146  class RandomSeq
147  {
148  size_t lim_;
149  size_t cnt_;
150  char letter_;
151 
152  static char
153  rndLetter()
154  {
155  return 'A' + rani(26);
156  }
157 
158  public:
159  RandomSeq(int len =0)
160  : lim_{len>=0? len : std::numeric_limits<size_t>::max()}
161  , cnt_{0}
162  , letter_{rndLetter()}
163  { }
164 
165  bool
166  checkPoint () const
167  {
168  return cnt_ < lim_;
169  }
170 
171  char&
172  yield () const
173  {
174  return unConst(this)->letter_;
175  }
176 
177  void
178  iterNext ()
179  {
180  ASSERT (checkPoint());
181  ++cnt_;
182  letter_ = rndLetter();
183  }
184  };
185 
186 
188  template<class II>
189  inline string
190  materialise (II&& ii)
191  { // note: copy here when given by-ref
192  return util::join (std::forward<II> (ii), "-");
193  }
194 
196  template<class II>
197  inline void
198  pullOut (II & ii)
199  {
200  while (ii)
201  {
202  cout << *ii;
203  if (++ii) cout << "-";
204  }
205  cout << endl;
206  }
207 
208  } // (END) test helpers
209 
210 
211 
212 
213 
214 
215 
216  /*******************************************************************/
262  class IterExplorer_test : public Test
263  {
264 
265  virtual void
266  run (Arg)
267  {
268  seedRand();
269 
270  verify_wrappedState();
271  verify_wrappedIterator();
272 
273  verify_expandOperation();
274  verify_expand_rootCurrent();
275  verify_transformOperation();
276  verify_elementGroupingOperation();
277  verify_aggregatingGroupItration();
278  verify_combinedExpandTransform();
279  verify_customProcessingLayer();
280  verify_scheduledExpansion();
281  verify_untilStopTrigger();
282  verify_FilterIterator();
283  verify_FilterChanges();
284  verify_asIterSource();
285  verify_IterSource();
286  verify_reduceVal();
287  verify_effuse();
288  verify_dedup();
289 
290  verify_depthFirstExploration();
291  demonstrate_LayeredEvaluation();
292  }
293 
294 
295 
299  void
301  {
302  auto ii = explore (CountDown{5,0});
303  CHECK (!isnil (ii));
304  CHECK (5 == *ii);
305  ++ii;
306  CHECK (4 == *ii);
307  pullOut(ii);
308  CHECK ( isnil (ii));
309  CHECK (!ii);
310 
311  VERIFY_ERROR (ITER_EXHAUST, *ii );
312  VERIFY_ERROR (ITER_EXHAUST, ++ii );
313 
314  ii = explore (CountDown{5});
315  CHECK (materialise(ii) == "5-4-3-2-1"_expect);
316  ii = explore (CountDown{7,4});
317  CHECK (materialise(ii) == "7-6-5"_expect);
318  ii = explore (CountDown{});
319  CHECK ( isnil (ii));
320  CHECK (!ii);
321  }
322 
323 
325  void
327  {
328  vector<int> numz{1,-2,3,-5,8,-13};
329  auto ii = eachElm(numz);
330  CHECK (!isnil (ii));
331  CHECK (1 == *ii);
332  ++ii;
333  CHECK (-2 == *ii);
334 
335  auto jj = explore(ii);
336  CHECK (!isnil (jj));
337  CHECK (-2 == *jj);
338  ++jj;
339  CHECK (3 == *jj);
340 
341  // we passed a LValue-Ref, thus a copy was made
342  CHECK (-2 == *ii);
343 
344  CHECK (materialise(ii) == "-2-3--5-8--13");
345  CHECK (materialise(jj) == "3--5-8--13");
346 
347  // can even adapt STL container automatically
348  auto kk = explore(numz);
349  CHECK (!isnil (kk));
350  CHECK (1 == *kk);
351  CHECK (materialise(kk) == "1--2-3--5-8--13");
352  }
353 
354 
355 
390  void
392  {
393  /* == "monadic flatMap" == */
394 
395  verify_treeExpandingIterator(
396  explore(CountDown{5})
397  .expand([](uint j){ return CountDown{j-1}; }) // expand-functor: Val > StateCore
398  );
399 
400  verify_treeExpandingIterator(
401  explore(CountDown{5})
402  .expand([](uint j){ return NumberSequence{j-1}; }) // expand-functor: Val > Iter
403  ); // NOTE: different Iterator type than the source!
404 
405  // lambda with side-effect and return type different from source iter
406  vector<vector<uint>> childBuffer;
407  auto expandIntoChildBuffer = [&](uint j) -> vector<uint>&
408  {
409  childBuffer.emplace_back();
410  vector<uint>& childNumbz = childBuffer.back();
411  for (size_t i=0; i<j-1; ++i)
412  childNumbz.push_back(j-1 - i);
413  return childNumbz;
414  };
415 
416  verify_treeExpandingIterator(
417  explore(CountDown{5})
418  .expand(expandIntoChildBuffer) // expand-functor: Val > STL-container&
419  );
420 
421  // test routine called the expansion functor five times
422  CHECK (5 == childBuffer.size());
423 
424 
425 
426  /* == "state manipulation" use cases == */
427 
428  verify_treeExpandingIterator(
429  explore(CountDown{5})
430  .expand([](CountDown const& core){ return CountDown{ core.yield() - 1}; }) // expand-functor: StateCore const& -> StateCore
431  );
432 
433  verify_treeExpandingIterator(
434  explore(CountDown{5})
435  .expand([](CountDown core){ return NumberSequence{ core.yield() - 1}; }) // expand-functor: StateCore -> Iter
436  );
437 
438  verify_treeExpandingIterator(
439  explore(CountDown{5})
440  .expand([](auto & it){ return CountDown{ *it - 1}; }) // generic Lambda: Iter& -> StateCore
441  );
442 
443  verify_treeExpandingIterator(
444  explore(CountDown{5})
445  .expand([](auto it){ return decltype(it){ *it - 1}; }) // generic Lambda: Iter -> Iter
446  );
447  }
448 
449 
450  template<class EXP>
451  void
452  verify_treeExpandingIterator (EXP ii)
453  {
454  CHECK (!isnil (ii));
455  CHECK (5 == *ii);
456  ++ii;
457  CHECK (4 == *ii);
458 
459  CHECK (0 == ii.depth());
460  ii.expandChildren();
461  CHECK (3 == *ii);
462  CHECK (1 == ii.depth());
463  ++ii;
464  CHECK (2 == *ii);
465  CHECK (1 == ii.depth());
466  ii.expandChildren();
467  CHECK (1 == *ii);
468  CHECK (2 == ii.depth());
469  ++ii;
470  CHECK (1 == *ii);
471  CHECK (1 == ii.depth());
472  ++ii;
473  CHECK (3 == *ii);
474  CHECK (0 == ii.depth());
475  CHECK (materialise(ii) == "3-2-1");
476  ii.expandChildren();
477  CHECK (1 == ii.depth());
478  CHECK (materialise(ii) == "2-1-2-1");
479  ++++ii;
480  CHECK (0 == ii.depth());
481  CHECK (materialise(ii) == "2-1");
482  ii.expandChildren();
483  CHECK (1 == ii.depth());
484  CHECK (materialise(ii) == "1-1");
485  ++ii;
486  CHECK (0 == ii.depth());
487  CHECK (1 == *ii);
488  CHECK (materialise(ii) == "1");
489  ii.expandChildren();
490  CHECK (isnil (ii));
491  VERIFY_ERROR (ITER_EXHAUST, *ii );
492  VERIFY_ERROR (ITER_EXHAUST, ++ii );
493  }
494 
495 
503  void
505  {
506  auto tree = explore(CountDown{25})
507  .expand([](uint j){ return CountDown{j-1}; });
508 
509  CHECK (materialise(tree) == "25-24-23-22-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1");
510 
511  CHECK (0 == tree.depth());
512  CHECK (25 == *tree);
513  ++tree;
514  ++tree;
515  ++tree;
516  ++tree;
517  CHECK (21 == *tree);
518  tree.expandChildren();
519  CHECK (1 == tree.depth());
520  ++tree;
521  ++tree;
522  ++tree;
523  ++tree;
524  ++tree;
525  CHECK (15 == *tree);
526  tree.expandChildren();
527  ++tree;
528  ++tree;
529  CHECK (2 == tree.depth());
530  CHECK (materialise(tree) == "12-11-10-9-8-7-6-5-4-3-2-1-" // this is the level-2 child sequence
531  "14-13-12-11-10-9-8-7-6-5-4-3-2-1-" // ...returning to the rest of the level-1 sequence
532  "20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-1"); // ...followed by the rest of the original root sequence
533  CHECK (12 == *tree);
534 
535  tree.rootCurrent();
536  CHECK (12 == *tree);
537  CHECK (materialise(tree) == "12-11-10-9-8-7-6-5-4-3-2-1"); // note: level-2 continues unaltered, but level-1 and the original root are gone.
538  CHECK (0 == tree.depth());
539  }
540 
541 
542 
558  void
560  {
561  auto multiply = [](int v){ return 2*v; }; // functional map: value -> value
562 
563  _Fmt embrace{"≺%s≻"};
564  auto formatify = [&](auto it){ return string{embrace % *it}; }; // generic lambda: assumed to take an Iterator&
565 
566 
567  auto ii = explore(CountDown{7,4})
568  .transform(multiply)
569  ;
570 
571  CHECK (14 == *ii);
572  CHECK (14 == *ii);
573  ++ii;
574  CHECK (12 == *ii);
575  ++ii;
576  CHECK (10 == *ii);
577  ++ii;
578  CHECK (isnil (ii));
579  VERIFY_ERROR (ITER_EXHAUST, *ii );
580  VERIFY_ERROR (ITER_EXHAUST, ++ii );
581 
582 
583 
584  // demonstrate chaining of several transformation layers
585  vector<int64_t> numz{1,-2,3,-5,8,-13};
586 
587  CHECK ("≺1≻-≺-2≻-≺3≻-≺-5≻-≺8≻-≺-13≻" == materialise (explore(numz)
588  .transform(formatify)) );
589 
590  CHECK ("≺2≻-≺-4≻-≺6≻-≺-10≻-≺16≻-≺-26≻" == materialise (explore(numz)
591  .transform(multiply)
592  .transform(formatify)) );
593 
594  CHECK ("≺≺4≻≻-≺≺-8≻≻-≺≺12≻≻-≺≺-20≻≻-≺≺32≻≻-≺≺-52≻≻" == materialise (explore(numz)
595  .transform(multiply)
596  .transform(multiply)
597  .transform(formatify)
598  .transform(formatify)) );
599 
600 
601  // demonstrate the functor is evaluated only once per step
602  int fact = 3;
603 
604  auto jj = explore (CountDown{4})
605  .transform([&](int v)
606  {
607  v *=fact;
608  fact *= -2;
609  return v;
610  });
611  CHECK (3*4 == *jj);
612  CHECK (fact == -2*3);
613 
614  CHECK (3*4 == *jj);
615  CHECK (3*4 == *jj);
616 
617  ++jj;
618  CHECK (fact == -2*3); // NOTE : functor is evaluated on first demand
619  CHECK (-2*3*3 == *jj); // ...which happens on yield (access the iterator value)
620  CHECK (fact == 2*2*3); // and this also causes the side-effect
621  CHECK (-2*3*3 == *jj);
622  CHECK (-2*3*3 == *jj);
623  CHECK (fact == 2*2*3); // no further evaluation and thus no further side-effect
624 
625  ++jj;
626  CHECK (2*2*3*2 == *jj);
627  CHECK (fact == -2*2*2*3);
628 
629  fact = -23;
630  CHECK (2*2*3*2 == *jj);
631 
632  ++jj;
633  CHECK (fact == -23);
634  CHECK (-23*1 == *jj);
635  CHECK (fact == 2*23);
636 
637  ++jj;
638  CHECK (isnil (jj));
639  CHECK (fact == 2*23);
640 
641  VERIFY_ERROR (ITER_EXHAUST, *ii );
642  CHECK (fact == 2*23); // exhaustion detected on source and thus no further evaluation
643 
644 
645 
646  // demonstrate a transformer accessing the source state core...
647  // should not be relevant in practice, but works due to the generic adapters
648  auto kk = explore (CountDown{9,4})
649  .transform([](CountDown& core)
650  {
651  uint delta = core.p - core.e;
652  if (delta % 2 == 0)
653  --core.p; // EVIL EVIL
654  return delta;
655  });
656 
657  CHECK (5 == *kk); // the delta between 9 (start) and 4 (end)
658  ++kk;
659  CHECK (4 == *kk); // Core manipulated by SIDE-EFFECT at this point...
660  CHECK (4 == *kk); // ...but not yet obvious, since the result is cached
661  ++kk;
662  CHECK (2 == *kk); // Surprise -- someone ate my numberz...
663  ++kk;
664  CHECK (isnil (kk));
665  }
666 
667 
668 
678  void
680  {
681  auto showGroup = [](auto it){ return "["+util::join(*it)+"]"; };
682  CHECK (materialise (
683  explore(CountDown{10})
684  .grouped<3>()
685  .transform(showGroup)
686  )
687  == "[10, 9, 8]-[7, 6, 5]-[4, 3, 2]"_expect);
688 
689 
690  auto ii = explore(CountDown{23})
691  .grouped<5>();
692  CHECK(ii);
693  CHECK(ii.getGroupedElms());
694  CHECK(not ii.getRestElms());
695  CHECK (materialise(ii.getGroupedElms()) == "23-22-21-20-19"_expect);
696 
697  CHECK ( test::showType<decltype(*ii)>()== "array<uint, 5ul>&"_expect);
698 
699  uint s = *(ii.getGroupedElms());
700  for ( ; ii; ++ii)
701  {
702  auto grp = *ii;
703  CHECK (5 == grp.size());
704  auto& [a,b,c,d,e] = grp;
705  CHECK (a == s);
706  CHECK (b == a-1);
707  CHECK (c == a-2);
708  CHECK (d == a-3);
709  CHECK (e == a-4);
710  CHECK (not ii.getRestElms());
711  s -= 5;
712  }
713  CHECK (s < 5);
714  CHECK (s == 3);
715 
716  CHECK (not ii);
717  CHECK(ii.getGroupedElms());
718  CHECK(ii.getRestElms());
719  CHECK (materialise(ii.getGroupedElms()) == "3-2-1"_expect);
720  CHECK (materialise(ii.getRestElms()) == "3-2-1"_expect);
721 
722 
723  auto iii = explore(CountDown{4})
724  .grouped<5>();
725  CHECK (not iii);
726  CHECK (materialise(iii.getRestElms()) == "4-3-2-1"_expect);
727  }
728 
729 
739  void
741  {
742  CHECK (materialise (
743  explore(CountDown{10})
744  .groupedBy(std::ilogbf)
745  )
746  == "27-22-5-1"_expect); // 10+9+8|7+6+5+4|3+2|1
747 
748  CHECK (materialise (
749  explore(CountDown{10})
750  .transform(util::toString<uint>)
751  .groupedBy([](auto& it) { return std::ilogbf (it.p); }) // note trickery: takes not the value, rather the iterator and
752  ) // accesses internals of CountDown, bypassing the transform layer above
753  == "1098-7654-32-1"_expect); // `+` does string concatenation
754 
755 
756  auto showGroup = [](auto it){ return "["+util::join(*it)+"]"; };
757  // elaborate form with custom aggregation...
758  CHECK (materialise (
759  explore(CountDown{10})
760  .groupedBy(std::ilogbf
761  ,[](vector<uint>& accum, uint val)
762  {
763  accum.push_back (val);
764  })
765  .transform(showGroup)
766  )
767  == "[10, 9, 8]-[7, 6, 5, 4]-[3, 2]-[1]"_expect);
768  }
769 
770 
793  void
795  {
796  auto ii = explore(CountDown{5})
797  .expand([](uint j){ return CountDown{j-1}; })
798  .transform([](int v){ return 2*v; })
799  ;
800 
801  CHECK ("int" == meta::typeStr(*ii)); // result type is what the last transformer yields
802  CHECK (10 == *ii);
803  ++ii;
804  CHECK (8 == *ii);
805  ii.expandChildren();
806  CHECK ("6-4-2-6-4-2" == materialise(ii) );
807 
808 
809  // the following contrived example demonstrates
810  // how intermediary processing steps may interact
811 
812  CHECK (materialise (
813  explore(CountDown{5})
814  .expand([](uint j){ return CountDown{j-1}; })
815  .transform([](int v){ return 2*v; })
816  .transform([](auto& it)
817  {
818  auto elm = *it;
819  if (elm == 6)
820  {
821  it.expandChildren(); // NOTE at that point we're forced to decide if
822  elm = *it * 10; // we want to return the parent or the 1st child
823  }
824  return elm;
825  })
826  .transform([](float f){ return 0.055 + f/2; })
827  )
828  == "5.055-4.055-20.055-1.055-2.055-1.055" );
829  }
830 
831 
837  template<class SRC>
839  : public SRC
840  {
841  using SRC::SRC;
842 
843  void
844  iterNext()
845  {
846  ++(*this);
847  if (*this)
848  ++(*this);
849  }
850  };
851 
857  void
859  {
860  CHECK (materialise(
861  explore(CountDown{7})
862  .processingLayer<MagicTestRubbish>()
863  )
864  == "7-5-3-1");
865 
866  CHECK (materialise(
867  explore(CountDown{7})
868  .transform([](uint v){ return 2*v; })
869  .processingLayer<MagicTestRubbish>()
870  .filter([](int v){ return v % 3; })
871  )
872  == "14-10-2");
873  }
874 
875 
876 
886  void
888  {
889  auto ii = explore(CountDown{6})
890  .expand([](uint j){ return CountDown{j-2}; })
891  .expandOnIteration();
892 
893  CHECK (!isnil (ii));
894  CHECK (6 == *ii);
895  ++ii;
896  CHECK (5 == *ii);
897  CHECK (ii.depth() == 0);
898 
899  ii.expandChildren();
900  CHECK (5 == *ii);
901  CHECK (ii.depth() == 0);
902  ++ii;
903  CHECK (3 == *ii);
904  CHECK (ii.depth() == 1);
905 
906  ii.expandChildren();
907  ii.expandChildren();
908  CHECK (ii.depth() == 1);
909  CHECK (3 == *ii);
910  ++ii;
911  CHECK (1 == *ii);
912  CHECK (ii.depth() == 2);
913  ++ii;
914  CHECK (2 == *ii);
915  CHECK (ii.depth() == 1);
916 
917  ii.expandChildren();
918  ++ii;
919  CHECK (1 == *ii);
920  CHECK (ii.depth() == 1);
921  ++ii;
922  CHECK (4 == *ii);
923  CHECK (ii.depth() == 0);
924  ++ii;
925  CHECK (3 == *ii);
926  ++ii;
927  CHECK (2 == *ii);
928  ++ii;
929  CHECK (1 == *ii);
930  ++ii;
931  CHECK (isnil (ii));
932  }
933 
934 
935 
942  void
944  {
945  CHECK (materialise (
946  explore (CountDown{10})
947  .iterUntil([](uint j){ return j < 5; })
948  )
949  == "10-9-8-7-6-5"_expect);
950 
951  CHECK (materialise (
952  explore (CountDown{10})
953  .iterWhile([](uint j){ return j > 5; })
954  )
955  == "10-9-8-7-6"_expect);
956 
957  CHECK (materialise (
958  explore (CountDown{10})
959  .iterWhile([](int j){ return j > -5; })
960  )
961  == "10-9-8-7-6-5-4-3-2-1"_expect);
962 
963  CHECK (materialise (
964  explore (CountDown{10})
965  .iterWhile([](uint j){ return j > 25; })
966  )
967  == ""_expect);
968  }
969 
970 
971 
978  void
980  {
981  // canonical example, using a clean side-effect free predicate based on element values
982  CHECK (materialise (
983  explore(CountDown{10})
984  .filter([](uint j){ return j % 2; })
985  )
986  == "9-7-5-3-1"_expect);
987 
988 
989  // Filter may lead to consuming util exhaustion...
990  auto ii = explore(CountDown{10})
991  .filter([](int j){ return j > 9; });
992 
993  CHECK (not isnil (ii));
994  CHECK (10 == *ii);
995  ++ ii;
996  CHECK (isnil (ii));
997  VERIFY_ERROR (ITER_EXHAUST, ++ii );
998 
999 
1000  // none of the source elements can be approved here...
1001  auto jj = explore(CountDown{5})
1002  .filter([](int j){ return j > 9; });
1003 
1004  CHECK (isnil (jj));
1005 
1006 
1007 
1008  // a tricky example, where the predicate takes the source core as argument;
1009  // since the source core is embedded as baseclass, it can thus "undermine"
1010  // and bypass the layers configured in between; here the transformer changes
1011  // uint to float, but the filter interacts directly with the core and thus
1012  // judges based on the original values
1013  CHECK (materialise (
1014  explore(CountDown{10,4})
1015  .transform([](float f){ return 0.55 + 2*f; })
1016  .filter([](CountDown& core){ return core.p % 2; })
1017  )
1018  == "18.55-14.55-10.55"_expect);
1019 
1020 
1021 
1022  // contrived example to verify interplay of filtering and child expansion;
1023  // especially note that the filter is re-evaluated after expansion happened.
1024  CHECK (materialise (
1025  explore(CountDown{10})
1026  .expand([](uint i){ return CountDown{i%4==0? i-1 : 0}; }) // generate subtree at 8 and 4 ==> 10-9-8-7-6-5-4-3-2-1-3-2-1-7-6-5-4-3-2-1-3-2-1
1027  .filter([](uint i){ return i%2 == 0; })
1028  .expandAll() // Note: sends the expandChildren down through the filter
1029  )
1030  == "10-8-6-4-2-2-6-4-2-2"_expect);
1031 
1032 
1033 
1034  // another convoluted example to demonstrate
1035  // - a filter predicate with side-effect
1036  // - and moreover the predicate is a generic lambda
1037  // - accepting the iterator to trigger child expansion
1038  // - which also causes re-evaluation of the preceding transformer
1039  bool toggle = false;
1040  auto kk = explore(CountDown{10,5})
1041  .expand([](uint j){ return CountDown{j-1}; })
1042  .transform([](int v){ return 2*v; })
1043  .filter([&](auto& it)
1044  {
1045  if (*it == 16)
1046  {
1047  it.expandChildren();
1048  toggle = true;
1049  }
1050  return toggle;
1051  });
1052 
1053  CHECK (materialise(kk)
1054  == "14-12-10-8-6-4-2-14-12"_expect);
1055  // Explanation:
1056  // The source starts at 10, but since the toggle is false,
1057  // none of the initial values makes it though to the result.
1058  // The interspersed transformer doubles the source values, and
1059  // thus at source == 8 the trigger value (16) is hit. Thus the
1060  // filter now flips the context-bound toggle (side-effect) and
1061  // then expands children, which consumes current source value 8
1062  // to replace it with the sequence 7,6,5,4,3,2,1, followed by
1063  // the rest of the original sequence, 7,6 (which stops above 5).
1064 
1065  CHECK (materialise(kk.filter([](long i){ return i % 7; }))
1066  == "12-10-8-6-4-2-12"_expect);
1067  // Explanation:
1068  // Since the original IterExplorer was assigned to variable kk,
1069  // the materialise()-Function got a lvalue-ref and thus made a copy
1070  // of the whole compound. For that reason, the original state within
1071  // kk still rests at 7 -- because the filter evaluates eagerly, the
1072  // source was pulled right at construction until we reached the first
1073  // value to yield, which is the first child (7,....) within the
1074  // expanded sequence. But now, in the second call to materialise(),
1075  // we don't just copy, rather we add another filter layer on top,
1076  // which happens to filter away this first result (== 2*7), and
1077  // also the first element of the original sequence after the
1078  // expanded children
1079 
1080  // WARNING: kk is now defunct, since we moved it into the builder expression
1081  // and then moved the resulting extended iterator into materialise!
1082  }
1083 
1084 
1085 
1087  void
1089  {
1090  auto seq = explore(CountDown{20})
1091  .mutableFilter();
1092 
1093  auto takeEve = [](uint i){ return i%2 == 0; };
1094  auto takeTrd = [](uint i){ return i%3 == 0; };
1095 
1096  CHECK (20 == *seq);
1097  ++seq;
1098  CHECK (19 == *seq);
1099  CHECK (19 == *seq);
1100 
1101  seq.andFilter (takeEve);
1102  CHECK (18 == *seq);
1103  ++seq;
1104  CHECK (16 == *seq);
1105 
1106  seq.andFilter (takeTrd);
1107  CHECK (12 == *seq); // is divisible (by 2 AND by 3)
1108 
1109  seq.flipFilter();
1110  CHECK (11 == *seq); // not divisible (by 2 AND by 3)
1111  ++seq;
1112  CHECK (10 == *seq);
1113 
1114  seq.setNewFilter (takeTrd);
1115  CHECK ( 9 == *seq);
1116  ++seq;
1117  CHECK ( 6 == *seq);
1118 
1119  seq.orNotFilter (takeEve);
1120  CHECK ( 6 == *seq);
1121  ++seq;
1122  CHECK ( 5 == *seq); // disjunctive condition actually weakens the filter
1123  ++seq;
1124  CHECK ( 3 == *seq);
1125 
1126  // NOTE: arbitrary functors can be used/combined,
1127  // since they are adapted individually.
1128  // To demonstrate this, we use a functor accessing and
1129  // manipulating the state core by side effect...
1130  string buff{"."};
1131  seq.andNotFilter ([&](CountDown& core)
1132  {
1133  buff += util::toString(core.p) + ".";
1134  --core.p; // manipulate state core
1135  return core.p % 2; // return a number, not bool
1136  });
1137 
1138  CHECK ( 2 == *seq); // value in the core has been manipulated
1139  CHECK (".3." == buff); // the filter has been invoked once, and saw core == 3
1140 
1141  ++seq; // core == 2 is filtered by the existing other filter (== not take even)
1142  CHECK (".3.1." == buff); // the filter has been invoked again, and saw core == 1
1143  CHECK (0 == seq.p); // ...which he manipulated, so that core == 0
1144  CHECK (isnil (seq)); // .....and thus iteration end is detected
1145  VERIFY_ERROR (ITER_EXHAUST, *seq );
1146 
1147 
1148  // verify enabling and disabling...
1149  seq = explore(CountDown{10})
1150  .mutableFilter(takeTrd);
1151 
1152  CHECK (9 == *seq);
1153  seq.disableFilter();
1154  CHECK (9 == *seq);
1155  ++seq;
1156  CHECK (8 == *seq);
1157  seq.andNotFilter (takeEve);
1158  CHECK (7 == *seq);
1159  ++seq;
1160  CHECK (5 == *seq);
1161  seq.disableFilter();
1162  CHECK (5 == *seq);
1163  ++seq;
1164  CHECK (4 == *seq);
1165  ++seq;
1166  CHECK (3 == *seq);
1167  seq.flipFilter(); // everything rejected
1168  CHECK (isnil (seq));
1169  }
1170 
1171 
1172 
1173 
1176  void
1178  {
1179  auto accumulated = explore(CountDown{30})
1180  .transform([](int i){ return i-1; }) // note: implicitly converts uint -> int
1181  .resultSum();
1182 
1183  using Res = decltype(accumulated);
1184  CHECK (lib::test::showType<Res>() == "int"_expect);
1185 
1186  auto expectedSum = [](auto N){ return N*(N+1) / 2; };
1187  CHECK (accumulated == expectedSum(29));
1188 
1189  // In the general case an accessor and a junctor can be given...
1190  CHECK (explore(CountDown{10})
1191  .reduce([](int i){ return i - 0.5; } // accessor: produce a double
1192  ,[](string accu, float val)
1193  {
1194  return accu+">"+util::toString(val); // junctor: convert to String and combine with separator char
1195  }
1196  , string{">-"} // seedVal: starting point for the reduction; also defines result type
1197  )
1198  == ">->9.5>8.5>7.5>6.5>5.5>4.5>3.5>2.5>1.5>0.5"_expect);
1199 
1200  // If only the accessor is given, values are combined by std::plus...
1201  CHECK (explore(CountDown{9})
1202  .reduce([](auto it) -> string
1203  {
1204  return _Fmt{"○%s●"} % *it; // accessor: format into a string
1205  })
1206  == "○9●○8●○7●○6●○5●○4●○3●○2●○1●"_expect);
1207 
1208  // a predefined IDENTITY accessor takes values from the pipeline as-is
1209  CHECK (explore(CountDown{9})
1210  .reduce(iter_explorer::IDENTITY, std::minus<int>(), expectedSum(9))
1211  == 0);
1212  }
1213 
1214 
1215 
1218  void
1220  {
1221  auto solidified = explore(CountDown{20})
1222  .filter ([](uint i){ return i % 2; })
1223  .transform([](uint i){ return 0.5*i; })
1224  .effuse();
1225 
1226  using Res = decltype(solidified);
1227  CHECK (lib::test::showType<Res>() == "vector<double>"_expect);
1228  CHECK (util::join(solidified, "|") == "9.5|8.5|7.5|6.5|5.5|4.5|3.5|2.5|1.5|0.5"_expect);
1229  }
1230 
1231 
1234  void
1236  {
1237  CHECK (materialise (
1238  explore(CountDown{23})
1239  .transform([](uint j){ return j % 5; })
1240  .deduplicate()
1241  )
1242  == "0-1-2-3-4"_expect); // note: values were also sorted ascending by std::set
1243  }
1244 
1245 
1246 
1247 
1269  void
1271  {
1272  IterSource<uint>::iterator sequence; // note `sequence` is polymorphic
1273  CHECK (isnil (sequence));
1274 
1275  sequence = explore(CountDown{20,10})
1276  .filter([](uint i){ return i % 2; })
1277  .asIterSource(); // note this terminal builder function
1278  // moves the whole pipeline onto the heap
1279  CHECK (not isnil (sequence));
1280  CHECK (19 == *sequence);
1281 
1282 
1283  // use one sequence as source to build another one
1284  sequence = explore(sequence)
1285  .transform([](uint i){ return i*2; })
1286  .asIterSource();
1287 
1288  CHECK (38 == *sequence);
1289  CHECK ("38-34-30-26-22" == materialise(sequence));
1290 
1291  // WARNING pitfall: `sequence` is a copyable iterator front-end
1292  // but holds onto the actual pipeline by shared-ptr
1293  // Thus, even while materialise() creates a copy,
1294  // the iteration state gets shared....
1295  CHECK (22 == *sequence);
1296  ++sequence; // ...and even worse, iteration end is only detected after increment
1297  CHECK (isnil (sequence));
1298 
1299 
1300  // extended API to invoke child expansion opaquely
1301  IterExploreSource<char> exploreIter;
1302  CHECK (isnil (exploreIter));
1303 
1304  exploreIter = explore(CountDown{20,10})
1305  .filter([](uint i){ return i % 2; })
1306  .transform([](uint i){ return i*2; })
1307  .filter([](int i){ return i>25; })
1308  .expand([](uint i){ return CountDown{i-10, 20}; })
1309  .transform([](uint u) -> char { return '@'+u-20; })
1310  .asIterSource();
1311 
1312 
1313  CHECK ('R' == *exploreIter); // 38-20 + '@'
1314  ++exploreIter;
1315  CHECK ('N' == *exploreIter); // 34-20 + '@'
1316 
1317  exploreIter.expandChildren(); // expand consumes the current element (34)
1318  // and injects the sequence (24...20[ instead
1319  CHECK ('D' == *exploreIter); // 34-10 == 24 and 'D' == 24-20 + '@'
1320 
1321  CHECK ("D-C-B-A-J-F" == materialise(exploreIter));
1322  } // note how the remainder of the original sequence is picked up with 'J'...
1323 
1324 
1325 
1326 
1338  void
1340  {
1341  class PrivateSource
1342  : public IterSource<uint>
1343  {
1344  public:
1345  virtual PrivateSource* expandChildren() const =0;
1346  };
1347 
1348  class VerySpecificIter
1349  : public WrappedLumieraIter<NumberSequence
1350  , PrivateSource >
1351  {
1352  public:
1353  VerySpecificIter(uint start)
1354  : WrappedLumieraIter(NumberSequence{start})
1355  { }
1356 
1357  virtual PrivateSource*
1358  expandChildren() const override
1359  {
1360  return new VerySpecificIter{*wrappedIter() - 2};
1361  }
1362 
1363  uint
1364  currentVal() const
1365  {
1366  return *wrappedIter();
1367  }
1368  };
1369 
1370 
1371  // simple standard case: create a new heap allocated IterSource implementation.
1372  // IterExplorer will take ownership (by smart-ptr) and build a Lumiera Iterator front-End
1373  CHECK ("7-6-5-4-3-2-1" == materialise (
1374  explore (new VerySpecificIter{7})));
1375 
1376 
1377  // missing source detected
1378  PrivateSource* niente = nullptr;
1379  CHECK (isnil (explore (niente)));
1380 
1381 
1382  // attach to an IterSource living here in local scope...
1383  VerySpecificIter vsit{5};
1384 
1385  // ...and build a child expansion on top, which calls through the PrivateSource-API
1386  // Effectively this means we do not know the concrete type of the "expanded children" iterator,
1387  // only that it adheres to the same IterSource sub-interface as used on the base iterator.
1388  auto ii = explore(vsit)
1389  .expand ([](PrivateSource& source){ return source.expandChildren(); });
1390 
1391  CHECK (not isnil (ii));
1392  CHECK (5 == *ii);
1393  CHECK (5 == vsit.currentVal());
1394  ++ii;
1395  CHECK (4 == *ii);
1396  CHECK (4 == vsit.currentVal());
1397 
1398  CHECK (0 == ii.depth());
1399  ii.expandChildren(); // note: calls through source's VTable to invoke VerySpecificIter::expandChildren()
1400  CHECK (1 == ii.depth());
1401 
1402  CHECK (2 == *ii);
1403  ++ii;
1404  CHECK (1 == *ii);
1405 
1406  CHECK (4 == vsit.currentVal()); // note: as long as expanded children are alive, the source pipeline is not pulled further
1407  CHECK (1 == ii.depth());
1408  ++ii;
1409  CHECK (0 == ii.depth()); // ... but now the children were exhausted and thus also the source advanced
1410  CHECK (3 == *ii);
1411  CHECK (3 == vsit.currentVal());
1412  ++ii;
1413  CHECK (2 == *ii);
1414  CHECK (2 == vsit.currentVal());
1415  ++ii;
1416  CHECK (1 == *ii);
1417  CHECK (1 == vsit.currentVal());
1418  ++ii;
1419  CHECK (isnil (ii));
1420  }
1421 
1422 
1423 
1441  void
1443  {
1444  CHECK (materialise(
1445  explore(CountDown{4})
1446  .expand([](uint j){ return CountDown{j-1}; })
1447  .expandAll()
1448  .transform([](int i){ return i*10; })
1449  )
1450  == "40-30-20-10-10-20-10-10-30-20-10-10-20-10-10");
1451 
1452 
1453  using std::get;
1454  using Tu2 = std::tuple<uint, uint>;
1455  auto summingExpander = [](Tu2 const& tup)
1456  {
1457  uint val = get<0>(tup);
1458  uint sum = get<1>(tup);
1459  return val? singleValIterator (Tu2{val-1, sum+val})
1460  : SingleValIter<Tu2>();
1461  };
1462 
1463  CHECK (materialise(
1464  explore(CountDown{4})
1465  .transform([](uint i){ return Tu2{i,0}; })
1466  .expand(summingExpander)
1467  .expandAll()
1468  .transform([](Tu2 res){ return get<1>(res); })
1469  )
1470  == "0-4-7-9-10-0-3-5-6-0-2-3-0-1");
1471  }
1472 
1473 
1474 
1498  void
1500  {
1501  // Layer-1: the search space with "hidden" implementation
1502  using DataSrc = IterExploreSource<char>;
1503  DataSrc searchSpace = explore(RandomSeq{-1})
1504  .expand([](char){ return RandomSeq{15}; })
1505  .asIterSource();
1506 
1507  // Layer-2: State for search algorithm
1508  struct State
1509  {
1510  DataSrc& src;
1511  string& toFind;
1512  vector<uint> protocol;
1513 
1514  State(DataSrc& s, string& t)
1515  : src{s}
1516  , toFind{t}
1517  , protocol{0}
1518  { }
1519 
1520  bool
1521  checkPoint() const
1522  {
1523  return bool{src};
1524  }
1525 
1526  State&
1527  yield() const
1528  {
1529  return *unConst(this);
1530  }
1531 
1532  void
1533  iterNext()
1534  {
1535  ++src;
1536  protocol.resize (1+src.depth());
1537  ++protocol.back();
1538  }
1539 
1540  void
1541  expandChildren()
1542  {
1543  src.expandChildren();
1544  protocol.resize (1+src.depth());
1545  }
1546 
1547  bool
1548  isMatch() const
1549  {
1550  ASSERT (src.depth() < toFind.size());
1551  return *src == toFind[src.depth()];
1552  }
1553  };
1554 
1555 
1556  // Layer-3: Evaluation pipeline to drive search
1557  string toFind = util::join (explore (RandomSeq{5}), "");
1558  cout << "Search in random tree: toFind = "<<toFind<<endl;
1559 
1560  auto theSearch = explore (State{searchSpace, toFind})
1561  .filter([](auto& it)
1562  {
1563  while (it->src.depth() < it->toFind.size() - 1
1564  and it->isMatch())
1565  it->expandChildren();
1566 
1567  return it->isMatch();
1568  });
1569 
1570 
1571  // perform the search over a random tree...
1572  CHECK (not isnil(theSearch));
1573  cout << "Protocol of the search: " << materialise(theSearch->protocol) <<endl;
1574  }
1575  };
1576 
1577 
1578 
1579  LAUNCHER (IterExplorer_test, "unit common");
1580 
1581 
1582 }} // namespace lib::test
1583 
This iteration _"state core" type_ describes a descending sequence of numbers yet to be delivered...
string materialise(II &&ii)
Diagnostic helper: join all the elements from the iterator.
Automatically use custom string conversion in C++ stream output.
auto explore(IT &&srcSeq)
start building a IterExplorer by suitably wrapping the given iterable source.
bool filter(Placement< DummyMO > const &candidate)
a filter predicate to pick some objects from a resultset.
Definition: run.hpp:40
demo of a custom processing layer interacting directly with the iteration mechanism.
ostringstream protocol
used to verify the test function calls
Front-end for printf-style string template interpolation.
int rani(uint bound=_iBOUND())
Definition: random.hpp:135
bool operator==(PtrDerefIter< I1 > const &il, PtrDerefIter< I2 > const &ir)
Supporting equality comparisons...
#define VERIFY_ERROR(ERROR_ID, ERRONEOUS_STATEMENT)
Macro to verify that a statement indeed raises an exception.
A straight descending number sequence as basic test iterator.
Iterator front-end to manage and operate a IterExplorer pipeline opaquely.
A front-end for using printf-style formatting.
Implementation namespace for support and library code.
Iteration source interface to abstract a data source, which then can be accessed through IterAdapter ...
Definition: iter-source.hpp:79
Simplistic test class runner.
int reduce(Gtk::Button &icon)
attempt to reduce space consumption
Another Lumiera Forward Iterator building block, based on incorporating a state type as »*State Core*...
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
A collection of frequently used helper functions to support unit testing.
_SeqT< CON >::Range eachElm(CON &coll)
auto singleValIterator(VAL &&something)
Build a SingleValIter: convenience free function shortcut, to pick up just any value and wrap it as L...
Definition: itertools.hpp:655
Helpers for type detection, type rewriting and metaprogramming.
Collection of small helpers and convenience shortcuts for diagnostics & formatting.
void pullOut(II &ii)
Diagnostic helper: "squeeze out" the given iterator until exhaustion.
Helpers for working with iterators based on the pipeline model.
Pseudo-Iterator to yield just a single value.
Definition: itertools.hpp:626
Building tree expanding and backtracking evaluations within hierarchical scopes.
Preconfigured adapters for some STL container standard usage situations.
Standard implementation of the IterSource interface: a wrapped "Lumiera Forward Iterator".
Another iteration _"state core"_ to produce a sequence of random numbers.
bool isSameObject(A const &a, B const &b)
compare plain object identity, based directly on the referee&#39;s memory identities. ...
Definition: util.hpp:421