PolyBoRi
|
00001 // -*- c++ -*- 00002 //***************************************************************************** 00014 //***************************************************************************** 00015 00016 #ifndef polybori_routines_pbori_routines_order_h_ 00017 #define polybori_routines_pbori_routines_order_h_ 00018 00019 // include basic definitions 00020 #include <polybori/pbori_defs.h> 00021 #include "pbori_algo.h" 00022 #include <polybori/common/traits.h> 00023 00024 00025 BEGIN_NAMESPACE_PBORI 00026 00027 template <class FirstIterator, class SecondIterator, class BinaryPredicate> 00028 CTypes::comp_type 00029 lex_compare_3way(FirstIterator start, FirstIterator finish, 00030 SecondIterator rhs_start, SecondIterator rhs_finish, 00031 BinaryPredicate idx_comp) { 00032 00033 while ( (start != finish) && (rhs_start != rhs_finish) && 00034 (*start == *rhs_start) ) { 00035 ++start; ++rhs_start; 00036 } 00037 00038 if (start == finish) { 00039 if (rhs_start == rhs_finish) 00040 return CTypes::equality; 00041 00042 return CTypes::less_than; 00043 } 00044 00045 if (rhs_start == rhs_finish) 00046 return CTypes::greater_than; 00047 00048 return (idx_comp(*start, *rhs_start)? 00049 CTypes::greater_than: CTypes::less_than); 00050 } 00051 00052 00054 template <class LhsType, class RhsType, class BinaryPredicate> 00055 CTypes::comp_type 00056 lex_compare(const LhsType& lhs, const RhsType& rhs, 00057 BinaryPredicate idx_comp, valid_tag has_easy_equality_test) { 00058 00059 if (lhs == rhs) 00060 return CTypes::equality; 00061 00062 return lex_compare_3way(lhs.begin(), lhs.end(), 00063 rhs.begin(), rhs.end(), idx_comp); 00064 //typedef lex_compare_predicate<LhsType, RhsType, BinaryPredicate> comp_type; 00065 //return generic_compare_3way(lhs, rhs, comp_type(idx_comp)); 00066 } 00067 00068 00070 template <class LhsType, class RhsType, class BinaryPredicate> 00071 CTypes::comp_type 00072 lex_compare(const LhsType& lhs, const RhsType& rhs, 00073 BinaryPredicate idx_comp, invalid_tag has_no_easy_equality_test) { 00074 00075 return lex_compare_3way(lhs.begin(), lhs.end(), 00076 rhs.begin(), rhs.end(), idx_comp); 00077 } 00078 00080 template <class LhsType, class RhsType, class BinaryPredicate> 00081 CTypes::comp_type 00082 lex_compare(const LhsType& lhs, const RhsType& rhs, BinaryPredicate idx_comp) { 00083 00084 typedef typename pbori_binary_traits<LhsType, RhsType>::easy_equality_property 00085 equality_property; 00086 00087 return lex_compare(lhs, rhs, idx_comp, equality_property()); 00088 } 00089 00091 template<class LhsType, class RhsType, class BinaryPredicate> 00092 CTypes::comp_type 00093 deg_lex_compare(const LhsType& lhs, const RhsType& rhs, 00094 BinaryPredicate idx_comp) { 00095 00096 typedef typename LhsType::size_type size_type; 00097 CTypes::comp_type result = generic_compare_3way( lhs.size(), rhs.size(), 00098 std::greater<size_type>() ); 00099 00100 return (result == CTypes::equality? lex_compare(lhs, rhs, idx_comp): result); 00101 } 00102 00103 00104 template <class OrderType, class Iterator> 00105 class generic_iteration; 00106 00107 template<class DummyType> 00108 class dummy_data_type { 00109 public: 00110 dummy_data_type(const DummyType&) {} 00111 dummy_data_type(DummyType&) {} 00112 dummy_data_type() {} 00113 }; 00114 00116 template <class StackType, class Iterator> 00117 void dummy_append(StackType& stack, Iterator start, Iterator finish) { 00118 00119 while (start != finish) { 00120 stack.push(*start); 00121 ++start; 00122 } 00123 } 00124 00125 template<class NaviType, class DescendingProperty = valid_tag> 00126 class bounded_restricted_term { 00127 public: 00128 typedef NaviType navigator; 00129 typedef DescendingProperty descending_property; 00130 typedef bounded_restricted_term<navigator, descending_property> self; 00131 typedef std::vector<navigator> stack_type; 00132 typedef unsigned size_type; 00133 typedef unsigned idx_type; 00134 00135 bounded_restricted_term (): 00136 m_stack(), m_max_idx(0), m_upperbound(0), m_next() {} 00137 00138 is_same_type<descending_property, valid_tag> descendingVariables; 00139 00140 bounded_restricted_term (navigator navi, size_type upperbound, 00141 idx_type max_idx): 00142 m_stack(), m_upperbound(upperbound), m_max_idx(max_idx), m_next(navi) { 00143 00144 m_stack.reserve(upperbound); 00145 00146 followThen(); 00147 00148 while (!is_path_end() && !empty() ) 00149 increment(); 00150 } 00151 00152 size_type operator*() const { 00153 return m_stack.size(); 00154 } 00155 00156 const navigator& next() const { 00157 return m_next; 00158 } 00159 00160 typename stack_type::const_iterator begin() const { 00161 return m_stack.begin(); 00162 } 00163 00164 typename stack_type::const_iterator end() const { 00165 return m_stack.end(); 00166 } 00167 00168 self& operator++() { 00169 PBORI_ASSERT(!empty()); 00170 00171 // if upperbound was already found we're done 00172 // (should be optimized away for ascending variables) 00173 if (descendingVariables() && (m_stack.size() == m_upperbound) ) 00174 return *this = self(); 00175 00176 do { 00177 increment(); 00178 } while (!empty() && !is_path_end()); 00179 00180 return *this; 00181 } 00182 00183 void print() const { 00184 00185 typename stack_type::const_iterator start(m_stack.begin()), 00186 finish(m_stack.end()); 00187 00188 std::cout <<'('; 00189 while (start != finish) { 00190 std::cout << *(*start) << ", " ; 00191 ++start; 00192 } 00193 std::cout <<')'; 00194 00195 } 00196 00197 bool operator==(const self& rhs) const { 00198 if (rhs.empty()) 00199 return empty(); 00200 if (empty()) 00201 return rhs.empty(); 00202 00203 else (m_stack == rhs.m_stack); 00204 } 00205 bool operator!=(const self& rhs) const { 00206 return !(*this == rhs); 00207 } 00208 protected: 00209 00210 void followThen() { 00211 while (within_degree() && !at_end()) 00212 nextThen(); 00213 } 00214 00215 void increment() { 00216 PBORI_ASSERT(!empty()); 00217 00218 m_next = top(); 00219 m_next.incrementElse(); 00220 m_stack.pop_back(); 00221 00222 followThen(); 00223 00224 } 00225 00226 bool empty() const{ 00227 return m_stack.empty(); 00228 } 00229 00230 navigator top() const{ 00231 return m_stack.back(); 00232 } 00233 00234 bool is_path_end() { 00235 00236 path_end(); 00237 return (!m_next.isConstant() && (*m_next >= m_max_idx)) || 00238 m_next.terminalValue(); 00239 } 00240 00241 void path_end() { 00242 while (!at_end()) { 00243 m_next.incrementElse(); 00244 } 00245 } 00246 00247 void nextThen() { 00248 PBORI_ASSERT(!m_next.isConstant()); 00249 m_stack.push_back(m_next); 00250 m_next.incrementThen(); 00251 } 00252 00253 00254 00255 bool within_degree() const { 00256 00257 return (*(*this) < m_upperbound); 00258 } 00259 00260 bool at_end() const { 00261 00262 return m_next.isConstant() || (*m_next >= m_max_idx); 00263 } 00264 00265 private: 00266 stack_type m_stack; 00267 idx_type m_max_idx; 00268 size_type m_upperbound; 00269 navigator m_next; 00270 }; 00271 00272 00273 00276 template <class DegreeCacher, class NaviType, class IdxType> 00277 typename NaviType::deg_type 00278 dd_cached_block_degree(const DegreeCacher& cache, NaviType navi, 00279 IdxType nextBlock) { 00280 00281 typedef typename NaviType::deg_type deg_type; 00282 00283 if( navi.isConstant() || (*navi >= nextBlock) ) // end of block reached 00284 return 0; 00285 00286 // Look whether result was cached before 00287 typename DegreeCacher::node_type result = cache.find(navi, nextBlock); 00288 if (result.isValid()) 00289 return *result; 00290 00291 // Get degree of then branch (contains at least one valid path)... 00292 deg_type deg = dd_cached_block_degree(cache, navi.thenBranch(), nextBlock) + 1; 00293 00294 // ... combine with degree of else branch 00295 deg = std::max(deg, dd_cached_block_degree(cache, navi.elseBranch(), nextBlock) ); 00296 00297 // Write result to cache 00298 cache.insert(navi, nextBlock, deg); 00299 00300 return deg; 00301 } 00302 00303 00304 template<class DegCacheMgr, class NaviType, class IdxType, class SizeType> 00305 bool max_block_degree_on_then(const DegCacheMgr& deg_mgr, NaviType navi, 00306 IdxType next_block, 00307 SizeType degree, valid_tag is_descending) { 00308 navi.incrementThen(); 00309 return ((dd_cached_block_degree(deg_mgr, navi, next_block/*,degree - 1*/) + 1) == degree); 00310 } 00311 00312 template<class DegCacheMgr, class NaviType, class IdxType, class SizeType> 00313 bool max_block_degree_on_then(const DegCacheMgr& deg_mgr, NaviType navi, 00314 IdxType next_block, 00315 SizeType degree, invalid_tag non_descending) { 00316 navi.incrementElse(); 00317 return (dd_cached_block_degree(deg_mgr, navi, next_block/*, degree*/) != degree); 00318 } 00319 00320 00321 // with degree bound 00322 template <class CacheType, class DegCacheMgr, class NaviType, 00323 class TermType, class Iterator, class SizeType, class DescendingProperty> 00324 TermType 00325 dd_block_degree_lead(const CacheType& cache_mgr, 00326 const DegCacheMgr& deg_mgr, 00327 NaviType navi, Iterator block_iter, 00328 TermType init, SizeType degree, 00329 DescendingProperty prop) { 00330 00331 if (navi.isConstant()) 00332 return cache_mgr.generate(navi); 00333 00334 while( (*navi >= *block_iter) && (*block_iter != CUDD_MAXINDEX)) { 00335 ++block_iter; 00336 degree = dd_cached_block_degree(deg_mgr, navi, *block_iter); 00337 } 00338 00339 00340 // Check cache for previous results - Wrong in general, bounds may have changed! 00341 // NaviType cached = cache_mgr.find(navi); 00342 // if (cached.isValid()) 00343 // return cache_mgr.generate(cached); 00344 00345 // Go to next branch 00346 if ( max_block_degree_on_then(deg_mgr, navi, *block_iter, degree, prop) ) { 00347 init = dd_block_degree_lead(cache_mgr, deg_mgr, navi.thenBranch(), 00348 block_iter, 00349 init, degree - 1, prop).change(*navi); 00350 } 00351 else { 00352 init = dd_block_degree_lead(cache_mgr, deg_mgr, navi.elseBranch(), 00353 block_iter, 00354 init, degree, prop); 00355 } 00356 00357 NaviType resultNavi(init.navigation()); 00358 // cache_mgr.insert(navi, resultNavi); 00359 deg_mgr.insert(resultNavi, *block_iter, degree); 00360 00361 return init; 00362 } 00363 00364 00365 template <class CacheType, class DegCacheMgr, class NaviType, class Iterator, 00366 class TermType, class DescendingProperty> 00367 TermType 00368 dd_block_degree_lead(const CacheType& cache_mgr, const DegCacheMgr& deg_mgr, 00369 NaviType navi, Iterator block_iter, TermType init, 00370 DescendingProperty prop){ 00371 00372 if (navi.isConstant()) 00373 return cache_mgr.generate(navi); 00374 00375 return dd_block_degree_lead(cache_mgr, deg_mgr, navi,block_iter, init, 00376 dd_cached_block_degree(deg_mgr, navi, 00377 *block_iter), prop); 00378 } 00379 00380 00381 template <class FirstIterator, class SecondIterator, class IdxType, 00382 class BinaryPredicate> 00383 CTypes::comp_type 00384 restricted_lex_compare_3way(FirstIterator start, FirstIterator finish, 00385 SecondIterator rhs_start, SecondIterator rhs_finish, 00386 IdxType max_index, 00387 BinaryPredicate idx_comp) { 00388 00389 while ( (start != finish) && (*start < max_index) && (rhs_start != rhs_finish) 00390 && (*rhs_start < max_index) && (*start == *rhs_start) ) { 00391 ++start; ++rhs_start; 00392 } 00393 00394 if ( (start == finish) || (*start >= max_index) ) { 00395 if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) ) 00396 return CTypes::equality; 00397 00398 return CTypes::less_than; 00399 } 00400 00401 if ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) ) 00402 return CTypes::greater_than; 00403 00404 return (idx_comp(*start, *rhs_start)? 00405 CTypes::greater_than: CTypes::less_than); 00406 } 00407 00408 00409 00410 00411 template<class LhsIterator, class RhsIterator, class Iterator, 00412 class BinaryPredicate> 00413 CTypes::comp_type 00414 block_dlex_compare(LhsIterator lhsStart, LhsIterator lhsFinish, 00415 RhsIterator rhsStart, RhsIterator rhsFinish, 00416 Iterator start, Iterator finish, 00417 BinaryPredicate idx_comp) { 00418 00419 // unsigned lhsdeg = 0, rhsdeg = 0; 00420 00421 00422 CTypes::comp_type result = CTypes::equality; 00423 00424 while ( (start != finish) && (result == CTypes::equality) ) { 00425 CTypes::deg_type lhsdeg = 0, rhsdeg = 0; 00426 LhsIterator oldLhs(lhsStart); // maybe one can save this and do both 00427 RhsIterator oldRhs(rhsStart); // comparisons at once. 00428 00429 // maybe one can save 00430 while( (lhsStart != lhsFinish) && (*lhsStart < *start) ) { 00431 ++lhsStart; ++lhsdeg; 00432 } 00433 while( (rhsStart != rhsFinish) && (*rhsStart < *start) ) { 00434 ++rhsStart; ++rhsdeg; 00435 } 00436 result = generic_compare_3way(lhsdeg, rhsdeg, 00437 std::greater<unsigned>() ); 00438 00439 if (result == CTypes::equality) { 00440 result = restricted_lex_compare_3way(oldLhs, lhsFinish, 00441 oldRhs, rhsFinish, *start, idx_comp); 00442 } 00443 00444 ++start; 00445 } 00446 00447 return result; 00448 } 00449 00450 00452 template <class IdxType, class Iterator, class BinaryPredicate> 00453 CTypes::comp_type 00454 block_deg_lex_idx_compare(IdxType lhs, IdxType rhs, 00455 Iterator start, Iterator finish, 00456 BinaryPredicate idx_comp) { 00457 00458 if (lhs == rhs) 00459 return CTypes::equality; 00460 00461 Iterator lhsend = std::find_if(start, finish, 00462 std::bind2nd(std::greater<IdxType>(), lhs)); 00463 00464 00465 Iterator rhsend = std::find_if(start, finish, 00466 std::bind2nd(std::greater<IdxType>(), rhs)); 00467 00468 CTypes::comp_type result = CTypes::equality; 00469 00470 if PBORI_UNLIKELY( (rhsend == finish) && (lhsend != finish) ) 00471 result = CTypes::less_than; 00472 else if PBORI_UNLIKELY(lhsend == finish) 00473 result = CTypes::greater_than; 00474 else { 00475 PBORI_ASSERT((lhsend != finish) && (rhsend != finish)); 00476 result = generic_compare_3way( *lhsend, *rhsend, std::less<IdxType>() ); 00477 } 00478 00479 return ( result == CTypes::equality? 00480 generic_compare_3way(lhs, rhs, idx_comp): result ); 00481 } 00482 00483 END_NAMESPACE_PBORI 00484 00485 #endif