• Main Page
  • Related Pages
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

OrderedManager.h

Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //*****************************************************************************
00117 //*****************************************************************************
00118 
00119 // include basic definitions
00120 #include "pbori_defs.h"
00121 
00122 // get decision diagram manager interface
00123 #include "CDDManager.h"
00124 
00125 #include "BoolePolynomial.h"
00126 
00127 #include "BooleMonomial.h"
00128 
00129 #include "BooleExponent.h"
00130 
00131 #include "COrderProperties.h"
00132 #include "CVariableNames.h"
00133 
00134 #include "CGenericIter.h"
00135 
00136 
00137 #include <vector>
00138 #ifndef OrderedManager_h_
00139 #define OrderedManager_h_
00140 
00141 #include "COrderedIter.h"
00142 
00143 BEGIN_NAMESPACE_PBORI
00144 
00145 template <class IdxType, class OrderType>
00146 bool
00147 lie_in_same_block(IdxType, IdxType, const OrderType&,
00148                   invalid_tag) { // not a block order 
00149   return true;
00150 }
00151 
00152 
00153 template <class IdxType, class OrderType>
00154 bool
00155 lie_in_same_block(IdxType first, IdxType second, const OrderType& order,
00156                   valid_tag) { // is block order 
00157   if (second < first)
00158     std::swap(first, second);
00159   
00160   typename OrderType::block_iterator upper(order.blockBegin());
00161   while (first >= *upper)    // Note: convention, last element is max_idx
00162      ++upper;
00163   return (second < *upper);
00164 }
00165 
00166 
00167 
00168 // template <class ManType>
00169 // class CNamedManager:
00170 //   public CDDManager<ManType> { 
00171 
00172 // public:
00173 
00174 //   /// Variable manager type
00175 //   typedef ManType manager_type;
00176 
00177 //   /// Variable manager interface (base type)
00178 //   typedef CDDManager<manager_type> base;
00179 
00180 //   /// Type of *this
00181 //   typedef CNamedManager<manager_type> self;
00182 
00183 //   /// @name adopt global type definitions
00184 //   //@{
00185 //   typedef CTypes::bool_type bool_type;
00186 //   typedef CTypes::dd_type dd_type;
00187 //   typedef CTypes::size_type size_type;
00188 //   typedef CTypes::idx_type idx_type;
00189 //   typedef CTypes::comp_type comp_type;
00190 //   typedef CTypes::ordercode_type ordercode_type;
00191 //   typedef BooleMonomial monom_type;
00192 //   typedef BoolePolynomial poly_type;
00193 //   typedef BoolePolynomial::navigator navigator;
00194 //   typedef BooleExponent exp_type;
00195 //   //@}
00196 
00197 //   /// Define type for storing names of variables
00198 //   typedef CVariableNames variable_names_type;
00199 
00200 //   /// Define type for getting names of variables
00201 //   typedef variable_names_type::const_reference const_varname_reference;
00202 
00203 //   /// Construct new decision diagramm manager
00204 //   CNamedManager(size_type nvars = 0): 
00205 //     base(nvars)  { }
00206 
00207 //   /// Construct old decision diagramm manager
00208 //   CNamedManager(const base& rhs): 
00209 //     base(rhs) { }
00210 
00211 
00212 //   /// Construct new decision diagramm manager
00213 //   CNamedManager(const self& rhs): 
00214 //     base(rhs) { }
00215 
00216 //   // Destructor
00217 //   ~CNamedManager() { }
00218 
00219 //   /// Set name of variable with index idx
00220 //   void setVariableName(idx_type idx, const_varname_reference varname) {
00221 //     base::manager().names().set(idx, varname);
00222 //   }
00223 
00224 //   /// Get name of variable with index idx
00225 //   const_varname_reference getVariableName(idx_type idx) const { 
00226 //     return base::manager().names()[idx];
00227 //   }
00228 
00229 // private:
00230 //   /// Stores names of variables
00231 //   //variable_names_type m_names;
00232 // };
00233 
00234 
00241 class CDynamicOrderBase { 
00242 
00243 public:
00244 
00246   typedef CDynamicOrderBase self;
00247 
00249 
00250   typedef CTypes::bool_type bool_type;
00251   typedef CTypes::size_type size_type;
00252   typedef CTypes::idx_type idx_type;
00253   typedef CTypes::comp_type comp_type;
00254   typedef CTypes::ordercode_type ordercode_type;
00255   typedef BoolePolynomial poly_type;
00256   typedef poly_type::monom_type monom_type;
00257   typedef poly_type::navigator navigator;
00258   typedef poly_type::exp_type exp_type;
00259 
00260 
00261   typedef COrderedIter<navigator, monom_type> ordered_iterator;
00262   typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
00264 
00266   typedef std::vector<idx_type> block_idx_type;
00267 
00269   typedef block_idx_type::const_iterator block_iterator;
00270 
00271 
00273   CDynamicOrderBase() { }
00274 
00275   // Destructor
00276   virtual ~CDynamicOrderBase() { }
00277 
00279   virtual comp_type compare(idx_type, idx_type) const = 0;
00280 
00281   virtual comp_type compare(const monom_type&, const monom_type&) const = 0;
00282 
00283   virtual comp_type compare(const exp_type&, const exp_type&) const = 0;
00284 
00286   virtual monom_type lead(const poly_type&) const = 0;
00287 
00289   virtual monom_type lead(const poly_type&, size_type) const = 0;
00290 
00292   virtual exp_type leadExp(const poly_type&) const = 0;
00293 
00295   virtual exp_type leadExp(const poly_type&, size_type) const = 0;
00296 
00298   virtual poly_type leadFirst(const poly_type&) const = 0;
00299 
00301   virtual bool_type isLexicographical() const = 0;
00302 
00304   virtual bool_type orderedStandardIteration() const = 0;
00305 
00307   virtual bool_type isSymmetric() const = 0;
00308 
00310   virtual bool_type isDegreeOrder() const = 0;
00311 
00313   virtual bool_type isBlockOrder() const = 0;
00314 
00316   virtual bool_type isTotalDegreeOrder() const = 0;
00317 
00319   virtual bool_type ascendingVariables() const = 0;
00320 
00322   virtual bool_type descendingVariables() const = 0;
00323 
00325   virtual bool_type isDegreeReverseLexicograpical() const = 0;
00326 
00328   virtual ordered_iterator leadIteratorBegin(const poly_type&) const = 0;
00329 
00330   virtual ordered_iterator leadIteratorEnd() const = 0;
00331   virtual ordered_exp_iterator leadExpIteratorBegin(const poly_type&) const = 0;
00332 
00333   virtual ordered_exp_iterator leadExpIteratorEnd() const = 0;
00334 
00336   virtual ordercode_type getOrderCode() const = 0;
00337 
00339   virtual ordercode_type getBaseOrderCode() const = 0 ;
00340 
00342 
00343   virtual block_iterator blockBegin() const = 0;
00344   virtual block_iterator blockEnd() const = 0;
00345   virtual void appendBlock(idx_type) = 0;
00346   virtual void clearBlocks() = 0;
00348 
00351   virtual bool_type lieInSameBlock(idx_type, idx_type) const = 0;
00352 
00353 };
00354 
00361 template <class OrderType>
00362 class CDynamicOrder:
00363   public CDynamicOrderBase { 
00364 
00365 public:
00366 
00367 
00369   typedef OrderType order_type;
00370 
00372   typedef CDynamicOrderBase base;
00373 
00375   typedef CDynamicOrder<order_type> self;
00376 
00378   typedef COrderProperties<order_type> properties_type;
00379 
00381 
00382   typedef typename base::bool_type bool_type;
00383   typedef typename base::size_type size_type;
00384   typedef typename base::idx_type idx_type;
00385   typedef typename base::comp_type comp_type;
00386   typedef typename base::monom_type monom_type;
00387   typedef typename base::poly_type poly_type;
00388   typedef typename base::exp_type exp_type;
00389   typedef typename base::ordered_iterator ordered_iterator;
00390   typedef typename base::ordered_exp_iterator ordered_exp_iterator;
00391   typedef typename base::ordercode_type ordercode_type;
00392   typedef typename base::block_iterator block_iterator;
00394 
00396   CDynamicOrder( const order_type& theOrder = order_type() ): 
00397     ordering(theOrder) { }
00398   
00400   CDynamicOrder(const self& rhs): 
00401     ordering(rhs.ordering) { }
00402 
00403   // Destructor
00404   ~CDynamicOrder() { }
00405 
00407   comp_type compare(idx_type lhs, idx_type rhs) const {
00408     return ordering.compare(lhs, rhs);
00409   }
00410 
00412   comp_type compare(const monom_type& lhs, const monom_type& rhs) const {
00413     return ordering.compare(lhs, rhs);
00414   }
00415 
00416   comp_type compare(const exp_type& lhs, const exp_type& rhs) const {
00417     return ordering.compare(lhs, rhs);
00418   }
00419 
00421   monom_type lead(const poly_type& rhs) const {
00422 
00423     return ordering.lead(rhs);
00424   }
00426   monom_type lead(const poly_type& rhs, size_type bound) const {
00427 
00428     return ordering.lead(rhs, bound);
00429   }
00430 
00432   exp_type leadExp(const poly_type& rhs) const {
00433 
00434     return ordering.leadExp(rhs);
00435   }
00436 
00438   exp_type leadExp(const poly_type& rhs, size_type bound) const {
00439 
00440     return ordering.leadExp(rhs, bound);
00441   }
00442 
00444   poly_type leadFirst(const poly_type& poly) const {
00445 
00446     if(orderedStandardIteration())
00447       return poly;
00448     else 
00449       return lead(poly);
00450   }
00451 
00453   bool_type isLexicographical() const {
00454     return properties_type().isLexicographical();
00455   }
00456 
00458   bool_type orderedStandardIteration() const {
00459     return properties_type().orderedStandardIteration();
00460   }
00461 
00463   bool_type isSymmetric() const {
00464     return properties_type().isSymmetric();
00465   }
00466 
00468   bool_type isDegreeOrder() const {
00469     return properties_type().isDegreeOrder();
00470   }
00471 
00473   bool_type isBlockOrder() const {
00474     return properties_type().isBlockOrder();
00475   }
00476 
00478   bool_type isTotalDegreeOrder() const {
00479     return properties_type().isTotalDegreeOrder();
00480   }
00481 
00483   bool_type isDegreeReverseLexicograpical() const {
00484     return properties_type().isDegreeReverseLexicograpical();
00485   }
00486 
00488   bool_type ascendingVariables() const {
00489     return properties_type().ascendingVariables();
00490   }
00491 
00493   bool_type descendingVariables() const {
00494     return properties_type().descendingVariables();
00495   }
00496 
00498   //  iterator leadIterator(const poly_type& poly) const {
00499   //    return ordering.leadIterator(poly);
00500   //  }
00502   ordered_iterator leadIteratorBegin(const poly_type& poly) const {
00503     return ordering.leadIteratorBegin(poly);
00504   }
00505 
00506   ordered_iterator leadIteratorEnd() const {
00507     return ordering.leadIteratorEnd();
00508   }
00510   ordered_exp_iterator leadExpIteratorBegin(const poly_type& poly) const {
00511     return ordering.leadExpIteratorBegin(poly);
00512   }
00513 
00514   ordered_exp_iterator leadExpIteratorEnd() const {
00515     return ordering.leadExpIteratorEnd();
00516   }
00517 
00519   ordercode_type getOrderCode() const {
00520     return order_type::order_code;
00521   }
00522 
00524   ordercode_type getBaseOrderCode() const {
00525     return order_type::baseorder_code;
00526   }
00527 
00529 
00530   block_iterator blockBegin() const { return ordering.blockBegin(); }
00531   block_iterator blockEnd() const { return ordering.blockEnd();  }
00532   void appendBlock(idx_type idx) { ordering.appendBlock(idx); }
00533   void clearBlocks() { ordering.clearBlocks();  }
00535 
00538   bool_type lieInSameBlock(idx_type first, idx_type second) const {
00539     return lie_in_same_block(first, second, *this,
00540                              typename properties_type::blockorder_property());
00541   }
00542 
00543 protected:
00544   order_type ordering;
00545 };
00546 
00547 END_NAMESPACE_PBORI
00548 
00549 #endif

Generated on Thu Feb 10 2011 for PolyBoRi by  doxygen 1.7.1