These templates can lookup, append, reverse, sort, print and map functions over lists. Quite useless but purely functional :)
1 #include <iostream> 2 #include <limits.h> 3 4 using std::cout; 5 using std::endl; 6 7 template <int...> 8 struct int_list {}; 9 10 /// 11 /// length of the list 12 /// 13 template <class list> 14 struct length; 15 16 template <> 17 struct length<int_list<> > { 18 enum { 19 value = 0 20 }; 21 }; 22 23 template <int head, int... tail> 24 struct length<int_list<head, tail...> > { 25 enum { 26 value = 1 + length<int_list<tail...> >::value 27 }; 28 }; 29 30 /// 31 /// access by index 32 /// 33 template <int idx, class list> 34 struct at; 35 36 template <int head, int... tail> 37 struct at<0, int_list<head, tail...> > { 38 enum {result = head}; 39 }; 40 41 template <int idx, int head, int... tail> 42 struct at<idx, int_list<head, tail...> > { 43 enum {result = at<idx - 1, int_list<tail...> >::result}; 44 }; 45 46 /// 47 /// find in list, returns index or -1 on fail 48 /// 49 template <int x, class list> 50 struct lookup; 51 52 // lookup fail 53 template <int x> 54 struct lookup<x, int_list<> > { 55 enum { 56 value = -1 57 }; 58 }; 59 60 // step 61 template <int x, int head, int... tail> 62 struct lookup<x, int_list<head, tail...> > { 63 private: 64 enum { 65 tmp = lookup<x, int_list<tail...> >::value 66 }; 67 public: 68 enum { 69 value = (tmp == -1) ? -1 : (1 + tmp) 70 }; 71 }; 72 73 // found 74 template <int x, int... tail> 75 struct lookup<x, int_list<x, tail...> > { 76 enum { 77 value = 0 78 }; 79 }; 80 81 /// 82 /// concatenate two lists 83 /// 84 template <class list1, class list2> 85 struct concat; 86 87 // even simplier than usually in functional languages 88 template <int... list1, int... list2> 89 struct concat<int_list<list1...>, int_list<list2...> > { 90 typedef int_list<list1..., list2...> result; 91 }; 92 93 /// 94 /// replace all occurences of x with y 95 /// 96 template <int x, int y, class list> 97 struct replace; 98 99 // empty 100 template <int x, int y> 101 struct replace<x, y, int_list<> > { 102 typedef int_list<> result; 103 }; 104 105 // miss 106 template <int x, int y, int head, int... tail> 107 struct replace<x, y, int_list<head, tail...> > { 108 private: 109 typedef typename replace<x, y, int_list<tail...> >::result tmp; 110 public: 111 typedef typename concat<int_list<head>, tmp>::result result; 112 }; 113 114 // found 115 template <int x, int y, int... tail> 116 struct replace<x, y, int_list<x, tail...> > { 117 private: 118 typedef typename replace<x, y, int_list<tail...> >::result tmp; 119 public: 120 typedef typename concat<int_list<y>, tmp>::result result; 121 }; 122 123 124 /// 125 /// map template over list 126 /// 127 template<template<int> class func, class list> 128 struct map; 129 130 template<template<int> class func> 131 struct map<func, int_list<> > { 132 typedef int_list<> result; 133 }; 134 135 template<template<int> class func, int head, int... tail> 136 struct map<func, int_list<head, tail...> > { 137 private: 138 enum {tmp_head = func<head>::value}; 139 typedef typename map<func, int_list<tail...> >::result tmp_tail; 140 public: 141 typedef typename concat<int_list<tmp_head>, tmp_tail>::result result; 142 }; 143 144 /// 145 /// print list contents 146 /// 147 148 template <class list> 149 struct printer; 150 151 template <> 152 struct printer<int_list<> > { 153 static inline void print() 154 { 155 cout << endl; 156 }; 157 }; 158 159 template <int head, int... tail> 160 struct printer<int_list<head, tail...> > { 161 static inline void print() 162 { 163 cout << head << " "; 164 printer<int_list<tail...> >::print(); 165 } 166 }; 167 168 /// 169 /// reverse list 170 /// 171 template <class list> 172 struct reverse; 173 174 template <> 175 struct reverse<int_list<> > { 176 typedef int_list<> result; 177 }; 178 179 template <int head, int... tail> 180 struct reverse<int_list<head, tail...> > { 181 private: 182 typedef typename reverse<int_list<tail...> >::result tmp; 183 public: 184 typedef typename concat<tmp, int_list<head> >::result result; 185 }; 186 187 /// 188 /// kill first occurance 189 /// 190 template <int x, class list> 191 struct kill; 192 193 /// good guarantee: will not compile if no occurance. 194 template <int x, int head, int... tail> 195 struct kill<x, int_list<head, tail...> > { 196 private: 197 typedef typename kill<x, int_list<tail...> >::result tmp; 198 public: 199 typedef typename concat<int_list<head>, tmp>::result result; 200 }; 201 202 template <int x, int... tail> 203 struct kill<x, int_list<x, tail...> > { 204 typedef int_list<tail...> result; 205 }; 206 207 /// 208 /// min 209 /// 210 template <int cur, class list> 211 struct min_helper; 212 213 template <int cur> 214 struct min_helper<cur, int_list<> > { 215 enum { 216 result = cur, 217 }; 218 }; 219 220 template <int cur, int head, int... tail> 221 struct min_helper<cur, int_list<head, tail...> > { 222 private: 223 enum { 224 tmp = (cur < head) ? cur : head, 225 }; 226 public: 227 enum { 228 result = min_helper<tmp, int_list<tail...> >::result, 229 }; 230 }; 231 232 template <class list> 233 struct min { 234 enum { 235 result = min_helper<INT_MAX, list>::result, 236 }; 237 }; 238 239 /// 240 /// sort a list 241 /// 242 template <class list> 243 struct sort; 244 245 template <> 246 struct sort<int_list<> > { 247 typedef int_list<> result; 248 }; 249 250 template <int... ints> 251 struct sort<int_list<ints...> > { 252 private: 253 enum { 254 tmp_head = min<int_list<ints...>>::result 255 }; 256 typedef typename sort< 257 typename kill<tmp_head, int_list<ints...> >::result >::result tmp_tail; 258 public: 259 typedef typename concat<int_list<tmp_head>, tmp_tail>::result result; 260 }; 261 262 template <int i> 263 struct square { 264 enum { 265 value = i*i 266 }; 267 }; 268 269 int main(void) 270 { 271 typedef int_list<1, 2, 3, 4> list_1234; 272 273 cout << "list consists of values: "; 274 printer<list_1234>::print(); 275 276 cout << "length is " << length<list_1234>::value << endl; 277 278 cout << "at position 2 in the list stands " << 279 at<2, list_1234>::result << endl; 280 281 cout << "minimum value is: " << 282 min<list_1234>::result << endl; 283 284 typedef concat<list_1234, list_1234>::result list_12341234; 285 cout << "concatenated with itself: "; 286 printer<list_12341234>::print(); 287 288 cout << "with removed 2: "; 289 printer<kill<2, list_1234>::result>::print(); 290 291 cout << "index of 3 is " << 292 lookup<3, list_1234>::value << 293 " and of absent 10 is " << 294 lookup<10, list_1234>::value << endl; 295 296 cout << "list of squares is: "; 297 printer<map<square, list_1234>::result>::print(); 298 299 typedef replace<2, 5, list_1234>::result list_1534; 300 typedef replace<1, 8, list_1534>::result list_8534; 301 cout << "after replacing 2->5 and 1->8 list numbers are: "; 302 printer<list_8534>::print(); 303 304 typedef reverse<list_1234>::result list_4321; 305 cout << "reversed list looks like this: "; 306 printer<list_4321>::print(); 307 308 typedef int_list<6, 33, 5, 8, 5, 12, 27, 10, 1, 5, 7, 8, 13, 309 56, 76, 34, 65, 23, 65, 67, 78, 22, 6, 4, 1, 4, 8, 6, 4, 3, 310 11, 3, 10, 2, 5, 6, 3> long_list; 311 312 cout << "long list is: "; 313 printer<long_list>::print(); 314 cout << "after sort: "; 315 printer<sort<long_list>::result>::print(); 316 } 317
No comments:
Post a Comment