1
2 /*
3 * File Metaiterators.hpp.
4 *
5 * This file is part of the source code of the software program
6 * Vampire. It is protected by applicable
7 * copyright laws.
8 *
9 * This source code is distributed under the licence found here
10 * https://vprover.github.io/license.html
11 * and in the source directory
12 *
13 * In summary, you are allowed to use Vampire for non-commercial
14 * purposes but not allowed to distribute, modify, copy, create derivatives,
15 * or use in competitions.
16 * For other uses of Vampire please contact developers for a different
17 * licence, which we will make an effort to provide.
18 */
19 /**
20 * @file Metaiterators.hpp
21 * Defines class Metaiterators.
22 */
23
24
25 #ifndef __Metaiterators__
26 #define __Metaiterators__
27
28 #include <utility>
29 #include <functional>
30
31 #include "Forwards.hpp"
32
33 #include "List.hpp"
34 #include "DHSet.hpp"
35 #include "Recycler.hpp"
36 #include "VirtualIterator.hpp"
37 #include "TimeCounter.hpp"
38
39 namespace Lib {
40
41 ///@addtogroup Iterators
42 ///@{
43
44
45 /**
46 * Return iterator on the container C
47 *
48 * The getContentIterator method makes it possible to
49 * iterate on arbitrary containers, provided the @b ITERATOR_TYPE
50 * macro can obtain the iterator type of the container.
51 *
52 * For types where the use of the @b ITERATOR_TYPE macro is not
53 * suitable, this method can be overloaded to obtain the
54 * iterator by some other means.
55 */
56 template<class C>
getContentIterator(C & c)57 ITERATOR_TYPE(C) getContentIterator(C& c)
58 {
59 return ITERATOR_TYPE(C)(c);
60 }
61
62 /**
63 * Iterator class that iterates an array and never stops. This iterator
64 * needs to be used e.g. inside a WhileLimitedIterator.
65 */
66 template<class El>
67 class InfiniteArrayIterator
68 {
69 public:
70 DECL_ELEMENT_TYPE(El);
InfiniteArrayIterator(const El * ptr)71 InfiniteArrayIterator(const El* ptr) : _nextPtr(ptr) {}
hasNext()72 inline bool hasNext() { return true; }
next()73 inline OWN_ELEMENT_TYPE next() { return *(_nextPtr++); }
74 private:
75 const El* _nextPtr;
76 };
77
78 template<class El>
getInfiniteArrayIterator(const El * ptr)79 InfiniteArrayIterator<El> getInfiniteArrayIterator(const El* ptr)
80 {
81 CALL("getInfiniteArrayIterator");
82 return InfiniteArrayIterator<El>(ptr);
83 }
84
85 /**
86 * Iterator class for types whose elements are accessible by
87 * @b operator[](size_t) with the first element at the index 0
88 * and the others at consecutive indexes
89 *
90 * If the iterated object has a @b size() function, the single
91 * argument constructor can be used. Otherwise the two parameter
92 * constructor must be used, the second parameter being the size
93 * of the container (so that the elements are at indexes 0, ...,
94 * size-1).
95 */
96 template<class Arr>
97 class ArrayishObjectIterator
98 {
99 public:
100 DECL_ELEMENT_TYPE(ELEMENT_TYPE(Arr));
ArrayishObjectIterator(Arr & arr)101 ArrayishObjectIterator(Arr& arr) : _arr(arr),
102 _index(0), _size(_arr.size()) {}
ArrayishObjectIterator(Arr & arr,size_t size)103 ArrayishObjectIterator(Arr& arr, size_t size) : _arr(arr),
104 _index(0), _size(size) {}
hasNext()105 inline bool hasNext() { return _index<_size; }
next()106 inline ELEMENT_TYPE(Arr) next() { ASS(_index<_size); return _arr[_index++]; }
knowsSize()107 inline bool knowsSize() { return true;}
size()108 inline bool size() { return _size;}
109 private:
110 Arr& _arr;
111 size_t _index;
112 size_t _size;
113 };
114
115 template<class Arr>
getArrayishObjectIterator(Arr & arr,size_t size)116 ArrayishObjectIterator<Arr> getArrayishObjectIterator(Arr& arr, size_t size)
117 {
118 CALL("getArrayishObjectIterator");
119 return ArrayishObjectIterator<Arr>(arr, size);
120 }
121
122 template<class Arr>
getArrayishObjectIterator(Arr & arr)123 ArrayishObjectIterator<Arr> getArrayishObjectIterator(Arr& arr)
124 {
125 CALL("getArrayishObjectIterator");
126 return ArrayishObjectIterator<Arr>(arr);
127 }
128
129 /**
130 * Reads given number of values from an input stream.
131 *
132 * Assumes that the input stream has enough values for that!
133 */
134 template<typename T>
135 class InputIterator
136 {
137 public:
138 DECL_ELEMENT_TYPE(T);
InputIterator(istream & inp,size_t cnt)139 InputIterator(istream& inp, size_t cnt) : _inp(inp), _remaining(cnt) {}
140
hasNext() const141 bool hasNext() const { return _remaining>0; }
next()142 T next() {
143 CALL("InputIterator::next");
144 ASS_G(_remaining,0);
145 _remaining--;
146 T res;
147 _inp >> res;
148 return res;
149 }
150
151 private:
152 istream& _inp;
153 size_t _remaining;
154 };
155
156 /**
157 * Iterator class for pointers
158 *
159 * The constructor takes two arguments - a pointer to the first element,
160 * and a pointer to the element after the last element to be returned.
161 *
162 * Consecutive elements are being obtained by the postfix @b operator++().
163 */
164 template<typename T>
165 class PointerIterator
166 {
167 public:
168 DECL_ELEMENT_TYPE(T);
PointerIterator(const T * first,const T * afterLast)169 inline PointerIterator(const T* first, const T* afterLast) :
170 _curr(first), _afterLast(afterLast) {}
hasNext()171 inline bool hasNext() { ASS(_curr<=_afterLast); return _curr!=_afterLast; }
next()172 inline T next() { ASS(hasNext()); return *(_curr++); }
173 private:
174 const T* _curr;
175 const T* _afterLast;
176 };
177
178 /**
179 * Iterator class for pointers returning pointers to elements
180 *
181 * The constructor takes two arguments - a pointer to the first element,
182 * and a pointer to the element after the last element to be returned.
183 *
184 * Consecutive elements are being obtained by the postfix @b operator++().
185 */
186 template<typename T>
187 class PointerPtrIterator
188 {
189 public:
190 DECL_ELEMENT_TYPE(T*);
PointerPtrIterator(T * first,T * afterLast)191 inline PointerPtrIterator(T* first, T* afterLast) :
192 _curr(first), _afterLast(afterLast) {}
hasNext()193 inline bool hasNext() { ASS(_curr<=_afterLast); return _curr!=_afterLast; }
next()194 inline T* next() { ASS(hasNext()); return _curr++; }
195 private:
196 T* _curr;
197 T* _afterLast;
198 };
199
200
201 /**
202 * Iterator returning a single element
203 *
204 * The single element is being passed to the constructor of the iterator.
205 */
206 template<typename T>
207 class SingletonIterator
208 {
209 public:
210 DECL_ELEMENT_TYPE(T);
SingletonIterator(T el)211 explicit SingletonIterator(T el) : _finished(false), _el(el) {}
hasNext()212 inline bool hasNext() { return !_finished; };
next()213 inline T next() { ASS(!_finished); _finished=true; return _el; };
knowsSize() const214 inline bool knowsSize() const { return true; }
size() const215 inline size_t size() const { return 1; }
216 private:
217 bool _finished;
218 T _el;
219 };
220
221 /**
222 * Return iterator returning @b el as a single element
223 *
224 * @see SingletonIterator
225 */
226 template<typename T>
227 inline
getSingletonIterator(T el)228 SingletonIterator<T> getSingletonIterator(T el)
229 {
230 return SingletonIterator<T>(el);
231 }
232
233 /**
234 * sequence of functions for creating tuple iterators
235 */
236 template<typename T>
ti(T el)237 VirtualIterator<T> ti(T el)
238 {
239 return pvi( getSingletonIterator(el) );
240 }
241
242 template<typename T>
ti(T el1,T el2)243 VirtualIterator<T> ti(T el1, T el2)
244 {
245 return pvi( getConcatenatedIterator(getSingletonIterator(el1),getSingletonIterator(el2)) );
246 }
247
248 template<typename T>
ti(T el1,T el2,T el3)249 VirtualIterator<T> ti(T el1, T el2, T el3)
250 {
251 return pvi( getConcatenatedIterator(getSingletonIterator(el1),
252 getConcatenatedIterator(getSingletonIterator(el2),getSingletonIterator(el3))) );
253 }
254
255 /**
256 * Iterator that can casts objects of its inner iterator to the target type
257 * @b To with the static_cast operator
258 *
259 * @tparam To target type of the iterator
260 * @tparam Inner type of the inner iterator
261 */
262 template<typename To, class Inner>
263 class StaticCastIterator
264 {
265 public:
266 DECL_ELEMENT_TYPE(To);
StaticCastIterator(Inner inn)267 explicit StaticCastIterator(Inner inn) :_inn(inn) {}
hasNext()268 inline bool hasNext() { return _inn.hasNext(); };
next()269 inline To next() { return static_cast<To>(_inn.next()); };
270 private:
271 Inner _inn;
272 };
273
274 /**
275 * Return an iterator that can casts objects of the iterator @b it to the target type
276 * @b To
277 *
278 * @see StaticCastIterator
279 */
280 template<typename To, class Inner>
281 inline
getStaticCastIterator(Inner it)282 StaticCastIterator<To,Inner> getStaticCastIterator(Inner it)
283 {
284 return StaticCastIterator<To,Inner>(it);
285 }
286
287
288 template <typename T>
289 struct identity
290 {
291 typedef T type;
292 };
293 /**
294 * A functor class that transforms a lambda object into a Functor with a return type
295 * @author Giles
296 */
297 template<typename Out,typename In>
298 struct Lambda
299 {
LambdaLib::Lambda300 Lambda(typename identity<std::function<Out(In)>>::type f) : _lambda(f) {}
301 DECL_RETURN_TYPE(Out);
operator ()Lib::Lambda302 Out operator()(In obj){ return _lambda(obj); }
303 std::function<Out(In)> _lambda;
304 };
305
306 template<typename T,typename S>
lambda(std::function<T (S)> f)307 Lambda<T,S> lambda(std::function<T(S)> f){ return Lambda<T,S>(f); }
308
309 /**
310 * A functor class that returns true if the argument is non-zero
311 *
312 * The nonzeroness is tested by @b x!=0 .
313 */
314 struct NonzeroFn
315 {
316 DECL_RETURN_TYPE(bool);
317 template<typename T>
operator ()Lib::NonzeroFn318 bool operator()(T obj)
319 {
320 return obj!=0;
321 }
322 };
323
324 /**
325 * A functor class that returns true if the argument is not equal
326 * to a specified object
327 *
328 * The forbidded object is specified by the argument of the
329 * object constructor.
330 *
331 * The nonequality is tested by the @b operator!=() .
332 */
333 template<typename T>
334 struct NonequalFn
335 {
NonequalFnLib::NonequalFn336 NonequalFn(T forbidden) : _forbidden(forbidden) {}
337 DECL_RETURN_TYPE(bool);
operator ()Lib::NonequalFn338 bool operator()(T obj)
339 {
340 return obj!=_forbidden;
341 }
342 T _forbidden;
343 };
344
345 /**
346 * Return a functor object that checks for non-equality to the
347 * @b forbidden object
348 *
349 * @see NonequalFn
350 */
351 template<typename T>
getNonequalFn(T forbidden)352 NonequalFn<T> getNonequalFn(T forbidden)
353 {
354 return NonequalFn<T>(forbidden);
355 }
356
357 /**
358 * Iterator class that returns elements of the inner iterator
359 * for which the functor returns true
360 *
361 * @tparam Inner type of the inner iterator
362 * @tparam Functor type of the functor used for filtering the
363 * elements returned by the inner iterator
364 */
365 template<class Inner, class Functor>
366 class FilteredIterator
367 {
368 public:
369 DECL_ELEMENT_TYPE(ELEMENT_TYPE(Inner));
370
FilteredIterator(Inner inn,Functor func)371 FilteredIterator(Inner inn, Functor func)
372 : _func(func), _inn(inn), _nextStored(false) {}
hasNext()373 bool hasNext()
374 {
375 if(_nextStored) {
376 return true;
377 }
378 while(_inn.hasNext()) {
379 _next=_inn.next();
380 if(_func(_next)) {
381 _nextStored=true;
382 return true;
383 }
384 }
385 return false;
386 };
next()387 OWN_ELEMENT_TYPE next()
388 {
389 if(!_nextStored) {
390 ALWAYS(hasNext());
391 ASS(_nextStored);
392 }
393 _nextStored=false;
394 return _next;
395 };
396 private:
397 Functor _func;
398 Inner _inn;
399 OWN_ELEMENT_TYPE _next;
400 bool _nextStored;
401 };
402
403 template<class Inner, class Functor>
404 class FilteredDelIterator
405 {
406 public:
407 DECL_ELEMENT_TYPE(ELEMENT_TYPE(Inner));
408
FilteredDelIterator(Inner inn,Functor func)409 FilteredDelIterator(Inner inn, Functor func)
410 : _func(func), _inn(inn), _nextStored(false) {}
hasNext()411 bool hasNext()
412 {
413 if(_nextStored) {
414 return true;
415 }
416 while(_inn.hasNext()) {
417 _next=_inn.next();
418 if(_func(_next)) {
419 _nextStored=true;
420 return true;
421 } else {
422 _inn.del();
423 }
424 }
425 return false;
426 };
next()427 OWN_ELEMENT_TYPE next()
428 {
429 if(!_nextStored) {
430 ALWAYS(hasNext());
431 ASS(_nextStored);
432 }
433 _nextStored=false;
434 return _next;
435 };
436 private:
437 Functor _func;
438 Inner _inn;
439 OWN_ELEMENT_TYPE _next;
440 bool _nextStored;
441 };
442
443 /**
444 * Return an iterator object that returns elements of the @b inn iterator
445 * for which the functor @b func returns true
446 *
447 * @see FilteredIterator
448 */
449 template<class Inner, class Functor>
450 inline
getFilteredIterator(Inner inn,Functor func)451 FilteredIterator<Inner,Functor> getFilteredIterator(Inner inn, Functor func)
452 {
453 return FilteredIterator<Inner,Functor>(inn, func);
454 }
455
456 template<class Inner, class Functor>
457 inline
getFilteredDelIterator(Inner inn,Functor func)458 FilteredDelIterator<Inner,Functor> getFilteredDelIterator(Inner inn, Functor func)
459 {
460 return FilteredDelIterator<Inner,Functor>(inn, func);
461 }
462
463
464 /**
465 * Iterator class that returns elements of an inner iterator
466 * only until the specified functor returns false for some element
467 * (this element is already not returned)
468 */
469 template<class Inner, class Functor>
470 class WhileLimitedIterator
471 {
472 public:
473 DECL_ELEMENT_TYPE(ELEMENT_TYPE(Inner));
WhileLimitedIterator(Inner inn,Functor func)474 WhileLimitedIterator(Inner inn, Functor func)
475 : _func(func), _inn(inn), _nextStored(false) {}
hasNext()476 bool hasNext()
477 {
478 if(!_nextStored) {
479 if(!_inn.hasNext()) {
480 return false;
481 }
482 _next=_inn.next();
483 _nextStored=true;
484 }
485 return _func(_next);
486 };
next()487 OWN_ELEMENT_TYPE next()
488 {
489 if(!_nextStored) {
490 ALWAYS(hasNext());
491 ASS(_nextStored);
492 }
493 _nextStored=false;
494 return _next;
495 };
496 private:
497 Functor _func;
498 Inner _inn;
499 OWN_ELEMENT_TYPE _next;
500 bool _nextStored;
501 };
502
503 /**
504 * Return iterator object that returns elements of an inner iterator
505 * @b inn only until the functor @b func returns false for some element
506 * (this element is already not returned)
507 *
508 * @see WhileLimitedIterator
509 */
510 template<class Inner, class Functor>
511 inline
getWhileLimitedIterator(Inner inn,Functor func)512 WhileLimitedIterator<Inner,Functor> getWhileLimitedIterator(Inner inn, Functor func)
513 {
514 return WhileLimitedIterator<Inner,Functor>(inn, func);
515 }
516
517
518 /**
519 * Iterator that concatenates two other iterators
520 *
521 * The @b knowsSize() and @b size() functions of this iterator can be
522 * called only if both underlying iterators contain these functions.
523 */
524 template<class It1,class It2>
525 class CatIterator
526 {
527 public:
528 DECL_ELEMENT_TYPE(ELEMENT_TYPE(It1));
529
CatIterator(It1 it1,It2 it2)530 CatIterator(It1 it1, It2 it2)
531 :_first(true), _it1(it1), _it2(it2) {}
hasNext()532 bool hasNext()
533 {
534 if(_first) {
535 if(_it1.hasNext()) {
536 return true;
537 }
538 _first=false;
539 }
540 return _it2.hasNext();
541 };
542 /**
543 * Return the next value
544 * @warning hasNext() must have been called before
545 */
next()546 OWN_ELEMENT_TYPE next()
547 {
548 if(_first) {
549 //_it1 contains the next value, as hasNext must have
550 //been called before. (It would have updated the
551 //_first value otherwise.)
552 return _it1.next();
553 }
554 return _it2.next();
555 };
556
557 /**
558 * Return true the size of the iterator can be obtained
559 *
560 * This function can be called only if both underlying iterators contain
561 * the @b knowsSize() function.
562 */
knowsSize() const563 bool knowsSize() const { return _it1.knowsSize() && _it2.knowsSize(); }
564 /**
565 * Return the initial number of elements of this iterator
566 *
567 * This function can be called only if both underlying iterators contain
568 * the @b size() function, and if the @b knowsSize() function returns true.
569 */
size() const570 size_t size() const { return _it1.size()+_it2.size(); }
571 private:
572 /** False if we have already iterated through the first iterator */
573 bool _first;
574 It1 _it1;
575 It2 _it2;
576 };
577
578 /**
579 * Return iterators @b it1 and @b it2 contatenated using object of
580 * the @b CatIterator class
581 *
582 * @see CatIterator
583 */
584 template<class It1,class It2>
585 inline
getConcatenatedIterator(It1 it1,It2 it2)586 CatIterator<It1,It2> getConcatenatedIterator(It1 it1, It2 it2)
587 {
588 return CatIterator<It1,It2>(it1, it2);
589 }
590
591
592
593 /**
594 * Iterator that transforms elements of its inner iterator by
595 * a specified functor
596 *
597 * The @b knowsSize() and @b size() functions of this iterator can be
598 * called only if the underlying iterator contains these functions.
599 */
600 template<typename Inner, typename Functor, typename ResultType=RETURN_TYPE(Functor)>
601 class MappingIterator
602 {
603 public:
604 DECL_ELEMENT_TYPE(ResultType);
MappingIterator(Inner inner,Functor func)605 explicit MappingIterator(Inner inner, Functor func)
606 : _func(func), _inner(inner) {}
hasNext()607 inline bool hasNext() { CALL("MappingIterator::hasNext"); return _inner.hasNext(); };
next()608 inline ResultType next() { return _func(_inner.next()); };
609
610 /**
611 * Return true the size of the iterator can be obtained
612 *
613 * This function can be called only if the underlying iterator contains
614 * the @b knowsSize() function.
615 */
knowsSize() const616 inline bool knowsSize() const { return _inner.knowsSize(); }
617 /**
618 * Return the initial number of elements of this iterator
619 *
620 * This function can be called only if the underlying iterator contains
621 * the @b size() function, and if the @b knowsSize() function returns true.
622 */
size() const623 inline size_t size() const { return _inner.size(); }
624 private:
625 Functor _func;
626 Inner _inner;
627 };
628
629 /**
630 * Return iterator that returns elements of @b it transformed by
631 * the functor @b f
632 *
633 * @see MappingIterator
634 */
635 template<typename Inner, typename Functor>
getMappingIterator(Inner it,Functor f)636 MappingIterator<Inner,Functor,RETURN_TYPE(Functor)> getMappingIterator(Inner it, Functor f)
637 {
638 return MappingIterator<Inner,Functor,RETURN_TYPE(Functor)>(it, f);
639 }
640
641 /**
642 * Return iterator that returns elements of @b it transformed by
643 * the lambda @b f
644 *
645 * @see MappingIterator
646 */
647 template<typename Inner, typename Functor,typename ResultType>
getMappingIterator(Inner it,std::function<ResultType (Inner)> f)648 MappingIterator<Inner,Functor,ResultType> getMappingIterator(Inner it, std::function<ResultType(Inner)> f)
649 {
650 return MappingIterator<Inner,Functor,ResultType>(it, f);
651 }
652
653 /**
654 * Return iterator that returns elements of @b it transformed by
655 * the functor @b f
656 *
657 * @see MappingIterator
658 */
659 template<typename ResultType, typename Inner, typename Functor>
getMappingIteratorKnownRes(Inner it,Functor f)660 MappingIterator<Inner,Functor,ResultType> getMappingIteratorKnownRes(Inner it, Functor f)
661 {
662 return MappingIterator<Inner,Functor,ResultType>(it, f);
663 }
664
665
666 /**
667 * Iterator that uses elements of its inner iterator as argments to
668 * single-parameter constructor @b Constructor, and yields created
669 * objects.
670 */
671 template<typename Constructor, typename Inner>
672 class ConstructingIterator
673 {
674 public:
675 DECL_ELEMENT_TYPE(Constructor*);
ConstructingIterator(Inner inner)676 explicit ConstructingIterator(Inner inner)
677 : _inner(inner) {}
hasNext()678 inline bool hasNext() { return _inner.hasNext(); };
next()679 inline Constructor* next() { return new Constructor(_inner.next()); };
680 private:
681 Inner _inner;
682 };
683
684 /**
685 * Return iterator that uses elements of @b it as arguments to
686 * the single-paramater constructor of type @b Constructor and
687 * returns the created elements
688 *
689 * @see ConstructingIterator
690 */
691 template<typename Constructor, typename Inner>
692 inline
getConstructingIterator(Inner it)693 ConstructingIterator<Constructor,Inner> getConstructingIterator(Inner it)
694 {
695 return ConstructingIterator<Constructor,Inner>(it);
696 }
697
698
699 /**
700 * Iterator that takes iterator over iterators as its argument and
701 * flattens it, returning elements of the inner iterators.
702 *
703 * @tparam Master The outer iterator to be flattened. It must be
704 * an iterator over iterators, which also means that the macro
705 * @b ELEMENT_TYPE() must be applicable to the result of
706 * @b ELEMENT_TYPE(Master)
707 */
708 template<typename Master>
709 class FlatteningIterator
710 {
711 public:
712 typedef ELEMENT_TYPE(Master) Inner;
713 typedef ELEMENT_TYPE(Inner) T;
714 DECL_ELEMENT_TYPE(T);
715
FlatteningIterator(Master master)716 explicit FlatteningIterator(Master master)
717 : _master(master)
718 {
719 if(_master.hasNext()) {
720 _current=_master.next();
721 _empty=false;
722 } else {
723 _empty=true;
724 }
725 }
hasNext()726 bool hasNext()
727 {
728 CALL("FlatteningIterator::hasNext");
729 if(_empty) {
730 return false;
731 }
732 for(;;) {
733 if(_current.hasNext()) {
734 return true;
735 }
736 if(!_master.hasNext()) {
737 return false;
738 }
739 _current=_master.next();
740 }
741 }
742 inline
next()743 T next()
744 {
745 CALL("FlatteningIterator::next");
746 ASS(_current.hasNext());
747 return _current.next();
748 }
749 private:
750 bool _empty;
751 Master _master;
752 Inner _current;
753 };
754
755 /**
756 * Iterator that takes iterator over iterators as its argument and
757 * flattens it, returning elements of the inner iterators.
758 *
759 * This specialization is used for virtual iterators over virtual
760 * iterators. It takes care that the inner iterators are released
761 * as early as possible:
762 *
763 * When the inner iterator is empty, pointer to its core is
764 * dropped even before the hasNext() method of the outer iterator
765 * is called. This is important when inner iterators use some resource
766 * of the outer iterator which has to be released by its destructor
767 * before asking the outer iterator about next element.
768 */
769 template<typename T>
770 class FlatteningIterator<VirtualIterator<VirtualIterator<T> > >
771 {
772 public:
773 typedef VirtualIterator<T> Inner;
774 typedef VirtualIterator<Inner> Master;
775 DECL_ELEMENT_TYPE(T);
776
FlatteningIterator(Master master)777 explicit FlatteningIterator(Master master)
778 : _master(master), _current(Inner::getEmpty()) {}
hasNext()779 bool hasNext()
780 {
781 CALL("FlatteningIterator::hasNext");
782 for(;;) {
783 if(_current.hasNext()) {
784 return true;
785 }
786 _current.drop();
787 if(!_master.hasNext()) {
788 return false;
789 }
790 _current=_master.next();
791 }
792 }
793 inline
next()794 T next()
795 {
796 CALL("FlatteningIterator::next");
797 ASS(_current.hasNext());
798 return _current.next();
799 }
800 private:
801 Master _master;
802 Inner _current;
803 };
804
805 /**
806 * Return iterator that flattens the iterator over iterators @b it
807 * into an iterator over elements the inner elements
808 *
809 * @b it must be an iterator over iterators
810 *
811 * @see FlatteningIterator, FlatteningIterator<VirtualIterator<VirtualIterator<T>>>
812 */
813 template<typename T>
814 inline
getFlattenedIterator(T it)815 FlatteningIterator<T> getFlattenedIterator(T it)
816 {
817 return FlatteningIterator<T>(it);
818 }
819
820 /**
821 * Return iterator that applies functor @b f to elements of the @b it
822 * iterator, treats the result as iterators and flattens them
823 *
824 * This function is a combination of the @b getMappingIterator() and
825 * @b getFlattenedIterator() functions.
826 *
827 * The functor @b f must return an iterator
828 *
829 * @see getMappingIterator(), getFlattenedIterator()
830 */
831 template<typename Inner, typename Functor>
832 inline
getMapAndFlattenIterator(Inner it,Functor f)833 FlatteningIterator<MappingIterator<Inner,Functor> > getMapAndFlattenIterator(Inner it, Functor f)
834 {
835 return FlatteningIterator<MappingIterator<Inner,Functor> >(
836 MappingIterator<Inner,Functor>(it, f) );
837 }
838
839 /**
840 * Iterator that in its constructor stores elements of an inner iterator
841 * and then returns these elements later in the same order
842 *
843 * The iterator object does not contain the copy constructor or
844 * the operator=. If this behavior is required, it should be created
845 * on the heap and pointer to it put inside a VirtualIterator object.
846 *
847 * This iterator should be used when a resource held by an iterator
848 * needs to be released before the elements of the iterator are required.
849 *
850 * @see VirtualIterator
851 */
852 template<class Inner>
853 class PersistentIterator
854 : public IteratorCore<ELEMENT_TYPE(Inner)>
855 {
856 public:
857 typedef ELEMENT_TYPE(Inner) T;
PersistentIterator(Inner inn)858 explicit PersistentIterator(Inner inn)
859 : _items(0)
860 {
861 List<T>** ptr=&_items;
862 while(inn.hasNext()) {
863 *ptr=new List<T>(inn.next());
864 ptr=&(*ptr)->tailReference();
865 }
866 }
~PersistentIterator()867 ~PersistentIterator()
868 {
869 if(_items) {
870 List<T>::destroy(_items);
871 }
872 }
hasNext()873 inline bool hasNext() { return _items; };
874 inline
next()875 T next()
876 {
877 return List<T>::pop(_items);
878 };
879 private:
880 List<T>* _items;
881 };
882
883 /**
884 * Return iterator that stores values of @b it in its constructor,
885 * and then yields them in the same order
886 *
887 * After the call to this function, the iterator @b it and any resources
888 * it holds may be released, since the elements are stored independently
889 * of it.
890 *
891 * @see PersistentIterator
892 */
893 template<class Inner>
894 inline
getPersistentIterator(Inner it)895 VirtualIterator<ELEMENT_TYPE(Inner)> getPersistentIterator(Inner it)
896 {
897 return vi( new PersistentIterator<Inner>(it) );
898 }
899
900
901 /**
902 * Iterator that in its constructor stores elements of an inner iterator
903 * and then returns these elements later in a deterministic order, skipping
904 * the duplicate ones
905 *
906 * The iterator object does not contain the copy constructor or
907 * the operator=. If this behavior is required, it should be created
908 * on the heap and pointer to it put inside a VirtualIterator object.
909 *
910 * @see VirtualIterator
911 */
912 template<class Inner>
913 class UniquePersistentIterator
914 : public IteratorCore<ELEMENT_TYPE(Inner)>
915 {
916 public:
917 typedef ELEMENT_TYPE(Inner) T;
918 private:
919 typedef List<T> ItemList;
920 public:
921
UniquePersistentIterator(Inner & inn)922 explicit UniquePersistentIterator(Inner& inn)
923 {
924 _items=getUniqueItemList(inn, _size);
925 }
~UniquePersistentIterator()926 ~UniquePersistentIterator()
927 {
928 if(_items) {
929 ItemList::destroy(_items);
930 }
931 }
hasNext()932 inline bool hasNext() { return _items; };
next()933 inline T next()
934 {
935 return ItemList::pop(_items);
936 };
937
knowsSize() const938 inline bool knowsSize() const { return true; }
size() const939 inline size_t size() const { return _size; }
940 private:
941 typedef DHSet<T> ItemSet;
942
getUniqueItemList(Inner & inn,size_t & sizeRef)943 static ItemList* getUniqueItemList(Inner& inn, size_t& sizeRef)
944 {
945 CALL("UniquePersistentIterator::getUniqueItemList");
946
947 ItemList* res=0;
948 ItemSet* iset;
949 Recycler::get(iset);
950 iset->reset();
951
952 sizeRef=0;
953 while(inn.hasNext()) {
954 T el=inn.next();
955 if(iset->insert(el)) {
956 ItemList::push(el, res);
957 sizeRef++;
958 }
959 }
960
961 Recycler::release(iset);
962 return res;
963 }
964
965 ItemList* _items;
966 size_t _size;
967 };
968
969 /**
970 * Return iterator that stores values of @b it in its constructor,
971 * and then yields them in a deterministic order, skipping duplicate values
972 *
973 * After the call to this function, the iterator @b it and any resources
974 * it holds may be released, since the elements are stored independently
975 * of it.
976 *
977 * @see UniquePersistentIterator
978 */
979 template<class Inner>
980 inline
getUniquePersistentIterator(Inner it)981 VirtualIterator<ELEMENT_TYPE(Inner)> getUniquePersistentIterator(Inner it)
982 {
983 if(!it.hasNext()) {
984 return VirtualIterator<ELEMENT_TYPE(Inner)>::getEmpty();
985 }
986 return vi( new UniquePersistentIterator<Inner>(it) );
987 }
988
989 /**
990 * Return iterator that stores values of the iterator pointed to by @b it
991 * in its constructor, and then yields them in a deterministic order,
992 * skipping duplicate values
993 *
994 * After the call to this function, the iterator pointed to by @b it and
995 * any resources it holds may be released, since the elements are stored
996 * independently of it.
997 *
998 * @see UniquePersistentIterator
999 */
1000 template<class Inner>
1001 inline
getUniquePersistentIteratorFromPtr(Inner * it)1002 VirtualIterator<ELEMENT_TYPE(Inner)> getUniquePersistentIteratorFromPtr(Inner* it)
1003 {
1004 if(!it->hasNext()) {
1005 return VirtualIterator<ELEMENT_TYPE(Inner)>::getEmpty();
1006 }
1007 return vi( new UniquePersistentIterator<Inner>(*it) );
1008 }
1009
1010 /**
1011 * Remove duplicate elements from the container @c cont
1012 */
1013 template<class Container>
makeUnique(Container & cont)1014 void makeUnique(Container& cont)
1015 {
1016 CALL("makeUnique");
1017
1018 VirtualIterator<ELEMENT_TYPE(Container)> uniqueIt = pvi(
1019 getUniquePersistentIterator(ITERATOR_TYPE(Container)(cont)) );
1020 cont.reset();
1021 cont.loadFromIterator(uniqueIt);
1022 }
1023
1024 /**
1025 * Return number of elements in iterator @c it
1026 */
1027 template<class It>
countIteratorElements(It it)1028 size_t countIteratorElements(It it)
1029 {
1030 CALL("countIteratorElements");
1031
1032 size_t res = 0;
1033 while(it.hasNext()) {
1034 it.next();
1035 res++;
1036 }
1037 return res;
1038 }
1039
1040
1041 /**
1042 * Iterator that goes from object @b from to the object @b to using the
1043 * postfix @b operator++. (The objects are passed in the constructor.)
1044 * The object @b to is not returned.
1045 */
1046 template<typename T>
1047 class RangeIterator
1048 {
1049 public:
1050 DECL_ELEMENT_TYPE(T);
1051 inline
RangeIterator(T from,T to)1052 RangeIterator(T from, T to)
1053 : _next(from), _from(from), _to(to) {}
hasNext()1054 inline bool hasNext() { return _next<_to; };
next()1055 inline T next() { return _next++; };
knowsSize() const1056 inline bool knowsSize() const { return true; }
size() const1057 inline size_t size() const { return (_to>_from) ? (_to-_from) : 0; }
1058 private:
1059 T _next;
1060 T _from;
1061 T _to;
1062 };
1063
1064 /**
1065 * Return iterator that goes from object @b from to the object @b to
1066 * using the postfix @b operator++; the object @b to is not returned
1067 *
1068 * @see RangeIterator
1069 */
1070 template<typename T>
getRangeIterator(T from,T to)1071 RangeIterator<T> getRangeIterator(T from, T to)
1072 {
1073 return RangeIterator<T>(from, to);
1074 }
1075
1076 template<typename T>
1077 class CombinationIterator
1078 {
1079 public:
1080 DECL_ELEMENT_TYPE(pair<T,T>);
CombinationIterator(T from,T to)1081 CombinationIterator(T from, T to)
1082 : _first(from), _second(from), _afterLast(to)
1083 {
1084 ASS_LE(from,to);
1085 if(from!=to) {
1086 if(from+1==to) {
1087 _second=_afterLast;
1088 } else {
1089 moveToNext();
1090 }
1091 }
1092 }
hasNext()1093 inline bool hasNext()
1094 { ASS_LE(_first,_afterLast); return _second!=_afterLast; }
next()1095 pair<T,T> next()
1096 {
1097 ASS(hasNext());
1098 pair<T,T> res=pair<T,T>(_first,_second);
1099 moveToNext();
1100 return res;
1101 }
1102 private:
moveToNext()1103 void moveToNext()
1104 {
1105 _second++;
1106 ASS_LE(_second,_afterLast);
1107 if(_second==_afterLast) {
1108 _first++;
1109 _second=_first;
1110 _second++;
1111 //now, if _second==_afterLast, there's no combination left
1112 }
1113 }
1114 T _first;
1115 T _second;
1116 T _afterLast;
1117 };
1118
1119 /**
1120 * Return iterator, that yields all unordered pairs from set {@b from,
1121 * (@b from)+1, (@b from)+2,..., (@b to)-1}. (The addition is performed
1122 * by the operator++.) For a singleton set, nothing is yielded.
1123 */
1124 template<typename T>
1125 inline
getCombinationIterator(T from,T to)1126 CombinationIterator<T> getCombinationIterator(T from, T to)
1127 {
1128 return CombinationIterator<T>(from, to);
1129 }
1130
1131 template<typename T>
1132 class Combination2Iterator
1133 {
1134 public:
1135 DECL_ELEMENT_TYPE(pair<T,T>);
Combination2Iterator(T from,T to1,T to2)1136 Combination2Iterator(T from, T to1, T to2)
1137 : _first(from), _second(from), _afterLast1(to1), _afterLast2(to2)
1138 {
1139 ASS_LE(from,to1);
1140 ASS_LE(to1,to2);
1141 if(from!=to1) {
1142 moveToNext();
1143 }
1144 }
hasNext()1145 inline bool hasNext()
1146 { return _first!=_afterLast1 && _second!=_afterLast2; }
next()1147 pair<T,T> next()
1148 {
1149 ASS(hasNext());
1150 pair<T,T> res=pair<T,T>(_first,_second);
1151 ASS_LE(_first,_afterLast1);
1152 ASS_LE(_second,_afterLast2);
1153 moveToNext();
1154 return res;
1155 }
1156 private:
moveToNext()1157 void moveToNext()
1158 {
1159 _second++;
1160 ASS_LE(_second,_afterLast2);
1161 if(_second==_afterLast2) {
1162 _first++;
1163 _second=_first;
1164 _second++;
1165 //now, if _second==_afterLast, there's no combination left
1166 }
1167 }
1168 T _first;
1169 T _second;
1170 T _afterLast1;
1171 T _afterLast2;
1172 };
1173
1174 /**
1175 * Return iterator, that yields all unordered pairs from set {@b from,
1176 * (@b from)+1, (@b from)+2,..., (@b to2)-1} where one of the pair is
1177 * less than @b to1. (The addition is performed by the operator++.)
1178 * For a singleton set, nothing is yielded.
1179 *
1180 * Parameter @b to1 must be less than or equal to @b to2.
1181 */
1182 template<typename T>
1183 inline
getCombinationIterator(T from,T to1,T to2)1184 Combination2Iterator<T> getCombinationIterator(T from, T to1, T to2)
1185 {
1186 return Combination2Iterator<T>(from, to1, to2);
1187 }
1188
1189
1190 /**
1191 * Wraps a context around specified iterator.
1192 *
1193 * Context is an object of type @b Ctx with methods
1194 * bool enter(T)
1195 * void leave(T)
1196 * where @b T is the return type of inner iterator.
1197 * Method @b enter is called before an element of inner
1198 * iterator is yielded (with this element as a parameter).
1199 * If @b enter returns false, the element is skipped (@b leave is
1200 * not called for it).
1201 * @b leave is called when an element becomes no longer
1202 * needed (after the hasNext method is called next time,
1203 * or when the iterator is being destroyed).
1204 */
1205 template<class Inner, class Ctx>
1206 class ContextualIterator
1207 {
1208 public:
1209 DECL_ELEMENT_TYPE(ELEMENT_TYPE(Inner));
1210
ContextualIterator(Inner iit,Ctx context)1211 ContextualIterator(Inner iit, Ctx context)
1212 : _inContext(false), _used(true), _context(context), _iit(iit) {}
1213
~ContextualIterator()1214 ~ContextualIterator()
1215 {
1216 assureContextLeft();
1217 }
hasNext()1218 bool hasNext()
1219 {
1220 if(!_used) {
1221 return true;
1222 }
1223 assureContextLeft();
1224 do {
1225 if(!_iit.hasNext()) {
1226 return false;
1227 }
1228 _current=_iit.next();
1229 } while (!_context.enter(_current));
1230 _inContext=true;
1231
1232 _used=false;
1233 return true;
1234 }
1235 inline
next()1236 ELEMENT_TYPE(Inner) next()
1237 {
1238 ASS(!_used);
1239 _used=true;
1240 return _current;
1241 }
1242 private:
assureContextLeft()1243 void assureContextLeft()
1244 {
1245 if(_inContext) {
1246 _context.leave(_current);
1247 _inContext=false;
1248 }
1249 }
1250
1251 bool _inContext;
1252 bool _used;
1253 Ctx _context;
1254 Inner _iit;
1255 ELEMENT_TYPE(Inner) _current;
1256 };
1257
1258 template<class Inner, class Ctx>
1259 inline
getContextualIterator(Inner it,Ctx context)1260 ContextualIterator<Inner,Ctx> getContextualIterator(Inner it, Ctx context)
1261 {
1262 return ContextualIterator<Inner,Ctx>(it, context);
1263 }
1264
1265
1266 template<class Inner>
1267 class TimeCountedIterator
1268 : public IteratorCore<ELEMENT_TYPE(Inner)>
1269 {
1270 public:
1271 typedef ELEMENT_TYPE(Inner) T;
1272
TimeCountedIterator(Inner inn,TimeCounterUnit tcu)1273 explicit TimeCountedIterator(Inner inn, TimeCounterUnit tcu)
1274 : _inn(inn), _tcu(tcu) {}
1275
hasNext()1276 inline bool hasNext()
1277 {
1278 TimeCounter tc(_tcu);
1279 return _inn.hasNext();
1280 };
1281 inline
next()1282 T next()
1283 {
1284 TimeCounter tc(_tcu);
1285 return _inn.next();
1286 };
1287 private:
1288 Inner _inn;
1289 TimeCounterUnit _tcu;
1290 };
1291
1292 /**
1293 * Return iterator, that yields the same values in
1294 * the same order as @b it. Benefit of this iterator
1295 * is, that @b it object is used only during
1296 * initialization. (So it's underlying object can be
1297 * freed and the returned iterator will remain valid.)
1298 */
1299 template<class Inner>
1300 inline
getTimeCountedIterator(Inner it,TimeCounterUnit tcu)1301 VirtualIterator<ELEMENT_TYPE(Inner)> getTimeCountedIterator(Inner it, TimeCounterUnit tcu)
1302 {
1303 return vi( new TimeCountedIterator<Inner>(it, tcu) );
1304 }
1305
1306 /**
1307 * Return true iff @c it1 and it2 contain the same values in the same order
1308 */
1309 template<class It1, class It2>
iteratorsEqual(It1 it1,It2 it2)1310 bool iteratorsEqual(It1 it1, It2 it2)
1311 {
1312 CALL("iteratorsEqual");
1313
1314 while(it1.hasNext()) {
1315 if(!it2.hasNext()) {
1316 return false;
1317 }
1318 if(it1.next()!=it2.next()) {
1319 return false;
1320 }
1321 }
1322 return !it2.hasNext();
1323 }
1324
1325 template<typename T>
lessThan(T a,T b)1326 static bool lessThan(T a, T b) { return a<b; }
1327
1328 /**
1329 * Return true iff @c it is sorted according to the default < ordering
1330 * (each element is less than its successive element).
1331 */
1332 template<class It>
isSorted(It it)1333 bool isSorted(It it)
1334 {
1335 CALL("isSorted/1");
1336
1337 if(!it.hasNext()) { return true; }
1338
1339 ELEMENT_TYPE(It) prev = it.next();
1340
1341 while(it.hasNext()) {
1342 ELEMENT_TYPE(It) curr = it.next();
1343 if(!(prev<curr)) {
1344 return false;
1345 }
1346 prev = curr;
1347 }
1348 return true;
1349 }
1350
1351 /**
1352 * Return true iff @c it is sorted according to ordering specified by lessThan
1353 * (each element is less than its successive element).
1354 *
1355 * Transitivity of @c lessThan is assumed.
1356 */
1357 template<class It, typename Pred>
isSorted(It it,Pred lessThan)1358 bool isSorted(It it, Pred lessThan)
1359 {
1360 CALL("isSorted/2");
1361
1362 if(!it.hasNext()) { return true; }
1363
1364 ELEMENT_TYPE(It) prev = it.next();
1365
1366 while(it.hasNext()) {
1367 ELEMENT_TYPE(It) curr = it.next();
1368 if(!lessThan(prev, curr)) {
1369 return false;
1370 }
1371 prev = curr;
1372 }
1373 return true;
1374 }
1375
1376 /**
1377 * Return true iff pred returns true for all elements of it
1378 */
1379 template<class It, typename Pred>
forAll(It it,Pred pred)1380 bool forAll(It it, Pred pred)
1381 {
1382 CALL("forAll");
1383
1384 while(it.hasNext()) {
1385 if(!pred(it.next())) {
1386 return false;
1387 }
1388 }
1389 return true;
1390 }
1391
1392 /**
1393 * Return first element for which pred returns true.
1394 * There must be an element for which true is returned in the iterator.
1395 */
1396 template<class It, typename Pred>
getFirstTrue(It it,Pred pred)1397 ELEMENT_TYPE(It) getFirstTrue(It it, Pred pred)
1398 {
1399 CALL("getFirstTrue");
1400
1401 while(it.hasNext()) {
1402 ELEMENT_TYPE(It) el = it.next();
1403 if(pred(el)) {
1404 return el;
1405 }
1406 }
1407 ASSERTION_VIOLATION;
1408 }
1409
1410 /**
1411 * Do folding on iterator it using fn which is a function taking
1412 * iterator element as first argument and the intermediate result
1413 * as the second.
1414 */
1415 template<class It, typename Fun, typename Res>
fold(It it,Fun fn,Res init)1416 Res fold(It it, Fun fn, Res init)
1417 {
1418 CALL("fold/3");
1419 Res res = init;
1420 while(it.hasNext()) {
1421 res = fn(it.next(), res);
1422 }
1423 return res;
1424 }
1425
1426 /**
1427 * Do folding on iterator it using fn which is a function taking
1428 * iterator element as first argument and the intermediate result
1429 * as the second.
1430 * it must be a non-empty iterator.
1431 */
1432 template<class It, typename Fun>
fold(It it,Fun fn)1433 ELEMENT_TYPE(It) fold(It it, Fun fn)
1434 {
1435 CALL("fold/2");
1436
1437 ALWAYS(it.hasNext());
1438 ELEMENT_TYPE(It) init = it.next();
1439 return fold(it,fn,init);
1440 }
1441
1442 /** sum function, useful for fold */
1443 template<typename T>
sumFn(T a1,T a2)1444 T sumFn(T a1, T a2) { return a1+a2; }
1445
1446 /** max function, useful for fold */
1447 template<typename T>
maxFn(T a1,T a2)1448 T maxFn(T a1, T a2) { return max(a1,a2); }
1449
1450 /** min function, useful for fold */
1451 template<typename T>
minFn(T a1,T a2)1452 T minFn(T a1, T a2) { return min(a1,a2); }
1453
1454
1455 template<class It>
1456 struct StmJoinAuxStruct
1457 {
StmJoinAuxStructLib::StmJoinAuxStruct1458 StmJoinAuxStruct(vstring glue, It it) : _glue(glue), _it(it) {}
1459 vstring _glue;
1460 It _it;
1461 };
1462
1463 template<class It>
join(vstring glue,It it)1464 StmJoinAuxStruct<It> join(vstring glue, It it)
1465 {
1466 return StmJoinAuxStruct<It>(glue, it);
1467 }
1468 template<typename It>
operator <<(ostream & out,const StmJoinAuxStruct<It> & info)1469 std::ostream& operator<< (ostream& out, const StmJoinAuxStruct<It>& info )
1470 {
1471 It it = info._it;
1472 while(it.hasNext()) {
1473 out << it.next();
1474 if(it.hasNext()) {
1475 out << info._glue;
1476 }
1477 }
1478 return out;
1479 }
1480
1481
1482 /**
1483 * Split iterator @c it into two iterators in the element satisfying
1484 * the @c edge predicate. If there is no element satisfying @c edge,
1485 * return false, put the original iterator into res1 and make res2 empty.
1486 * The first element for which edge succeeded is not present in any
1487 * of the resulting iterators.
1488 */
1489 template<class It, class Pred>
splitIterator(It it,Pred edge,VirtualIterator<ELEMENT_TYPE (It)> & res1,VirtualIterator<ELEMENT_TYPE (It)> & res2)1490 bool splitIterator(It it, Pred edge, VirtualIterator<ELEMENT_TYPE(It)>& res1, VirtualIterator<ELEMENT_TYPE(It)>& res2)
1491 {
1492 CALL("splitIterator");
1493
1494 typedef ELEMENT_TYPE(It) T;
1495
1496 bool success = false;
1497 List<T>* firstPart = 0;
1498 while(it.hasNext()) {
1499 T itm = it.next();
1500 if(edge(itm)) {
1501 success = true;
1502 break;
1503 }
1504 List<T>::push(itm, firstPart);
1505 }
1506 firstPart = firstPart->reverse();
1507 res1 = fpvi(typename List<T>::DestructiveIterator(firstPart));
1508 res2 = pvi(it);
1509 return success;
1510 }
1511
1512 template<typename Inner>
1513 struct NegPred
1514 {
1515 DECL_RETURN_TYPE(bool);
NegPredLib::NegPred1516 NegPred(const Inner& inner) : _inner(inner) {}
1517 template<typename Arg>
operator ()Lib::NegPred1518 bool operator()(Arg a) { return !_inner(a); }
1519 private:
1520 Inner _inner;
1521 };
1522
1523 template<typename Inner>
negPred(Inner inner)1524 NegPred<Inner> negPred(Inner inner) {
1525 return NegPred<Inner>(inner);
1526 }
1527
1528 template<typename T>
1529 struct ConstEqPred
1530 {
1531 DECL_RETURN_TYPE(bool);
ConstEqPredLib::ConstEqPred1532 ConstEqPred(const T& val) : _val(val) {}
1533 template<typename Arg>
operator ()Lib::ConstEqPred1534 bool operator()(Arg a) { return a==_val; }
1535 private:
1536 T _val;
1537 };
1538
1539 template<typename T>
constEqPred(const T & val)1540 ConstEqPred<T> constEqPred(const T& val) {
1541 return ConstEqPred<T>(val);
1542 }
1543
1544 template<typename OuterFn, typename InnerFn>
1545 struct CompositionFn {
1546 DECL_RETURN_TYPE(RETURN_TYPE(OuterFn));
CompositionFnLib::CompositionFn1547 CompositionFn(OuterFn outer, InnerFn inner)
1548 : _outer(outer), _inner(inner) { }
1549
1550 template<typename Arg>
operator ()Lib::CompositionFn1551 OWN_RETURN_TYPE operator()(Arg a) {
1552 return _outer(_inner(a));
1553 }
1554 private:
1555 OuterFn _outer;
1556 InnerFn _inner;
1557 };
1558
1559 template<typename OuterFn, typename InnerFn>
getCompositionFn(OuterFn outer,InnerFn inner)1560 CompositionFn<OuterFn,InnerFn> getCompositionFn(OuterFn outer, InnerFn inner)
1561 {
1562 CALL("getCompositionFn");
1563 return CompositionFn<OuterFn,InnerFn>(outer,inner);
1564 }
1565
1566 template<class P>
1567 struct GetFirstOfPair {
1568 DECL_RETURN_TYPE(typename P::first_type);
operator ()Lib::GetFirstOfPair1569 OWN_RETURN_TYPE operator()(P p) {
1570 return p.first;
1571 }
1572 };
1573
1574 template<class P>
1575 struct GetSecondOfPair {
1576 DECL_RETURN_TYPE(typename P::second_type);
operator ()Lib::GetSecondOfPair1577 OWN_RETURN_TYPE operator()(P p) {
1578 return p.second;
1579 }
1580 };
1581
1582 ///@}
1583
1584 }
1585
1586 #endif /* __Metaiterators__ */
1587