Context Navigation

Back to Ticket #3044

Ticket #3044: while_recur.cpp

File while_recur.cpp, 18.3 KB (added by cppljevans@…, 13 years ago)
while.cpp replacement: while_recur (no unroll) while_unroll_recur(does unrolling)

Line
1	#ifndef BOOST_MPL_WHILE_HPP_INCLUDED
2	#define BOOST_MPL_WHILE_HPP_INCLUDED
3	// Copyright Larry Evans 2009
4	//
5
6	// $Id: while.cpp,v 1.51 2009/06/05 15:55:23 evansl Exp $
7	// $Date: 2009/06/05 15:55:23 $
8	// $Revision: 1.51 $
9
10	#include <boost/mpl/eval_if.hpp>
11	#include <boost/mpl/apply.hpp>
12	#include <boost/mpl/identity.hpp>
13	#include <boost/mpl/arg.hpp>
14	#include <boost/mpl/always.hpp>
15	#include <boost/mpl/equal.hpp>
16	#define USE_WHILE_UNROLL
17	#ifdef USE_WHILE_UNROLL
18	# include <boost/preprocessor/repeat.hpp>
19	# include <boost/preprocessor/inc.hpp>
20	# include <boost/preprocessor/cat.hpp>
21	#endif
22
23	namespace boost
24	{
25	namespace mpl
26	{
27	//Notation:
28	// MFC_or_LE = Metafunction class or Lambda Expression
29	// (See Description on libs/mpl/doc/refmanual/apply.html)
30	//
31	// State = Any type.
32	// (this is term used in libs/mpl/doc/refmanual/fold.html)
33	//
34	template
35	< class StateMeta//nullary metafunction returning current State.
36	, class OpPred=always<false_>//unary MFC_or_LE from State to Bool.
37	, class OpThen=identity<arg<1> >//unary MFC_or_LE from State to State,
38	>
39	struct while_recur
40	{
41	typedef
42	typename eval_if
43	< typename apply<OpPred,typename StateMeta::type>::type
44	, while_recur
45	< apply<OpThen,typename StateMeta::type>
46	, OpPred
47	, OpThen
48	>
49	, StateMeta
50	>::type
51	type
52	;
53	};
54
55	template
56	< class OpPred
57	, class OpThen
58	, class OpElse=identity<arg<1> >
59	>
60	struct while_step
61	/**@brief
62	* metafunction class whose nested apply template
63	* represents one iteration in a while_recur loop with
64	* given OpPred and Opthen.
65	* i.e. one iteration of the "loop":
66	*
67	* while_recur<State,OpPred,OpThen>
68	*
69	*/
70	{
71	template
72	< class StateOld
73	>
74	struct apply
75	/**@brief
76	* Calculates new state from old state, StateOld.
77	*/
78	: eval_if
79	< typename ::boost::mpl::apply
80	< OpPred
81	, StateOld
82	>::type
83	, ::boost::mpl::apply
84	< OpThen
85	, StateOld
86	>
87	, ::boost::mpl::apply
88	< OpElse
89	, StateOld
90	>
91	>
92	{};
93
94	};
95
96	#ifdef USE_WHILE_UNROLL
97
98	// local macros, #undef-ined at the end of the header
99	//
100	// Acknowledegement:
101	// Thr following macros are modelled after:
102	// AUX_ITER_FOLD_FORWARD_STEP
103	// AUX_LAST_FORWARD_STEP
104	// at:
105	// https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/aux_/iter_fold_if_impl.hpp#L124
106	// on:
107	// 2009-06-02(revision 29239)
108	//
109
110	# define AUX_WHILE_UNROLL_STEP(unused, i, unused2) \
111	typedef \
112	typename while_unroller::template apply \
113	< typename BOOST_PP_CAT(while_unroll_step,i)::type \
114	> \
115	BOOST_PP_CAT(while_unroll_step, BOOST_PP_INC(i)); \
116	/**/
117
118	# define AUX_LAST_UNROLL_STEP \
119	BOOST_PP_CAT(while_unroll_step, BOOST_MPL_LIMIT_UNROLLING) \
120	/**/
121
122	template
123	< class StateMeta//nullary metafunction returning current State.
124	, class OpPred=always<false_>//unary MFC_or_LE from State to Bool.
125	, class OpThen=identity<arg<1> >//unary MFC_or_LE from State to State,
126	>
127	struct while_unroll_recur
128	/**@brief
129	* Purpose is same as while_recur; however, lessens the template recursion
130	* depth problem.
131	**@references
132	* [1] http://www.mywikinet.com/mpl/paper/mpl_paper.html#sequences.unrolling
133	* (NOTE: there's a typo. The `recursion` typedef should have
134	* `fold_impl` instead of `fold_impl_step` as its template name.
135	* Also, the recursion typedef here uses eval_if and while_unroll_recur
136	* instead of just the enclosing while_unroll_recur {fold_impl in [1]} .)
137	*/
138	{
139	private:
140	typedef
141	while_step
142	< OpPred
143	, OpThen
144	>
145	while_unroller
146	;
147	typedef
148	StateMeta
149	while_unroll_step0
150	;
151
152	//The following BOOST_PP_REPEAT call corresponds to the
153	//1st one inside the `struct iter_fold_if_impl` of
154	//https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/aux_/iter_fold_if_impl.hpp
155	BOOST_PP_REPEAT(
156	BOOST_MPL_LIMIT_UNROLLING
157	, AUX_WHILE_UNROLL_STEP
158	, unused
159	)
160
161	typedef
162	AUX_LAST_UNROLL_STEP
163	last_unroll_step
164	;
165	typedef
166	eval_if
167	< typename apply<OpPred,typename last_unroll_step::type>::type
168	, while_unroll_recur
169	< apply<OpThen,typename last_unroll_step::type>
170	, OpPred
171	, OpThen
172	>
173	, last_unroll_step
174	>
175	recursion
176	;
177
178	public:
179	typedef
180	typename recursion::type
181	type
182	;
183
184	};
185	# undef AUX_WHILE_UNROLL_STEP
186	# undef AUX_LAST_UNROLL_STEP
187
188	#endif //USE_WHILE_UNROLL
189
190	template
191	< class StateNow
192	, class OpStateState
193	, class OpStatesEqual=is_same<arg<1>,arg<2> >
194	>
195	struct fix_point
196	/**@brief
197	* Finds the fixed point of unary metafunction
198	* class, OpStateState.
199	*/
200	{
201	typedef
202	StateNow
203	state_now
204	;
205	typedef
206	typename OpStateState::template apply
207	< state_now
208	>::type
209	state_next
210	;
211	typedef
212	fix_point
213	< state_next
214	, OpStateState
215	, OpStatesEqual
216	>
217	op_recur
218	;
219	typedef
220	typename apply
221	< OpStatesEqual
222	, state_now
223	, state_next
224	>::type
225	done
226	;
227	typedef
228	typename eval_if
229	< done
230	, identity<state_now>
231	, op_recur
232	>::type
233	type
234	;
235	};
236
237	}//exit mpl namespace
238	}//exit boost namespace
239	#endif
240
241	#ifndef BOOST_MPL_WHILE_RECUR_SEQ_HPP_INCLUDED
242	#define BOOST_MPL_WHILE_RECUR_SEQ_HPP_INCLUDED
243	//#include <boost/mpl/while.hpp>
244	#include <boost/mpl/begin_end.hpp>
245	#include <boost/mpl/next.hpp>
246	#include <boost/mpl/deref.hpp>
247	#include <boost/mpl/push_front.hpp>
248	#include <boost/mpl/and.hpp>
249	#include <boost/mpl/list.hpp>
250
251	namespace boost
252	{
253	namespace mpl
254	{
255	namespace aux
256	{
257	namespace while_recur_seq
258	{
259
260	template
261	< typename State
262	>
263	struct while_state
264	{
265	typedef State state;
266	typedef while_state type;
267	};
268	template
269	< typename Stack
270	, typename State
271	>
272	struct while_stack_state
273	: while_state<State>
274	{
275	typedef Stack stack;
276	typedef while_stack_state type;
277	};
278	template
279	< typename State
280	, typename Iter
281	>
282	struct while_state_iter
283	: State //either while_state or while_stack_state
284	{
285	typedef Iter iter;
286	typedef while_state_iter type;
287	};
288
289	template
290	< typename State
291	, typename Op
292	>
293	struct forward_step
294	{
295	typedef
296	typename deref<typename State::iter>::type
297	item;
298	typedef
299	while_state_iter
300	< while_stack_state
301	< typename push_front<typename State::stack, item>::type
302	, typename apply<Op,typename State::state,item>::type
303	>
304	, typename next<typename State::iter>::type
305	>
306	type;
307
308	};
309
310	template
311	< typename State
312	, typename Op
313	>
314	struct backward_step
315	{
316	typedef
317	typename deref<typename State::iter>::type
318	item;
319	typedef
320	while_state_iter
321	< while_state<typename apply<Op,typename State::state,item>::type>
322	, typename next<typename State::iter>::type
323	>
324	type;
325
326	};
327
328	template
329	< typename State
330	, typename Op
331	>
332	struct direction_step
333	;
334
335	template
336	< typename State
337	, typename Iter
338	, typename Op
339	>
340	struct direction_step
341	< while_state_iter
342	< while_state<State>
343	, Iter
344	>
345	, Op
346	>
347	: backward_step
348	< while_state_iter<State,Iter>
349	, Op
350	>
351	{
352	};
353
354	template
355	< typename Stack
356	, typename State
357	, typename Iter
358	, typename Op
359	>
360	struct direction_step
361	< while_state_iter
362	< while_stack_state<Stack,State>
363	, Iter
364	>
365	, Op
366	>
367	: forward_step
368	< while_state_iter
369	< while_stack_state<Stack,State>
370	, Iter
371	>
372	, Op
373	>
374	{
375	};
376
377	template
378	< typename StateNow
379	, typename IterLast
380	>
381	struct not_iter_last
382	: not_
383	< is_same
384	< typename StateNow::iter
385	, IterLast
386	>
387	>
388	{
389	};
390
391	template
392	< typename Op
393	, typename LazyExpr
394	>
395	struct apply_lazy1
396	{
397	typedef typename apply<Op,typename LazyExpr::type>::type type;
398	};
399	template
400	< typename StateNow
401	, typename IterLast
402	, typename Predicate=always<true_>
403	>
404	struct not_iter_last_pred
405	: and_
406	< not_iter_last<StateNow,IterLast>
407	, apply_lazy1<Predicate, deref<typename StateNow::iter> >
408	>
409	{
410	};
411
412	}//exit while_recur_seq namespace
413
414	}//exit aux namespace
415
416	template
417	< typename Seq
418	, typename State
419	, typename OperStateVal
420	, typename PredicateVal=always<true_>
421	, template<class,class>class Step=aux::while_recur_seq::backward_step
422	>
423	struct while_seq_directed
424	{
425	typedef
426	typename begin<Seq>::type
427	first;
428	typedef
429	typename end<Seq>::type
430	last;
431	typedef
432	aux::while_recur_seq::while_state_iter<State,first>
433	state_iter;
434	typedef
435	Step
436	< arg<1>
437	, typename lambda<OperStateVal>::type
438	>
439	oper_state_ref;
440	typedef
441	aux::while_recur_seq::not_iter_last_pred
442	< arg<1>
443	, last
444	, typename lambda<PredicateVal>::type
445	>
446	predicate_ref;
447	typedef
448	typename
449	#ifdef USE_WHILE_UNROLL
450	while_unroll_recur
451	#else
452	while_recur
453	#endif
454	< state_iter
455	, predicate_ref
456	, oper_state_ref
457	>::type
458	type;
459	};
460
461	template
462	< typename BOOST_MPL_AUX_NA_PARAM(Sequence)
463	, typename BOOST_MPL_AUX_NA_PARAM(State)
464	, typename BOOST_MPL_AUX_NA_PARAM(ForwardOp)
465	, typename BOOST_MPL_AUX_NA_PARAM(ForwardPredicate)
466	, typename BOOST_MPL_AUX_NA_PARAM(BackwardOp)
467	, typename BOOST_MPL_AUX_NA_PARAM(BackwardPredicate)
468	>
469	struct while_recur_seq
470	{
471	#define WHILE_RECUR_SEQ_USE_WHILE_SEQ_DIRECTED
472	struct forward
473	{
474	typedef list<> stack0;
475	typedef Sequence seq;
476	typedef State state_0;
477	#ifndef WHILE_RECUR_SEQ_USE_WHILE_SEQ_DIRECTED
478	typedef typename begin<seq>::type first;
479	typedef typename end<seq>::type last;
480	typedef typename lambda<ForwardOp>::type state_op;
481	typedef typename lambda<ForwardPredicate>::type pred_op;
482
483	typedef
484	aux::while_recur_seq::while_state_iter
485	< aux::while_recur_seq::while_stack_state<stack0,state_0>
486	, first
487	>
488	state_aux_0;
489	typedef aux::while_recur_seq::not_iter_last_pred< arg<1>, last, pred_op> pred_aux_op;
490	typedef aux::while_recur_seq::forward_step< arg<1>, state_op> state_aux_op;
491
492	typedef typename while_recur<state_aux_0,pred_aux_op,state_aux_op>::type result;
493	#else
494	typedef
495	typename while_seq_directed
496	< seq
497	, aux::while_recur_seq::while_stack_state<stack0,state_0>
498	, ForwardOp
499	, ForwardPredicate
500	, aux::while_recur_seq::forward_step
501	>::type
502	result
503	;
504	#endif
505	};
506
507	struct backward
508	{
509	typedef typename forward::result::stack seq;
510	typedef typename forward::result::state state_0;
511	#ifndef WHILE_RECUR_SEQ_USE_WHILE_SEQ_DIRECTED
512	typedef typename begin<seq>::type first;
513	typedef typename end<seq>::type last;
514	typedef typename lambda<BackwardOp>::type state_op;
515	typedef typename lambda<BackwardPredicate>::type pred_op;
516
517	typedef
518	aux::while_recur_seq::while_state_iter
519	< aux::while_recur_seq::while_state<state_0>
520	, first
521	>
522	state_aux_0;
523	typedef aux::while_recur_seq::not_iter_last_pred< arg<1>, last, pred_op> pred_aux_op;
524	typedef aux::while_recur_seq::backward_step<arg<1>,state_op> state_aux_op;
525
526	typedef typename while_recur<state_aux_0,pred_aux_op,state_aux_op>::type result;
527	#else
528	typedef
529	typename while_seq_directed
530	< seq
531	, aux::while_recur_seq::while_state<state_0>
532	, BackwardOp
533	, BackwardPredicate
534	, aux::while_recur_seq::backward_step
535	>::type
536	result
537	;
538	#endif
539	};
540
541	typedef typename backward::result::state type;
542
543	};
544
545	}//exit mpl namespace
546	}//exit boost namespace
547	#endif
548
549	//-{--while_recur_seq_test--
550	#include <boost/mpl/list.hpp>
551	#include <boost/mpl/list_c.hpp>
552	#include <boost/mpl/range_c.hpp>
553	#include <boost/mpl/vector.hpp>
554	#include <boost/mpl/vector_c.hpp>
555
556	#include <boost/mpl/less.hpp>
557	#include <boost/mpl/greater.hpp>
558	#include <boost/mpl/equal_to.hpp>
559	#include <boost/mpl/equal.hpp>
560	#include <boost/mpl/pair.hpp>
561
562	#include <boost/mpl/aux_/test.hpp>
563
564	namespace boost
565	{
566	namespace mpl
567	{
568	namespace test_while
569	{
570	typedef
571	int
572	int_type
573	;
574	typedef
575	#if 0
576	range_c< int_type, 9, 13>
577	#else
578	list_c< int_type, 9, 10, 11, 12>
579	#endif
580	numbers
581	;
582	namespace palindrome
583	{
584	typedef
585	while_recur_seq
586	< numbers
587	, vector<>
588	, push_front<arg<1>, arg<2> >
589	, always<true_>
590	, push_front<arg<1>, arg<2> >
591	, always<true_>
592	>
593	while_result
594	;
595	typedef
596	while_result::type
597	actual_result
598	;
599	typedef
600	vector_c<int_type, 9,10,11,12,12,11,10,9>
601	expected_result
602	;
603	BOOST_MPL_ASSERT((equal<actual_result,expected_result>))
604	;
605
606	}//exit palindrome namespace
607
608	namespace palindrome_pred_fwd
609	{
610	typedef
611	while_recur_seq
612	< numbers
613	, vector<>
614	, push_front<arg<1>, arg<2> >
615	, less<arg<1>,integral_c<int_type,12> >
616	, push_front<arg<1>, arg<2> >
617	, always<true_>
618	>
619	while_result
620	;
621	typedef
622	while_result::type
623	actual_result
624	;
625	typedef
626	vector_c<int, 9,10,11,11,10,9>
627	expected_result
628	;
629	BOOST_MPL_ASSERT((equal<actual_result,expected_result>))
630	;
631
632	}//exit palindrome_pred_fwd namespace
633
634	namespace palindrome_pred_both
635	{
636	typedef
637	while_recur_seq
638	< numbers
639	, vector<>
640	, push_front<arg<1>, arg<2> >
641	, less<arg<1>,integral_c<int_type,12> >
642	, push_front<arg<1>, arg<2> >
643	, greater<arg<1>,integral_c<int_type,9> >
644	>
645	while_result
646	;
647	typedef
648	while_result::type
649	actual_result
650	;
651	typedef
652	vector_c<int, 10,11,11,10,9>
653	expected_result
654	;
655	BOOST_MPL_ASSERT((equal<actual_result,expected_result>))
656	;
657
658	}//exit palindrome_pred_both namespace
659
660	}//exit test_while namespace
661
662	namespace test_fix_point
663	{
664	typedef
665	int
666	int_type
667	;
668	namespace int_dec_to_0
669	{
670	typedef
671	integral_c<int_type,0>
672	expected_fix_down_result
673	;
674	int_type const
675	val0_down=3
676	;
677	typedef
678	integral_c<int_type,val0_down>
679	state0_down
680	;
681	typedef
682	greater<arg<1>,expected_fix_down_result>
683	op_pred_down
684	;
685	typedef
686	apply
687	< op_pred_down
688	, state0_down
689	>::type
690	actual_pred_down_result
691	;
692	BOOST_MPL_ASSERT((actual_pred_down_result))
693	;
694	typedef
695	prior<arg<1> >
696	op_state_down
697	;
698	#if 1
699	typedef
700	while_step
701	< op_pred_down
702	, op_state_down
703	>
704	op_step_down
705	;
706	typedef
707	op_step_down::apply<state0_down>::type
708	actual_step_down_result
709	;
710	typedef
711	prior<state0_down>::type
712	expected_step_down_result
713	;
714	BOOST_MPL_ASSERT((equal_to<actual_step_down_result,expected_step_down_result>))
715	;
716	#endif
717	#if 1
718	typedef
719	fix_point
720	< state0_down
721	, op_step_down
722	, equal_to<arg<1>,arg<2> >
723	>::type
724	actual_fix_down_result
725	;
726	BOOST_MPL_ASSERT((equal_to<actual_fix_down_result,expected_fix_down_result>))
727	;
728	#endif
729	typedef
730	op_step_down::apply<state0_down>::type
731	state1_down
732	;
733	typedef
734	op_step_down::apply<state1_down>::type
735	state2_down
736	;
737	BOOST_MPL_ASSERT_NOT((equal_to<state2_down,expected_fix_down_result>))
738	;
739	typedef
740	op_step_down::apply<state2_down>::type
741	state3_down
742	;
743	BOOST_MPL_ASSERT((equal_to<state3_down,expected_fix_down_result>))
744	;
745	typedef
746	integral_c<int_type,val0_down+2>
747	expected_fix_up_result
748	;
749	typedef
750	and_
751	< greater<first<arg<1> >,expected_fix_down_result>
752	, less<second<arg<1> >,expected_fix_up_result>
753	>
754	op_pred_up
755	;
756	typedef
757	next<second<arg<1> > >
758	op_state_up
759	;
760	typedef
761	while_step
762	< op_pred_up
763	, op_state_up
764	, second<arg<1> >
765	>
766	op_step_up
767	;
768	typedef
769	pair<state3_down,state3_down>
770	state3_pair
771	;
772	typedef
773	apply
774	< op_pred_up
775	, state3_pair
776	>::type
777	actual_op_pred_state3_up
778	;
779	BOOST_MPL_ASSERT_NOT((actual_op_pred_state3_up))
780	;
781	typedef
782	apply
783	< op_state_up
784	, state3_pair
785	>::type
786	actual_op_state_state3_up
787	;
788	BOOST_MPL_ASSERT((is_same<actual_op_state_state3_up,next<state3_down>::type>))
789	;
790	typedef
791	op_step_up::apply
792	< state3_pair
793	>::type
794	state3_up
795	;
796	BOOST_MPL_ASSERT((equal_to<state3_up,state3_down>))
797	;
798	typedef
799	pair<state2_down,state3_up>
800	state2_pair
801	;
802	typedef
803	apply
804	< op_pred_up
805	, state2_pair
806	>::type
807	actual_op_pred_state2_up
808	;
809	BOOST_MPL_ASSERT((actual_op_pred_state2_up))
810	;
811	typedef
812	op_step_up::apply
813	< state2_pair
814	>::type
815	state2_up
816	;
817	BOOST_MPL_ASSERT((equal_to<state2_up,state2_down>))
818	;
819	typedef
820	pair<state1_down,state2_up>
821	state1_pair
822	;
823	typedef
824	op_step_up::apply
825	< state1_pair
826	>::type
827	state1_up
828	;
829	BOOST_MPL_ASSERT((equal_to<state1_up,state1_down>))
830	;
831	typedef
832	pair<state0_down,state1_up>
833	state0_pair
834	;
835	typedef
836	op_step_up::apply
837	< state0_pair
838	>::type
839	state0_up
840	;
841	BOOST_MPL_ASSERT((equal_to<state0_up,state0_down>))
842	;
843	#if 0
844	#endif
845
846	}//exit int_dec_to_0 namespace
847
848	}//exit test_fix_point namespace
849
850	}//exit mpl namespace
851	}//exit boost namespace
852	//-}--while_recur_seq_test--

Download in other formats:

Original Format