|
|
 
1 #ifndef _COMPILER_CALCULATION_H
2#define _COMPILER_CALCULATION_H
3
4//================================================================
5//编译期计算模板
6namespace fredazsq
7 {
8
9//====计算整数的阶: n*(n-1)*(n-2)*.*1==========================
10template<int n>
11struct IntegerRank
12  {
13 enum {value = IntegerRank<n-1>::value * n};
14 };
15
16template<>
17struct IntegerRank<1>
18{
19 enum {value = 1};
20};
21
22
23//====计算整数的和: n + (n-1) + (n-2) +.+1=====================
24template<int n>
25struct IntegerSum
26{
27 enum {value = IntegerSum<n-1>::value + n};
28};
29
30template<>
31struct IntegerSum<1>
32{
33 enum {value = 1};
34};
35
36//====计算整数的1！+2！+3！+………n！=====================
37template<int n>
38struct IntegerRankSum
39{
40 enum {value = IntegerRankSum<n-1>::value + IntegerRank<n>::value};
41};
42
43template<>
44struct IntegerRankSum<1>
45{
46 enum {value = 1};
47};
48
49//====计算k的n次方================================================
50template<int k, int n>
51struct Pow
52{
53 enum { value = Pow<k, n-1>::value * k };
54};
55
56template<int k>
57struct Pow<k, 0>
58{
59 enum {value = 1};
60};
61
62
63//====计算平方根==================================================
64//方法1:编译速度慢
65template <int N, int LO=1, int HI=N>
66class Sqrt2
67{
68 public:
69 //compute the midpoint, rounded up
70 enum { mid = (LO+HI+1)/2 };
71
72 //search a not too large value in a halved interval
73 enum { value = (N<mid*mid) ? Sqrt2<N,LO,mid-1>::result : Sqrt2<N,mid,HI>::value };
74};
75
76// partial specialization for the case when LO equals HI
77template<int N, int M>
78class Sqrt2<N, M, M>
79{
80public:
81 enum { value = M };
82};
83
84//以下代码需要Loki支持.
85//====方法2:最佳解法,需要偏特化支持==============================
86template<int N, int LO=1, int HI=N>
87class Sqrt
88{
89public:
90 // compute the midpoint, rounded up
91 enum { mid = (LO+HI+1)/2 };
92
93 // search a not too large value in a halved interval
94 typedef typename Loki::Select<(N < mid*mid), Sqrt<N, LO, mid-1>, Sqrt<N, mid, HI> >::Result SubT;
95 enum { value = SubT::value };
96};
97
98// partial specialization for end of recursion criterion
99template<int N, int S>
100class Sqrt<N, S, S>
101{
102public:
103 enum { value = S };
104};
105
106
107//====编译器链接出错报告质数 so funny!=============================
108//主模板:Prime_print
109//prime number computation by Erwin Unruh
110
111//判断是否素数的模板
112template <int m, int i=m-1>
113struct is_prime
114{
115 enum { prim = (m==2) || (m%i) && is_prime<(i>2?m:0),i-1>::prim };
116};
117
118template<>
119struct is_prime<0, 0>
120{
121 enum {prim=1};
122};
123
124template<>
125struct is_prime<0, 1>
126{
127 enum {prim=1};
128};
129
130template <int i>
131struct ErrMsg
132{
133 ErrMsg(int){}
134 ErrMsg(float);//不定义函数体以造成无法解析的外部符号错误.
135};
136
137// primary template for loop to print prime numbers
138template <int i>
139struct Prime_print
140{
141 enum { prim = is_prime<i>::prim };
142 void operator()()
143 {
144 //ErrMsg<i> d = prim? 1.0f : 1L;
145 //会导致编译器在测试语法时就同时检查两种可能发生的错误.
146 //这时可用Select并同时应用重载技巧排除.
147 ErrMsg<i> d = Loki::Select<prim, float, int>::Result();
148 Prime_print<i-1>()();//递归,只要不调用函数,模板实例化是永远正确的.
149 }
150};
151
152// full specialization to end the loop
153template<>
154struct Prime_print<1>
155{
156 void operator()(){}
157};
158
159#define PRINT_PRIME(x) fredazsq::Prime_print<x>()()
160
161
162//====出错信息打印Fabonacci数列======================================
163//====该技巧演示了如何不用特化模板结束 Unroll Loops.
164//====u: 在u以内的数列项.
165template<int u, int k=1, int n=1>
166struct Fabonacci
167{
168 void operator()()
169 {
170 ErrMsg<k> d = 1.0f;
171 Loki::Select<(n < u), Fabonacci<u, n, k+n>, Prime_print<1> >::Result()();
172 }
173};
174
175//====出错信息打印某种递归数列(n ? n+1 = n+2)==========================================
176//====该技巧演示了如何不用特化模板结束 Unroll Loops.
177//====RecursionPolicy: 接受2个模板参数的模板,并定义value为k ? n的结果.
178//====u: 在u以内的数列项.
179//VS2003不支持, gc++支持.
180template<template<int, int> class RecursionPolicy, int u, int k=1, int n=1>
181struct RecursionNumber
182{
183 void operator()()
184 {
185 ErrMsg<k> d = 1.0f;
186 Loki::Select<(n < u), RecursionNumber<RecursionPolicy, u, n, RecursionPolicy<k, n>::value>, Prime_print<1> >::Result()();
187 }
188};
189
190
191//====将质数数列值送入执行期====================================
192//====i: i以内的质数
193//====PrimeTypelist最终的Result类型为携带数列值的
194//====Loki的TYPELIST(参阅Modern C++ Design)
195template <int i>
196struct PrimeTypelist
197{
198 //将来要输出的由类型携带的数列值.
199 enum { value = i };
200 enum { prim = is_prime<i>::prim };
201
202 //当前递归所处类型
203 typedef PrimeTypelist<i> thisType;
204
205 //递归处理
206 typedef typename PrimeTypelist<i-1>::Result ResultTypelist;
207
208 //将每次递归的类型加入typelist, Result是最终输出的结果TYPELIST.
209 typedef typename Loki::Select<prim, typename Loki::TL::Append<ResultTypelist, thisType>::Result, ResultTypelist>::Result Result;
210};
211
212// full specialization to end the loop
213template<>
214struct PrimeTypelist<1>
215{
216 typedef Loki::NullType Result;
217};
218
219
220
221//====将Fabonacci数列值送入执行期====================================
222//====u: u个数值. k,n: 起始项
223//====FabonacciArray最终的Result类型为携带数列值的/
224//====Loki的TYPELIST(参阅Modern C++ Design)
225//====Unroll Loops技法不再适用.
226template<int u, int k=1, int n=1>
227struct FabonacciTypelist
228{
229 //将来要输出的由类型携带的数列值.
230 enum {value = k};
231
232 //当前递归所处类型
233 typedef FabonacciTypelist<u, k, n> thisType;
234
235 //递归处理
236 typedef typename FabonacciTypelist<u-1, n, k+n>::Result ResultTypelist;
237 //typedef typename Loki::Select<(n < u), typename FabonacciTypelist<u, n, k+n>::Result, Loki::NullType>::Result ResultTypelist;
238
239 //将每次递归的类型加入typelist, Result是最终输出的结果TYPELIST.
240 typedef typename Loki::TL::Append<ResultTypelist, thisType>::Result Result;
241};
242
243//特化u=0结束
244template<int k, int n>
245struct FabonacciTypelist<0, k, n>
246{
247 typedef Loki::NullType Result;
248};
249
250
251//====将递归数列值送入执行期====================================
252//====u: u个数值. k,n: 起始项
253//====FabonacciArray最终的Result类型为携带数列值的/
254//====Loki的TYPELIST(参阅Modern C++ Design)
255//====RecursionPolicy: 接受2个模板参数的模板,并定义value为k ? n的结果.
256template<template<int, int> class RecursionPolicy, int u, int k=1, int n=1>
257struct RecursionNumberTypelist
258{
259 //将来要输出的由类型携带的数列值.
260 enum {value = k};
261
262 //当前递归所处类型
263 typedef RecursionNumberTypelist<RecursionPolicy, u, k, n> thisType;
264
265 //递归处理
266 typedef typename RecursionNumberTypelist<RecursionPolicy, u-1, n, RecursionPolicy<k, n>::value>::Result ResultTypelist;
267
268 //将每次递归的类型加入typelist, Result是最终输出的结果TYPELIST.
269 typedef typename Loki::TL::Append<ResultTypelist, thisType>::Result Result;
270};
271
272//特化u=0结束
273template<template<int, int> class RecursionPolicy, int k, int n>
274struct RecursionNumberTypelist<RecursionPolicy, 0, k, n>
275{
276 typedef Loki::NullType Result;
277};
278
279
280//====将Fabonacci数列值送入执行期====================================
281//====u: u以内的数值. k,n: 起始项
282//====展示默认参数和模板特化联合时的威力.
283//====如何解决在100内结束的问题.
284template<int u, int k=1, int n=1, bool b = (k < u)>
285struct FabonacciTypelist2
286{
287 //将来要输出的由类型携带的数列值.
288 enum {value = k};
289
290 //当前递归所处类型
291 typedef FabonacciTypelist2<u, k, n, b> thisType;
292
293 //递归处理
294 typedef typename FabonacciTypelist2<u, n, k+n>::Result ResultTypelist;
295 //typedef typename Loki::Select<(n < u), typename FabonacciTypelist<u, n, k+n>::Result, Loki::NullType>::Result ResultTypelist;
296
297 //将每次递归的类型加入typelist, Result是最终输出的结果TYPELIST.
298 typedef typename Loki::TL::Append<ResultTypelist, thisType>::Result Result;
299};
300
301//特化b = (k < u) = false即 k > u结束.
302template<int u, int k, int n>
303struct FabonacciTypelist2<u, k, n, false>
304{
305 typedef Loki::NullType Result;
306};
307
308
309/**////////////////////////////////////////////////////////////////////////////////////////////////
310//====将递归数列值送入执行期====================================
311//====u: u以内的数值. k,n: 起始项
312//====RecursionPolicy: 接受2个模板参数的模板,并定义value为k ? n的结果.
313template<template<int, int> class RecursionPolicy, int u, int k=1, int n=1, bool b = (k < u)>
314struct RecursionNumberTypelist2
315{
316 //将来要输出的由类型携带的数列值.
317 enum {value = k};
318
319 //当前递归所处类型
320 typedef RecursionNumberTypelist2<RecursionPolicy, u, k, n, b> thisType;
321
322 //递归处理
323 typedef typename RecursionNumberTypelist2<RecursionPolicy, u, n, RecursionPolicy<k, n>::value>::Result ResultTypelist;
324
325 //将每次递归的类型加入typelist, Result是最终输出的结果TYPELIST.
326 typedef typename Loki::TL::Append<ResultTypelist, thisType>::Result Result;
327};
328
329//特化u=0结束
330template<template<int, int> class RecursionPolicy, int k, int n>
331struct RecursionNumberTypelist2<RecursionPolicy, 0, k, n, false>
332{
333 typedef Loki::NullType Result;
334};
335/**////////////////////////////////////////////////////////////////////////////////////////////////
336
337
338// 使用范例
339// 执行时赋值good
340// template<typename T> struct ExtractDataType {
341// int operator()() {return T::value;} };
342// typedef Loki::TL::IterateTypes<MyTL, ExtractDataType> TypelistValueGenerator;
343// std::vector<int> vecData;
344// TypelistValueGenerator()(std::back_inserter(vecData));
345
346// 编译期初始赋值,still need macro TYPEVALUE_N.
347// typedef fredazsq::SomeTypelist<6>::Result MyTL;
348// int data[6] = {TYPEVALUE_6(MyTL)};
349#define TYPEVALUE(tl, idx) Loki::TL::TypeAt<tl, idx>::Result::value
350#define TYPEVALUE_1(tl) TYPEVALUE(tl, 0)
351#define TYPEVALUE_2(tl) TYPEVALUE_1(tl),TYPEVALUE(tl, 1)
352#define TYPEVALUE_3(tl) TYPEVALUE_2(tl),TYPEVALUE(tl, 2)
353#define TYPEVALUE_4(tl) TYPEVALUE_3(tl),TYPEVALUE(tl, 3)
354#define TYPEVALUE_5(tl) TYPEVALUE_4(tl),TYPEVALUE(tl, 4)
355#define TYPEVALUE_6(tl) TYPEVALUE_5(tl),TYPEVALUE(tl, 5)
356#define TYPEVALUE_7(tl) TYPEVALUE_6(tl),TYPEVALUE(tl, 6)
357#define TYPEVALUE_8(tl) TYPEVALUE_7(tl),TYPEVALUE(tl, 7)
358#define TYPEVALUE_9(tl) TYPEVALUE_8(tl),TYPEVALUE(tl, 8)
359#define TYPEVALUE_10(tl) TYPEVALUE_9(tl),TYPEVALUE(tl, 9)
360#define TYPEVALUE_11(tl) TYPEVALUE_10(tl),TYPEVALUE(tl, 10)
361#define TYPEVALUE_12(tl) TYPEVALUE_11(tl),TYPEVALUE(tl, 11)
362#define TYPEVALUE_13(tl) TYPEVALUE_12(tl),TYPEVALUE(tl, 12)
363#define TYPEVALUE_14(tl) TYPEVALUE_13(tl),TYPEVALUE(tl, 13)
364
365namespace Private
366{
367 //m:测试对象
368 //t:测试数
369 template<int m, int t>
370 struct CaculMinMutiplePrime
371 {
372 //运算过程是由(t=2)->(t=m)进行逐个判断
373 //如果m被t整除,则t一定是最小素数约数.
374 enum {value = m%t? CaculMinMutiplePrime<m, t+1>::value : t};
375 };
376 template<int t> struct CaculMinMutiplePrime<1, t>
377 {
378 enum {value = 1};
379 };
380 template<int m> struct CaculMinMutiplePrime<m, m>
381 {
382 enum {value = m};
383 };
384
385
386 //求乘积为v的mTL, nTL的公倍数//////////////////////////////////////////////////////////////////////////////////
387 template<int v, typename mTL, typename nTL> struct CaculCommonMultiple;
388 template<int v, typename T, typename U, typename nTL>
389 struct CaculCommonMultiple<v, Loki::Typelist<T, U>, nTL>
390 {
391 //nTL中是否存在T::value.
392 enum {bHasEnumValueTypeT = EnumValueTL::HasEnumValueType<T::value, nTL>::isTrue};
393
394 //存在则扣除nTL中的携T::value值的类型
395 typedef typename EnumValueTL::EraseEnumValueType<T::value, nTL>::Result Result;
396
397 //后续递归的计算结果.
398 enum {recurse_value = CaculCommonMultiple<v, U, Result>::value};
399
400 //递归,值为后续递归的计算结果除当前若携T::value值.
401 enum {value = bHasEnumValueTypeT? recurse_value/T::value : recurse_value};
402 };
403 template<int v, typename T, typename nTL>
404 struct CaculCommonMultiple<v, Loki::Typelist<T, Loki::NullType>, nTL>
405 {
406 enum {bHasEnumValueTypeT = EnumValueTL::HasEnumValueType<T::value, nTL>::isTrue};
407 enum {value = bHasEnumValueTypeT?v/T::value:v};
408 };
409
410
411 //mTL, nTL的最小公约数//////////////////////////////////////////////////////////////////////////////////
412 template<int v, typename mTL, typename nTL> struct CaculCommonSubmultiple;
413 template<int v, typename T, typename U, typename nTL>
414 struct CaculCommonSubmultiple<v, Loki::Typelist<T, U>, nTL>
415 {
416 //nTL中是否存在T::value.
417 enum {bHasEnumValueTypeT = EnumValueTL::HasEnumValueType<T::value, nTL>::isTrue};
418
419 //存在则扣除nTL中的携T::value值的类型
420 typedef typename EnumValueTL::EraseEnumValueType<T::value, nTL>::Result Result;
421
422 //后续递归的计算结果.
423 enum {recurse_value = CaculCommonSubmultiple<v, U, Result>::value};
424
425 //递归,值为后续递归的计算结果除当前若携T::value值.
426 enum {value = bHasEnumValueTypeT? recurse_value*T::value : recurse_value};
427 };
428 template<int v, typename T, typename nTL>
429 struct CaculCommonSubmultiple<v, Loki::Typelist<T, Loki::NullType>, nTL>
430 {
431 enum {bHasEnumValueTypeT = EnumValueTL::HasEnumValueType<T::value, nTL>::isTrue};
432 enum {value = bHasEnumValueTypeT?v*T::value:v};
433 };
434};
435
436/**////////////////////////////////////////////////////////////////////////////////////////////////
437//====求m的最小素数约数========================================
438template<int m>
439struct MinMutiplePrime
440{
441 enum {value = Private::CaculMinMutiplePrime<m, 2>::value};
442};
443/**////////////////////////////////////////////////////////////////////////////////////////////////
444
445
446///////////////////////////////////////////////////////////////////////////////////////////////
447//====将一个整数拆成素数的乘积=================================
448//====结果Result以TYPELIST形式输出
449template<int m>
450struct PrimeMutiple
451{
452 //将来要输出的由类型携带的数列值.
453 //求m的最小素数约数
454 enum { value = MinMutiplePrime<m>::value };
455
456 //当前类型
457 typedef PrimeMutiple<m> thisType;
458
459 //递归处理
460 //求除去m的最小约数后的整数的素数乘积
461 typedef typename PrimeMutiple<m/value>::Result ResultTypelist;
462
463 //将每次递归的类型加入typelist, Result是最终输出的结果TYPELIST.
464 typedef typename Loki::TL::Append<ResultTypelist, thisType>::Result Result;
465};
466template<> struct PrimeMutiple<1>
467{
468 typedef Loki::NullType Result;
469};
470/**////////////////////////////////////////////////////////////////////////////////////////////////
471
472
473///////////////////////////////////////////////////////////////////////////////////////////////
474//=====计算m和n的最小公倍数===============================================================
475template<int m, int n>
476struct CommonMultiple
477{
478 //求m的素数乘积序列
479 typedef typename PrimeMutiple<m>::Result PrimeMutiple_mTL;
480
481 //求n的素数乘积序列
482 typedef typename PrimeMutiple<n>::Result PrimeMutiple_nTL;
483
484 //调用私有空间的核心计算模板
485 enum {value = Private::CaculCommonMultiple<m*n, PrimeMutiple_mTL, PrimeMutiple_nTL>::value};
486};
487template<int n> struct CommonMultiple<1, n>
488{
489 enum {value = n};
490};
491template<int m> struct CommonMultiple<m, 1>
492{
493 enum {value = m};
494};
495/**////////////////////////////////////////////////////////////////////////////////////////////////
496
497
498///////////////////////////////////////////////////////////////////////////////////////////////
499//=====计算m和n的最大公约数===============================================================
500template<int m, int n>
501struct CommonSubmultiple
502{
503 //求m的素数乘积序列
504 typedef typename PrimeMutiple<m>::Result PrimeMutiple_mTL;
505
506 //求n的素数乘积序列
507 typedef typename PrimeMutiple<n>::Result PrimeMutiple_nTL;
508
509 //调用私有空间的核心计算模板
510 enum {value = Private::CaculCommonSubmultiple<1, PrimeMutiple_mTL, PrimeMutiple_nTL>::value};
511};
512template<int n> struct CommonSubmultiple<1, n>
513{
514 enum {value = n};
515};
516template<int m> struct CommonSubmultiple<m, 1>
517{
518 enum {value = m};
519};
520/**////////////////////////////////////////////////////////////////////////////////////////////////
521
522//====出错信息打印当前时间
523// template <char*>
524// struct _Print_NowTime; \
525// _Print_NowTime<__TIME__>
526
527 }//namespace fredazsq
528#endif //_COMPILER_CALCULATION_H
529
530
531// Loki的Select实现
532//template <bool flag, typename T, typename U>
533//struct Select
534//{
535// typedef T Result;
536//};
537//template <typename T, typename U>
538//struct Select<false, T, U>
539//{
540// typedef U Result;
541//};
542
543//Sample.h
544//#include <iostream>
545//#include <stdlib.h>
546//#include <vector>
547//#define _USE_LOKI_
548//#include <STL/CompilerCaculation.h>
549//#include <DataGenerators.h>
550//
551//using namespace std;
552//
553//template<typename T>
554//struct ExtractDataType
555//{
556// int operator()()
557// {
558// return T::value;
559// }
560//};
561//
562//template<int k, int n>
563//struct MyRecursePolicy
564//{
565// enum {value = n+6};
566//};
567//
568//int main(int argc, char *argv[])
569//{
570// typedef fredazsq::RecursionNumberTypelist<MyRecursePolicy, 16>::Result MyTL;
571// typedef Loki::TL::IterateTypes<MyTL, ExtractDataType> TypelistValueGenerator;
572// std::vector<int> vecData;
573// TypelistValueGenerator()(std::back_inserter(vecData));
574//
575// for(std::vector<int>::reverse_iterator it = vecData.rbegin(); it != vecData.rend(); ++it)
576// {
577// std::cout << *it << ",";
578// }
579// std::cout << std::endl;
580//
581// system("PAUSE");
582// return 0;
583//}
584
585
586//std::stringstream stream;
587//const num = 368;
588//typedef PrimeMutiple<num>::Result MyTL;
589//typedef Loki::TL::IterateTypes<MyTL, ExtractDataType> TypelistValueGenerator;
590//std::vector<int> vecData;
591//TypelistValueGenerator()(std::back_inserter(vecData));
592//
593//stream << num << " = ";
594//for(std::vector<int>::reverse_iterator it = vecData.rbegin(); it != vecData.rend(); ++it)
595//{
596// stream << *it << " * ";
597//}
598//
599//MessageBox(stream.str().substr(0, stream.str().length()-2).c_str());
600
601
602/**//*
603泛型编程的语义
6041.if语义
605 a.typedef Loki::Select<bool, ClassA, ClassB> ExecuteType;
606 ExecuteType()();
607 b.模板特化
608 c.重载选型.
609
6102.else语义
611 a.多个模板重载项的非特化项.
612
6133.真假语义
614 a.编译期bool常量
615
6164.switch语义
617 a.多个模板重载项
618
6195.for语义
620 struct EmptyFunctor
621 {
622 void operator(){}
623 };
624
6256.do while语义
626*/
|