BoolePolynomial.h

Go to the documentation of this file.

// -*- c++ -*-
//*****************************************************************************
//*****************************************************************************

#ifndef BoolePolynomial_h_
#define BoolePolynomial_h_

// include standard definitions
#include <vector>

// get standard map functionality
#include <map>

// get standard algorithmic functionalites
#include <algorithm>

#include "BooleRing.h"
// include basic definitions and decision diagram interface
#include "CDDInterface.h"

// include definition of sets of Boolean variables
#include "CTermIter.h"
#include "CBidirectTermIter.h"

#include "pbori_func.h"
#include "pbori_tags.h"
#include "BooleSet.h"

#include "CTermIter.h"
#include "BooleConstant.h"

BEGIN_NAMESPACE_PBORI


// forward declarations
class LexOrder;
class DegLexOrder;
class DegRevLexAscOrder;
class BlockDegLexOrder;
class BlockDegRevLexAscOrder;

class BooleMonomial;
class BooleVariable;
class BooleExponent;


template <class IteratorType, class MonomType>
class CIndirectIter;

template <class IteratorType, class MonomType>
class COrderedIter;


//template<class, class, class, class> class CGenericIter;
template<class, class, class, class> class CDelayedTermIter;

template<class OrderType, class NavigatorType, class MonomType>
class CGenericIter;

template<class OrderType, class NavigatorType, class MonomType>
class MyCGenericIter;


template<class NavigatorType, class ExpType>
class CExpIter;


class BoolePolynomial;
BoolePolynomial 
operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs);

class BoolePolynomial {

public:

  friend class BooleMonomial;

  //-------------------------------------------------------------------------
  // types definitions
  //-------------------------------------------------------------------------

  typedef BoolePolynomial self;


  typedef CTypes::manager_type manager_type;
  typedef CTypes::manager_reference manager_reference;
  typedef CTypes::manager_ptr manager_ptr;
  typedef CTypes::dd_type dd_type;
  typedef CTypes::size_type size_type;
  typedef CTypes::idx_type idx_type;
  typedef CTypes::bool_type bool_type;
  typedef CTypes::ostream_type ostream_type;
  typedef CTypes::hash_type hash_type;

  typedef dd_type::first_iterator first_iterator;

  typedef dd_type::navigator navigator;

  typedef dd_type::pretty_out_type pretty_out_type;

  typedef dd_type::filename_type filename_type;


  typedef BooleMonomial monom_type; 

  typedef BooleVariable var_type; 

  typedef BooleExponent exp_type; 

  typedef BooleConstant constant_type;

  typedef BooleRing ring_type;

  typedef 
  binary_composition< std::plus<size_type>, 
                      project_ith<1>, integral_constant<size_type, 1> > 
  increment_type;

  typedef 
  binary_composition< std::minus<size_type>, 
                      project_ith<1>, integral_constant<size_type, 1> > 
  decrement_type;



  //  typedef COrderedIter<exp_type> ordered_exp_iterator;
  typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;

  //  typedef COrderedIter<monom_type> ordered_iterator;
  typedef COrderedIter<navigator, monom_type> ordered_iterator;


  typedef CGenericIter<LexOrder, navigator, monom_type> lex_iterator;
  typedef CGenericIter<DegLexOrder, navigator, monom_type> dlex_iterator;
  typedef CGenericIter<DegRevLexAscOrder, navigator, monom_type> 
  dp_asc_iterator;

  typedef CGenericIter<BlockDegLexOrder,  navigator, monom_type> 
  block_dlex_iterator;
  typedef CGenericIter<BlockDegRevLexAscOrder,  navigator, monom_type> 
  block_dp_asc_iterator;

  typedef CGenericIter<LexOrder, navigator, exp_type> lex_exp_iterator;
  typedef CGenericIter<DegLexOrder,  navigator, exp_type> dlex_exp_iterator;
  typedef CGenericIter<DegRevLexAscOrder,  navigator, exp_type> 
  dp_asc_exp_iterator;
  typedef CGenericIter<BlockDegLexOrder, navigator, exp_type> 
  block_dlex_exp_iterator;
  typedef CGenericIter<BlockDegRevLexAscOrder, navigator, exp_type> 
  block_dp_asc_exp_iterator;

  typedef lex_iterator const_iterator;

  typedef CExpIter<navigator, exp_type> exp_iterator;

  typedef CGenericIter<LexOrder, navigator, size_type> deg_iterator;

  typedef std::vector<monom_type> termlist_type;

  typedef dd_type::easy_equality_property easy_equality_property;

  typedef BooleSet set_type;

  typedef std::map<self, idx_type, symmetric_composition<
    std::less<navigator>, navigates<self> > > idx_map_type;
  typedef std::map<self, std::vector<self>, symmetric_composition<
    std::less<navigator>, navigates<self> > > poly_vec_map_type;

  //-------------------------------------------------------------------------
  // constructors and destructor
  //-------------------------------------------------------------------------

