Advertisement
Guest User

Untitled

a guest
Sep 1st, 2015
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <limits>
  3. #include <initializer_list>
  4.  
  5. template<typename T>
  6. class List
  7. {
  8. template<typename T2>
  9. friend std::ostream &operator<<(std::ostream &, const List<T2> &);
  10. public:
  11. constexpr List();
  12. constexpr List(std::initializer_list<T>);
  13. constexpr T head() const;
  14. constexpr List<T> tail() const;
  15. constexpr List<T> add(T) const;
  16. constexpr List<T> merge(List<T>) const;
  17. constexpr List<T> reverse() const;
  18. template<typename Filter>
  19. constexpr List<T> filter(Filter) const;
  20. constexpr List<T> sort() const;
  21. constexpr T sum() const;
  22. private:
  23. int length;
  24. T array[std::numeric_limits<int>::max() >> 2];
  25. };
  26.  
  27. template<typename T>
  28. constexpr List<T>::List()
  29. : length {0}
  30. , array {0}
  31. {
  32. }
  33.  
  34. template<typename T>
  35. constexpr List<T>::List(std::initializer_list<T> l)
  36. : length {static_cast<int>(l.size())}
  37. , array {0}
  38. {
  39. for (auto it = l.begin(); it != l.end(); ++it)
  40. {
  41. array[it - l.begin()] = *it;
  42. }
  43. }
  44.  
  45. template<typename T>
  46. constexpr T List<T>::head() const
  47. {
  48. return array[0];
  49. }
  50.  
  51. template<typename T>
  52. constexpr List<T> List<T>::tail() const
  53. {
  54. List<T> l;
  55. l.length = length - 1;
  56. for (int i = 0; i < l.length; ++i)
  57. {
  58. l.array[i] = array[i + 1];
  59. }
  60. return l;
  61. }
  62.  
  63. template<typename T>
  64. constexpr List<T> List<T>::add(T t) const
  65. {
  66. List<T> l {*this};
  67. l.array[l.length++] = t;
  68. return l;
  69. }
  70.  
  71. template<typename T>
  72. constexpr List<T> List<T>::merge(List<T> l) const
  73. {
  74. for (int i = l.length - 1; i >= 0; --i)
  75. {
  76. l.array[i + length] = l.array[i];
  77. }
  78. for (int i = 0; i < length; ++i)
  79. {
  80. l.array[i] = array[i];
  81. }
  82. l.length += length;
  83. return l;
  84. }
  85.  
  86. template<typename T>
  87. constexpr List<T> List<T>::reverse() const
  88. {
  89. List<T> l;
  90. l.length = length;
  91. for (int i = 0; i < l.length; ++i)
  92. {
  93. l.array[i] = array[length - i - 1];
  94. }
  95. return l;
  96. }
  97.  
  98. template<typename T>
  99. template<typename Filter>
  100. constexpr List<T> List<T>::filter(Filter f) const
  101. {
  102. List<T> l;
  103. for (int i {0}; i < length; ++i)
  104. {
  105. if (f(array[i]))
  106. {
  107. l = l.add(array[i]);
  108. }
  109. }
  110. return l;
  111. }
  112.  
  113. template<typename T>
  114. struct LT
  115. {
  116. T pivot;
  117. constexpr bool operator()(T t) const
  118. {
  119. return t < pivot;
  120. }
  121. };
  122.  
  123. template<typename T>
  124. struct GE
  125. {
  126. T pivot;
  127. constexpr bool operator()(T t) const
  128. {
  129. return t >= pivot;
  130. }
  131. };
  132.  
  133. template<typename T>
  134. constexpr List<T> List<T>::sort() const
  135. {
  136. if (length == 0)
  137. {
  138. return *this;
  139. }
  140. return tail().filter(LT<T> {head()}).sort().add(head())
  141. .merge(tail().filter(GE<T> {head()}).sort());
  142. }
  143.  
  144. template<typename T>
  145. constexpr T List<T>::sum() const
  146. {
  147. if (length == 0)
  148. {
  149. return T {};
  150. }
  151. return head() + tail().sum();
  152. }
  153.  
  154. template<typename T>
  155. std::ostream &operator<<(std::ostream &os, const List<T> &l)
  156. {
  157. os << '{';
  158. for (int i {0}; i < l.length - 1; ++i)
  159. {
  160. os << l.array[i] << ", ";
  161. }
  162. return os << l.array[l.length - 1] << '}';
  163. }
  164.  
  165. inline constexpr List<int> range(int a, int b, int c = 1)
  166. {
  167. List<int> l;
  168. while (a < b)
  169. {
  170. l = l.add(a);
  171. a += c;
  172. }
  173. return l;
  174. }
  175.  
  176. int main()
  177. {
  178. constexpr std::size_t n = range(0, 300).reverse().sort().sum();
  179. std::cout << n << std::endl;
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement