poly.h

Go to the documentation of this file.

#ifndef PolyType_h
#define PolyType_h

#include <boost/iterator/iterator_facade.hpp>
#include <boost/operators.hpp>
#include <boost/foreach.hpp>
#include <iostream>
#include <list>
#include <set>

template<class T> class poly;
template<class T> poly<T> operator+ (const poly<T>&, const char* ); 
template<class T> poly<T> operator+ (const char*, const poly<T>& ); 

template<class T>
class poly :
  boost::incrementable< poly<T>,
  boost::addable< poly<T>,
  boost::multipliable< poly<T>,
  boost::multipliable2< poly<T>, T,
  boost::less_than_comparable< poly<T> > > > > > {    
    
    std::list<std::set<T> > columns;
    
  public:

    class const_iterator;
    typedef T value_type;
    typedef typename std::list<std::set<T> >::iterator                column_iterator;
    typedef typename std::list<std::set<T> >::const_iterator    const_column_iterator;
    poly() {}
    poly(const T& t) {operator+=(t);}

    bool operator<(const poly& R) const { 
      const_column_iterator column(columns.begin()), Rcolumn(R.columns.begin());
      while( column!=columns.end() && Rcolumn!=R.columns.end() && *column==*Rcolumn) { ++column; ++Rcolumn; }
      return column!=columns.end() && Rcolumn!=R.columns.end() && *column < *Rcolumn;
    }  
    poly operator++() {columns.push_back(std::set<T>()); return *this;}                    
    poly operator+=(const poly& R) { columns.insert(columns.end(),R.columns.begin(),R.columns.end()); return *this;}
    poly operator+=(const T& r) { operator++(); return operator*=(r);}
    poly operator*=(const T& r) { columns.back().insert(r); return *this;}    
    poly operator*=(const poly& R) { columns.back().insert(R.begin(),R.end()); return *this;}    
    friend poly<T> operator+ <> (const poly<T>&, const char*);
    friend poly<T> operator+ <> (const char*, const poly<T>&);

    const_iterator begin() const { return const_iterator(*this);}
    const_iterator end()   const { return const_iterator::end_of(*this);} 

    column_iterator begin_columns() { return columns.begin();}
    column_iterator end_columns()   { return columns.end();}

    const_column_iterator begin_columns() const { return columns.begin();}
    const_column_iterator end_columns()   const { return columns.end();}

    size_t size() const { 
      if(columns.empty()) return 0;
      size_t size=1;
      for( const_column_iterator column = columns.begin(); column != columns.end(); ++column) 
    size *= column->size(); 
      return size;
    }

    class const_iterator 
      : public boost::iterator_facade< const_iterator, T const, boost::bidirectional_traversal_tag, T >  {
      friend class boost::iterator_core_access;

      std::list<typename std::set<T>::const_iterator>    state;
      typename std::list<std::set<T> >::const_iterator   begin, end;

      typedef typename std::list<typename std::set<T>::const_iterator>::iterator                state_iterator;
      typedef typename std::list<typename std::set<T>::const_iterator>::const_iterator    const_state_iterator;

      bool equal(const_iterator const& rhs) const { return std::equal( state.begin(), state.end(), rhs.state.begin() ); }
      T dereference() const { T s; for(const_state_iterator istate=state.begin(); istate!=state.end(); ++istate)  s+= **istate; return s; }
      void increment() { 
    state_iterator istate = state.begin();
    const_column_iterator column = begin;
    while( column != end && ++*istate == column->end() ) { ++istate; ++column;} 
    if( column == end ) {--column; --istate;}
    while( istate != state.begin() ) {--istate; *istate = (--column)->begin();}
      }
      void decrement() {  
    state_iterator istate = state.begin();
    const_column_iterator column = begin;
    while( column != end && *istate == column->begin())  { ++istate; ++column;}
    if( column != end) --*istate;
    while( istate != state.begin() ) {--istate; *istate = --((--column)->end());} 
      }
      
    public:
      
      const_iterator() {}
      const_iterator(const poly& p) : begin(p.begin_columns()), end(p.end_columns()) {
    const_column_iterator column = begin; 
    while(column!=end) state.push_back((column++)->begin()); 
      }
      static const_iterator end_of(const poly& p) {
    const_iterator it(p);
    if(p.size()!=0) *--(it.state.end()) = (--p.end_columns())->end();
    return it;
      }
      
  };    

};

template<class T> poly<T> operator+ (const poly<T>& lhs, const char* rhs ) { return lhs + poly<T>(rhs);} 
template<class T> poly<T> operator+ (const char* lhs, const poly<T>& rhs ) { return poly<T>(lhs) + rhs;}

template <class charT, class traits, class T> 
inline
std::basic_ostream<charT,traits>& operator<<(std::basic_ostream<charT,traits>& strm, const poly<T>& f) { 
  BOOST_FOREACH(std::set<T> column, std::make_pair(f.begin_columns(),f.end_columns())) 
    { strm << "( "; BOOST_FOREACH(T entry, column) strm << entry << ", "; strm << " )" << std::endl; }
  return strm; 
}

#endif