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) Lumiera.org
5  2017, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 * *****************************************************/
22 
53 #include "lib/test/run.hpp"
54 #include "lib/test/test-helper.hpp"
55 #include "lib/iter-adapter-stl.hpp"
56 #include "lib/format-string.hpp"
57 #include "lib/format-cout.hpp"
58 #include "lib/format-util.hpp"
59 #include "lib/itertools.hpp"
60 #include "lib/util.hpp"
61 
62 #include "lib/iter-explorer.hpp"
63 #include "lib/meta/trait.hpp"
64 
65 #include <utility>
66 #include <vector>
67 #include <limits>
68 #include <string>
69 #include <tuple>
70 
71 
72 namespace lib {
73 namespace test{
74 
75  using ::Test;
76  using util::_Fmt;
77  using util::isnil;
78  using util::isSameObject;
80  using lumiera::error::LERR_(ITER_EXHAUST);
81  using std::vector;
82  using std::string;
83 
84 
85  namespace { // test substrate: simple number sequence iterator
86 
91  struct CountDown
92  {
93  uint p,e;
94 
95  CountDown(uint start =0, uint end =0)
96  : p(start)
97  , e(end)
98  { }
99 
100  bool
101  checkPoint () const
102  {
103  return p > e;
104  }
105 
106  uint&
107  yield () const
108  {
109  return util::unConst (checkPoint()? p : e);
110  }
111 
112  void
113  iterNext ()
114  {
115  if (not checkPoint()) return;
116  --p;
117  }
118 
119  bool
120  operator== (CountDown const& o) const
121  {
122  return e == o.e
123  and p == o.p;
124  }
125  };
126 
127 
134  : public IterStateWrapper<uint, CountDown>
135  {
136 
137  public:
138  explicit
139  NumberSequence(uint start = 0)
141  { }
142  NumberSequence(uint start, uint end)
144  { }
145  };
146 
147 
148 
153  class RandomSeq
154  {
155  size_t lim_;
156  size_t cnt_;
157  char letter_;
158 
159  static char
160  rndLetter()
161  {
162  return 'A' + rand() % 26;
163  }
164 
165  public:
166  RandomSeq(int len =0)
167  : lim_{len>=0? len : std::numeric_limits<size_t>::max()}
168  , cnt_{0}
169  , letter_{rndLetter()}
170  { }
171 
172  bool
173  checkPoint () const
174  {
175  return cnt_ < lim_;
176  }
177 
178  char&
179  yield () const
180  {
181  return unConst(this)->letter_;
182  }
183 
184  void
185  iterNext ()
186  {
187  ASSERT (checkPoint());
188  ++cnt_;
189  letter_ = rndLetter();
190  }
191  };
192 
193 
195  template<class II>
196  inline string
197  materialise (II&& ii)
198  {
199  return util::join (std::forward<II> (ii), "-");
200  }
201 
203  template<class II>
204  inline void
205  pullOut (II & ii)
206  {
207  while (ii)
208  {
209  cout << *ii;
210  if (++ii) cout << "-";
211  }
212  cout << endl;
213  }
214 
215  } // (END) test helpers
216 
217 
218 
219 
220 
221 
222 
223  /*******************************************************************/
269  class IterExplorer_test : public Test
270  {
271 
272  virtual void
273  run (Arg)
274  {
275  verify_wrappedState();
276  verify_wrappedIterator();
277 
278  verify_expandOperation();
279  verify_expand_rootCurrent();
280  verify_transformOperation();
281  verify_combinedExpandTransform();
282  verify_customProcessingLayer();
283  verify_scheduledExpansion();
284  verify_untilStopTrigger();
285  verify_FilterIterator();
286  verify_FilterChanges();
287  verify_asIterSource();
288  verify_IterSource();
289  verify_reduceVal();
290  verify_effuse();
291 
292  verify_depthFirstExploration();
293  demonstrate_LayeredEvaluation();
294  }
295 
296 
297 
301  void
303  {
304  auto ii = explore (CountDown{5,0});
305  CHECK (!isnil (ii));
306  CHECK (5 == *ii);
307  ++ii;
308  CHECK (4 == *ii);
309  pullOut(ii);
310  CHECK ( isnil (ii));
311  CHECK (!ii);
312 
313  VERIFY_ERROR (ITER_EXHAUST, *ii );
314  VERIFY_ERROR (ITER_EXHAUST, ++ii );
315 
316  ii = explore (CountDown{5});
317  CHECK (materialise(ii) == "5-4-3-2-1");
318  ii = explore (CountDown{7,4});
319  CHECK (materialise(ii) == "7-6-5");
320  ii = explore (CountDown{});
321  CHECK ( isnil (ii));
322  CHECK (!ii);
323  }
324 
325 
327  void
329  {
330  vector<int> numz{1,-2,3,-5,8,-13};
331  auto ii = eachElm(numz);
332  CHECK (!isnil (ii));
333  CHECK (1 == *ii);
334  ++ii;
335  CHECK (-2 == *ii);
336 
337  auto jj = explore(ii);
338  CHECK (!isnil (jj));
339  CHECK (-2 == *jj);
340  ++jj;
341  CHECK (3 == *jj);
342 
343  // we passed a LValue-Ref, thus a copy was made
344  CHECK (-2 == *ii);
345 
346  CHECK (materialise(ii) == "-2-3--5-8--13");
347  CHECK (materialise(jj) == "3--5-8--13");
348 
349  // can even adapt STL container automatically
350  auto kk = explore(numz);
351  CHECK (!isnil (kk));
352  CHECK (1 == *kk);
353  CHECK (materialise(kk) == "1--2-3--5-8--13");
354  }
355 
356 
357 
392  void
394  {
395  /* == "monadic flatMap" == */
396 
397  verify_treeExpandingIterator(
398  explore(CountDown{5})
399  .expand([](uint j){ return CountDown{j-1}; }) // expand-functor: Val > StateCore
400  );
401 
402  verify_treeExpandingIterator(
403  explore(CountDown{5})
404  .expand([](uint j){ return NumberSequence{j-1}; }) // expand-functor: Val > Iter
405  ); // NOTE: different Iterator type than the source!
406 
407  // lambda with side-effect and return type different from source iter
408  vector<vector<uint>> childBuffer;
409  auto expandIntoChildBuffer = [&](uint j) -> vector<uint>&
410  {
411  childBuffer.emplace_back();
412  vector<uint>& childNumbz = childBuffer.back();
413  for (size_t i=0; i<j-1; ++i)
414  childNumbz.push_back(j-1 - i);
415  return childNumbz;
416  };
417 
418  verify_treeExpandingIterator(
419  explore(CountDown{5})
420  .expand(expandIntoChildBuffer) // expand-functor: Val > STL-container&
421  );
422 
423  // test routine called the expansion functor five times
424  CHECK (5 == childBuffer.size());
425 
426 
427 
428  /* == "state manipulation" use cases == */
429 
430  verify_treeExpandingIterator(
431  explore(CountDown{5})
432  .expand([](CountDown const& core){ return CountDown{ core.yield() - 1}; }) // expand-functor: StateCore const& -> StateCore
433  );
434 
435  verify_treeExpandingIterator(
436  explore(CountDown{5})
437  .expand([](CountDown core){ return NumberSequence{ core.yield() - 1}; }) // expand-functor: StateCore -> Iter
438  );
439 
440  verify_treeExpandingIterator(
441  explore(CountDown{5})
442  .expand([](auto & it){ return CountDown{ *it - 1}; }) // generic Lambda: Iter& -> StateCore
443  );
444 
445  verify_treeExpandingIterator(
446  explore(CountDown{5})
447  .expand([](auto it){ return decltype(it){ *it - 1}; }) // generic Lambda: Iter -> Iter
448  );
449  }
450 
451 
452  template<class EXP>
453  void
454  verify_treeExpandingIterator (EXP ii)
455  {
456  CHECK (!isnil (ii));
457  CHECK (5 == *ii);
458  ++ii;
459  CHECK (4 == *ii);
460 
461  CHECK (0 == ii.depth());
462  ii.expandChildren();
463  CHECK (3 == *ii);
464  CHECK (1 == ii.depth());
465  ++ii;
466  CHECK (2 == *ii);
467  CHECK (1 == ii.depth());
468  ii.expandChildren();
469  CHECK (1 == *ii);
470  CHECK (2 == ii.depth());
471  ++ii;
472  CHECK (1 == *ii);
473  CHECK (1 == ii.depth());
474  ++ii;
475  CHECK (3 == *ii);
476  CHECK (0 == ii.depth());
477  CHECK (materialise(ii) == "3-2-1");
478  ii.expandChildren();
479  CHECK (1 == ii.depth());
480  CHECK (materialise(ii) == "2-1-2-1");
481  ++++ii;
482  CHECK (0 == ii.depth());
483  CHECK (materialise(ii) == "2-1");
484  ii.expandChildren();
485  CHECK (1 == ii.depth());
486  CHECK (materialise(ii) == "1-1");
487  ++ii;
488  CHECK (0 == ii.depth());
489  CHECK (1 == *ii);
490  CHECK (materialise(ii) == "1");
491  ii.expandChildren();
492  CHECK (isnil (ii));
493  VERIFY_ERROR (ITER_EXHAUST, *ii );
494  VERIFY_ERROR (ITER_EXHAUST, ++ii );
495  }
496 
497 
505  void
507  {
508  auto tree = explore(CountDown{25})
509  .expand([](uint j){ return CountDown{j-1}; });
510 
511  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");
512 
513  CHECK (0 == tree.depth());
514  CHECK (25 == *tree);
515  ++tree;
516  ++tree;
517  ++tree;
518  ++tree;
519  CHECK (21 == *tree);
520  tree.expandChildren();
521  CHECK (1 == tree.depth());
522  ++tree;
523  ++tree;
524  ++tree;
525  ++tree;
526  ++tree;
527  CHECK (15 == *tree);
528  tree.expandChildren();
529  ++tree;
530  ++tree;
531  CHECK (2 == tree.depth());
532  CHECK (materialise(tree) == "12-11-10-9-8-7-6-5-4-3-2-1-" // this is the level-2 child sequence
533  "14-13-12-11-10-9-8-7-6-5-4-3-2-1-" // ...returning to the rest of the level-1 sequence
534  "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
535  CHECK (12 == *tree);
536 
537  tree.rootCurrent();
538  CHECK (12 == *tree);
539  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.
540  CHECK (0 == tree.depth());
541  }
542 
543 
544 
560  void
562  {
563  auto multiply = [](int v){ return 2*v; }; // functional map: value -> value
564 
565  _Fmt embrace{"≺%s≻"};
566  auto formatify = [&](auto it){ return string{embrace % *it}; }; // generic lambda: assumed to take an Iterator&
567 
568 
569  auto ii = explore(CountDown{7,4})
570  .transform(multiply)
571  ;
572 
573  CHECK (14 == *ii);
574  CHECK (14 == *ii);
575  ++ii;
576  CHECK (12 == *ii);
577  ++ii;
578  CHECK (10 == *ii);
579  ++ii;
580  CHECK (isnil (ii));
581  VERIFY_ERROR (ITER_EXHAUST, *ii );
582  VERIFY_ERROR (ITER_EXHAUST, ++ii );
583 
584 
585 
586  // demonstrate chaining of several transformation layers
587  vector<int64_t> numz{1,-2,3,-5,8,-13};
588 
589  CHECK ("≺1≻-≺-2≻-≺3≻-≺-5≻-≺8≻-≺-13≻" == materialise (explore(numz)
590  .transform(formatify)) );
591 
592  CHECK ("≺2≻-≺-4≻-≺6≻-≺-10≻-≺16≻-≺-26≻" == materialise (explore(numz)
593  .transform(multiply)
594  .transform(formatify)) );
595 
596  CHECK ("≺≺4≻≻-≺≺-8≻≻-≺≺12≻≻-≺≺-20≻≻-≺≺32≻≻-≺≺-52≻≻" == materialise (explore(numz)
597  .transform(multiply)
598  .transform(multiply)
599  .transform(formatify)
600  .transform(formatify)) );
601 
602 
603  // demonstrate the functor is evaluated only once per step
604  int fact = 3;
605 
606  auto jj = explore (CountDown{4})
607  .transform([&](int v)
608  {
609  v *=fact;
610  fact *= -2;
611  return v;
612  });
613  CHECK (3*4 == *jj);
614  CHECK (fact == -2*3);
615 
616  CHECK (3*4 == *jj);
617  CHECK (3*4 == *jj);
618 
619  ++jj;
620  CHECK (fact == -2*3); // NOTE : functor is evaluated on first demand
621  CHECK (-2*3*3 == *jj); // ...which happens on yield (access the iterator value)
622  CHECK (fact == 2*2*3); // and this also causes the side-effect
623  CHECK (-2*3*3 == *jj);
624  CHECK (-2*3*3 == *jj);
625  CHECK (fact == 2*2*3); // no further evaluation and thus no further side-effect
626 
627  ++jj;
628  CHECK (2*2*3*2 == *jj);
629  CHECK (fact == -2*2*2*3);
630 
631  fact = -23;
632  CHECK (2*2*3*2 == *jj);
633 
634  ++jj;
635  CHECK (fact == -23);
636  CHECK (-23*1 == *jj);
637  CHECK (fact == 2*23);
638 
639  ++jj;
640  CHECK (isnil (jj));
641  CHECK (fact == 2*23);
642 
643  VERIFY_ERROR (ITER_EXHAUST, *ii );
644  CHECK (fact == 2*23); // exhaustion detected on source and thus no further evaluation
645 
646 
647 
648  // demonstrate a transformer accessing the source state core...
649  // should not be relevant in practice, but works due to the generic adapters
650  auto kk = explore (CountDown{9,4})
651  .transform([](CountDown& core)
652  {
653  uint delta = core.p - core.e;
654  if (delta % 2 == 0)
655  --core.p; // EVIL EVIL
656  return delta;
657  });
658 
659  CHECK (5 == *kk); // the delta between 9 (start) and 4 (end)
660  ++kk;
661  CHECK (4 == *kk); // Core manipulated by SIDE-EFFECT at this point...
662  CHECK (4 == *kk); // ...but not yet obvious, since the result is cached
663  ++kk;
664  CHECK (2 == *kk); // Surprise -- someone ate my numberz...
665  ++kk;
666  CHECK (isnil (kk));
667  }
668 
669 
692  void
694  {
695  auto ii = explore(CountDown{5})
696  .expand([](uint j){ return CountDown{j-1}; })
697  .transform([](int v){ return 2*v; })
698  ;
699 
700  CHECK ("int" == meta::typeStr(*ii)); // result type is what the last transformer yields
701  CHECK (10 == *ii);
702  ++ii;
703  CHECK (8 == *ii);
704  ii.expandChildren();
705  CHECK ("6-4-2-6-4-2" == materialise(ii) );
706 
707 
708  // the following contrived example demonstrates
709  // how intermediary processing steps may interact
710 
711  CHECK (materialise (
712  explore(CountDown{5})
713  .expand([](uint j){ return CountDown{j-1}; })
714  .transform([](int v){ return 2*v; })
715  .transform([](auto& it)
716  {
717  auto elm = *it;
718  if (elm == 6)
719  {
720  it.expandChildren(); // NOTE at that point we're forced to decide if
721  elm = *it * 10; // we want to return the parent or the 1st child
722  }
723  return elm;
724  })
725  .transform([](float f){ return 0.055 + f/2; })
726  )
727  == "5.055-4.055-20.055-1.055-2.055-1.055" );
728  }
729 
730 
736  template<class SRC>
738  : public SRC
739  {
740  using SRC::SRC;
741 
742  void
743  iterNext()
744  {
745  ++(*this);
746  if (*this)
747  ++(*this);
748  }
749  };
750 
756  void
758  {
759  CHECK (materialise(
760  explore(CountDown{7})
761  .processingLayer<MagicTestRubbish>()
762  )
763  == "7-5-3-1");
764 
765  CHECK (materialise(
766  explore(CountDown{7})
767  .transform([](uint v){ return 2*v; })
768  .processingLayer<MagicTestRubbish>()
769  .filter([](int v){ return v % 3; })
770  )
771  == "14-10-2");
772  }
773 
774 
775 
785  void
787  {
788  auto ii = explore(CountDown{6})
789  .expand([](uint j){ return CountDown{j-2}; })
790  .expandOnIteration();
791 
792  CHECK (!isnil (ii));
793  CHECK (6 == *ii);
794  ++ii;
795  CHECK (5 == *ii);
796  CHECK (ii.depth() == 0);
797 
798  ii.expandChildren();
799  CHECK (5 == *ii);
800  CHECK (ii.depth() == 0);
801  ++ii;
802  CHECK (3 == *ii);
803  CHECK (ii.depth() == 1);
804 
805  ii.expandChildren();
806  ii.expandChildren();
807  CHECK (ii.depth() == 1);
808  CHECK (3 == *ii);
809  ++ii;
810  CHECK (1 == *ii);
811  CHECK (ii.depth() == 2);
812  ++ii;
813  CHECK (2 == *ii);
814  CHECK (ii.depth() == 1);
815 
816  ii.expandChildren();
817  ++ii;
818  CHECK (1 == *ii);
819  CHECK (ii.depth() == 1);
820  ++ii;
821  CHECK (4 == *ii);
822  CHECK (ii.depth() == 0);
823  ++ii;
824  CHECK (3 == *ii);
825  ++ii;
826  CHECK (2 == *ii);
827  ++ii;
828  CHECK (1 == *ii);
829  ++ii;
830  CHECK (isnil (ii));
831  }
832 
833 
834 
841  void
843  {
844  CHECK (materialise (
845  explore (CountDown{10})
846  .iterUntil([](uint j){ return j < 5; })
847  )
848  == "10-9-8-7-6-5"_expect);
849 
850  CHECK (materialise (
851  explore (CountDown{10})
852  .iterWhile([](uint j){ return j > 5; })
853  )
854  == "10-9-8-7-6"_expect);
855 
856  CHECK (materialise (
857  explore (CountDown{10})
858  .iterWhile([](int j){ return j > -5; })
859  )
860  == "10-9-8-7-6-5-4-3-2-1"_expect);
861 
862  CHECK (materialise (
863  explore (CountDown{10})
864  .iterWhile([](uint j){ return j > 25; })
865  )
866  == ""_expect);
867  }
868 
869 
870 
877  void
879  {
880  // canonical example, using a clean side-effect free predicate based on element values
881  CHECK (materialise (
882  explore(CountDown{10})
883  .filter([](uint j){ return j % 2; })
884  )
885  == "9-7-5-3-1"_expect);
886 
887 
888  // Filter may lead to consuming util exhaustion...
889  auto ii = explore(CountDown{10})
890  .filter([](int j){ return j > 9; });
891 
892  CHECK (not isnil (ii));
893  CHECK (10 == *ii);
894  ++ ii;
895  CHECK (isnil (ii));
896  VERIFY_ERROR (ITER_EXHAUST, ++ii );
897 
898 
899  // none of the source elements can be approved here...
900  auto jj = explore(CountDown{5})
901  .filter([](int j){ return j > 9; });
902 
903  CHECK (isnil (jj));
904 
905 
906 
907  // a tricky example, where the predicate takes the source core as argument;
908  // since the source core is embedded as baseclass, it can thus "undermine"
909  // and bypass the layers configured in between; here the transformer changes
910  // uint to float, but the filter interacts directly with the core and thus
911  // judges based on the original values
912  CHECK (materialise (
913  explore(CountDown{10,4})
914  .transform([](float f){ return 0.55 + 2*f; })
915  .filter([](CountDown& core){ return core.p % 2; })
916  )
917  == "18.55-14.55-10.55"_expect);
918 
919 
920 
921  // contrived example to verify interplay of filtering and child expansion;
922  // especially note that the filter is re-evaluated after expansion happened.
923  CHECK (materialise (
924  explore(CountDown{10})
925  .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
926  .filter([](uint i){ return i%2 == 0; })
927  .expandAll() // Note: sends the expandChildren down through the filter
928  )
929  == "10-8-6-4-2-2-6-4-2-2"_expect);
930 
931 
932 
933  // another convoluted example to demonstrate
934  // - a filter predicate with side-effect
935  // - and moreover the predicate is a generic lambda
936  // - accepting the iterator to trigger child expansion
937  // - which also causes re-evaluation of the preceding transformer
938  bool toggle = false;
939  auto kk = explore(CountDown{10,5})
940  .expand([](uint j){ return CountDown{j-1}; })
941  .transform([](int v){ return 2*v; })
942  .filter([&](auto& it)
943  {
944  if (*it == 16)
945  {
946  it.expandChildren();
947  toggle = true;
948  }
949  return toggle;
950  });
951 
952  CHECK (materialise(kk)
953  == "14-12-10-8-6-4-2-14-12"_expect);
954  // Explanation:
955  // The source starts at 10, but since the toggle is false,
956  // none of the initial values makes it though to the result.
957  // The interspersed transformer doubles the source values, and
958  // thus at source == 8 the trigger value (16) is hit. Thus the
959  // filter now flips the context-bound toggle (side-effect) and
960  // then expands children, which consumes current source value 8
961  // to replace it with the sequence 7,6,5,4,3,2,1, followed by
962  // the rest of the original sequence, 7,6 (which stops above 5).
963 
964  CHECK (materialise(kk.filter([](long i){ return i % 7; }))
965  == "12-10-8-6-4-2-12"_expect);
966  // Explanation:
967  // Since the original IterExplorer was assigned to variable kk,
968  // the materialise()-Function got a lvalue-ref and thus made a copy
969  // of the whole compound. For that reason, the original state within
970  // kk still rests at 7 -- because the filter evaluates eagerly, the
971  // source was pulled right at construction until we reached the first
972  // value to yield, which is the first child (7,....) within the
973  // expanded sequence. But now, in the second call to materialise(),
974  // we don't just copy, rather we add another filter layer on top,
975  // which happens to filter away this first result (== 2*7), and
976  // also the first element of the original sequence after the
977  // expanded children
978 
979  // WARNING: kk is now defunct, since we moved it into the builder expression
980  // and then moved the resulting extended iterator into materialise!
981  }
982 
983 
984 
986  void
988  {
989  auto seq = explore(CountDown{20})
990  .mutableFilter();
991 
992  auto takeEve = [](uint i){ return i%2 == 0; };
993  auto takeTrd = [](uint i){ return i%3 == 0; };
994 
995  CHECK (20 == *seq);
996  ++seq;
997  CHECK (19 == *seq);
998  CHECK (19 == *seq);
999 
1000  seq.andFilter (takeEve);
1001  CHECK (18 == *seq);
1002  ++seq;
1003  CHECK (16 == *seq);
1004 
1005  seq.andFilter (takeTrd);
1006  CHECK (12 == *seq); // is divisible (by 2 AND by 3)
1007 
1008  seq.flipFilter();
1009  CHECK (11 == *seq); // not divisible (by 2 AND by 3)
1010  ++seq;
1011  CHECK (10 == *seq);
1012 
1013  seq.setNewFilter (takeTrd);
1014  CHECK ( 9 == *seq);
1015  ++seq;
1016  CHECK ( 6 == *seq);
1017 
1018  seq.orNotFilter (takeEve);
1019  CHECK ( 6 == *seq);
1020  ++seq;
1021  CHECK ( 5 == *seq); // disjunctive condition actually weakens the filter
1022  ++seq;
1023  CHECK ( 3 == *seq);
1024 
1025  // NOTE: arbitrary functors can be used/combined,
1026  // since they are adapted individually.
1027  // To demonstrate this, we use a functor accessing and
1028  // manipulating the state core by side effect...
1029  string buff{"."};
1030  seq.andNotFilter ([&](CountDown& core)
1031  {
1032  buff += util::toString(core.p) + ".";
1033  --core.p; // manipulate state core
1034  return core.p % 2; // return a number, not bool
1035  });
1036 
1037  CHECK ( 2 == *seq); // value in the core has been manipulated
1038  CHECK (".3." == buff); // the filter has been invoked once, and saw core == 3
1039 
1040  ++seq; // core == 2 is filtered by the existing other filter (== not take even)
1041  CHECK (".3.1." == buff); // the filter has been invoked again, and saw core == 1
1042  CHECK (0 == seq.p); // ...which he manipulated, so that core == 0
1043  CHECK (isnil (seq)); // .....and thus iteration end is detected
1044  VERIFY_ERROR (ITER_EXHAUST, *seq );
1045 
1046 
1047  // verify enabling and disabling...
1048  seq = explore(CountDown{10})
1049  .mutableFilter(takeTrd);
1050 
1051  CHECK (9 == *seq);
1052  seq.disableFilter();
1053  CHECK (9 == *seq);
1054  ++seq;
1055  CHECK (8 == *seq);
1056  seq.andNotFilter (takeEve);
1057  CHECK (7 == *seq);
1058  ++seq;
1059  CHECK (5 == *seq);
1060  seq.disableFilter();
1061  CHECK (5 == *seq);
1062  ++seq;
1063  CHECK (4 == *seq);
1064  ++seq;
1065  CHECK (3 == *seq);
1066  seq.flipFilter(); // everything rejected
1067  CHECK (isnil (seq));
1068  }
1069 
1070 
1071 
1072 
1075  void
1077  {
1078  auto accumulated = explore(CountDown{30})
1079  .transform([](int i){ return i-1; }) // note: implicitly converts uint -> int
1080  .resultSum();
1081 
1082  using Res = decltype(accumulated);
1083  CHECK (lib::test::showType<Res>() == "int"_expect);
1084 
1085  auto expectedSum = [](auto N){ return N*(N+1) / 2; };
1086  CHECK (accumulated == expectedSum(29));
1087 
1088  // In the general case an accessor and a junctor can be given...
1089  CHECK (explore(CountDown{10})
1090  .reduce([](int i){ return i - 0.5; } // accessor: produce a double
1091  ,[](string accu, float val)
1092  {
1093  return accu+">"+util::toString(val); // junctor: convert to String and combine with separator char
1094  }
1095  , string{">-"} // seedVal: starting point for the reduction; also defines result type
1096  )
1097  == ">->9.5>8.5>7.5>6.5>5.5>4.5>3.5>2.5>1.5>0.5"_expect);
1098 
1099  // If only the accessor is given, values are combined by std::plus...
1100  CHECK (explore(CountDown{9})
1101  .reduce([](auto it) -> string
1102  {
1103  return _Fmt{"○%s●"} % *it; // accessor: format into a string
1104  })
1105  == "○9●○8●○7●○6●○5●○4●○3●○2●○1●"_expect);
1106  }
1107 
1108 
1109 
1112  void
1114  {
1115  auto solidified = explore(CountDown{20})
1116  .filter ([](uint i){ return i % 2; })
1117  .transform([](uint i){ return 0.5*i; })
1118  .effuse();
1119 
1120  using Res = decltype(solidified);
1121  CHECK (lib::test::showType<Res>() == "vector<double>"_expect);
1122  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);
1123  }
1124 
1125 
1126 
1127 
1149  void
1151  {
1152  IterSource<uint>::iterator sequence; // note `sequence` is polymorphic
1153  CHECK (isnil (sequence));
1154 
1155  sequence = explore(CountDown{20,10})
1156  .filter([](uint i){ return i % 2; })
1157  .asIterSource(); // note this terminal builder function
1158  // moves the whole pipeline onto the heap
1159  CHECK (not isnil (sequence));
1160  CHECK (19 == *sequence);
1161 
1162 
1163  // use one sequence as source to build another one
1164  sequence = explore(sequence)
1165  .transform([](uint i){ return i*2; })
1166  .asIterSource();
1167 
1168  CHECK (38 == *sequence);
1169  CHECK ("38-34-30-26-22" == materialise(sequence));
1170 
1171  // WARNING pitfall: `sequence` is a copyable iterator front-end
1172  // but holds onto the actual pipeline by shared-ptr
1173  // Thus, even while materialise() creates a copy,
1174  // the iteration state gets shared....
1175  CHECK (22 == *sequence);
1176  ++sequence; // ...and even worse, iteration end is only detected after increment
1177  CHECK (isnil (sequence));
1178 
1179 
1180  // extended API to invoke child expansion opaquely
1181  IterExploreSource<char> exploreIter;
1182  CHECK (isnil (exploreIter));
1183 
1184  exploreIter = explore(CountDown{20,10})
1185  .filter([](uint i){ return i % 2; })
1186  .transform([](uint i){ return i*2; })
1187  .filter([](int i){ return i>25; })
1188  .expand([](uint i){ return CountDown{i-10, 20}; })
1189  .transform([](uint u) -> char { return '@'+u-20; })
1190  .asIterSource();
1191 
1192 
1193  CHECK ('R' == *exploreIter); // 38-20 + '@'
1194  ++exploreIter;
1195  CHECK ('N' == *exploreIter); // 34-20 + '@'
1196 
1197  exploreIter.expandChildren(); // expand consumes the current element (34)
1198  // and injects the sequence (24...20[ instead
1199  CHECK ('D' == *exploreIter); // 34-10 == 24 and 'D' == 24-20 + '@'
1200 
1201  CHECK ("D-C-B-A-J-F" == materialise(exploreIter));
1202  } // note how the remainder of the original sequence is picked up with 'J'...
1203 
1204 
1205 
1206 
1218  void
1220  {
1221  class PrivateSource
1222  : public IterSource<uint>
1223  {
1224  public:
1225  virtual PrivateSource* expandChildren() const =0;
1226  };
1227 
1228  class VerySpecificIter
1229  : public WrappedLumieraIter<NumberSequence
1230  , PrivateSource >
1231  {
1232  public:
1233  VerySpecificIter(uint start)
1234  : WrappedLumieraIter(NumberSequence{start})
1235  { }
1236 
1237  virtual PrivateSource*
1238  expandChildren() const override
1239  {
1240  return new VerySpecificIter{*wrappedIter() - 2};
1241  }
1242 
1243  uint
1244  currentVal() const
1245  {
1246  return *wrappedIter();
1247  }
1248  };
1249 
1250 
1251  // simple standard case: create a new heap allocated IterSource implementation.
1252  // IterExplorer will take ownership (by smart-ptr) and build a Lumiera Iterator front-End
1253  CHECK ("7-6-5-4-3-2-1" == materialise (
1254  explore (new VerySpecificIter{7})));
1255 
1256 
1257  // missing source detected
1258  PrivateSource* niente = nullptr;
1259  CHECK (isnil (explore (niente)));
1260 
1261 
1262  // attach to an IterSource living here in local scope...
1263  VerySpecificIter vsit{5};
1264 
1265  // ...and build a child expansion on top, which calls through the PrivateSource-API
1266  // Effectively this means we do not know the concrete type of the "expanded children" iterator,
1267  // only that it adheres to the same IterSource sub-interface as used on the base iterator.
1268  auto ii = explore(vsit)
1269  .expand ([](PrivateSource& source){ return source.expandChildren(); });
1270 
1271  CHECK (not isnil (ii));
1272  CHECK (5 == *ii);
1273  CHECK (5 == vsit.currentVal());
1274  ++ii;
1275  CHECK (4 == *ii);
1276  CHECK (4 == vsit.currentVal());
1277 
1278  CHECK (0 == ii.depth());
1279  ii.expandChildren(); // note: calls through source's VTable to invoke VerySpecificIter::expandChildren()
1280  CHECK (1 == ii.depth());
1281 
1282  CHECK (2 == *ii);
1283  ++ii;
1284  CHECK (1 == *ii);
1285 
1286  CHECK (4 == vsit.currentVal()); // note: as long as expanded children are alive, the source pipeline is not pulled further
1287  CHECK (1 == ii.depth());
1288  ++ii;
1289  CHECK (0 == ii.depth()); // ... but now the children were exhausted and thus also the source advanced
1290  CHECK (3 == *ii);
1291  CHECK (3 == vsit.currentVal());
1292  ++ii;
1293  CHECK (2 == *ii);
1294  CHECK (2 == vsit.currentVal());
1295  ++ii;
1296  CHECK (1 == *ii);
1297  CHECK (1 == vsit.currentVal());
1298  ++ii;
1299  CHECK (isnil (ii));
1300  }
1301 
1302 
1303 
1321  void
1323  {
1324  CHECK (materialise(
1325  explore(CountDown{4})
1326  .expand([](uint j){ return CountDown{j-1}; })
1327  .expandAll()
1328  .transform([](int i){ return i*10; })
1329  )
1330  == "40-30-20-10-10-20-10-10-30-20-10-10-20-10-10");
1331 
1332 
1333  using std::get;
1334  using Tu2 = std::tuple<uint, uint>;
1335  auto summingExpander = [](Tu2 const& tup)
1336  {
1337  uint val = get<0>(tup);
1338  uint sum = get<1>(tup);
1339  return val? singleValIterator (Tu2{val-1, sum+val})
1340  : SingleValIter<Tu2>();
1341  };
1342 
1343  CHECK (materialise(
1344  explore(CountDown{4})
1345  .transform([](uint i){ return Tu2{i,0}; })
1346  .expand(summingExpander)
1347  .expandAll()
1348  .transform([](Tu2 res){ return get<1>(res); })
1349  )
1350  == "0-4-7-9-10-0-3-5-6-0-2-3-0-1");
1351  }
1352 
1353 
1354 
1378  void
1380  {
1381  // Layer-1: the search space with "hidden" implementation
1382  using DataSrc = IterExploreSource<char>;
1383  DataSrc searchSpace = explore(RandomSeq{-1})
1384  .expand([](char){ return RandomSeq{15}; })
1385  .asIterSource();
1386 
1387  // Layer-2: State for search algorithm
1388  struct State
1389  {
1390  DataSrc& src;
1391  string& toFind;
1392  vector<uint> protocol;
1393 
1394  State(DataSrc& s, string& t)
1395  : src{s}
1396  , toFind{t}
1397  , protocol{0}
1398  { }
1399 
1400  bool
1401  checkPoint() const
1402  {
1403  return bool{src};
1404  }
1405 
1406  State&
1407  yield() const
1408  {
1409  return *unConst(this);
1410  }
1411 
1412  void
1413  iterNext()
1414  {
1415  ++src;
1416  protocol.resize (1+src.depth());
1417  ++protocol.back();
1418  }
1419 
1420  void
1421  expandChildren()
1422  {
1423  src.expandChildren();
1424  protocol.resize (1+src.depth());
1425  }
1426 
1427  bool
1428  isMatch() const
1429  {
1430  ASSERT (src.depth() < toFind.size());
1431  return *src == toFind[src.depth()];
1432  }
1433  };
1434 
1435 
1436  // Layer-3: Evaluation pipeline to drive search
1437  string toFind = util::join (explore (RandomSeq{5}), "");
1438  cout << "Search in random tree: toFind = "<<toFind<<endl;
1439 
1440  auto theSearch = explore (State{searchSpace, toFind})
1441  .filter([](auto& it)
1442  {
1443  while (it->src.depth() < it->toFind.size() - 1
1444  and it->isMatch())
1445  it->expandChildren();
1446 
1447  return it->isMatch();
1448  });
1449 
1450 
1451  // perform the search over a random tree...
1452  CHECK (not isnil(theSearch));
1453  cout << "Protocol of the search: " << materialise(theSearch->protocol) <<endl;
1454  }
1455  };
1456 
1457 
1458 
1459  LAUNCHER (IterExplorer_test, "unit common");
1460 
1461 
1462 }} // namespace lib::test
1463 
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 a copy of 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:49
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.
bool operator==(PtrDerefIter< I1 > const &il, PtrDerefIter< I2 > const &ir)
Supporting equality comparisons...
#define VERIFY_ERROR(ERROR_ID, ERRONEOUS_STATEMENT)
Macro to verify 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:88
Simple 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 right into the i...
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:664
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:635
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, bypassing any custom comparison operators.
Definition: util.hpp:347