algorithm

   1 // vi:ft=cpp
   2 #ifndef _STL_ALGORITHM_H
   3 #define _STL_ALGORITHM_H
   4
   5 #include "type_traits"
   6 #include "iterator"
   7 #include "cstring" // for memmove
   8
   9 namespace std {
  10
  11 template <class T>
  12 T &&move(T &x)
  13 {
  14     return x;
  15 }
  16
  17 template <class T>
  18 void swap(T &a, T &b)
  19 {
  20     T tmp(move(a));
  21     a = move(b);
  22     b = move(tmp);
  23 }
  24
  25 template <class T>
  26 void __copy_pod(const T *first, const T *last, T *result_start)
  27 {
  28     memmove(
  29       static_cast<void *>(result_start),
  30       static_cast<const void *>(first),
  31       (last - first) * sizeof(T)
  32     );
  33 }
  34
  35 /*** MOVE ***/
  36
  37 /* naive implementation */
  38 template <class InputIterator, class OutputIterator,
  39   bool IsPod = is_pod<typename iterator_traits<OutputIterator>::value_type>::value>
  40 struct __move {
  41     static OutputIterator run(InputIterator first, InputIterator last, OutputIterator result)
  42     {
  43         while (first != last){
  44             *result++ = move(*first++);
  45         }
  46         return result;
  47     }
  48 };
  49
  50 /* pod implementation */
  51 template <class T>
  52 struct __move<T *, typename remove_cv<T>::type *, true> {
  53     static T *run(const T *first, const T *last, typename remove_cv<T>::type *result)
  54     {
  55         __copy_pod(first, last, result);
  56         return result + (last - first);
  57     }
  58 };
  59
  60 template <class InputIterator, class OutputIterator>
  61 OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
  62 {
  63     return const_cast<OutputIterator>(__move<InputIterator, OutputIterator>::run(first, last, result));
  64 }
  65
  66 /*** MOVE BACKWARD ***/
  67
  68 /* naive implementation */
  69 template <class InputIterator, class OutputIterator,
  70   bool IsPod = is_pod<typename iterator_traits<OutputIterator>::value_type>::value>
  71 struct __move_backward {
  72     static OutputIterator run(InputIterator first, InputIterator last, OutputIterator result)
  73     {
  74         while (last != first){
  75             *--result = move(*--last);
  76         }
  77         return result;
  78     }
  79 };
  80
  81 /* pod implementation */
  82 template <class T>
  83 struct __move_backward<T *, typename remove_cv<T>::type *, true> {
  84     static T *run(const T *first, const T *last, typename remove_cv<T>::type *result)
  85     {
  86         __copy_pod(first, last, result - (last - first));
  87         return result;
  88     }
  89 };
  90
  91 template <class InputIterator, class OutputIterator>
  92 OutputIterator move_backward(InputIterator first, InputIterator last, OutputIterator result)
  93 {
  94     return const_cast<OutputIterator>(__move_backward<InputIterator, OutputIterator>::run(first, last, result));
  95 }
  96
  97 /*** COPY ***/
  98
  99 /* naive implementation */
 100 template <class InputIterator, class OutputIterator,
 101   bool IsPod = is_pod<typename iterator_traits<OutputIterator>::value_type>::value>
 102 struct __copy {
 103     static OutputIterator run(InputIterator first, InputIterator last, OutputIterator result)
 104     {
 105         while (first != last){
 106             *result++ = *first++;
 107         }
 108         return result;
 109     }
 110 };
 111
 112 /* pod implementation */
 113 template <class T>
 114 struct __copy<T *, typename remove_cv<T>::type *, true> {
 115     static T *run(const T *first, const T *last, typename remove_cv<T>::type *result)
 116     {
 117         __copy_pod(first, last, result);
 118         return result + (last - first);
 119     }
 120 };
 121
 122 template <class InputIterator, class OutputIterator>
 123 OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
 124 {
 125     return const_cast<OutputIterator>(__copy<InputIterator, OutputIterator>::run(first, last, result));
 126 }
 127
 128 /*** COPY BACKWARD ***/
 129
 130 /* naive implementation */
 131 template <class InputIterator, class OutputIterator,
 132   bool IsPod = is_pod<typename iterator_traits<OutputIterator>::value_type>::value>
 133 struct __copy_backward {
 134     static OutputIterator run(InputIterator first, InputIterator last, OutputIterator result)
 135     {
 136         while (last != first){
 137             *--result = *--last;
 138         }
 139         return result;
 140     }
 141 };
 142
 143 /* pod implementation */
 144 template <class T>
 145 struct __copy_backward<T *, typename remove_cv<T>::type *, true> {
 146     static T *run(const T *first, const T *last, typename remove_cv<T>::type *result)
 147     {
 148         __copy_pod(first, last, result - (last - first));
 149         return result;
 150     }
 151 };
 152
 153 template <class InputIterator, class OutputIterator>
 154 OutputIterator copy_backward(InputIterator first, InputIterator last, OutputIterator result)
 155 {
 156     return const_cast<OutputIterator>(__copy_backward<InputIterator, OutputIterator>::run(first, last, result));
 157 }
 158
 159 template <class OutputIterator, class Size, class T>
 160 void fill_n(OutputIterator first, Size n, const T &value)
 161 {
 162     // naive implementation
 163     while (n--){
 164         *first++ = value;
 165     }
 166 }
 167
 168 }
 169
 170 #endif