  BoolePolynomial();

  explicit BoolePolynomial(constant_type);

  BoolePolynomial(constant_type isOne, const ring_type& ring):
    m_dd(isOne? ring.one(): ring.zero() )  { }

  BoolePolynomial(const dd_type& rhs): m_dd(rhs) {}

  BoolePolynomial(const set_type& rhs): m_dd(rhs.diagram()) {}

  BoolePolynomial(const exp_type&, const ring_type&); 

  BoolePolynomial(const navigator& rhs, const ring_type& ring):
    m_dd(ring.manager().manager(), rhs)  {
    assert(rhs.isValid());
  }

  ~BoolePolynomial() {}

  //-------------------------------------------------------------------------
  // operators and member functions
  //-------------------------------------------------------------------------

  //  self& operator=(const self& rhs) { 
  //  return m_dd = rhs.m_dd;
  // }

  self& operator=(constant_type rhs) { 
    return (*this) = self(rhs);//rhs.generate(*this); 
  }

  const self& operator-() const { return *this; }
  self& operator+=(const self&);
  self& operator+=(constant_type rhs) {

    //return *this = (self(*this) + (rhs).generate(*this));
    if (rhs) (*this) = (*this + ring().one());
     return *this;
  }
  template <class RHSType>
  self& operator-=(const RHSType& rhs) { return operator+=(rhs); }
  self& operator*=(const monom_type&);
  self& operator*=(const exp_type&);
  self& operator*=(const self&);
  self& operator*=(constant_type rhs) {
    if (!rhs) *this = ring().zero();
    return *this;
  }
  self& operator/=(const monom_type&);
  self& operator/=(const exp_type&);
  self& operator/=(const self& rhs);
  self& operator/=(constant_type rhs);
  self& operator%=(const monom_type&);
  self& operator%=(const self& rhs) { 
    return (*this) -= (self(rhs) *= (self(*this) /= rhs)); 
  }
  self& operator%=(constant_type rhs) { return (*this) /= (!rhs); }


  bool_type operator==(const self& rhs) const { return (m_dd == rhs.m_dd); }
  bool_type operator!=(const self& rhs) const { return (m_dd != rhs.m_dd); }
  bool_type operator==(constant_type rhs) const { 
    return ( rhs? isOne(): isZero() );
  }
  bool_type operator!=(constant_type rhs) const {
    return ( rhs? isZero(): isOne() );
  }

  bool_type isZero() const { return m_dd.emptiness(); }

  bool_type isOne() const { return m_dd.blankness(); }

  bool_type isConstant() const { return m_dd.isConstant(); }

  bool_type hasConstantPart() const { return m_dd.ownsOne(); }

  bool_type reducibleBy(const self&) const;

  monom_type lead() const;

  monom_type lexLead() const;

  monom_type boundedLead(size_type bound) const;

  exp_type leadExp() const;

  exp_type boundedLeadExp(size_type bound) const;

  set_type lmDivisors() const { return leadFirst().firstDivisors(); };
  
  hash_type hash() const { return m_dd.hash(); }

  hash_type stableHash() const { return m_dd.stableHash(); } 

  hash_type lmStableHash() const;
  
  size_type deg() const;

  size_type lmDeg() const;

  size_type lexLmDeg() const;

  size_type totalDeg() const;

  size_type lmTotalDeg() const;

  self gradedPart(size_type deg) const;

  size_type nNodes() const;

  size_type nUsedVariables() const;

  monom_type usedVariables() const;

  exp_type usedVariablesExp() const;

  size_type length() const;

  ostream_type& print(ostream_type&) const;

  void prettyPrint() const;

  void prettyPrint(const char* filename) const;

  const_iterator begin() const;

  const_iterator end() const;

  exp_iterator expBegin() const;

  exp_iterator expEnd() const;

  first_iterator firstBegin() const;

  first_iterator firstEnd() const;

  monom_type firstTerm() const;

  deg_iterator degBegin() const;

  deg_iterator degEnd() const;

  ordered_iterator orderedBegin() const; 

  ordered_iterator orderedEnd() const;

  ordered_exp_iterator orderedExpBegin() const; 

  ordered_exp_iterator orderedExpEnd() const;


  lex_iterator genericBegin(lex_tag) const;
  lex_iterator genericEnd(lex_tag) const;
  dlex_iterator genericBegin(dlex_tag) const;
  dlex_iterator genericEnd(dlex_tag) const;
  dp_asc_iterator genericBegin(dp_asc_tag) const;
  dp_asc_iterator genericEnd(dp_asc_tag) const;
  block_dlex_iterator genericBegin(block_dlex_tag) const;
  block_dlex_iterator genericEnd(block_dlex_tag) const;
  block_dp_asc_iterator genericBegin(block_dp_asc_tag) const;
  block_dp_asc_iterator genericEnd(block_dp_asc_tag) const;


