PolyBoRi
pbori_routines_order.h
Go to the documentation of this file.
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