pascals_triangle.hpp

Go to the documentation of this file.

 
/*****************************************************************************
** Ifdefs
*****************************************************************************/
 
#ifndef ECL_GEOMETRY_PASCALS_HPP_
#define ECL_GEOMETRY_PASCALS_HPP_
 
/*****************************************************************************
** Includes
*****************************************************************************/
 
#include <ecl/config/macros.hpp>
#include <ecl/containers/array.hpp>
#include <ecl/formatters/common.hpp>
#include <ecl/formatters/number.hpp>
 
/*****************************************************************************
** Namespaces
*****************************************************************************/
 
namespace ecl {
 
/*****************************************************************************
** Class [PascalsTriangle]
*****************************************************************************/
 
template <int N>
class ECL_PUBLIC PascalsTriangle {
    public:
        /*********************
        ** C&D
        **********************/
        PascalsTriangle();
        virtual ~PascalsTriangle() {};
 
        /*********************
        ** Iterators
        **********************/
        typedef typename Array<int,(N+2)*(N+1)/2>::const_iterator const_iterator;  
        const_iterator begin(unsigned int index = 0) const;
        const_iterator end(unsigned int index = 0) const;
 
        /*********************
        ** Streaming
        **********************/
        template <typename OutputStream, int PowerN>
        friend OutputStream& operator<<(OutputStream &ostream, const PascalsTriangle<PowerN> &triangle);
 
    private:
        Array<int,(N+2)*(N+1)/2> coefficients;
};
/*****************************************************************************
** Specialisations [Pascals Triangle][3]
*****************************************************************************/
template <>
class ECL_PUBLIC PascalsTriangle<3> {
    public:
        /*********************
        ** C&D
        **********************/
        PascalsTriangle();
        virtual ~PascalsTriangle() {};
 
        /*********************
        ** Iterators
        **********************/
        typedef Array<int,10>::const_iterator const_iterator; 
        const_iterator begin(unsigned int index = 0) const;
        const_iterator end(unsigned int index = 0) const;
 
        /*********************
        ** Streaming
        **********************/
        template <typename OutputStream>
        friend OutputStream& operator<<(OutputStream &ostream, const PascalsTriangle<3> &triangle);
 
    private:
        Array<int,10> coefficients;
};
 
/*****************************************************************************
** Specialisations [Pascals Triangle][5]
*****************************************************************************/
template <>
class ECL_PUBLIC PascalsTriangle<5> {
    public:
        /*********************
        ** C&D
        **********************/
        PascalsTriangle();
        virtual ~PascalsTriangle() {};
 
        /*********************
        ** Iterators
        **********************/
        typedef Array<int,21>::const_iterator const_iterator; 
        const_iterator begin(unsigned int index = 0) const;
        const_iterator end(unsigned int index = 0) const;
 
        /*********************
        ** Streaming
        **********************/
        template <typename OutputStream>
        friend OutputStream& operator<<(OutputStream &ostream, const PascalsTriangle<5> &triangle);
 
    private:
        Array<int,21> coefficients;
};
 
/*****************************************************************************
** Implementation [Pascals Triangle]
*****************************************************************************/
template <int N>
PascalsTriangle<N>::PascalsTriangle() {
    int counter = 0;
    for (int i = N+1; i > 0; --i ) {
        for (int j = 0; j < i; ++j ) {
            if ( ( i == N+1 ) || ( j == 0 ) ) {
                coefficients[counter] = 1;
            } else {
                coefficients[counter] =  coefficients[counter-1] + coefficients[counter-(i+1)];
            }
            ++counter;
        }
    }
}
 
template <int N>
typename PascalsTriangle<N>::const_iterator PascalsTriangle<N>::begin(unsigned int index) const {
    int coeff_index = 0;
    for (unsigned int i = 0; i < index; ++i ) {
        coeff_index += N+1-i;
    }
    return const_iterator( &coefficients[coeff_index] );
}
template <int N>
typename PascalsTriangle<N>::const_iterator PascalsTriangle<N>::end(unsigned int index) const {
    int coeff_index = 0;
    for (unsigned int i = 0; i <= index; ++i ) {
        coeff_index += N+1-i;
    }
    coeff_index -= 1; // dont want to call beyond the array limit.
    return const_iterator( (&coefficients[coeff_index])+1);
}
 
/*****************************************************************************
** Streaming
*****************************************************************************/
 
template <typename OutputStream, int PowerN>
OutputStream& operator << ( OutputStream &ostream, const PascalsTriangle<PowerN> &triangle)
{
    Format<int> format(2+PowerN/5,CentreAlign); // Rough hack to get a good auto-sizing working. Might blow up for large N.
    int counter = 0;
    for (int i = PowerN+1; i > 0; --i ) {
        for (int j = 0; j < i; ++j ) {
            ostream << format(triangle.coefficients[counter]) << " ";
            ++counter;
        }
        ostream << "\n";
    }
    ostream.flush();
 
    return ostream;
}
 
template <typename OutputStream>
OutputStream& operator << ( OutputStream &ostream, const PascalsTriangle<3> &triangle)
{
    Format<int> format(2,CentreAlign);
    int counter = 0;
    for (int i = 4; i > 0; --i ) {
        for (int j = 0; j < i; ++j ) {
            ostream << format(triangle.coefficients[counter]) << " ";
            ++counter;
        }
        ostream << "\n";
    }
    ostream.flush();
 
    return ostream;
}
 
template <typename OutputStream>
OutputStream& operator << ( OutputStream &ostream, const PascalsTriangle<5> &triangle)
{
    Format<int> format(3,CentreAlign);
    int counter = 0;
    for (int i = 6; i > 0; --i ) {
        for (int j = 0; j < i; ++j ) {
            ostream << format(triangle.coefficients[counter]) << " ";
            ++counter;
        }
        ostream << "\n";
    }
    ostream.flush();
 
    return ostream;
}
 
} // namespace ecl
 
 
 
#endif /* ECL_GEOMETRY_PASCALS_HPP_ */