00001
00002
00114
00115
00116
00117 #include "pbori_defs.h"
00118
00119
00120 #include "CDDManager.h"
00121
00122 #include "BoolePolynomial.h"
00123
00124 #include "BooleMonomial.h"
00125
00126 #include "BooleExponent.h"
00127
00128 #include "COrderProperties.h"
00129 #include "CVariableNames.h"
00130
00131 #include "CGenericIter.h"
00132
00133
00134 #include <vector>
00135 #ifndef OrderedManager_h_
00136 #define OrderedManager_h_
00137
00138 #include "COrderedIter.h"
00139
00140 BEGIN_NAMESPACE_PBORI
00141
00142 template <class IdxType, class OrderType>
00143 bool
00144 lie_in_same_block(IdxType, IdxType, const OrderType&,
00145 invalid_tag) {
00146 return true;
00147 }
00148
00149
00150 template <class IdxType, class OrderType>
00151 bool
00152 lie_in_same_block(IdxType first, IdxType second, const OrderType& order,
00153 valid_tag) {
00154 if (second < first)
00155 std::swap(first, second);
00156
00157 typename OrderType::block_iterator upper(order.blockBegin());
00158 while (first >= *upper)
00159 ++upper;
00160 return (second < *upper);
00161 }
00162
00163
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
00238 class CDynamicOrderBase {
00239
00240 public:
00241
00243 typedef CDynamicOrderBase self;
00244
00246
00247 typedef CTypes::bool_type bool_type;
00248 typedef CTypes::size_type size_type;
00249 typedef CTypes::idx_type idx_type;
00250 typedef CTypes::comp_type comp_type;
00251 typedef CTypes::ordercode_type ordercode_type;
00252 typedef BoolePolynomial poly_type;
00253 typedef poly_type::monom_type monom_type;
00254 typedef poly_type::navigator navigator;
00255 typedef poly_type::exp_type exp_type;
00256
00257
00258 typedef COrderedIter<navigator, monom_type> ordered_iterator;
00259 typedef COrderedIter<navigator, exp_type> ordered_exp_iterator;
00261
00263 typedef std::vector<idx_type> block_idx_type;
00264
00266 typedef block_idx_type::const_iterator block_iterator;
00267
00268
00270 CDynamicOrderBase() { }
00271
00272
00273 virtual ~CDynamicOrderBase() { }
00274
00276 virtual comp_type compare(idx_type, idx_type) const = 0;
00277
00278 virtual comp_type compare(const monom_type&, const monom_type&) const = 0;
00279
00280 virtual comp_type compare(const exp_type&, const exp_type&) const = 0;
00281
00283 virtual monom_type lead(const poly_type&) const = 0;
00284
00286 virtual monom_type lead(const poly_type&, size_type) const = 0;
00287
00289 virtual exp_type leadExp(const poly_type&) const = 0;
00290
00292 virtual exp_type leadExp(const poly_type&, size_type) const = 0;
00293
00295 virtual poly_type leadFirst(const poly_type&) const = 0;
00296
00298 virtual bool_type isLexicographical() const = 0;
00299
00301 virtual bool_type orderedStandardIteration() const = 0;
00302
00304 virtual bool_type isSymmetric() const = 0;
00305
00307 virtual bool_type isDegreeOrder() const = 0;
00308
00310 virtual bool_type isBlockOrder() const = 0;
00311
00313 virtual bool_type isTotalDegreeOrder() const = 0;
00314
00316 virtual bool_type ascendingVariables() const = 0;
00317
00319 virtual bool_type descendingVariables() const = 0;
00320
00322 virtual bool_type isDegreeReverseLexicograpical() const = 0;
00323
00325 virtual ordered_iterator leadIteratorBegin(const poly_type&) const = 0;
00326
00327 virtual ordered_iterator leadIteratorEnd() const = 0;
00328 virtual ordered_exp_iterator leadExpIteratorBegin(const poly_type&) const = 0;
00329
00330 virtual ordered_exp_iterator leadExpIteratorEnd() const = 0;
00331
00333 virtual ordercode_type getOrderCode() const = 0;
00334
00336 virtual ordercode_type getBaseOrderCode() const = 0 ;
00337
00339
00340 virtual block_iterator blockBegin() const = 0;
00341 virtual block_iterator blockEnd() const = 0;
00342 virtual void appendBlock(idx_type) = 0;
00343 virtual void clearBlocks() = 0;
00345
00348 virtual bool_type lieInSameBlock(idx_type, idx_type) const = 0;
00349
00350 };
00351
00358 template <class OrderType>
00359 class CDynamicOrder:
00360 public CDynamicOrderBase {
00361
00362 public:
00363
00364
00366 typedef OrderType order_type;
00367
00369 typedef CDynamicOrderBase base;
00370
00372 typedef CDynamicOrder<order_type> self;
00373
00375 typedef COrderProperties<order_type> properties_type;
00376
00378
00379 typedef typename base::bool_type bool_type;
00380 typedef typename base::size_type size_type;
00381 typedef typename base::idx_type idx_type;
00382 typedef typename base::comp_type comp_type;
00383 typedef typename base::monom_type monom_type;
00384 typedef typename base::poly_type poly_type;
00385 typedef typename base::exp_type exp_type;
00386 typedef typename base::ordered_iterator ordered_iterator;
00387 typedef typename base::ordered_exp_iterator ordered_exp_iterator;
00388 typedef typename base::ordercode_type ordercode_type;
00389 typedef typename base::block_iterator block_iterator;
00391
00393 CDynamicOrder( const order_type& theOrder = order_type() ):
00394 ordering(theOrder) { }
00395
00397 CDynamicOrder(const self& rhs):
00398 ordering(rhs.ordering) { }
00399
00400
00401 ~CDynamicOrder() { }
00402
00404 comp_type compare(idx_type lhs, idx_type rhs) const {
00405 return ordering.compare(lhs, rhs);
00406 }
00407
00409 comp_type compare(const monom_type& lhs, const monom_type& rhs) const {
00410 return ordering.compare(lhs, rhs);
00411 }
00412
00413 comp_type compare(const exp_type& lhs, const exp_type& rhs) const {
00414 return ordering.compare(lhs, rhs);
00415 }
00416
00418 monom_type lead(const poly_type& rhs) const {
00419
00420 return ordering.lead(rhs);
00421 }
00423 monom_type lead(const poly_type& rhs, size_type bound) const {
00424
00425 return ordering.lead(rhs, bound);
00426 }
00427
00429 exp_type leadExp(const poly_type& rhs) const {
00430
00431 return ordering.leadExp(rhs);
00432 }
00433
00435 exp_type leadExp(const poly_type& rhs, size_type bound) const {
00436
00437 return ordering.leadExp(rhs, bound);
00438 }
00439
00441 poly_type leadFirst(const poly_type& poly) const {
00442
00443 if(orderedStandardIteration())
00444 return poly;
00445 else
00446 return lead(poly);
00447 }
00448
00450 bool_type isLexicographical() const {
00451 return properties_type().isLexicographical();
00452 }
00453
00455 bool_type orderedStandardIteration() const {
00456 return properties_type().orderedStandardIteration();
00457 }
00458
00460 bool_type isSymmetric() const {
00461 return properties_type().isSymmetric();
00462 }
00463
00465 bool_type isDegreeOrder() const {
00466 return properties_type().isDegreeOrder();
00467 }
00468
00470 bool_type isBlockOrder() const {
00471 return properties_type().isBlockOrder();
00472 }
00473
00475 bool_type isTotalDegreeOrder() const {
00476 return properties_type().isTotalDegreeOrder();
00477 }
00478
00480 bool_type isDegreeReverseLexicograpical() const {
00481 return properties_type().isDegreeReverseLexicograpical();
00482 }
00483
00485 bool_type ascendingVariables() const {
00486 return properties_type().ascendingVariables();
00487 }
00488
00490 bool_type descendingVariables() const {
00491 return properties_type().descendingVariables();
00492 }
00493
00495
00496
00497
00499 ordered_iterator leadIteratorBegin(const poly_type& poly) const {
00500 return ordering.leadIteratorBegin(poly);
00501 }
00502
00503 ordered_iterator leadIteratorEnd() const {
00504 return ordering.leadIteratorEnd();
00505 }
00507 ordered_exp_iterator leadExpIteratorBegin(const poly_type& poly) const {
00508 return ordering.leadExpIteratorBegin(poly);
00509 }
00510
00511 ordered_exp_iterator leadExpIteratorEnd() const {
00512 return ordering.leadExpIteratorEnd();
00513 }
00514
00516 ordercode_type getOrderCode() const {
00517 return order_type::order_code;
00518 }
00519
00521 ordercode_type getBaseOrderCode() const {
00522 return order_type::baseorder_code;
00523 }
00524
00526
00527 block_iterator blockBegin() const { return ordering.blockBegin(); }
00528 block_iterator blockEnd() const { return ordering.blockEnd(); }
00529 void appendBlock(idx_type idx) { ordering.appendBlock(idx); }
00530 void clearBlocks() { ordering.clearBlocks(); }
00532
00535 bool_type lieInSameBlock(idx_type first, idx_type second) const {
00536 return lie_in_same_block(first, second, *this,
00537 typename properties_type::blockorder_property());
00538 }
00539
00540 protected:
00541 order_type ordering;
00542 };
00543
00544 END_NAMESPACE_PBORI
00545
00546 #endif