<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Crystal Space 1.2.1: csutil/partialorder.h Source File (Crystal Space 1.2.1 Public API Reference)</title>
<link href="tabs.css" rel="stylesheet" type="text/css">
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<table border="0" cellpadding="0" cellspacing="0" width="100%" class="head">
<tr height="59">
<td class="head" width="202" valign="bottom" style="padding-left:0;"><a href="http://www.crystalspace3d.org/"><img src="csblur.png" width="236" height="59" alt="CrystalSpace" border="0"></a></td>
<td class="head"><h2>Public API Reference</h2></td>
</tr>
<tr height="11">
<td colspan="2" class="headshadow" valign="top" style="padding-left:0;"><img src="csblurb.png" width="236" height="11" alt="" border="0"></td>
</tr>
</table>
<div class="content">
<!-- Generated by Doxygen 1.5.3 -->
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="classes.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
</ul>
</div>
<h1>csutil/partialorder.h</h1><a href="partialorder_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/* -*- Mode: C++; c-basic-offset: 2 -*-</span>
<a name="l00002"></a>00002 <span class="comment"> Copyright (C) 2005 by Adam D. Bradley <artdodge@cs.bu.edu></span>
<a name="l00003"></a>00003 <span class="comment"> </span>
<a name="l00004"></a>00004 <span class="comment"> This library is free software; you can redistribute it and/or</span>
<a name="l00005"></a>00005 <span class="comment"> modify it under the terms of the GNU Lesser General Public</span>
<a name="l00006"></a>00006 <span class="comment"> License as published by the Free Software Foundation; either</span>
<a name="l00007"></a>00007 <span class="comment"> version 2 of the License, or (at your option) any later version.</span>
<a name="l00008"></a>00008 <span class="comment"> </span>
<a name="l00009"></a>00009 <span class="comment"> This library is distributed in the hope that it will be useful,</span>
<a name="l00010"></a>00010 <span class="comment"> but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00011"></a>00011 <span class="comment"> MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</span>
<a name="l00012"></a>00012 <span class="comment"> Library General Public License for more details.</span>
<a name="l00013"></a>00013 <span class="comment"> </span>
<a name="l00014"></a>00014 <span class="comment"> You should have received a copy of the GNU Library General Public</span>
<a name="l00015"></a>00015 <span class="comment"> License along with this library; if not, write to the Free</span>
<a name="l00016"></a>00016 <span class="comment"> Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.</span>
<a name="l00017"></a>00017 <span class="comment">*/</span>
<a name="l00018"></a>00018
<a name="l00019"></a>00019 <span class="preprocessor">#ifndef __CS_UTIL_PO_H__</span>
<a name="l00020"></a>00020 <span class="preprocessor"></span><span class="preprocessor">#define __CS_UTIL_PO_H__</span>
<a name="l00021"></a>00021 <span class="preprocessor"></span>
<a name="l00026"></a>00026 <span class="preprocessor">#include "csextern.h"</span>
<a name="l00027"></a>00027 <span class="preprocessor">#include "<a class="code" href="csutil_2array_8h.html" title="Generic Array Template.">csutil/array.h</a>"</span>
<a name="l00028"></a>00028 <span class="preprocessor">#include "<a class="code" href="comparator_8h.html" title="Template providing various comparison and ordering functions.">csutil/comparator.h</a>"</span>
<a name="l00029"></a>00029 <span class="preprocessor">#include "<a class="code" href="hash_8h.html" title="A generic hash table.">csutil/hash.h</a>"</span>
<a name="l00030"></a>00030 <span class="preprocessor">#include "<a class="code" href="list_8h.html" title="Double-linked list.">csutil/list.h</a>"</span>
<a name="l00031"></a>00031 <span class="preprocessor">#include "<a class="code" href="ref_8h.html" title="Smart Pointers.">csutil/ref.h</a>"</span>
<a name="l00032"></a>00032 <span class="preprocessor">#include "<a class="code" href="util_8h.html" title="Miscellaneous utilities.">csutil/util.h</a>"</span>
<a name="l00033"></a>00033
<a name="l00034"></a>00034 <span class="preprocessor">#ifdef ADB_DEBUG</span>
<a name="l00035"></a>00035 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="csutil_2eventhandlers_8h.html" title="Event handler naming, name management, indexing, and instantiation.">csutil/eventhandlers.h</a>"</span>
<a name="l00036"></a>00036 <span class="preprocessor">#include <iostream></span>
<a name="l00037"></a>00037 <span class="preprocessor">#endif </span><span class="comment">/* ADB_DEBUG */</span>
<a name="l00038"></a>00038
<a name="l00051"></a>00051 <span class="keyword">template</span> <<span class="keyword">class</span> T>
<a name="l00052"></a><a class="code" href="classcsPartialOrder.html">00052</a> <span class="keyword">class </span>CS_CRYSTALSPACE_EXPORT <a class="code" href="classcsPartialOrder.html" title="A generic finite partial order class.">csPartialOrder</a>
<a name="l00053"></a>00053 {
<a name="l00054"></a>00054 <span class="keyword">protected</span>:
<a name="l00055"></a><a class="code" href="classcsPartialOrder_1_1Node.html">00055</a> <span class="keyword">class </span><a class="code" href="classcsPartialOrder_1_1Node.html">Node</a>
<a name="l00056"></a>00056 {
<a name="l00057"></a>00057 <span class="keyword">public</span>:
<a name="l00058"></a><a class="code" href="classcsPartialOrder_1_1Node.html#ddda51e2a8dfdefd5bc502827713f0e1">00058</a> <a class="code" href="classcsPartialOrder_1_1Node.html">Node</a>(<span class="keyword">const</span> <a class="code" href="classcsPartialOrder_1_1Node.html">Node</a> &other)
<a name="l00059"></a>00059 : self(other.self), output(other.output),
<a name="l00060"></a>00060 marked(other.marked),
<a name="l00061"></a>00061 pre(other.pre), post(other.post)
<a name="l00062"></a>00062 { }
<a name="l00063"></a><a class="code" href="classcsPartialOrder_1_1Node.html#3dd05334d426ba512f0c75327d39add7">00063</a> <a class="code" href="classcsPartialOrder_1_1Node.html">Node</a>(<span class="keyword">const</span> T &<span class="keywordtype">id</span>)
<a name="l00064"></a>00064 : self(id), output(false), marked(false),
<a name="l00065"></a>00065 pre(), post()
<a name="l00066"></a>00066 { }
<a name="l00067"></a><a class="code" href="classcsPartialOrder_1_1Node.html#00c2c7d8c56be36e08ece05ab213933c">00067</a> <span class="keyword">const</span> T <span class="keyword">self</span>;
<a name="l00068"></a><a class="code" href="classcsPartialOrder_1_1Node.html#a4028b196ed3996807371d91b68272b6">00068</a> <span class="keywordtype">bool</span> output;
<a name="l00069"></a><a class="code" href="classcsPartialOrder_1_1Node.html#4d35cbb7ed18f5e0f936b081db735b2d">00069</a> <span class="keywordtype">bool</span> marked;
<a name="l00070"></a><a class="code" href="classcsPartialOrder_1_1Node.html#26f57a7dcc7de54ab1825d1ea7af5e84">00070</a> <a class="code" href="classcsArray.html" title="A templated array class.">csArray<size_t></a> pre;
<a name="l00071"></a><a class="code" href="classcsPartialOrder_1_1Node.html#481004251b133289d292e7e86d3b5ab3">00071</a> <a class="code" href="classcsArray.html" title="A templated array class.">csArray<size_t></a> post;
<a name="l00072"></a>00072 };
<a name="l00073"></a><a class="code" href="classcsPartialOrder.html#8adaefa03d5ee93ca042496c5477c976">00073</a> <a class="code" href="classcsArray.html" title="A templated array class.">csArray<Node></a> Nodes;
<a name="l00074"></a><a class="code" href="classcsPartialOrder.html#40387ebdcee22aa03f91b9e48253025a">00074</a> <a class="code" href="classcsHash.html" title="A generic hash table class, which grows dynamically and whose buckets are unsorted...">csHash<size_t,const T></a> NodeMap;
<a name="l00075"></a>00075
<a name="l00076"></a>00076 <span class="keyword">public</span>:
<a name="l00078"></a><a class="code" href="classcsPartialOrder.html#74776d0e1abc139c8d1d37fa32562e9a">00078</a> <a class="code" href="classcsPartialOrder.html" title="A generic finite partial order class.">csPartialOrder</a> ()
<a name="l00079"></a>00079 : Nodes (), NodeMap()
<a name="l00080"></a>00080 {
<a name="l00081"></a>00081 <span class="keywordflow">return</span>;
<a name="l00082"></a>00082 }
<a name="l00083"></a>00083
<a name="l00085"></a><a class="code" href="classcsPartialOrder.html#c049ed09a49c6bc15c02fed6c964541f">00085</a> <a class="code" href="classcsPartialOrder.html" title="A generic finite partial order class.">csPartialOrder</a>(<span class="keyword">const</span> <a class="code" href="classcsPartialOrder.html" title="A generic finite partial order class.">csPartialOrder</a> &other)
<a name="l00086"></a>00086 : Nodes (other.Nodes), NodeMap (other.NodeMap)
<a name="l00087"></a>00087 {
<a name="l00088"></a>00088 <span class="keywordflow">return</span>;
<a name="l00089"></a>00089 }
<a name="l00090"></a>00090
<a name="l00091"></a>00091 <span class="preprocessor">#ifdef ADB_DEBUG</span>
<a name="l00092"></a>00092 <span class="preprocessor"></span> <span class="comment">// This code is particular to the csHandlerID scheduler.</span>
<a name="l00093"></a>00093 <span class="keywordtype">void</span> Dump (<a class="code" href="structiObjectRegistry.html" title="This interface serves as a registry of other objects.">iObjectRegistry</a> *objreg)
<a name="l00094"></a>00094 {
<a name="l00095"></a>00095 std::cerr << <span class="stringliteral">"Dumping PO Graph..."</span> << std::endl;
<a name="l00096"></a>00096 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes.GetSize () ; i++)
<a name="l00097"></a>00097 {
<a name="l00098"></a>00098 std::cerr << <span class="stringliteral">" NODE: "</span> << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Nodes[i].<span class="keyword">self</span>) << std::endl;
<a name="l00099"></a>00099 std::cerr << <span class="stringliteral">" pre: "</span>;
<a name="l00100"></a>00100 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> j=0 ; j<Nodes[i].pre.GetSize () ; j++)
<a name="l00101"></a>00101 {
<a name="l00102"></a>00102 std::cerr << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Nodes[Nodes[i].pre[j]].<span class="keyword">self</span>) << <span class="stringliteral">" "</span>;
<a name="l00103"></a>00103 }
<a name="l00104"></a>00104 std::cerr << std::endl << <span class="stringliteral">" post: "</span>;
<a name="l00105"></a>00105 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> j=0 ; j<Nodes[i].post.GetSize () ; j++)
<a name="l00106"></a>00106 {
<a name="l00107"></a>00107 std::cerr << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Nodes[Nodes[i].post[j]].<span class="keyword">self</span>) << <span class="stringliteral">" "</span>;
<a name="l00108"></a>00108 }
<a name="l00109"></a>00109 std::cerr << std::endl;
<a name="l00110"></a>00110 }
<a name="l00111"></a>00111 std::cerr << <span class="stringliteral">"End PO Graph, printing a solution..."</span> << std::endl;
<a name="l00112"></a>00112 <a class="code" href="classcsList.html" title="A lightweight double-linked list template.">csList<const T></a> Solution;
<a name="l00113"></a>00113 Solve (Solution);
<a name="l00114"></a>00114 <span class="keywordflow">while</span> (!Solution.<a class="code" href="classcsList.html#7a7b6e76147c34c1f6b8e2b3cb33167e">IsEmpty</a> ())
<a name="l00115"></a>00115 {
<a name="l00116"></a>00116 std::cerr << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Solution.<a class="code" href="classcsList.html#2470e0f3c9b2e5c5810ab23c13a1af98" title="Return first element of the list.">Front</a>()) << <span class="stringliteral">" "</span>;
<a name="l00117"></a>00117 Solution.<a class="code" href="classcsList.html#3ba57d74ccf1ee850b343f4dcc7bd383" title="Deletes the first element of the list.">PopFront</a>();
<a name="l00118"></a>00118 }
<a name="l00119"></a>00119 std::cerr << std::endl << <span class="stringliteral">"Done."</span> << std::endl << std::endl;
<a name="l00120"></a>00120 }
<a name="l00121"></a>00121 <span class="preprocessor">#endif </span><span class="comment">/* ADB_DEBUG */</span>
<a name="l00122"></a>00122
<a name="l00124"></a><a class="code" href="classcsPartialOrder.html#498c0364f7640329afb86ab2c7476e7e">00124</a> <a class="code" href="classcsPartialOrder.html" title="A generic finite partial order class.">csPartialOrder</a>(<span class="keyword">const</span> <a class="code" href="classcsPartialOrder.html" title="A generic finite partial order class.">csPartialOrder</a> *other)
<a name="l00125"></a>00125 : Nodes (other->Nodes), NodeMap (other->NodeMap)
<a name="l00126"></a>00126 {
<a name="l00127"></a>00127 <span class="keywordflow">return</span>;
<a name="l00128"></a>00128 }
<a name="l00129"></a>00129
<a name="l00131"></a><a class="code" href="classcsPartialOrder.html#65d4a11892772a892de83773fef1b399">00131</a> <span class="keywordtype">void</span> Add (<span class="keyword">const</span> T& node)
<a name="l00132"></a>00132 {
<a name="l00133"></a>00133 SanityCheck();
<a name="l00134"></a>00134 <span class="keywordflow">if</span> (NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>) == <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>)
<a name="l00135"></a>00135 {
<a name="l00136"></a>00136 NodeMap.PutUnique(node, Nodes.Push(node));
<a name="l00137"></a>00137 }
<a name="l00138"></a>00138 SanityCheck();
<a name="l00139"></a>00139 }
<a name="l00140"></a>00140
<a name="l00142"></a><a class="code" href="classcsPartialOrder.html#7f0eb5707007485b7f04460d2de00cff">00142</a> <span class="keywordtype">bool</span> Contains (<span class="keyword">const</span> T& node)
<a name="l00143"></a>00143 {
<a name="l00144"></a>00144 <span class="keywordflow">return</span> (NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>) != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00145"></a>00145 }
<a name="l00146"></a>00146
<a name="l00148"></a><a class="code" href="classcsPartialOrder.html#a2d8b4105fbbad447276689fe057a775">00148</a> <span class="keywordtype">bool</span> Contains (<span class="keyword">const</span> T& pre, <span class="keyword">const</span> T& post)
<a name="l00149"></a>00149 {
<a name="l00150"></a>00150 <span class="keywordflow">if</span> (!Contains (pre) || !Contains (post))
<a name="l00151"></a>00151 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00152"></a>00152 <span class="keywordtype">size_t</span> PreIdx = NodeMap.Get (pre, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00153"></a>00153 <span class="keywordtype">size_t</span> PostIdx = NodeMap.Get (post, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00154"></a>00154 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes[PreIdx].post.GetSize () ; i++)
<a name="l00155"></a>00155 {
<a name="l00156"></a>00156 <span class="keywordflow">if</span> (Nodes[PreIdx].post[i] == PostIdx)
<a name="l00157"></a>00157 {
<a name="l00158"></a>00158 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00159"></a>00159 }
<a name="l00160"></a>00160 }
<a name="l00161"></a>00161 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00162"></a>00162 }
<a name="l00163"></a>00163
<a name="l00165"></a><a class="code" href="classcsPartialOrder.html#e8942b40daf0f0e751493e41616b3f87">00165</a> <span class="keywordtype">void</span> Delete (<span class="keyword">const</span> T& node)
<a name="l00166"></a>00166 {
<a name="l00167"></a>00167 SanityCheck();
<a name="l00168"></a>00168 <span class="keywordtype">size_t</span> p = NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00169"></a>00169 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(p!=<a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00170"></a>00170 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(p < Nodes.GetSize ());
<a name="l00171"></a>00171 <span class="comment">// delete all posts pointing to node</span>
<a name="l00172"></a>00172 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter=0 ; iter<Nodes[p].pre.GetSize () ; iter++)
<a name="l00173"></a>00173 {
<a name="l00174"></a>00174 Nodes[Nodes[p].pre[iter]].post.Delete(p);
<a name="l00175"></a>00175 }
<a name="l00176"></a>00176 <span class="comment">// delete node's pre's</span>
<a name="l00177"></a>00177 Nodes[p].pre.DeleteAll();
<a name="l00178"></a>00178 <span class="comment">// delete all pres pointing to node</span>
<a name="l00179"></a>00179 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter=0 ; iter<Nodes[p].post.GetSize () ; iter++)
<a name="l00180"></a>00180 {
<a name="l00181"></a>00181 Nodes[Nodes[p].post[iter]].pre.Delete(p);
<a name="l00182"></a>00182 }
<a name="l00183"></a>00183 <span class="comment">// delete node's post's</span>
<a name="l00184"></a>00184 Nodes[p].post.DeleteAll();
<a name="l00185"></a>00185 <span class="comment">// delete node p, move the node at the end of the csArray into its place...</span>
<a name="l00186"></a>00186 Nodes.DeleteIndexFast(p);
<a name="l00187"></a>00187
<a name="l00188"></a>00188 <span class="comment">// update NodeMap accordingly by killing the lookup for the deleted node</span>
<a name="l00189"></a>00189 <span class="comment">// and updating the lookup for the node that moved into its place...</span>
<a name="l00190"></a>00190 NodeMap.Delete(node, p);
<a name="l00191"></a>00191 <span class="keywordflow">if</span> (Nodes.GetSize () > p)
<a name="l00192"></a>00192 {
<a name="l00193"></a>00193 <span class="comment">// who got moved into "p"?</span>
<a name="l00194"></a>00194 <span class="keywordtype">size_t</span> moved = NodeMap.Get(Nodes[p].<span class="keyword">self</span>, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00195"></a>00195 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a> (moved != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00196"></a>00196
<a name="l00197"></a>00197 <span class="comment">// change references to "moved" to reference "p"</span>
<a name="l00198"></a>00198 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter=0 ; iter<Nodes.GetSize () ; iter++)
<a name="l00199"></a>00199 {
<a name="l00200"></a>00200 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter2=0 ; iter2<Nodes[iter].pre.GetSize () ; iter2++)
<a name="l00201"></a>00201 {
<a name="l00202"></a>00202 <span class="keywordflow">if</span> (Nodes[iter].pre[iter2] == moved)
<a name="l00203"></a>00203 Nodes[iter].pre[iter2] = p;
<a name="l00204"></a>00204 }
<a name="l00205"></a>00205 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter2=0 ; iter2<Nodes[iter].post.GetSize () ; iter2++)
<a name="l00206"></a>00206 {
<a name="l00207"></a>00207 <span class="keywordflow">if</span> (Nodes[iter].post[iter2] == moved)
<a name="l00208"></a>00208 Nodes[iter].post[iter2] = p;
<a name="l00209"></a>00209 }
<a name="l00210"></a>00210 }
<a name="l00211"></a>00211 NodeMap.Delete(Nodes[p].<span class="keyword">self</span>, moved);
<a name="l00212"></a>00212 NodeMap.PutUnique(Nodes[p].<span class="keyword">self</span>, p);
<a name="l00213"></a>00213 }
<a name="l00214"></a>00214
<a name="l00215"></a>00215 SanityCheck();
<a name="l00216"></a>00216 }
<a name="l00217"></a>00217
<a name="l00224"></a><a class="code" href="classcsPartialOrder.html#59f8261061cd5bcd4a4b1db83c11406c">00224</a> <span class="keywordtype">bool</span> AddOrder (<span class="keyword">const</span> T& node1, <span class="keyword">const</span> T& node2)
<a name="l00225"></a>00225 {
<a name="l00226"></a>00226 SanityCheck();
<a name="l00227"></a>00227 <span class="keywordtype">size_t</span> n1 = NodeMap.Get(node1, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00228"></a>00228 <span class="keywordtype">size_t</span> n2 = NodeMap.Get(node2, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00229"></a>00229 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(n1 != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00230"></a>00230 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(n2 != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00231"></a>00231
<a name="l00232"></a>00232 <span class="comment">/* make the forward link "n1->n2" */</span>
<a name="l00233"></a>00233 Nodes[n1].post.Push(n2);
<a name="l00234"></a>00234
<a name="l00235"></a>00235 <span class="keywordflow">if</span> (InternalCycleTest(n1))
<a name="l00236"></a>00236 {
<a name="l00237"></a>00237 <span class="comment">/* undo our mischief and report failure */</span>
<a name="l00238"></a>00238 Nodes[n1].post.Pop();
<a name="l00239"></a>00239 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00240"></a>00240 }
<a name="l00241"></a>00241 <span class="keywordflow">else</span>
<a name="l00242"></a>00242 {
<a name="l00243"></a>00243 <span class="comment">/* make the paired pre link "n2<-n1" */</span>
<a name="l00244"></a>00244 Nodes[n2].pre.Push(n1);
<a name="l00245"></a>00245 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00246"></a>00246 }
<a name="l00247"></a>00247 SanityCheck();
<a name="l00248"></a>00248 }
<a name="l00249"></a>00249
<a name="l00251"></a><a class="code" href="classcsPartialOrder.html#6b7a8dfe6fa9e3a909c1a2a275abf58a">00251</a> <span class="keywordtype">void</span> DeleteOrder (<span class="keyword">const</span> T& node1, <span class="keyword">const</span> T& node2)
<a name="l00252"></a>00252 {
<a name="l00253"></a>00253 SanityCheck();
<a name="l00254"></a>00254 <span class="keywordtype">size_t</span> n1 = NodeMap.Get(node1, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00255"></a>00255 <span class="keywordtype">size_t</span> n2 = NodeMap.Get(node2, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00256"></a>00256 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(n1 != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00257"></a>00257 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(n2 != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00258"></a>00258 Nodes[n2].pre.DeleteFast(n1);
<a name="l00259"></a>00259 Nodes[n1].post.DeleteFast(n2);
<a name="l00260"></a>00260 SanityCheck();
<a name="l00261"></a>00261 }
<a name="l00262"></a>00262
<a name="l00264"></a><a class="code" href="classcsPartialOrder.html#f0fe0b0bcd5835fa7cfee9def815f2ba">00264</a> <span class="keywordtype">size_t</span> Size ()
<a name="l00265"></a>00265 {
<a name="l00266"></a>00266 <span class="keywordflow">return</span> Nodes.GetSize ();
<a name="l00267"></a>00267 }
<a name="l00268"></a>00268
<a name="l00270"></a><a class="code" href="classcsPartialOrder.html#b690c9faa3674e0e5a42d8858a282db5">00270</a> <span class="keyword">const</span> T GetByIndex(<span class="keywordtype">size_t</span> i)
<a name="l00271"></a>00271 {
<a name="l00272"></a>00272 <span class="keywordflow">return</span> Nodes[i].self;
<a name="l00273"></a>00273 }
<a name="l00274"></a>00274
<a name="l00279"></a><a class="code" href="classcsPartialOrder.html#d91a8f82306af55c5cf5e29134b500e3">00279</a> <span class="keywordtype">void</span> Solve (<a class="code" href="classcsList.html" title="A lightweight double-linked list template.">csList<const T></a> & result)
<a name="l00280"></a>00280 {
<a name="l00281"></a>00281 SanityCheck();
<a name="l00282"></a>00282 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter=0 ; iter<Nodes.GetSize () ; iter++)
<a name="l00283"></a>00283 {
<a name="l00284"></a>00284 Nodes[iter].output = <span class="keyword">false</span>;
<a name="l00285"></a>00285 }
<a name="l00286"></a>00286 result.<a class="code" href="classcsList.html#492cbe560e1a91585f84d49d8d1ed563" title="Empty an list.">DeleteAll</a>();
<a name="l00287"></a>00287 <span class="keywordtype">bool</span> done;
<a name="l00288"></a>00288 <span class="keywordflow">do</span>
<a name="l00289"></a>00289 {
<a name="l00290"></a>00290 done = <span class="keyword">true</span>;
<a name="l00291"></a>00291 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> iter=0 ; iter<Nodes.GetSize () ; iter++)
<a name="l00292"></a>00292 {
<a name="l00293"></a>00293 <span class="keywordflow">if</span> (Nodes[iter].output == <span class="keyword">false</span>)
<a name="l00294"></a>00294 {
<a name="l00295"></a>00295 <span class="keywordtype">int</span> canoutput = <span class="keyword">true</span>;
<a name="l00296"></a>00296 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i2=0 ; i2<Nodes[iter].pre.GetSize () ; i2++)
<a name="l00297"></a>00297 {
<a name="l00298"></a>00298 <span class="keywordflow">if</span> (!Nodes[Nodes[iter].pre[i2]].output)
<a name="l00299"></a>00299 {
<a name="l00300"></a>00300 canoutput = <span class="keyword">false</span>;
<a name="l00301"></a>00301 <span class="keywordflow">break</span>;
<a name="l00302"></a>00302 }
<a name="l00303"></a>00303 }
<a name="l00304"></a>00304 <span class="keywordflow">if</span> (canoutput)
<a name="l00305"></a>00305 {
<a name="l00306"></a>00306 result.<a class="code" href="classcsList.html#02303fc82d290f9bf65e7c3117fd5799" title="Add an item last in list. Copy T into the listdata.">PushBack</a>(Nodes[iter].<span class="keyword">self</span>);
<a name="l00307"></a>00307 Nodes[iter].output = <span class="keyword">true</span>;
<a name="l00308"></a>00308 }
<a name="l00309"></a>00309 <span class="keywordflow">else</span>
<a name="l00310"></a>00310 {
<a name="l00311"></a>00311 done = <span class="keyword">false</span>;
<a name="l00312"></a>00312 }
<a name="l00313"></a>00313 }
<a name="l00314"></a>00314 }
<a name="l00315"></a>00315 }
<a name="l00316"></a>00316 <span class="keywordflow">while</span> (!done);
<a name="l00317"></a>00317 SanityCheck();
<a name="l00318"></a>00318 }
<a name="l00319"></a>00319
<a name="l00324"></a><a class="code" href="classcsPartialOrder.html#343c1d3e9ab33e351b3079566d732453">00324</a> <span class="keywordtype">void</span> Mark (<span class="keyword">const</span> T& node)
<a name="l00325"></a>00325 {
<a name="l00326"></a>00326 <span class="keywordtype">size_t</span> i = NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00327"></a>00327 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00328"></a>00328 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i < Nodes.GetSize ());
<a name="l00329"></a>00329 Nodes[i].marked = <span class="keyword">true</span>;
<a name="l00330"></a>00330 }
<a name="l00331"></a>00331
<a name="l00335"></a><a class="code" href="classcsPartialOrder.html#c721d05bef4034c47ab13e61b5cc71b5">00335</a> <span class="keywordtype">bool</span> IsMarked (<span class="keyword">const</span> T& node)
<a name="l00336"></a>00336 {
<a name="l00337"></a>00337 <span class="keywordtype">size_t</span> i = NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00338"></a>00338 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00339"></a>00339 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i < Nodes.GetSize ());
<a name="l00340"></a>00340 <span class="keywordflow">return</span> Nodes[i].marked;
<a name="l00341"></a>00341 }
<a name="l00342"></a>00342
<a name="l00346"></a><a class="code" href="classcsPartialOrder.html#53b49d62606991fd51c58703c917fed5">00346</a> <span class="keywordtype">void</span> ClearMark (<span class="keyword">const</span> T& node)
<a name="l00347"></a>00347 {
<a name="l00348"></a>00348 <span class="keywordtype">size_t</span> i = NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00349"></a>00349 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00350"></a>00350 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i < Nodes.GetSize ());
<a name="l00351"></a>00351 Nodes[i].marked = <span class="keyword">false</span>;
<a name="l00352"></a>00352 }
<a name="l00353"></a>00353
<a name="l00357"></a><a class="code" href="classcsPartialOrder.html#a5a51a4c110addc4e962ee32e541009e">00357</a> <span class="keywordtype">void</span> ClearMark ()
<a name="l00358"></a>00358 {
<a name="l00359"></a>00359 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes.GetSize () ; i++)
<a name="l00360"></a>00360 {
<a name="l00361"></a>00361 Nodes[i].marked = <span class="keyword">false</span>;
<a name="l00362"></a>00362 }
<a name="l00363"></a>00363 }
<a name="l00364"></a>00364
<a name="l00369"></a><a class="code" href="classcsPartialOrder.html#3182ef0737a36dae86152ce3fc05f0c7">00369</a> <span class="keywordtype">bool</span> IsEnabled(<span class="keyword">const</span> T& node)
<a name="l00370"></a>00370 {
<a name="l00371"></a>00371 <span class="keywordtype">size_t</span> i = NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00372"></a>00372 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(i != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00373"></a>00373 <span class="keywordflow">return</span> InternalIsEnabled(i);
<a name="l00374"></a>00374 }
<a name="l00375"></a>00375
<a name="l00379"></a><a class="code" href="classcsPartialOrder.html#975de72526be86e223f1cc651815f602">00379</a> <span class="keywordtype">bool</span> HasEnabled()
<a name="l00380"></a>00380 {
<a name="l00381"></a>00381 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes.GetSize () ; i++)
<a name="l00382"></a>00382 {
<a name="l00383"></a>00383 <span class="keywordflow">if</span> (InternalIsEnabled(i))
<a name="l00384"></a>00384 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00385"></a>00385 }
<a name="l00386"></a>00386 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00387"></a>00387 }
<a name="l00388"></a>00388
<a name="l00392"></a><a class="code" href="classcsPartialOrder.html#3948a1cf8b69d0de21d8f3f586c5a74b">00392</a> <span class="keyword">const</span> T GetEnabled(T fail)
<a name="l00393"></a>00393 {
<a name="l00394"></a>00394 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes.GetSize () ; i++)
<a name="l00395"></a>00395 {
<a name="l00396"></a>00396 <span class="keywordflow">if</span> (InternalIsEnabled(i))
<a name="l00397"></a>00397 <span class="keywordflow">return</span> Nodes[i].<span class="keyword">self</span>;
<a name="l00398"></a>00398 }
<a name="l00399"></a>00399 <span class="keywordflow">return</span> fail;
<a name="l00400"></a>00400 }
<a name="l00401"></a>00401
<a name="l00402"></a>00402 <span class="keyword">protected</span>:
<a name="l00403"></a><a class="code" href="classcsPartialOrder.html#9a2af761ae85027f8ef28fe70818ae12">00403</a> <span class="keywordtype">void</span> SanityCheck ()
<a name="l00404"></a>00404 {
<a name="l00405"></a>00405 <span class="preprocessor">#ifdef CS_DEBUG</span>
<a name="l00406"></a>00406 <span class="preprocessor"></span> <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"NodeMap has different size from Node list"</span>,
<a name="l00407"></a>00407 NodeMap.GetSize() == Nodes.GetSize ());
<a name="l00408"></a>00408 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i1=0; i1<Nodes.GetSize () ; i1++)
<a name="l00409"></a>00409 {
<a name="l00410"></a>00410 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"NodeMap names wrong location for node"</span>,
<a name="l00411"></a>00411 NodeMap.Get(Nodes[i1].self, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>) == i1);
<a name="l00412"></a>00412 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i2=0 ; i2<Nodes[i1].pre.GetSize () ; i2++)
<a name="l00413"></a>00413 {
<a name="l00414"></a>00414 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"Node prefix index less than zero"</span>,
<a name="l00415"></a>00415 Nodes[i1].pre[i2] >= 0);
<a name="l00416"></a>00416 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"Node prefix index larger than Nodes list"</span>,
<a name="l00417"></a>00417 Nodes[i1].pre[i2] < Nodes.GetSize ());
<a name="l00418"></a>00418 <span class="keywordtype">bool</span> reciprocal_post_exists = <span class="keyword">false</span>;
<a name="l00419"></a>00419 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i3=0 ; i3<Nodes[Nodes[i1].pre[i2]].post.GetSize () ; i3++)
<a name="l00420"></a>00420 {
<a name="l00421"></a>00421 <span class="keywordflow">if</span> (Nodes[Nodes[i1].pre[i2]].post[i3] == i1)
<a name="l00422"></a>00422 {
<a name="l00423"></a>00423 reciprocal_post_exists = <span class="keyword">true</span>;
<a name="l00424"></a>00424 <span class="keywordflow">break</span>;
<a name="l00425"></a>00425 }
<a name="l00426"></a>00426 }
<a name="l00427"></a>00427 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"Node prefix does not have reciprocal postfix"</span>,
<a name="l00428"></a>00428 reciprocal_post_exists);
<a name="l00429"></a>00429 }
<a name="l00430"></a>00430 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i2=0 ; i2<Nodes[i1].post.GetSize () ; i2++)
<a name="l00431"></a>00431 {
<a name="l00432"></a>00432 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"Node postfix index less than zero"</span>,
<a name="l00433"></a>00433 Nodes[i1].post[i2] >= 0);
<a name="l00434"></a>00434 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"Node postfix index larger than Nodes list"</span>,
<a name="l00435"></a>00435 Nodes[i1].post[i2] < Nodes.GetSize ());
<a name="l00436"></a>00436 <span class="keywordtype">bool</span> reciprocal_pre_exists = <span class="keyword">false</span>;
<a name="l00437"></a>00437 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i3=0 ; i3<Nodes[Nodes[i1].post[i2]].pre.GetSize () ; i3++)
<a name="l00438"></a>00438 {
<a name="l00439"></a>00439 <span class="keywordflow">if</span> (Nodes[Nodes[i1].post[i2]].pre[i3] == i1)
<a name="l00440"></a>00440 {
<a name="l00441"></a>00441 reciprocal_pre_exists = <span class="keyword">true</span>;
<a name="l00442"></a>00442 <span class="keywordflow">break</span>;
<a name="l00443"></a>00443 }
<a name="l00444"></a>00444 }
<a name="l00445"></a>00445 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"Node postfix does not have reciprocal prefix"</span>,
<a name="l00446"></a>00446 reciprocal_pre_exists);
<a name="l00447"></a>00447 }
<a name="l00448"></a>00448 }
<a name="l00449"></a>00449 <span class="keyword">typename</span> <a class="code" href="classcsHash.html" title="A generic hash table class, which grows dynamically and whose buckets are unsorted...">csHash<size_t,const T>::GlobalIterator</a> iter =
<a name="l00450"></a>00450 NodeMap.GetIterator ();
<a name="l00451"></a>00451 <span class="keywordflow">while</span> (iter.HasNext())
<a name="l00452"></a>00452 {
<a name="l00453"></a>00453 <span class="keywordtype">size_t</span> idx = iter.Next();
<a name="l00454"></a>00454 <a class="code" href="cssysdef_8h.html#98cf1ab82994ac8a7c2a25120f6f15d2" title="Same as CS_ASSERT(expr), but additionally prints msg to stderr.">CS_ASSERT_MSG</a> (<span class="stringliteral">"NodeMap contains an index larger than Nodes list"</span>,
<a name="l00455"></a>00455 idx < Nodes.GetSize ());
<a name="l00456"></a>00456 }
<a name="l00457"></a>00457 <span class="preprocessor">#endif </span><span class="comment">/* CS_DEBUG */</span>
<a name="l00458"></a>00458 }
<a name="l00459"></a>00459
<a name="l00460"></a><a class="code" href="classcsPartialOrder.html#23c4136f9aee34312a493702aacbb2cf">00460</a> <span class="keywordtype">bool</span> CycleTest(<span class="keyword">const</span> T& node)
<a name="l00461"></a>00461 {
<a name="l00462"></a>00462 <span class="keywordtype">size_t</span> n = NodeMap.Get(node, <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00463"></a>00463 <a class="code" href="cssysdef_8h.html#c380bd47888ecfe73e7b7a40b6f827a1" title="Assertion.">CS_ASSERT</a>(n != <a class="code" href="group__util__containers.html#g7477ed9887527029069ab5d5c79e2f70" title="This value is returned whenever an array item could not be located or does not exist...">csArrayItemNotFound</a>);
<a name="l00464"></a>00464 <span class="keywordflow">return</span> InternalCycleTest(n);
<a name="l00465"></a>00465 }
<a name="l00466"></a>00466
<a name="l00467"></a><a class="code" href="classcsPartialOrder.html#3bcaa06c84c029e6bbff6ce51cb5adc2">00467</a> <span class="keywordtype">bool</span> InternalIsEnabled(<span class="keywordtype">size_t</span> i)
<a name="l00468"></a>00468 {
<a name="l00469"></a>00469 <span class="keywordflow">if</span> (Nodes[i].marked)
<a name="l00470"></a>00470 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00471"></a>00471 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> j=0 ; j<Nodes[i].pre.GetSize () ; j++)
<a name="l00472"></a>00472 {
<a name="l00473"></a>00473 <span class="keywordflow">if</span> (!Nodes[Nodes[i].pre[j]].marked)
<a name="l00474"></a>00474 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00475"></a>00475 }
<a name="l00476"></a>00476 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00477"></a>00477 }
<a name="l00478"></a>00478
<a name="l00479"></a><a class="code" href="classcsPartialOrder.html#9246f05824e723c48c4bc82bd83abf21">00479</a> <span class="keywordtype">bool</span> InternalCycleTest(<span class="keywordtype">size_t</span> n1, <span class="keywordtype">size_t</span> n2)
<a name="l00480"></a>00480 {
<a name="l00481"></a>00481 <span class="comment">// n1 is the inserted node, see if n2 hits n1 again...</span>
<a name="l00482"></a>00482 <span class="keywordflow">if</span> (n1==n2)
<a name="l00483"></a>00483 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00484"></a>00484 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes[n2].post.GetSize () ; i++)
<a name="l00485"></a>00485 {
<a name="l00486"></a>00486 <span class="keywordflow">if</span> (InternalCycleTest(n1, Nodes[n2].post[i]))
<a name="l00487"></a>00487 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00488"></a>00488 }
<a name="l00489"></a>00489 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00490"></a>00490 }
<a name="l00491"></a><a class="code" href="classcsPartialOrder.html#8c82fc79f67f35f6ee0669ef7cd3bc07">00491</a> <span class="keywordtype">bool</span> InternalCycleTest(<span class="keywordtype">size_t</span> n)
<a name="l00492"></a>00492 {
<a name="l00493"></a>00493 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0 ; i<Nodes[n].post.GetSize () ; i++)
<a name="l00494"></a>00494 {
<a name="l00495"></a>00495 <span class="keywordflow">if</span> (InternalCycleTest(n, Nodes[n].post[i]))
<a name="l00496"></a>00496 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00497"></a>00497 }
<a name="l00498"></a>00498 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00499"></a>00499 }
<a name="l00500"></a>00500 };
<a name="l00501"></a>00501
<a name="l00502"></a>00502 <span class="preprocessor">#endif // __CS_UTIL_PO_H__</span>
</pre></div><hr size="1"><address><small>Generated for Crystal Space 1.2.1 by
<a href="http://www.doxygen.org/index.html">doxygen</a> 1.5.3
</small></address> </div></body> </html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bad97183153701b09df5fae1052b1c30
>
files
>
2116
