Go to the documentation of this file.00001
00002
00117
00118
00119
00120 #include "pbori_defs.h"
00121
00122
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) {
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) {
00157 if (second < first)
00158 std::swap(first, second);
00159
00160 typename OrderType::block_iterator upper(order.blockBegin());
00161 while (first >= *upper)
00162 ++upper;
00163 return (second < *upper);
00164 }
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
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
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
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
00499
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