libalgebra-demo/libalgebra/monomial_basis.h

/* *************************************************************

Copyright 2010 Terry Lyons, Stephen Buckley, Djalil Chafai, 
Greg Gyurkó and Arend Janssen. 

Distributed under the terms of the GNU General Public License, 
Version 3. (See accompanying file License.txt)

************************************************************* */




//  monomial_basis.h


// Include once wrapper
#ifndef monomial_basisH_SEEN
#define monomial_basisH_SEEN


template<typename SCA, DEG n_letters, DEG max_degree>
class monomial_basis
{
public:
        typedef std::deque<LET> KEY;
        const KEY empty_key;
        typedef std::map<KEY, SCA> MAP;
private:
        DEG _size;
public:
        monomial_basis(void)
        {
                // We statically compute the size (n^{d+1}-1)/(n-1) 
                // where n == n_letters and d == max_degree.
                _size = 1;
                for (DEG i = 1; i <= max_degree; ++i)
                        _size += _size * n_letters;     
        }
public:
        inline KEY keyofletter(LET letter) const
        {
                KEY result;
                result.push_back(letter);
                return result;
        }
        inline bool letter(const KEY& k) const
        {
                return k.size() == 1;
        }
        inline LET getletter(const KEY& k) const
        {
                return k[0];
        }
        inline KEY lparent(const KEY& k) const
        {
                KEY result;
                result.push_back(k[0]);
                return result;
        }
        inline KEY rparent(const KEY& k) const
        {
                KEY result(k);
                result.pop_front();
                return result;
        }
        inline DEG degree(const KEY& k) const
        {
                return k.size();
        }
        inline DEG size(void) const
        {
                return _size;
        }
        inline DEG keypos(const KEY& k) const
        {
                DEG pos = 1;
                for (DEG i = 0; i < k.size(); ++i)
                        pos += n_letters * (k[i] - 1);
                return pos;
        }
        inline KEY begin(void) const
        {
                return empty_key;
        }
        inline KEY end(void) const
        {
                KEY result; // empty key.
                result.push_back(0); // invalid key.    
                return result;
        }
        inline KEY nextkey(const KEY& k) const
        {
                KEY::size_type i;
                for (i = k.size() - 1; i >= 0; --i)
                        if (k[i] < n_letters)
                        {
                                KEY result(k);
                                result[i] += 1;
                                return result;
                        }
                return end();
        }
        std::string key2string(const KEY& k) const
        {
                std::ostringstream oss;
                KEY::size_type i;
                if (!k.empty())
                        oss << k[0];
                for (i = 1; i < k.size(); ++i)
                        oss << "," << k[i];
                return oss.str();
        }
};


template<typename SCA, typename RAT, DEG n_letters, DEG max_degree>
class free_monomial_basis : public monomial_basis<SCA, n_letters, max_degree>
{
public:
        typedef monomial_basis<SCA, n_letters, max_degree> PBASIS;
        typedef typename PBASIS::KEY KEY;
        typedef typename PBASIS::MAP MAP;
        typedef RAT RATIONAL;
        typedef multi_polynomial<SCA, RAT, n_letters, max_degree> MULTIPOLY;
public:
        free_monomial_basis(void) {}
public:

        inline MULTIPOLY prod(const KEY& k1, const KEY& k2) const
        {
                static SCA one(+1);
                MULTIPOLY result;
                if ((max_degree == 0) || (k1.size() + k2.size() <= max_degree))
                {
                        KEY concat(k1);
                        for (typename KEY::size_type i = 0; i < k2.size(); ++i)
                                concat.push_back(k2[i]);
                        result[concat] = one;
                }
                return result;
        }
        inline friend
                std::ostream& operator<<(std::ostream& os, const std::pair<free_monomial_basis*, KEY>& t)
        {
                return os << (t.first)->key2string(t.second);
        }
};

// Include once wrapper
#endif

//EOF.