PolyBoRi
|
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