pascals_triangle.hpp
Go to the documentation of this file.
1 
8 /*****************************************************************************
9 ** Ifdefs
10 *****************************************************************************/
11 
12 #ifndef ECL_GEOMETRY_PASCALS_HPP_
13 #define ECL_GEOMETRY_PASCALS_HPP_
14 
15 /*****************************************************************************
16 ** Includes
17 *****************************************************************************/
18 
19 #include <ecl/config/macros.hpp>
20 #include <ecl/containers/array.hpp>
21 #include <ecl/formatters/common.hpp>
22 #include <ecl/formatters/number.hpp>
23 
24 /*****************************************************************************
25 ** Namespaces
26 *****************************************************************************/
27 
28 namespace ecl {
29 
30 /*****************************************************************************
31 ** Class [PascalsTriangle]
32 *****************************************************************************/
33 
56 template <int N>
57 class ECL_PUBLIC PascalsTriangle {
58  public:
59  /*********************
60  ** C&D
61  **********************/
62  PascalsTriangle();
63  virtual ~PascalsTriangle() {};
64 
65  /*********************
66  ** Iterators
67  **********************/
68  typedef typename Array<int,(N+2)*(N+1)/2>::const_iterator const_iterator;
69  const_iterator begin(unsigned int index = 0) const;
70  const_iterator end(unsigned int index = 0) const;
71 
72  /*********************
73  ** Streaming
74  **********************/
75  template <typename OutputStream, int PowerN>
76  friend OutputStream& operator<<(OutputStream &ostream, const PascalsTriangle<PowerN> &triangle);
77 
78  private:
79  Array<int,(N+2)*(N+1)/2> coefficients;
80 };
81 /*****************************************************************************
82 ** Specialisations [Pascals Triangle][3]
83 *****************************************************************************/
94 template <>
95 class ECL_PUBLIC PascalsTriangle<3> {
96  public:
97  /*********************
98  ** C&D
99  **********************/
106  PascalsTriangle();
107  virtual ~PascalsTriangle() {};
108 
109  /*********************
110  ** Iterators
111  **********************/
112  typedef Array<int,10>::const_iterator const_iterator;
120  const_iterator begin(unsigned int index = 0) const;
128  const_iterator end(unsigned int index = 0) const;
129 
130  /*********************
131  ** Streaming
132  **********************/
133  template <typename OutputStream>
134  friend OutputStream& operator<<(OutputStream &ostream, const PascalsTriangle<3> &triangle);
135 
136  private:
137  Array<int,10> coefficients;
138 };
139 
140 /*****************************************************************************
141 ** Specialisations [Pascals Triangle][5]
142 *****************************************************************************/
153 template <>
154 class ECL_PUBLIC PascalsTriangle<5> {
155  public:
156  /*********************
157  ** C&D
158  **********************/
165  PascalsTriangle();
166  virtual ~PascalsTriangle() {};
167 
168  /*********************
169  ** Iterators
170  **********************/
171  typedef Array<int,21>::const_iterator const_iterator;
179  const_iterator begin(unsigned int index = 0) const;
187  const_iterator end(unsigned int index = 0) const;
188 
189  /*********************
190  ** Streaming
191  **********************/
192  template <typename OutputStream>
193  friend OutputStream& operator<<(OutputStream &ostream, const PascalsTriangle<5> &triangle);
194 
195  private:
196  Array<int,21> coefficients;
197 };
198 
199 /*****************************************************************************
200 ** Implementation [Pascals Triangle]
201 *****************************************************************************/
207 template <int N>
209  int counter = 0;
210  for (int i = N+1; i > 0; --i ) {
211  for (int j = 0; j < i; ++j ) {
212  if ( ( i == N+1 ) || ( j == 0 ) ) {
213  coefficients[counter] = 1;
214  } else {
215  coefficients[counter] = coefficients[counter-1] + coefficients[counter-(i+1)];
216  }
217  ++counter;
218  }
219  }
220 }
221 
229 template <int N>
230 typename PascalsTriangle<N>::const_iterator PascalsTriangle<N>::begin(unsigned int index) const {
231  int coeff_index = 0;
232  for (unsigned int i = 0; i < index; ++i ) {
233  coeff_index += N+1-i;
234  }
235  return const_iterator( &coefficients[coeff_index] );
236 }
244 template <int N>
245 typename PascalsTriangle<N>::const_iterator PascalsTriangle<N>::end(unsigned int index) const {
246  int coeff_index = 0;
247  for (unsigned int i = 0; i <= index; ++i ) {
248  coeff_index += N+1-i;
249  }
250  coeff_index -= 1; // dont want to call beyond the array limit.
251  return const_iterator( (&coefficients[coeff_index])+1);
252 }
253 
254 /*****************************************************************************
255 ** Streaming
256 *****************************************************************************/
257 
270 template <typename OutputStream, int PowerN>
271 OutputStream& operator << ( OutputStream &ostream, const PascalsTriangle<PowerN> &triangle)
272 {
273  Format<int> format(2+PowerN/5,CentreAlign); // Rough hack to get a good auto-sizing working. Might blow up for large N.
274  int counter = 0;
275  for (int i = PowerN+1; i > 0; --i ) {
276  for (int j = 0; j < i; ++j ) {
277  ostream << format(triangle.coefficients[counter]) << " ";
278  ++counter;
279  }
280  ostream << "\n";
281  }
282  ostream.flush();
283 
284  return ostream;
285 }
286 
296 template <typename OutputStream>
297 OutputStream& operator << ( OutputStream &ostream, const PascalsTriangle<3> &triangle)
298 {
299  Format<int> format(2,CentreAlign);
300  int counter = 0;
301  for (int i = 4; i > 0; --i ) {
302  for (int j = 0; j < i; ++j ) {
303  ostream << format(triangle.coefficients[counter]) << " ";
304  ++counter;
305  }
306  ostream << "\n";
307  }
308  ostream.flush();
309 
310  return ostream;
311 }
312 
322 template <typename OutputStream>
323 OutputStream& operator << ( OutputStream &ostream, const PascalsTriangle<5> &triangle)
324 {
325  Format<int> format(3,CentreAlign);
326  int counter = 0;
327  for (int i = 6; i > 0; --i ) {
328  for (int j = 0; j < i; ++j ) {
329  ostream << format(triangle.coefficients[counter]) << " ";
330  ++counter;
331  }
332  ostream << "\n";
333  }
334  ostream.flush();
335 
336  return ostream;
337 }
338 
339 } // namespace ecl
340 
341 
342 
343 #endif /* ECL_GEOMETRY_PASCALS_HPP_ */
const int * const_iterator
const_iterator end(unsigned int index=0) const
Iterator generator for diagonals of pascals triangle [end].
Formatter for int types. It is a specialisation of the Format<IntegralNumber> class.
Definition: number.hpp:425
const_iterator begin(unsigned int index=0) const
Iterator generator for diagonals of pascals triangle [begin].
#define ECL_PUBLIC
Array< int,(N+2)*(N+1)/2 >::const_iterator const_iterator
PascalsTriangle()
Default constructor.
CentreAlign


xbot_node
Author(s): Roc, wangpeng@droid.ac.cn
autogenerated on Sat Oct 10 2020 03:28:13