  lex_exp_iterator genericExpBegin(lex_tag) const;
  lex_exp_iterator genericExpEnd(lex_tag) const;
  dlex_exp_iterator genericExpBegin(dlex_tag) const;
  dlex_exp_iterator genericExpEnd(dlex_tag) const;
  dp_asc_exp_iterator genericExpBegin(dp_asc_tag) const;
  dp_asc_exp_iterator genericExpEnd(dp_asc_tag) const;
  block_dlex_exp_iterator genericExpBegin(block_dlex_tag) const;
  block_dlex_exp_iterator genericExpEnd(block_dlex_tag) const;
  block_dp_asc_exp_iterator genericExpBegin(block_dp_asc_tag) const;
  block_dp_asc_exp_iterator genericExpEnd(block_dp_asc_tag) const;

  navigator navigation() const { return m_dd.navigation(); }
 
  navigator endOfNavigation() const { return navigator(); }
  
  dd_type copyDiagram(){   return diagram();  }

  operator set_type() const { return set(); };

  size_type eliminationLength() const;
  size_type eliminationLengthWithDegBound(size_type garantied_deg_bound) const;
  void fetchTerms(termlist_type&) const;

  termlist_type terms() const;

  const dd_type& diagram() const { return m_dd; }

  set_type set() const { return m_dd; }

  bool_type isSingleton() const { return dd_is_singleton(navigation()); }

  bool_type isSingletonOrPair() const { 
    return dd_is_singleton_or_pair(navigation()); 
  }

  bool_type isPair() const { return dd_is_pair(navigation()); }

  ring_type ring() const { return ring_type(m_dd.manager()); } 

protected:

  dd_type& internalDiagram() { return m_dd; }

  self leadFirst() const;

  set_type firstDivisors() const;


private:
  dd_type m_dd;
};


inline BoolePolynomial 
operator+(const BoolePolynomial& lhs, const BoolePolynomial& rhs) {

  return BoolePolynomial(lhs) += rhs;
}
inline BoolePolynomial 
operator+(const BoolePolynomial& lhs, BooleConstant rhs) {
  return BoolePolynomial(lhs) +=  (rhs);
  //return BoolePolynomial(lhs) +=  BoolePolynomial(rhs);
}

inline BoolePolynomial 
operator+(BooleConstant lhs, const BoolePolynomial& rhs) {

  return BoolePolynomial(rhs) += (lhs);
}


template <class RHSType>
inline BoolePolynomial 
operator-(const BoolePolynomial& lhs, const RHSType& rhs) {

  return BoolePolynomial(lhs) -= rhs;
}
inline BoolePolynomial 
operator-(const BooleConstant& lhs, const BoolePolynomial& rhs) {

  return -(BoolePolynomial(rhs) -= lhs);
}


#define PBORI_RHS_MULT(type) inline BoolePolynomial \
operator*(const BoolePolynomial& lhs, const type& rhs) { \
    return BoolePolynomial(lhs) *= rhs; }

PBORI_RHS_MULT(BoolePolynomial)
PBORI_RHS_MULT(BooleMonomial)
PBORI_RHS_MULT(BooleExponent)
PBORI_RHS_MULT(BooleConstant)


#undef PBORI_RHS_MULT

#define PBORI_LHS_MULT(type)  inline BoolePolynomial \
operator*(const type& lhs, const BoolePolynomial& rhs) { return rhs * lhs; }

PBORI_LHS_MULT(BooleMonomial)
PBORI_LHS_MULT(BooleExponent)
PBORI_LHS_MULT(BooleConstant)

#undef PBORI_LHS_MULT


template <class RHSType>
inline BoolePolynomial
operator/(const BoolePolynomial& lhs, const RHSType& rhs){
  return BoolePolynomial(lhs) /= rhs;
}

template <class RHSType>
inline BoolePolynomial
operator%(const BoolePolynomial& lhs, const RHSType& rhs){

  return BoolePolynomial(lhs) %= rhs;
}

inline BoolePolynomial::bool_type
operator==(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {

  return (rhs == lhs); 
}

inline BoolePolynomial::bool_type
operator!=(BoolePolynomial::bool_type lhs, const BoolePolynomial& rhs) {

  return (rhs != lhs); 
}

BoolePolynomial::ostream_type& 
operator<<(BoolePolynomial::ostream_type&, const BoolePolynomial&);

// tests whether polynomial can be reduced by rhs
inline BoolePolynomial::bool_type
BoolePolynomial::reducibleBy(const self& rhs) const {

  PBORI_TRACE_FUNC( "BoolePolynomial::reducibleBy(const self&) const" );

  if( rhs.isOne() )
    return true;

  if( isZero() )
    return rhs.isZero();

  return std::includes(firstBegin(), firstEnd(), 
                       rhs.firstBegin(), rhs.firstEnd());

}


END_NAMESPACE_PBORI

#endif // of BoolePolynomial_h_

---