<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>PolyBoRi: pbori_routines_order.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.9 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<h1>pbori_routines_order.h</h1><a href="pbori__routines__order_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// -*- c++ -*-</span>
<a name="l00002"></a>00002 <span class="comment">//*****************************************************************************</span>
<a name="l00057"></a>00057 <span class="comment"></span><span class="comment">//*****************************************************************************</span>
<a name="l00058"></a>00058
<a name="l00059"></a>00059 <span class="comment">// include basic definitions</span>
<a name="l00060"></a>00060 <span class="preprocessor">#include "<a class="code" href="pbori__defs_8h.html">pbori_defs.h</a>"</span>
<a name="l00061"></a>00061 <span class="preprocessor">#include "<a class="code" href="pbori__order_8h.html">pbori_order.h</a>"</span>
<a name="l00062"></a>00062 <span class="preprocessor">#include "<a class="code" href="pbori__algo_8h.html">pbori_algo.h</a>"</span>
<a name="l00063"></a>00063 <span class="preprocessor">#include "<a class="code" href="pbori__traits_8h.html">pbori_traits.h</a>"</span>
<a name="l00064"></a>00064
<a name="l00065"></a>00065 <span class="preprocessor">#include "<a class="code" href="CRestrictedIter_8h.html">CRestrictedIter.h</a>"</span>
<a name="l00066"></a>00066
<a name="l00067"></a>00067 <a class="code" href="pbori__defs_8h.html#6ae360a591580558f31b6157ee792a10" title="Start project&#39;s namespace.">BEGIN_NAMESPACE_PBORI</a>
<a name="l00068"></a>00068
<a name="l00069"></a>00069
<a name="l00070"></a>00070
<a name="l00071"></a>00071
<a name="l00072"></a>00072 <span class="keyword">template</span> <<span class="keyword">class</span> FirstIterator, <span class="keyword">class</span> SecondIterator, <span class="keyword">class</span> BinaryPredicate>
<a name="l00073"></a>00073 CTypes::comp_type
<a name="l00074"></a><a class="code" href="namespacepolybori.html#9346909ccaf2fa20d1f094287e9acae5">00074</a> <a class="code" href="namespacepolybori.html#9346909ccaf2fa20d1f094287e9acae5">lex_compare_3way</a>(FirstIterator start, FirstIterator finish,
<a name="l00075"></a>00075 SecondIterator rhs_start, SecondIterator rhs_finish,
<a name="l00076"></a>00076 BinaryPredicate idx_comp) {
<a name="l00077"></a>00077
<a name="l00078"></a>00078 <span class="keywordflow">while</span> ( (start != finish) && (rhs_start != rhs_finish) &&
<a name="l00079"></a>00079 (*start == *rhs_start) ) {
<a name="l00080"></a>00080 ++start; ++rhs_start;
<a name="l00081"></a>00081 }
<a name="l00082"></a>00082
<a name="l00083"></a>00083 <span class="keywordflow">if</span> (start == finish) {
<a name="l00084"></a>00084 <span class="keywordflow">if</span> (rhs_start == rhs_finish)
<a name="l00085"></a>00085 <span class="keywordflow">return</span> CTypes::equality;
<a name="l00086"></a>00086
<a name="l00087"></a>00087 <span class="keywordflow">return</span> CTypes::less_than;
<a name="l00088"></a>00088 }
<a name="l00089"></a>00089
<a name="l00090"></a>00090 <span class="keywordflow">if</span> (rhs_start == rhs_finish)
<a name="l00091"></a>00091 <span class="keywordflow">return</span> CTypes::greater_than;
<a name="l00092"></a>00092
<a name="l00093"></a>00093 <span class="keywordflow">return</span> (idx_comp(*start, *rhs_start)?
<a name="l00094"></a>00094 CTypes::greater_than: CTypes::less_than);
<a name="l00095"></a>00095 }
<a name="l00096"></a>00096
<a name="l00097"></a>00097
<a name="l00100"></a>00100 <span class="keyword">template</span> <<span class="keyword">class</span> LhsType, <span class="keyword">class</span> RhsType, <span class="keyword">class</span> BinaryPredicate>
<a name="l00101"></a>00101 CTypes::comp_type
<a name="l00102"></a><a class="code" href="namespacepolybori.html#3330b66bec883f1ee7a7cfc6afc1cd08">00102</a> <a class="code" href="namespacepolybori.html#3330b66bec883f1ee7a7cfc6afc1cd08" title="defines lexicographic comparison">lex_compare</a>(<span class="keyword">const</span> LhsType& lhs, <span class="keyword">const</span> RhsType& rhs,
<a name="l00103"></a>00103 BinaryPredicate idx_comp, <a class="code" href="structpolybori_1_1valid__tag.html" title="This class shows, whether a property of an order is valid.">valid_tag</a> has_easy_equality_test) {
<a name="l00104"></a>00104
<a name="l00105"></a>00105 <span class="keywordflow">if</span> (lhs == rhs)
<a name="l00106"></a>00106 <span class="keywordflow">return</span> CTypes::equality;
<a name="l00107"></a>00107
<a name="l00108"></a>00108 <span class="keywordflow">return</span> <a class="code" href="namespacepolybori.html#9346909ccaf2fa20d1f094287e9acae5">lex_compare_3way</a>(lhs.begin(), lhs.end(),
<a name="l00109"></a>00109 rhs.begin(), rhs.end(), idx_comp);
<a name="l00110"></a>00110 <span class="comment">//typedef lex_compare_predicate<LhsType, RhsType, BinaryPredicate> comp_type;</span>
<a name="l00111"></a>00111 <span class="comment">//return generic_compare_3way(lhs, rhs, comp_type(idx_comp));</span>
<a name="l00112"></a>00112 }
<a name="l00113"></a>00113
<a name="l00114"></a>00114
<a name="l00117"></a>00117 <span class="keyword">template</span> <<span class="keyword">class</span> LhsType, <span class="keyword">class</span> RhsType, <span class="keyword">class</span> BinaryPredicate>
<a name="l00118"></a>00118 CTypes::comp_type
<a name="l00119"></a><a class="code" href="namespacepolybori.html#fab147a58d8b2aa59174a9c944dca87b">00119</a> <a class="code" href="namespacepolybori.html#3330b66bec883f1ee7a7cfc6afc1cd08" title="defines lexicographic comparison">lex_compare</a>(<span class="keyword">const</span> LhsType& lhs, <span class="keyword">const</span> RhsType& rhs,
<a name="l00120"></a>00120 BinaryPredicate idx_comp, <a class="code" href="structpolybori_1_1invalid__tag.html" title="This class shows, whether a property of an order is invalid.">invalid_tag</a> has_no_easy_equality_test) {
<a name="l00121"></a>00121
<a name="l00122"></a>00122 <span class="keywordflow">return</span> <a class="code" href="namespacepolybori.html#9346909ccaf2fa20d1f094287e9acae5">lex_compare_3way</a>(lhs.begin(), lhs.end(),
<a name="l00123"></a>00123 rhs.begin(), rhs.end(), idx_comp);
<a name="l00124"></a>00124 }
<a name="l00125"></a>00125
<a name="l00128"></a>00128 <span class="keyword">template</span> <<span class="keyword">class</span> LhsType, <span class="keyword">class</span> RhsType, <span class="keyword">class</span> BinaryPredicate>
<a name="l00129"></a>00129 CTypes::comp_type
<a name="l00130"></a><a class="code" href="namespacepolybori.html#e96461b268eef88e1a7c3922aad5a6b9">00130</a> <a class="code" href="namespacepolybori.html#3330b66bec883f1ee7a7cfc6afc1cd08" title="defines lexicographic comparison">lex_compare</a>(<span class="keyword">const</span> LhsType& lhs, <span class="keyword">const</span> RhsType& rhs, BinaryPredicate idx_comp) {
<a name="l00131"></a>00131
<a name="l00132"></a>00132 <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structpolybori_1_1invalid__tag.html" title="This class shows, whether a property of an order is invalid.">pbori_binary_traits<LhsType, RhsType>::easy_equality_property</a>
<a name="l00133"></a>00133 <a class="code" href="classpolybori_1_1equality__property.html">equality_property</a>;
<a name="l00134"></a>00134
<a name="l00135"></a>00135 <span class="keywordflow">return</span> <a class="code" href="namespacepolybori.html#3330b66bec883f1ee7a7cfc6afc1cd08" title="defines lexicographic comparison">lex_compare</a>(lhs, rhs, idx_comp, equality_property());
<a name="l00136"></a>00136 }
<a name="l00137"></a>00137
<a name="l00140"></a>00140 <span class="keyword">template</span><<span class="keyword">class</span> LhsType, <span class="keyword">class</span> RhsType, <span class="keyword">class</span> BinaryPredicate>
<a name="l00141"></a>00141 CTypes::comp_type
<a name="l00142"></a><a class="code" href="namespacepolybori.html#4fe5854ff6cb0bf09008ab8a345b2f99">00142</a> <a class="code" href="namespacepolybori.html#4fe5854ff6cb0bf09008ab8a345b2f99" title="defines degree-lexicographic comparison">deg_lex_compare</a>(<span class="keyword">const</span> LhsType& lhs, <span class="keyword">const</span> RhsType& rhs,
<a name="l00143"></a>00143 BinaryPredicate idx_comp) {
<a name="l00144"></a>00144
<a name="l00145"></a>00145 <span class="keyword">typedef</span> <span class="keyword">typename</span> LhsType::size_type size_type;
<a name="l00146"></a>00146 CTypes::comp_type result = <a class="code" href="namespacepolybori.html#5d5bac8b009548eb8ec17ca2f47eced8" title="defines lexicographic comparison for variable indices">generic_compare_3way</a>( lhs.size(), rhs.size(),
<a name="l00147"></a>00147 std::greater<size_type>() );
<a name="l00148"></a>00148
<a name="l00149"></a>00149 <span class="keywordflow">return</span> (result == CTypes::equality? <a class="code" href="namespacepolybori.html#3330b66bec883f1ee7a7cfc6afc1cd08" title="defines lexicographic comparison">lex_compare</a>(lhs, rhs, idx_comp): result);
<a name="l00150"></a>00150 }
<a name="l00151"></a>00151
<a name="l00152"></a>00152
<a name="l00153"></a>00153 <span class="keyword">template</span> <<span class="keyword">class</span> OrderType, <span class="keyword">class</span> Iterator>
<a name="l00154"></a>00154 <span class="keyword">class </span>generic_iteration;
<a name="l00155"></a>00155
<a name="l00156"></a>00156 <span class="keyword">template</span><<span class="keyword">class</span> DummyType>
<a name="l00157"></a><a class="code" href="classpolybori_1_1dummy__data__type.html">00157</a> <span class="keyword">class </span><a class="code" href="classpolybori_1_1dummy__data__type.html">dummy_data_type</a> {
<a name="l00158"></a>00158 <span class="keyword">public</span>:
<a name="l00159"></a><a class="code" href="classpolybori_1_1dummy__data__type.html#7be3a82e9cb535b75a7a22277ee94ded">00159</a> <a class="code" href="classpolybori_1_1dummy__data__type.html#7be3a82e9cb535b75a7a22277ee94ded">dummy_data_type</a>(<span class="keyword">const</span> DummyType&) {}
<a name="l00160"></a><a class="code" href="classpolybori_1_1dummy__data__type.html#3545b4035c464f9aaf7184f4b8dd37c3">00160</a> <a class="code" href="classpolybori_1_1dummy__data__type.html#3545b4035c464f9aaf7184f4b8dd37c3">dummy_data_type</a>(DummyType&) {}
<a name="l00161"></a><a class="code" href="classpolybori_1_1dummy__data__type.html#96acddcacc4523aaa585a471d95b2262">00161</a> <a class="code" href="classpolybori_1_1dummy__data__type.html#96acddcacc4523aaa585a471d95b2262">dummy_data_type</a>() {}
<a name="l00162"></a>00162 };
<a name="l00163"></a>00163
<a name="l00164"></a>00164 <span class="comment">// LexOrder</span>
<a name="l00165"></a>00165 <span class="keyword">template</span> <<span class="keyword">class</span> Iterator>
<a name="l00166"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html">00166</a> <span class="keyword">class </span>generic_iteration<<a class="code" href="classpolybori_1_1LexOrder.html" title="This class defines ordering related functions.">LexOrder</a>, Iterator> {
<a name="l00167"></a>00167 <span class="keyword">public</span>:
<a name="l00168"></a>00168
<a name="l00170"></a>00170
<a name="l00171"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#f770124113742e4ff71e53b3ba1a1a10">00171</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1LexOrder.html" title="This class defines ordering related functions.">LexOrder</a> <a class="code" href="classpolybori_1_1LexOrder.html" title="This class defines ordering related functions.">order_type</a>;
<a name="l00172"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#55bbeff95eaad3388bdea3101ad29299">00172</a> <span class="keyword">typedef</span> Iterator iterator;
<a name="l00173"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#74d9c3dbac2a6a5278b5efdfd13b70be">00173</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">order_type::poly_type</a> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a>;
<a name="l00174"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#23be50721d5cd92c745e69aa8db0d796">00174</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1dummy__data__type.html">dummy_data_type<poly_type></a> <a class="code" href="classpolybori_1_1dummy__data__type.html">data_type</a>;
<a name="l00176"></a>00176
<a name="l00178"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#c5513ce60e4989a7f805295a019ff6c6">00178</a> iterator <a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#c5513ce60e4989a7f805295a019ff6c6" title="Define initial iterator generation for this ordering.">leadIterator</a>(<span class="keyword">const</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a>& poly)<span class="keyword"> const </span>{
<a name="l00179"></a>00179 <span class="keywordflow">return</span> iterator(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#f922cc6c7798bfee714a6614165b1e8b" title="Navigate through structure.">navigation</a>());
<a name="l00180"></a>00180 }
<a name="l00181"></a>00181
<a name="l00183"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#02126f70c509340a25f9d1c30837ea22">00183</a> iterator <a class="code" href="classpolybori_1_1generic__iteration_3_01LexOrder_00_01Iterator_01_4.html#02126f70c509340a25f9d1c30837ea22" title="Define iterator incrementation for this ordering.">incrementIterator</a>(iterator& iter, <span class="keyword">const</span> <a class="code" href="classpolybori_1_1dummy__data__type.html">data_type</a>&)<span class="keyword"> const </span>{
<a name="l00184"></a>00184 <span class="keywordflow">return</span> ++iter;
<a name="l00185"></a>00185 }
<a name="l00186"></a>00186 };
<a name="l00187"></a>00187
<a name="l00188"></a>00188 <span class="comment">// DegLexOrder</span>
<a name="l00189"></a>00189 <span class="keyword">template</span> <<span class="keyword">class</span> Iterator>
<a name="l00190"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html">00190</a> <span class="keyword">class </span>generic_iteration<<a class="code" href="classpolybori_1_1DegLexOrder.html" title="This class defines ordering related functions.">DegLexOrder</a>, Iterator> {
<a name="l00191"></a>00191 <span class="keyword">public</span>:
<a name="l00193"></a>00193
<a name="l00194"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#a38e94d8786b3cc5d4f351bb4494e4d9">00194</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1DegLexOrder.html" title="This class defines ordering related functions.">DegLexOrder</a> <a class="code" href="classpolybori_1_1DegLexOrder.html" title="This class defines ordering related functions.">order_type</a>;
<a name="l00195"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#9f00c259cb32756080d6b9b4e13f431a">00195</a> <span class="keyword">typedef</span> Iterator iterator;
<a name="l00196"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#1aeb17363242750b8bb6c2193b348084">00196</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">order_type::poly_type</a> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a>;
<a name="l00197"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#edc51a96b0f70e9c23170cd6a8cd8760">00197</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">data_type</a>;
<a name="l00198"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#c24232d13dd845d85c47372c3ca13112">00198</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> order_type::size_type size_type;
<a name="l00200"></a>00200
<a name="l00202"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#61020dd74fd6eb516f236de605de6865">00202</a> iterator <a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#61020dd74fd6eb516f236de605de6865" title="Define initial iterator generation for this ordering.">leadIterator</a>(<span class="keyword">const</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a>& poly)<span class="keyword"> const </span>{
<a name="l00203"></a>00203 <span class="keywordflow">return</span> std::max_element(iterator(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#f922cc6c7798bfee714a6614165b1e8b" title="Navigate through structure.">navigation</a>()),
<a name="l00204"></a>00204 iterator(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#8b143e2b48e41d8f322c86894b5f1dca" title="End of navigation marker.">endOfNavigation</a>()) );
<a name="l00205"></a>00205 }
<a name="l00206"></a>00206
<a name="l00208"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#b7ae76bb5e40ef406f234e780dbd05e6">00208</a> iterator& <a class="code" href="classpolybori_1_1generic__iteration_3_01DegLexOrder_00_01Iterator_01_4.html#b7ae76bb5e40ef406f234e780dbd05e6" title="Define iterator incrementation for this ordering.">incrementIterator</a>(iterator& iter, <span class="keyword">const</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">data_type</a>& poly)<span class="keyword"> const </span>{
<a name="l00209"></a>00209 <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1CRestrictedIter.html">CRestrictedIter<iterator></a> bounded_iterator;
<a name="l00210"></a>00210
<a name="l00211"></a>00211 iterator m_start(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#f922cc6c7798bfee714a6614165b1e8b" title="Navigate through structure.">navigation</a>());
<a name="l00212"></a>00212 iterator m_finish(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#8b143e2b48e41d8f322c86894b5f1dca" title="End of navigation marker.">endOfNavigation</a>());
<a name="l00213"></a>00213
<a name="l00214"></a>00214 <span class="keywordflow">if</span> (iter != m_finish) {
<a name="l00215"></a>00215 size_type deg = *iter;
<a name="l00216"></a>00216 ++iter;
<a name="l00217"></a>00217 iter = std::find(iter, m_finish, deg);
<a name="l00218"></a>00218
<a name="l00219"></a>00219 <span class="keywordflow">if</span>(iter == m_finish) {
<a name="l00220"></a>00220 iter = std::max_element( bounded_iterator(m_start, deg),
<a name="l00221"></a>00221 bounded_iterator(m_finish, deg) );
<a name="l00222"></a>00222
<a name="l00223"></a>00223 }
<a name="l00224"></a>00224 }
<a name="l00225"></a>00225 <span class="keywordflow">return</span> iter;
<a name="l00226"></a>00226 }
<a name="l00227"></a>00227 };
<a name="l00228"></a>00228
<a name="l00229"></a>00229
<a name="l00230"></a>00230 <span class="comment">// DegRevLexAscOrder</span>
<a name="l00231"></a>00231 <span class="keyword">template</span> <<span class="keyword">class</span> Iterator>
<a name="l00232"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html">00232</a> <span class="keyword">class </span>generic_iteration<<a class="code" href="classpolybori_1_1DegRevLexAscOrder.html" title="This class defines ordering related functions.">DegRevLexAscOrder</a>, Iterator> {
<a name="l00233"></a>00233 <span class="keyword">public</span>:
<a name="l00235"></a>00235
<a name="l00236"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#a71e6d6c30adfa4306a602a8eecf81ca">00236</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1DegRevLexAscOrder.html" title="This class defines ordering related functions.">DegRevLexAscOrder</a> <a class="code" href="classpolybori_1_1DegRevLexAscOrder.html" title="This class defines ordering related functions.">order_type</a>;
<a name="l00237"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#11ff67a145ee1dbdc29e66377230a463">00237</a> <span class="keyword">typedef</span> Iterator iterator;
<a name="l00238"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#4d92d2eb29852a1bd5a97aa4321406ec">00238</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">order_type::poly_type</a> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a>;
<a name="l00239"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#51c521a0219f59331bb2ef705f4790ee">00239</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">data_type</a>;
<a name="l00240"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#3c468eb1a2d6e849f2b00977903f828f">00240</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> order_type::size_type size_type;
<a name="l00242"></a>00242
<a name="l00244"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#836214d038b1ff2bfd1d7f363721b456">00244</a> iterator <a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#836214d038b1ff2bfd1d7f363721b456" title="Define initial iterator generation for this ordering.">leadIterator</a>(<span class="keyword">const</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">poly_type</a>& poly)<span class="keyword"> const </span>{
<a name="l00245"></a>00245 <span class="keywordflow">return</span> std::max_element(iterator(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#f922cc6c7798bfee714a6614165b1e8b" title="Navigate through structure.">navigation</a>()),
<a name="l00246"></a>00246 iterator(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#8b143e2b48e41d8f322c86894b5f1dca" title="End of navigation marker.">endOfNavigation</a>()),
<a name="l00247"></a>00247 std::less_equal<size_type>() );
<a name="l00248"></a>00248 }
<a name="l00249"></a>00249
<a name="l00251"></a><a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#6645912fc1bb73cb2692896f547b24c3">00251</a> iterator& <a class="code" href="classpolybori_1_1generic__iteration_3_01DegRevLexAscOrder_00_01Iterator_01_4.html#6645912fc1bb73cb2692896f547b24c3" title="Define iterator incrementation for this ordering.">incrementIterator</a>(iterator& iter, <span class="keyword">const</span> <a class="code" href="classpolybori_1_1BoolePolynomial.html" title="This class wraps the underlying decicion diagram type and defines the necessary operations...">data_type</a>& poly)<span class="keyword"> const </span>{
<a name="l00252"></a>00252
<a name="l00253"></a>00253 <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1CRestrictedIter.html">CRestrictedIter<iterator></a> bounded_iterator;
<a name="l00254"></a>00254
<a name="l00255"></a>00255 iterator m_start(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#f922cc6c7798bfee714a6614165b1e8b" title="Navigate through structure.">navigation</a>());
<a name="l00256"></a>00256 iterator m_finish(poly.<a class="code" href="classpolybori_1_1BoolePolynomial.html#8b143e2b48e41d8f322c86894b5f1dca" title="End of navigation marker.">endOfNavigation</a>());
<a name="l00257"></a>00257
<a name="l00258"></a>00258 <span class="keywordflow">if</span> (iter != m_finish) {
<a name="l00259"></a>00259
<a name="l00260"></a>00260 size_type deg = *iter;
<a name="l00261"></a>00261 --iter;
<a name="l00262"></a>00262 iter = std::find(<a class="code" href="classpolybori_1_1reversed__iteration__adaptor.html">reversed_iteration_adaptor<iterator></a>(iter),
<a name="l00263"></a>00263 <a class="code" href="classpolybori_1_1reversed__iteration__adaptor.html">reversed_iteration_adaptor<iterator></a>(m_finish), deg).get();
<a name="l00264"></a>00264
<a name="l00265"></a>00265 <span class="keywordflow">if</span>(iter == m_finish) {
<a name="l00266"></a>00266 iter = std::max_element( bounded_iterator(m_start, deg),
<a name="l00267"></a>00267 bounded_iterator(m_finish, deg),
<a name="l00268"></a>00268 std::less_equal<size_type>() );
<a name="l00269"></a>00269
<a name="l00270"></a>00270 }
<a name="l00271"></a>00271 }
<a name="l00272"></a>00272 <span class="keywordflow">return</span> iter;
<a name="l00273"></a>00273 }
<a name="l00274"></a>00274 };
<a name="l00275"></a>00275
<a name="l00276"></a>00276
<a name="l00279"></a>00279 <span class="keyword">template</span> <<span class="keyword">class</span> StackType, <span class="keyword">class</span> Iterator>
<a name="l00280"></a><a class="code" href="namespacepolybori.html#67e0fc6630ac90c42822b837e0231593">00280</a> <span class="keywordtype">void</span> <a class="code" href="namespacepolybori.html#67e0fc6630ac90c42822b837e0231593">dummy_append</a>(StackType& stack, Iterator start, Iterator finish) {
<a name="l00281"></a>00281
<a name="l00282"></a>00282 <span class="keywordflow">while</span> (start != finish) {
<a name="l00283"></a>00283 stack.push(*start);
<a name="l00284"></a>00284 ++start;
<a name="l00285"></a>00285 }
<a name="l00286"></a>00286 }
<a name="l00287"></a>00287
<a name="l00288"></a>00288 <span class="keyword">template</span><<span class="keyword">class</span> NaviType, <span class="keyword">class</span> DescendingProperty = val<span class="keywordtype">id</span>_tag>
<a name="l00289"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html">00289</a> <span class="keyword">class </span><a class="code" href="classpolybori_1_1bounded__restricted__term.html">bounded_restricted_term</a> {
<a name="l00290"></a>00290 <span class="keyword">public</span>:
<a name="l00291"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#6b600d1bb845463497bd3ee9dddfa134">00291</a> <span class="keyword">typedef</span> NaviType navigator;
<a name="l00292"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#1572ea03f959b7325b88672e874b4856">00292</a> <span class="keyword">typedef</span> DescendingProperty descending_property;
<a name="l00293"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#87fac7a62bde1f33d6e3c45634087bb2">00293</a> <span class="keyword">typedef</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html">bounded_restricted_term<navigator, descending_property></a> <span class="keyword">self</span>;
<a name="l00294"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#2556426fd6791a218fa6c6e5e2211cdb">00294</a> <span class="keyword">typedef</span> std::vector<navigator> stack_type;
<a name="l00295"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#3d032ecc77093972a427c3c34a4fc89c">00295</a> <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span> size_type;
<a name="l00296"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#c5384f2b81110d080b89562cde00c642">00296</a> <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span> <a class="code" href="namespacepolybori_1_1groebner.html#ef37a95e97afbd561cc4c5f84d660765">idx_type</a>;
<a name="l00297"></a>00297
<a name="l00298"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#68235847af4cf834d5bc4f332f8ece3e">00298</a> <a class="code" href="classpolybori_1_1bounded__restricted__term.html">bounded_restricted_term</a> ():
<a name="l00299"></a>00299 m_stack(), m_max_idx(0), m_upperbound(0), m_next() {}
<a name="l00300"></a>00300
<a name="l00301"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#3dee213c59aea7384b06b33a2998cef7">00301</a> <a class="code" href="classpolybori_1_1is__same__type.html">is_same_type<descending_property, valid_tag></a> descendingVariables;
<a name="l00302"></a>00302
<a name="l00303"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#177259216ba3cd6f3311e5144c3bc33d">00303</a> <a class="code" href="classpolybori_1_1bounded__restricted__term.html">bounded_restricted_term</a> (navigator navi, size_type upperbound,
<a name="l00304"></a>00304 <a class="code" href="namespacepolybori_1_1groebner.html#ef37a95e97afbd561cc4c5f84d660765">idx_type</a> max_idx):
<a name="l00305"></a>00305 m_stack(), m_upperbound(upperbound), m_max_idx(max_idx), m_next(navi) {
<a name="l00306"></a>00306
<a name="l00307"></a>00307 m_stack.reserve(upperbound);
<a name="l00308"></a>00308
<a name="l00309"></a>00309 followThen();
<a name="l00310"></a>00310
<a name="l00311"></a>00311 <span class="keywordflow">while</span> (!is_path_end() && !empty() )
<a name="l00312"></a>00312 increment();
<a name="l00313"></a>00313 }
<a name="l00314"></a>00314
<a name="l00315"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#2e18246b07e1f576207ac26efc80606a">00315</a> size_type <a class="code" href="classpolybori_1_1bounded__restricted__term.html#2e18246b07e1f576207ac26efc80606a">operator*</a>()<span class="keyword"> const </span>{
<a name="l00316"></a>00316 <span class="keywordflow">return</span> m_stack.size();
<a name="l00317"></a>00317 }
<a name="l00318"></a>00318
<a name="l00319"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#a3127d9e8c9ad9e37bdcbbd7d55eaf90">00319</a> <span class="keyword">const</span> navigator& <a class="code" href="classpolybori_1_1bounded__restricted__term.html#a3127d9e8c9ad9e37bdcbbd7d55eaf90">next</a>()<span class="keyword"> const </span>{
<a name="l00320"></a>00320 <span class="keywordflow">return</span> m_next;
<a name="l00321"></a>00321 }
<a name="l00322"></a>00322
<a name="l00323"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#fa1d9dd77f0f91c1a2bb544c68b497b3">00323</a> <span class="keyword">typename</span> stack_type::const_iterator <a class="code" href="classpolybori_1_1bounded__restricted__term.html#fa1d9dd77f0f91c1a2bb544c68b497b3">begin</a>()<span class="keyword"> const </span>{
<a name="l00324"></a>00324 <span class="keywordflow">return</span> m_stack.begin();
<a name="l00325"></a>00325 }
<a name="l00326"></a>00326
<a name="l00327"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#ac6133a562af7e064bcebdac4eaf74f2">00327</a> <span class="keyword">typename</span> stack_type::const_iterator <a class="code" href="classpolybori_1_1bounded__restricted__term.html#ac6133a562af7e064bcebdac4eaf74f2">end</a>()<span class="keyword"> const </span>{
<a name="l00328"></a>00328 <span class="keywordflow">return</span> m_stack.end();
<a name="l00329"></a>00329 }
<a name="l00330"></a>00330
<a name="l00331"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#a7e36cba4248a7a7bf19fb3562e991c5">00331</a> <span class="keyword">self</span>& <a class="code" href="classpolybori_1_1bounded__restricted__term.html#a7e36cba4248a7a7bf19fb3562e991c5">operator++</a>() {
<a name="l00332"></a>00332 assert(!empty());
<a name="l00333"></a>00333
<a name="l00334"></a>00334 <span class="comment">// if upperbound was already found we're done</span>
<a name="l00335"></a>00335 <span class="comment">// (should be optimized away for ascending variables)</span>
<a name="l00336"></a>00336 <span class="keywordflow">if</span> (descendingVariables() && (m_stack.size() == m_upperbound) )
<a name="l00337"></a>00337 <span class="keywordflow">return</span> *<span class="keyword">this</span> = <span class="keyword">self</span>();
<a name="l00338"></a>00338
<a name="l00339"></a>00339 <span class="keywordflow">do</span> {
<a name="l00340"></a>00340 increment();
<a name="l00341"></a>00341 } <span class="keywordflow">while</span> (!empty() && !is_path_end());
<a name="l00342"></a>00342
<a name="l00343"></a>00343 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l00344"></a>00344 }
<a name="l00345"></a>00345
<a name="l00346"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#6a8caed5bc88211761dc876e371402c6">00346</a> <span class="keywordtype">void</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#6a8caed5bc88211761dc876e371402c6">print</a>()<span class="keyword"> const </span>{
<a name="l00347"></a>00347
<a name="l00348"></a>00348 <span class="keyword">typename</span> stack_type::const_iterator start(m_stack.begin()),
<a name="l00349"></a>00349 finish(m_stack.end());
<a name="l00350"></a>00350
<a name="l00351"></a>00351 std::cout <<<span class="charliteral">'('</span>;
<a name="l00352"></a>00352 <span class="keywordflow">while</span> (start != finish) {
<a name="l00353"></a>00353 std::cout << *(*start) << <span class="stringliteral">", "</span> ;
<a name="l00354"></a>00354 ++start;
<a name="l00355"></a>00355 }
<a name="l00356"></a>00356 std::cout <<<span class="charliteral">')'</span>;
<a name="l00357"></a>00357
<a name="l00358"></a>00358 }
<a name="l00359"></a>00359
<a name="l00360"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#e275827fb8de00e87e976a1c1ab799e6">00360</a> <span class="keywordtype">bool</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#e275827fb8de00e87e976a1c1ab799e6">operator==</a>(<span class="keyword">const</span> <span class="keyword">self</span>& rhs)<span class="keyword"> const </span>{
<a name="l00361"></a>00361 <span class="keywordflow">if</span> (rhs.empty())
<a name="l00362"></a>00362 <span class="keywordflow">return</span> empty();
<a name="l00363"></a>00363 <span class="keywordflow">if</span> (empty())
<a name="l00364"></a>00364 <span class="keywordflow">return</span> rhs.empty();
<a name="l00365"></a>00365
<a name="l00366"></a>00366 <span class="keywordflow">else</span> (m_stack == rhs.m_stack);
<a name="l00367"></a>00367 }
<a name="l00368"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#d6c71efcc02efd8553c663525eb6f28a">00368</a> <span class="keywordtype">bool</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#d6c71efcc02efd8553c663525eb6f28a">operator!=</a>(<span class="keyword">const</span> <span class="keyword">self</span>& rhs)<span class="keyword"> const </span>{
<a name="l00369"></a>00369 <span class="keywordflow">return</span> !(*<span class="keyword">this</span> == rhs);
<a name="l00370"></a>00370 }
<a name="l00371"></a>00371 <span class="keyword">protected</span>:
<a name="l00372"></a>00372
<a name="l00373"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#a8600adb939d288f9dfe605cf5649284">00373</a> <span class="keywordtype">void</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#a8600adb939d288f9dfe605cf5649284">followThen</a>() {
<a name="l00374"></a>00374 <span class="keywordflow">while</span> (within_degree() && !at_end())
<a name="l00375"></a>00375 nextThen();
<a name="l00376"></a>00376 }
<a name="l00377"></a>00377
<a name="l00378"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#7bc5e97ef0353c2faba4be8e2c01bcf6">00378</a> <span class="keywordtype">void</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#7bc5e97ef0353c2faba4be8e2c01bcf6">increment</a>() {
<a name="l00379"></a>00379 assert(!empty());
<a name="l00380"></a>00380
<a name="l00381"></a>00381 m_next = top();
<a name="l00382"></a>00382 m_next.incrementElse();
<a name="l00383"></a>00383 m_stack.pop_back();
<a name="l00384"></a>00384
<a name="l00385"></a>00385 followThen();
<a name="l00386"></a>00386
<a name="l00387"></a>00387 }
<a name="l00388"></a>00388
<a name="l00389"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#02ffc64d01b8446fa192128ded9aab78">00389</a> <span class="keywordtype">bool</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#02ffc64d01b8446fa192128ded9aab78">empty</a>()<span class="keyword"> const</span>{
<a name="l00390"></a>00390 <span class="keywordflow">return</span> m_stack.empty();
<a name="l00391"></a>00391 }
<a name="l00392"></a>00392
<a name="l00393"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#b5836c55c4d08eafff1f8e59a3fb263a">00393</a> navigator <a class="code" href="classpolybori_1_1bounded__restricted__term.html#b5836c55c4d08eafff1f8e59a3fb263a">top</a>()<span class="keyword"> const</span>{
<a name="l00394"></a>00394 <span class="keywordflow">return</span> m_stack.back();
<a name="l00395"></a>00395 }
<a name="l00396"></a>00396
<a name="l00397"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#c48ccc2cdcf39c83f55cba4b64bf9830">00397</a> <span class="keywordtype">bool</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#c48ccc2cdcf39c83f55cba4b64bf9830">is_path_end</a>() {
<a name="l00398"></a>00398
<a name="l00399"></a>00399 path_end();
<a name="l00400"></a>00400 <span class="keywordflow">return</span> (!m_next.isConstant() && (*m_next >= m_max_idx)) ||
<a name="l00401"></a>00401 m_next.terminalValue();
<a name="l00402"></a>00402 }
<a name="l00403"></a>00403
<a name="l00404"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#498d885ed4c185456caba85ac69f608e">00404</a> <span class="keywordtype">void</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#498d885ed4c185456caba85ac69f608e">path_end</a>() {
<a name="l00405"></a>00405 <span class="keywordflow">while</span> (!at_end()) {
<a name="l00406"></a>00406 m_next.incrementElse();
<a name="l00407"></a>00407 }
<a name="l00408"></a>00408 }
<a name="l00409"></a>00409
<a name="l00410"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#3fb86d3477abf58c0bf368d1a3ef8625">00410</a> <span class="keywordtype">void</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#3fb86d3477abf58c0bf368d1a3ef8625">nextThen</a>() {
<a name="l00411"></a>00411 assert(!m_next.isConstant());
<a name="l00412"></a>00412 m_stack.push_back(m_next);
<a name="l00413"></a>00413 m_next.incrementThen();
<a name="l00414"></a>00414 }
<a name="l00415"></a>00415
<a name="l00416"></a>00416
<a name="l00417"></a>00417
<a name="l00418"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#4e1afd26d27b61843cb7d24175aee71e">00418</a> <span class="keywordtype">bool</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#4e1afd26d27b61843cb7d24175aee71e">within_degree</a>()<span class="keyword"> const </span>{
<a name="l00419"></a>00419
<a name="l00420"></a>00420 <span class="keywordflow">return</span> (*(*<span class="keyword">this</span>) < m_upperbound);
<a name="l00421"></a>00421 }
<a name="l00422"></a>00422
<a name="l00423"></a><a class="code" href="classpolybori_1_1bounded__restricted__term.html#4ad7be204eba344d9608ad7238496c60">00423</a> <span class="keywordtype">bool</span> <a class="code" href="classpolybori_1_1bounded__restricted__term.html#4ad7be204eba344d9608ad7238496c60">at_end</a>()<span class="keyword"> const </span>{
<a name="l00424"></a>00424
<a name="l00425"></a>00425 <span class="keywordflow">return</span> m_next.isConstant() || (*m_next >= m_max_idx);
<a name="l00426"></a>00426 }
<a name="l00427"></a>00427
<a name="l00428"></a>00428 <span class="keyword">private</span>:
<a name="l00429"></a>00429 stack_type m_stack;
<a name="l00430"></a>00430 <a class="code" href="namespacepolybori_1_1groebner.html#ef37a95e97afbd561cc4c5f84d660765">idx_type</a> m_max_idx;
<a name="l00431"></a>00431 size_type m_upperbound;
<a name="l00432"></a>00432 navigator m_next;
<a name="l00433"></a>00433 };
<a name="l00434"></a>00434
<a name="l00435"></a>00435
<a name="l00436"></a>00436
<a name="l00439"></a>00439 <span class="keyword">template</span> <<span class="keyword">class</span> DegreeCacher, <span class="keyword">class</span> NaviType, <span class="keyword">class</span> IdxType>
<a name="l00440"></a>00440 <span class="keyword">typename</span> NaviType::size_type
<a name="l00441"></a><a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">00441</a> <a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(<span class="keyword">const</span> DegreeCacher& cache, NaviType navi,
<a name="l00442"></a>00442 IdxType nextBlock) {
<a name="l00443"></a>00443
<a name="l00444"></a>00444 <span class="keyword">typedef</span> <span class="keyword">typename</span> NaviType::size_type size_type;
<a name="l00445"></a>00445
<a name="l00446"></a>00446 <span class="keywordflow">if</span>( navi.isConstant() || (*navi >= nextBlock) ) <span class="comment">// end of block reached</span>
<a name="l00447"></a>00447 <span class="keywordflow">return</span> 0;
<a name="l00448"></a>00448
<a name="l00449"></a>00449 <span class="comment">// Look whether result was cached before</span>
<a name="l00450"></a>00450 <span class="keyword">typename</span> DegreeCacher::node_type result = cache.find(navi, nextBlock);
<a name="l00451"></a>00451 <span class="keywordflow">if</span> (result.isValid())
<a name="l00452"></a>00452 <span class="keywordflow">return</span> *result;
<a name="l00453"></a>00453
<a name="l00454"></a>00454 <span class="comment">// Get degree of then branch (contains at least one valid path)...</span>
<a name="l00455"></a>00455 size_type deg = <a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(cache, navi.thenBranch(), nextBlock) + 1;
<a name="l00456"></a>00456
<a name="l00457"></a>00457 <span class="comment">// ... combine with degree of else branch</span>
<a name="l00458"></a>00458 deg = std::max(deg, <a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(cache, navi.elseBranch(), nextBlock) );
<a name="l00459"></a>00459
<a name="l00460"></a>00460 <span class="comment">// Write result to cache</span>
<a name="l00461"></a>00461 cache.insert(navi, nextBlock, deg);
<a name="l00462"></a>00462
<a name="l00463"></a>00463 <span class="keywordflow">return</span> deg;
<a name="l00464"></a>00464 }
<a name="l00465"></a>00465
<a name="l00466"></a>00466
<a name="l00467"></a>00467 <span class="keyword">template</span><<span class="keyword">class</span> DegCacheMgr, <span class="keyword">class</span> NaviType, <span class="keyword">class</span> IdxType, <span class="keyword">class</span> SizeType>
<a name="l00468"></a><a class="code" href="namespacepolybori.html#e098750147f7edd7f344d68143296c0a">00468</a> <span class="keywordtype">bool</span> <a class="code" href="namespacepolybori.html#e098750147f7edd7f344d68143296c0a">max_block_degree_on_then</a>(<span class="keyword">const</span> DegCacheMgr& deg_mgr, NaviType navi,
<a name="l00469"></a>00469 IdxType next_block,
<a name="l00470"></a>00470 SizeType degree, <a class="code" href="structpolybori_1_1valid__tag.html" title="This class shows, whether a property of an order is valid.">valid_tag</a> is_descending) {
<a name="l00471"></a>00471 navi.incrementThen();
<a name="l00472"></a>00472 <span class="keywordflow">return</span> ((<a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(deg_mgr, navi, next_block<span class="comment">/*,degree - 1*/</span>) + 1) == degree);
<a name="l00473"></a>00473 }
<a name="l00474"></a>00474
<a name="l00475"></a>00475 <span class="keyword">template</span><<span class="keyword">class</span> DegCacheMgr, <span class="keyword">class</span> NaviType, <span class="keyword">class</span> IdxType, <span class="keyword">class</span> SizeType>
<a name="l00476"></a><a class="code" href="namespacepolybori.html#9f4574d4f272d9423d7459a4280fa716">00476</a> <span class="keywordtype">bool</span> <a class="code" href="namespacepolybori.html#e098750147f7edd7f344d68143296c0a">max_block_degree_on_then</a>(<span class="keyword">const</span> DegCacheMgr& deg_mgr, NaviType navi,
<a name="l00477"></a>00477 IdxType next_block,
<a name="l00478"></a>00478 SizeType degree, <a class="code" href="structpolybori_1_1invalid__tag.html" title="This class shows, whether a property of an order is invalid.">invalid_tag</a> non_descending) {
<a name="l00479"></a>00479 navi.incrementElse();
<a name="l00480"></a>00480 <span class="keywordflow">return</span> (<a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(deg_mgr, navi, next_block<span class="comment">/*, degree*/</span>) != degree);
<a name="l00481"></a>00481 }
<a name="l00482"></a>00482
<a name="l00483"></a>00483
<a name="l00484"></a>00484 <span class="comment">// with degree bound</span>
<a name="l00485"></a>00485 <span class="keyword">template</span> <<span class="keyword">class </span>CacheType, <span class="keyword">class </span>DegCacheMgr, <span class="keyword">class </span>NaviType,
<a name="l00486"></a>00486 <span class="keyword">class </span>TermType, <span class="keyword">class </span>Iterator, <span class="keyword">class </span>SizeType, <span class="keyword">class </span>DescendingProperty>
<a name="l00487"></a>00487 TermType
<a name="l00488"></a><a class="code" href="namespacepolybori.html#c3aa221b482293e210dc2e595a2d69f3">00488</a> <a class="code" href="namespacepolybori.html#c3aa221b482293e210dc2e595a2d69f3">dd_block_degree_lead</a>(<span class="keyword">const</span> CacheType& cache_mgr,
<a name="l00489"></a>00489 <span class="keyword">const</span> DegCacheMgr& deg_mgr,
<a name="l00490"></a>00490 NaviType navi, Iterator block_iter,
<a name="l00491"></a>00491 TermType init, SizeType degree,
<a name="l00492"></a>00492 DescendingProperty prop) {
<a name="l00493"></a>00493
<a name="l00494"></a>00494 <span class="keywordflow">if</span> (navi.isConstant())
<a name="l00495"></a>00495 <span class="keywordflow">return</span> cache_mgr.generate(navi);
<a name="l00496"></a>00496
<a name="l00497"></a>00497 <span class="keywordflow">while</span>( (*navi >= *block_iter) && (*block_iter != CUDD_MAXINDEX)) {
<a name="l00498"></a>00498 ++block_iter;
<a name="l00499"></a>00499 degree = <a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(deg_mgr, navi, *block_iter);
<a name="l00500"></a>00500 }
<a name="l00501"></a>00501
<a name="l00502"></a>00502
<a name="l00503"></a>00503 <span class="comment">// Check cache for previous results</span>
<a name="l00504"></a>00504 NaviType cached = cache_mgr.find(navi);
<a name="l00505"></a>00505 <span class="keywordflow">if</span> (cached.isValid())
<a name="l00506"></a>00506 <span class="keywordflow">return</span> cache_mgr.generate(cached);
<a name="l00507"></a>00507
<a name="l00508"></a>00508 <span class="comment">// Go to next branch</span>
<a name="l00509"></a>00509 <span class="keywordflow">if</span> ( <a class="code" href="namespacepolybori.html#e098750147f7edd7f344d68143296c0a">max_block_degree_on_then</a>(deg_mgr, navi, *block_iter, degree, prop) ) {
<a name="l00510"></a>00510 init = <a class="code" href="namespacepolybori.html#c3aa221b482293e210dc2e595a2d69f3">dd_block_degree_lead</a>(cache_mgr, deg_mgr, navi.thenBranch(),
<a name="l00511"></a>00511 block_iter,
<a name="l00512"></a>00512 init, degree - 1, prop).<a class="code" href="classchange.html" title="Accessing .change().">change</a>(*navi);
<a name="l00513"></a>00513 }
<a name="l00514"></a>00514 <span class="keywordflow">else</span> {
<a name="l00515"></a>00515 init = <a class="code" href="namespacepolybori.html#c3aa221b482293e210dc2e595a2d69f3">dd_block_degree_lead</a>(cache_mgr, deg_mgr, navi.elseBranch(),
<a name="l00516"></a>00516 block_iter,
<a name="l00517"></a>00517 init, degree, prop);
<a name="l00518"></a>00518 }
<a name="l00519"></a>00519
<a name="l00520"></a>00520 NaviType resultNavi(init.navigation());
<a name="l00521"></a>00521 cache_mgr.insert(navi, resultNavi);
<a name="l00522"></a>00522 deg_mgr.insert(resultNavi, *block_iter, degree);
<a name="l00523"></a>00523
<a name="l00524"></a>00524 <span class="keywordflow">return</span> init;
<a name="l00525"></a>00525 }
<a name="l00526"></a>00526
<a name="l00527"></a>00527
<a name="l00528"></a>00528 <span class="keyword">template</span> <<span class="keyword">class </span>CacheType, <span class="keyword">class </span>DegCacheMgr, <span class="keyword">class </span>NaviType, <span class="keyword">class </span>Iterator,
<a name="l00529"></a>00529 <span class="keyword">class </span>TermType, <span class="keyword">class </span>DescendingProperty>
<a name="l00530"></a>00530 TermType
<a name="l00531"></a><a class="code" href="namespacepolybori.html#13472261afc223c55bb1b633c512bad0">00531</a> <a class="code" href="namespacepolybori.html#c3aa221b482293e210dc2e595a2d69f3">dd_block_degree_lead</a>(<span class="keyword">const</span> CacheType& cache_mgr, <span class="keyword">const</span> DegCacheMgr& deg_mgr,
<a name="l00532"></a>00532 NaviType navi, Iterator block_iter, TermType init,
<a name="l00533"></a>00533 DescendingProperty prop){
<a name="l00534"></a>00534
<a name="l00535"></a>00535 <span class="keywordflow">if</span> (navi.isConstant())
<a name="l00536"></a>00536 <span class="keywordflow">return</span> cache_mgr.generate(navi);
<a name="l00537"></a>00537
<a name="l00538"></a>00538 <span class="keywordflow">return</span> <a class="code" href="namespacepolybori.html#c3aa221b482293e210dc2e595a2d69f3">dd_block_degree_lead</a>(cache_mgr, deg_mgr, navi,block_iter, init,
<a name="l00539"></a>00539 <a class="code" href="namespacepolybori.html#3584bc11f3fe3a429096290a64d3a5fc">dd_cached_block_degree</a>(deg_mgr, navi,
<a name="l00540"></a>00540 *block_iter), prop);
<a name="l00541"></a>00541 }
<a name="l00542"></a>00542
<a name="l00543"></a>00543
<a name="l00544"></a>00544 <span class="keyword">template</span> <<span class="keyword">class </span>FirstIterator, <span class="keyword">class </span>SecondIterator, <span class="keyword">class </span>IdxType,
<a name="l00545"></a>00545 <span class="keyword">class </span>BinaryPredicate>
<a name="l00546"></a>00546 CTypes::comp_type
<a name="l00547"></a><a class="code" href="namespacepolybori.html#149f93ce4dc76f9f975bf33cfe7af155">00547</a> <a class="code" href="namespacepolybori.html#149f93ce4dc76f9f975bf33cfe7af155">restricted_lex_compare_3way</a>(FirstIterator start, FirstIterator finish,
<a name="l00548"></a>00548 SecondIterator rhs_start, SecondIterator rhs_finish,
<a name="l00549"></a>00549 IdxType max_index,
<a name="l00550"></a>00550 BinaryPredicate idx_comp) {
<a name="l00551"></a>00551
<a name="l00552"></a>00552 <span class="keywordflow">while</span> ( (start != finish) && (*start < max_index) && (rhs_start != rhs_finish)
<a name="l00553"></a>00553 && (*rhs_start < max_index) && (*start == *rhs_start) ) {
<a name="l00554"></a>00554 ++start; ++rhs_start;
<a name="l00555"></a>00555 }
<a name="l00556"></a>00556
<a name="l00557"></a>00557 <span class="keywordflow">if</span> ( (start == finish) || (*start >= max_index) ) {
<a name="l00558"></a>00558 <span class="keywordflow">if</span> ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
<a name="l00559"></a>00559 <span class="keywordflow">return</span> CTypes::equality;
<a name="l00560"></a>00560
<a name="l00561"></a>00561 <span class="keywordflow">return</span> CTypes::less_than;
<a name="l00562"></a>00562 }
<a name="l00563"></a>00563
<a name="l00564"></a>00564 <span class="keywordflow">if</span> ( (rhs_start == rhs_finish) || (*rhs_start >= max_index) )
<a name="l00565"></a>00565 <span class="keywordflow">return</span> CTypes::greater_than;
<a name="l00566"></a>00566
<a name="l00567"></a>00567 <span class="keywordflow">return</span> (idx_comp(*start, *rhs_start)?
<a name="l00568"></a>00568 CTypes::greater_than: CTypes::less_than);
<a name="l00569"></a>00569 }
<a name="l00570"></a>00570
<a name="l00571"></a>00571
<a name="l00572"></a>00572
<a name="l00573"></a>00573
<a name="l00574"></a>00574 <span class="keyword">template</span><<span class="keyword">class </span>LhsIterator, <span class="keyword">class </span>RhsIterator, <span class="keyword">class </span>Iterator,
<a name="l00575"></a>00575 <span class="keyword">class </span>BinaryPredicate>
<a name="l00576"></a>00576 CTypes::comp_type
<a name="l00577"></a><a class="code" href="namespacepolybori.html#b1ce4703b2763efb6a587c62ce208831">00577</a> <a class="code" href="namespacepolybori.html#b1ce4703b2763efb6a587c62ce208831">block_dlex_compare</a>(LhsIterator lhsStart, LhsIterator lhsFinish,
<a name="l00578"></a>00578 RhsIterator rhsStart, RhsIterator rhsFinish,
<a name="l00579"></a>00579 Iterator start, Iterator finish,
<a name="l00580"></a>00580 BinaryPredicate idx_comp) {
<a name="l00581"></a>00581
<a name="l00582"></a>00582 <span class="comment">// unsigned lhsdeg = 0, rhsdeg = 0;</span>
<a name="l00583"></a>00583
<a name="l00584"></a>00584
<a name="l00585"></a>00585 CTypes::comp_type result = CTypes::equality;
<a name="l00586"></a>00586
<a name="l00587"></a>00587 <span class="keywordflow">while</span> ( (start != finish) && (result == CTypes::equality) ) {
<a name="l00588"></a>00588 <span class="keywordtype">unsigned</span> lhsdeg = 0, rhsdeg = 0;
<a name="l00589"></a>00589 LhsIterator oldLhs(lhsStart); <span class="comment">// maybe one can save this and do both</span>
<a name="l00590"></a>00590 RhsIterator oldRhs(rhsStart); <span class="comment">// comparisons at once.</span>
<a name="l00591"></a>00591
<a name="l00592"></a>00592 <span class="comment">// maybe one can save </span>
<a name="l00593"></a>00593 <span class="keywordflow">while</span>( (lhsStart != lhsFinish) && (*lhsStart < *start) ) {
<a name="l00594"></a>00594 ++lhsStart; ++lhsdeg;
<a name="l00595"></a>00595 }
<a name="l00596"></a>00596 <span class="keywordflow">while</span>( (rhsStart != rhsFinish) && (*rhsStart < *start) ) {
<a name="l00597"></a>00597 ++rhsStart; ++rhsdeg;
<a name="l00598"></a>00598 }
<a name="l00599"></a>00599 result = <a class="code" href="namespacepolybori.html#5d5bac8b009548eb8ec17ca2f47eced8" title="defines lexicographic comparison for variable indices">generic_compare_3way</a>(lhsdeg, rhsdeg,
<a name="l00600"></a>00600 std::greater<unsigned>() );
<a name="l00601"></a>00601
<a name="l00602"></a>00602 <span class="keywordflow">if</span> (result == CTypes::equality) {
<a name="l00603"></a>00603 result = <a class="code" href="namespacepolybori.html#149f93ce4dc76f9f975bf33cfe7af155">restricted_lex_compare_3way</a>(oldLhs, lhsFinish,
<a name="l00604"></a>00604 oldRhs, rhsFinish, *start, idx_comp);
<a name="l00605"></a>00605 }
<a name="l00606"></a>00606
<a name="l00607"></a>00607 ++start;
<a name="l00608"></a>00608 }
<a name="l00609"></a>00609
<a name="l00610"></a>00610 <span class="keywordflow">return</span> result;
<a name="l00611"></a>00611 }
<a name="l00612"></a>00612
<a name="l00613"></a>00613
<a name="l00615"></a>00615 <span class="keyword">template</span> <<span class="keyword">class</span> IdxType, <span class="keyword">class</span> Iterator, <span class="keyword">class</span> BinaryPredicate>
<a name="l00616"></a>00616 CTypes::comp_type
<a name="l00617"></a><a class="code" href="namespacepolybori.html#d90ffa1658918f79156a9fb5d8e21fc4">00617</a> <a class="code" href="namespacepolybori.html#d90ffa1658918f79156a9fb5d8e21fc4">block_deg_lex_idx_compare</a>(IdxType lhs, IdxType rhs,
<a name="l00618"></a>00618 Iterator start, Iterator finish,
<a name="l00619"></a>00619 BinaryPredicate idx_comp) {
<a name="l00620"></a>00620
<a name="l00621"></a>00621 <span class="keywordflow">if</span> (lhs == rhs)
<a name="l00622"></a>00622 <span class="keywordflow">return</span> CTypes::equality;
<a name="l00623"></a>00623
<a name="l00624"></a>00624 Iterator lhsend = std::find_if(start, finish,
<a name="l00625"></a>00625 std::bind2nd(std::greater<IdxType>(), lhs));
<a name="l00626"></a>00626
<a name="l00627"></a>00627
<a name="l00628"></a>00628 Iterator rhsend = std::find_if(start, finish,
<a name="l00629"></a>00629 std::bind2nd(std::greater<IdxType>(), rhs));
<a name="l00630"></a>00630
<a name="l00631"></a>00631 assert((lhsend != finish) && (rhsend != finish));
<a name="l00632"></a>00632
<a name="l00633"></a>00633 CTypes::comp_type result = <a class="code" href="namespacepolybori.html#5d5bac8b009548eb8ec17ca2f47eced8" title="defines lexicographic comparison for variable indices">generic_compare_3way</a>( *lhsend, *rhsend,
<a name="l00634"></a>00634 std::less<IdxType>() );
<a name="l00635"></a>00635
<a name="l00636"></a>00636 <span class="keywordflow">return</span> ( result == CTypes::equality?
<a name="l00637"></a>00637 <a class="code" href="namespacepolybori.html#5d5bac8b009548eb8ec17ca2f47eced8" title="defines lexicographic comparison for variable indices">generic_compare_3way</a>(lhs, rhs, idx_comp): result );
<a name="l00638"></a>00638 }
<a name="l00639"></a>00639
<a name="l00640"></a>00640 <a class="code" href="pbori__defs_8h.html#faf094fde6c1a7f1aad18bcb455f3b06" title="Finish project&#39;s namespace.">END_NAMESPACE_PBORI</a>
</pre></div></div>
<hr size="1"><address style="text-align: right;"><small>Generated on Wed Sep 9 14:30:59 2009 for PolyBoRi by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.9 </small></address>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
a24e1a39141f9b4ca49bd1e2e23a54ba
>
files
>
827
