NiHu  2.0
algorithm.hpp
Go to the documentation of this file.
1 // This file is a part of NiHu, a C++ BEM template library.
2 //
3 // Copyright (C) 2012-2014 Peter Fiala <fiala@hit.bme.hu>
4 // Copyright (C) 2012-2014 Peter Rucz <rucz@hit.bme.hu>
5 //
6 // This program is free software: you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation, either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program. If not, see <http://www.gnu.org/licenses/>.
18 
25 #ifndef ALGORITHM_HPP_INCLUDED
26 #define ALGORITHM_HPP_INCLUDED
27 
28 #include "bool.hpp"
29 #include "if.hpp"
30 #include "integer.hpp"
31 #include "lambda.hpp"
32 #include "operator.hpp"
33 #include "sequence.hpp"
34 
35 #include <type_traits>
36 
37 namespace tmp
38 {
39  namespace internal
40  {
48  template <class Beg, class End, class Init, class Fun >
49  struct accumulate_impl : accumulate_impl<
50  typename next<Beg>::type,
51  End,
52  typename apply<Fun, Init, typename deref<Beg>::type>::type,
53  Fun
54  > {};
55 
59  template <class End, class Init, class Fun>
60  struct accumulate_impl<End, End, Init, Fun>
61  {
62  typedef Init type;
63  };
64  }
65 
72  template <class Seq, class Init, class Fun = tmp::plus<_1,_2> >
73  struct accumulate : internal::accumulate_impl<
74  typename begin<Seq>::type,
75  typename end<Seq>::type,
76  Init,
77  Fun
78  > {};
79 
84  template <class Seq>
85  struct min : accumulate<
86  Seq,
87  typename deref<typename begin<Seq>::type>::type,
88  if_<less<_1,_2>,_1,_2>
89  > {};
90 
95  template <class Seq>
96  struct max : accumulate<
97  Seq,
98  typename deref<typename begin<Seq>::type>::type,
99  if_<less<_1,_2>,_2,_1>
100  > {};
101 
102 
103  namespace internal
104  {
105  class empty;
106 
107  template <class A, class B>
108  struct inheriter
109  {
110  struct type : public A, public B {};
111  };
112 
113  template <class B>
114  struct inheriter<empty, B>
115  {
116  struct type : public B {};
117  };
118  }
119 
124  template <class Seq>
125  struct inherit : accumulate<
126  Seq,
127  internal::empty,
128  internal::inheriter<_1,_2>
129  > {};
130 
131  namespace internal
132  {
140  template <class Beg, class End, class Ins, class Trans>
141  struct transform_impl : transform_impl<
142  typename next<Beg>::type,
143  End,
144  inserter<
145  typename apply<
146  typename Ins::operation,
147  typename Ins::state,
148  typename apply<
149  Trans,
150  typename deref<Beg>::type
151  >::type
152  >::type,
153  typename Ins::operation
154  >,
155  Trans
156  > {};
157 
161  template <class End, class Ins, class Trans>
162  struct transform_impl<End, End, Ins, Trans>
163  {
164  typedef typename Ins::state type;
165  };
166 
175  template <class Beg, class End, class Ins, class Cond, class Trans>
176  struct transform_if_ptr_impl : transform_if_ptr_impl<
177  typename next<Beg>::type,
178  End,
179  inserter<
180  typename std::conditional<
181  apply<Cond, Beg>::type::value,
182  typename apply<
183  typename Ins::operation,
184  typename Ins::state,
185  typename apply<Trans, Beg>::type
186  >::type,
187  typename Ins::state
188  >::type,
189  typename Ins::operation
190  >,
191  Cond,
192  Trans
193  > {};
194 
198  template <class End, class Ins, class Cond, class Trans>
199  struct transform_if_ptr_impl<End, End, Ins, Cond, Trans>
200  {
201  typedef typename Ins::state type;
202  };
203  }
204 
211  template <class Seq, class Ins, class Trans>
212  struct transform : internal::transform_impl<
213  typename begin<Seq>::type,
214  typename end<Seq>::type,
215  Ins,
216  Trans
217  > {};
218 
226  template <class Seq, class Ins, class Cond, class Trans>
227  struct transform_if_ptr : internal::transform_if_ptr_impl<
228  typename begin<Seq>::type,
229  typename end<Seq>::type,
230  Ins,
231  Cond,
232  Trans
233  > {};
234 
240  template <class Seq, class Ins>
241  struct copy : transform<Seq, Ins, _1> {};
242 
248  template <class Seq, class Ins, class Cond>
249  struct copy_if : transform_if_ptr<Seq, Ins, Cond, tmp::deref<_1> > {};
250 
256  template <class Seq1, class Seq2>
257  struct concatenate : transform<
258  Seq2,
259  inserter<Seq1, push_back<_1, _2> >,
260  _1
261  > {};
262 
267  template <class Seq>
268  struct serialise : accumulate<
269  Seq,
270  typename empty<Seq>::type,
271  concatenate<_1, _2>
272  > {};
273 
274  namespace internal
275  {
276  template <class Beg, class End, class Elem>
277  struct find_impl : std::conditional<
278  std::is_same<typename deref<Beg>::type, Elem>::type::value,
279  Beg,
280  typename find_impl<typename next<Beg>::type, End, Elem>::type
281  > {};
282 
283  template <class End, class Elem>
284  struct find_impl<End, End, Elem>
285  {
286  typedef End type;
287  };
288  }
289 
297  template <class Seq, class Elem>
298  struct find : internal::find_impl<
299  typename begin<Seq>::type,
300  typename end<Seq>::type,
301  Elem
302  > {};
303 
310  template <class Seq, class Elem>
311  struct is_member : not_<
312  typename std::is_same<
313  typename find<Seq, Elem>::type,
314  typename end<Seq>::type
315  >::type
316  > {};
317 
323  template <class Seq>
324  struct unique : accumulate<
325  Seq,
326  typename empty<Seq>::type,
327  if_<is_member<_1,_2>, _1, push_back<_1,_2> >
328  > {};
329 
330  namespace internal
331  {
333  template <class first, class second, class condition>
334  struct swap_if;
335 
337  template <class first, class second>
338  struct swap_if<first, second, std::false_type>
339  {
340  typedef first first_t;
341  typedef second second_t;
342  };
343 
345  template <class first, class second>
346  struct swap_if<first, second, std::true_type>
347  {
348  typedef second first_t;
349  typedef first second_t;
350  };
351 
352  template <
353  class Seq, class Compare,
354  class siz = typename less<integer<int, 1>, typename size<Seq>::type>::type
355  >
356  struct bubble_cycle
357  {
358  // get first two elements and remove them from the sequence
359  typedef typename deref<typename begin<Seq>::type>::type first_t;
360  typedef typename deref<
361  typename begin<typename pop_front<Seq>::type>::type
362  >::type second_t;
363  typedef typename pop_front<typename pop_front<Seq>::type>::type trunc;
364  // swap the two elements if needed
365  typedef typename apply<Compare, first_t, second_t>::type cond;
366  typedef typename swap_if<first_t, second_t, cond>::first_t new_first;
367  typedef typename swap_if<first_t, second_t, cond>::second_t new_second;
368  // push the swapped second back
369  typedef typename push_front<trunc, new_second>::type processed;
370  // repeat for the remaining sequence and then push the first back
371  typedef typename push_front<
372  typename bubble_cycle<processed, Compare>::type,
373  new_first
374  >::type type;
375  };
376 
377  template <class Seq, class Compare>
378  struct bubble_cycle<Seq, Compare, std::false_type> : Seq {};
379  }
380 
385  template <
386  class Seq,
387  class Compare = less<_2, _1>,
388  class cnt = typename size<Seq>::type
389  >
390  struct bubble_sort : bubble_sort<
391  typename internal::bubble_cycle<Seq, Compare>::type,
392  Compare,
393  typename prev<cnt>::type
394  > {};
395 
397  template <class Seq, class Compare>
398  struct bubble_sort<Seq, Compare, integer<int, 0> > : Seq {};
399 
400 
401  namespace internal
402  {
403  template <class value, unsigned N, class Seq>
404  struct constant_sequence_impl : push_back<
405  typename constant_sequence_impl<
406  value, N-1, Seq
407  >::type,
408  value
409  > {};
410 
411  template <class value, class Seq>
412  struct constant_sequence_impl<value, 0, Seq>
413  {
414  typedef Seq type;
415  };
416  }
417 
419  template <class value, unsigned N, class Seq>
420  struct constant_sequence : internal::constant_sequence_impl<
421  value, N, typename empty<Seq>::type
422  > {};
423 
424 
425  namespace internal
426  {
427  template <class T, int increment>
428  struct increment_type;
429 
430  template <class T, int increment, T val>
431  struct increment_type<std::integral_constant<T, val>, increment>
432  : public std::integral_constant<T, val + increment> {};
433 
434  template <class value, unsigned N, class Seq, int increment>
435  struct arithmetic_sequence_impl : push_front<
436  typename arithmetic_sequence_impl<
437  typename increment_type<value, increment>::type, N-1, Seq, increment
438  >::type,
439  value
440  > {};
441 
442  template <class value, class Seq, int increment>
443  struct arithmetic_sequence_impl<value, 0, Seq, increment>
444  {
445  typedef Seq type;
446  };
447  }
448 
449 
456  template <class value, unsigned N, class Seq, int increment = 1>
457  struct arithmetic_sequence : internal::arithmetic_sequence_impl<
458  value, N, typename empty<Seq>::type, increment
459  > {};
460 }
461 
462 #endif /* ALGORITHM_HPP_INCLUDED */
tmp::inherit
combine a sequence of classes so that the result is inherited from each element
Definition: algorithm.hpp:125
tmp::constant_sequence
generate a constant sequence
Definition: algorithm.hpp:420
tmp::integer
integer type representation
Definition: integer.hpp:54
tmp
template metaprogramming functions
Definition: asymptotic_types.hpp:101
tmp::max
maximum of range
Definition: algorithm.hpp:96
tmp::bubble_sort
sort a sequence by bubble sort
Definition: algorithm.hpp:390
tmp::find
Find an element in a sequence.
Definition: algorithm.hpp:298
tmp::min
minimum of range
Definition: algorithm.hpp:85
lambda.hpp
implementation of placeholders and lambda functions
tmp::copy_if
copy elements from a container into an other
Definition: algorithm.hpp:249
integer.hpp
integer type representation and basic integer arithmetics
operator.hpp
declaration of operator metafunctions
tmp::unique
return a vector containing each element of Seq exactly once
Definition: algorithm.hpp:324
tmp::empty
return empty sequence
Definition: sequence.hpp:64
tmp::serialise
transform sequence of sequences into a flat sequence
Definition: algorithm.hpp:268
sequence.hpp
implementation of compile time sequences
bool.hpp
implementation of Boolean functions
tmp::copy
copy elements from a container into an other
Definition: algorithm.hpp:241
tmp::is_member
return true if the element is member of a sequence
Definition: algorithm.hpp:311
tmp::concatenate
concatenate two sequences into a new sequence
Definition: algorithm.hpp:257
if.hpp
Implementation of the tmp::if_ metafunction.
tmp::transform_if_ptr
conditionally transform elements in a sequence
Definition: algorithm.hpp:227
tmp::push_back
push an element to the back
Definition: sequence.hpp:99
tmp::not_
Boolean negation.
Definition: bool.hpp:44
tmp::accumulate
accumulate elements of a sequence using a binary metafunction
Definition: algorithm.hpp:73
tmp::transform
transform elements in a sequence using a user-specified metafunctor and an inserter
Definition: algorithm.hpp:212
tmp::arithmetic_sequence
generate an arithmetic sequence
Definition: algorithm.hpp:457