csutil/partialorder.h
Go to the documentation of this file.00001 /* -*- Mode: C++; c-basic-offset: 2 -*- 00002 Copyright (C) 2005 by Adam D. Bradley <artdodge@cs.bu.edu> 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Lesser General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00017 */ 00018 00019 #ifndef __CS_UTIL_PO_H__ 00020 #define __CS_UTIL_PO_H__ 00021 00026 #include "csextern.h" 00027 #include "csutil/array.h" 00028 #include "csutil/comparator.h" 00029 #include "csutil/hash.h" 00030 #include "csutil/list.h" 00031 #include "csutil/ref.h" 00032 #include "csutil/util.h" 00033 00034 #ifdef ADB_DEBUG 00035 #include <iostream> 00036 #endif /* ADB_DEBUG */ 00037 00050 template <class T> 00051 class CS_CRYSTALSPACE_EXPORT csPartialOrder 00052 { 00053 protected: 00054 class Node 00055 { 00056 public: 00057 Node(const Node &other) 00058 : self(other.self), output(other.output), 00059 marked(other.marked), 00060 pre(other.pre), post(other.post) 00061 { } 00062 Node(const T &id) 00063 : self(id), output(false), marked(false), 00064 pre(), post() 00065 { } 00066 const T self; 00067 bool output; 00068 bool marked; 00069 csArray<size_t> pre; 00070 csArray<size_t> post; 00071 }; 00072 csArray<Node> Nodes; 00073 csHash<size_t,const T> NodeMap; 00074 00075 public: 00077 csPartialOrder () 00078 : Nodes (), NodeMap() 00079 { 00080 return; 00081 } 00082 00084 csPartialOrder(const csPartialOrder &other) 00085 : Nodes (other.Nodes), NodeMap (other.NodeMap) 00086 { 00087 return; 00088 } 00089 00091 csPartialOrder(const csPartialOrder *other) 00092 : Nodes (other->Nodes), NodeMap (other->NodeMap) 00093 { 00094 return; 00095 } 00096 00098 void Add (const T& node) 00099 { 00100 SanityCheck(); 00101 if (NodeMap.Get(node, csArrayItemNotFound) == csArrayItemNotFound) 00102 { 00103 NodeMap.PutUnique(node, Nodes.Push(node)); 00104 } 00105 SanityCheck(); 00106 } 00107 00109 bool Contains (const T& node) 00110 { 00111 return (NodeMap.Get(node, csArrayItemNotFound) != csArrayItemNotFound); 00112 } 00113 00115 void Delete (const T& node) 00116 { 00117 SanityCheck(); 00118 size_t p = NodeMap.Get(node, csArrayItemNotFound); 00119 CS_ASSERT(p!=csArrayItemNotFound); 00120 CS_ASSERT(p < Nodes.Length()); 00121 // delete all posts pointing to node 00122 for (size_t iter=0 ; iter<Nodes[p].pre.Length() ; iter++) 00123 { 00124 Nodes[Nodes[p].pre[iter]].post.DeleteFast(p); 00125 } 00126 // delete node's pre's 00127 Nodes[p].pre.DeleteAll(); 00128 // delete all pres pointing to node 00129 for (size_t iter=0 ; iter<Nodes[p].post.Length() ; iter++) 00130 { 00131 Nodes[Nodes[p].post[iter]].pre.DeleteFast(p); 00132 } 00133 // delete node's post's 00134 Nodes[p].post.DeleteAll(); 00135 // delete node p, move someone else into its place... 00136 Nodes.DeleteIndexFast(p); 00137 00138 if (Nodes.Length() > p) 00139 { 00140 // who got moved into "p"? 00141 size_t retarget = NodeMap.Get(Nodes[p].self, csArrayItemNotFound); 00142 CS_ASSERT (retarget != csArrayItemNotFound); 00143 00144 // change references to "retarget" to reference "p" 00145 for (size_t iter=0 ; iter<Nodes.Length() ; iter++) 00146 { 00147 for (size_t iter2=0 ; iter2<Nodes[iter].pre.Length() ; iter2++) 00148 { 00149 if (Nodes[iter].pre[iter2] == retarget) 00150 Nodes[iter].pre[iter2] = p; 00151 } 00152 for (size_t iter2=0 ; iter2<Nodes[iter].post.Length() ; iter2++) 00153 { 00154 if (Nodes[iter].post[iter2] == retarget) 00155 Nodes[iter].post[iter2] = p; 00156 } 00157 } 00158 } 00159 00160 NodeMap.Delete(node, p); 00161 if (Nodes.Length() > p) 00162 NodeMap.PutUnique(Nodes[p].self, p); 00163 00164 SanityCheck(); 00165 } 00166 00173 bool AddOrder (const T& node1, const T& node2) 00174 { 00175 SanityCheck(); 00176 size_t n1 = NodeMap.Get(node1, csArrayItemNotFound); 00177 size_t n2 = NodeMap.Get(node2, csArrayItemNotFound); 00178 CS_ASSERT(n1 != csArrayItemNotFound); 00179 CS_ASSERT(n2 != csArrayItemNotFound); 00180 00181 /* make the forward link "n1->n2" */ 00182 Nodes[n1].post.Push(n2); 00183 00184 if (InternalCycleTest(n1)) 00185 { 00186 /* undo our mischief and report failure */ 00187 Nodes[n1].post.Pop(); 00188 return false; 00189 } 00190 else 00191 { 00192 /* make the paired pre link "n2<-n1" */ 00193 Nodes[n2].pre.Push(n1); 00194 return true; 00195 } 00196 SanityCheck(); 00197 } 00198 00200 void DeleteOrder (const T& node1, const T& node2) 00201 { 00202 SanityCheck(); 00203 size_t n1 = NodeMap.Get(node1, csArrayItemNotFound); 00204 size_t n2 = NodeMap.Get(node2, csArrayItemNotFound); 00205 CS_ASSERT(n1 != csArrayItemNotFound); 00206 CS_ASSERT(n2 != csArrayItemNotFound); 00207 Nodes[n2].pre.DeleteFast(n1); 00208 Nodes[n1].post.DeleteFast(n2); 00209 SanityCheck(); 00210 } 00211 00213 size_t Size () 00214 { 00215 return Nodes.Length(); 00216 } 00217 00219 const T GetByIndex(size_t i) 00220 { 00221 return Nodes[i].self; 00222 } 00223 00228 void Solve (csList<const T> & result) 00229 { 00230 SanityCheck(); 00231 for (size_t iter=0 ; iter<Nodes.Length() ; iter++) 00232 { 00233 Nodes[iter].output = false; 00234 } 00235 result.DeleteAll(); 00236 bool done; 00237 do 00238 { 00239 done = true; 00240 for (size_t iter=0 ; iter<Nodes.Length() ; iter++) 00241 { 00242 if (Nodes[iter].output == false) 00243 { 00244 int canoutput = true; 00245 for (size_t i2=0 ; i2<Nodes[iter].pre.Length() ; i2++) 00246 { 00247 if (!Nodes[Nodes[iter].pre[i2]].output) 00248 { 00249 canoutput = false; 00250 break; 00251 } 00252 } 00253 if (canoutput) 00254 { 00255 result.PushBack(Nodes[iter].self); 00256 Nodes[iter].output = true; 00257 } 00258 else 00259 { 00260 done = false; 00261 } 00262 } 00263 } 00264 } 00265 while (!done); 00266 SanityCheck(); 00267 } 00268 00273 void Mark (const T& node) 00274 { 00275 size_t i = NodeMap.Get(node, csArrayItemNotFound); 00276 CS_ASSERT(i != csArrayItemNotFound); 00277 Nodes[i].marked = true; 00278 } 00279 00283 bool IsMarked (const T& node) 00284 { 00285 size_t i = NodeMap.Get(node, csArrayItemNotFound); 00286 CS_ASSERT(i != csArrayItemNotFound); 00287 return Nodes[i].marked; 00288 } 00289 00293 void ClearMark (const T& node) 00294 { 00295 size_t i = NodeMap.Get(node, csArrayItemNotFound); 00296 CS_ASSERT(i != csArrayItemNotFound); 00297 Nodes[i].marked = false; 00298 } 00299 00303 void ClearMark () 00304 { 00305 for (size_t i=0 ; i<Nodes.Length() ; i++) 00306 { 00307 Nodes[i].marked = false; 00308 } 00309 } 00310 00315 bool IsEnabled(const T& node) 00316 { 00317 size_t i = NodeMap.Get(node, csArrayItemNotFound); 00318 CS_ASSERT(i != csArrayItemNotFound); 00319 return InternalIsEnabled(i); 00320 } 00321 00325 bool HasEnabled() 00326 { 00327 for (size_t i=0 ; i<Nodes.Length() ; i++) 00328 { 00329 if (InternalIsEnabled(i)) 00330 return true; 00331 } 00332 return false; 00333 } 00334 00338 const T GetEnabled(T fail) 00339 { 00340 for (size_t i=0 ; i<Nodes.Length() ; i++) 00341 { 00342 if (InternalIsEnabled(i)) 00343 return Nodes[i].self; 00344 } 00345 return fail; 00346 } 00347 00348 protected: 00349 void SanityCheck () 00350 { 00351 #ifdef CS_DEBUG 00352 CS_ASSERT (NodeMap.GetSize() == Nodes.Length()); 00353 for (size_t i1=0; i1<Nodes.Length() ; i1++) 00354 { 00355 CS_ASSERT (NodeMap.Get(Nodes[i1].self, csArrayItemNotFound) == i1); 00356 for (size_t i2=0 ; i2<Nodes[i1].pre.Length() ; i2++) 00357 { 00358 CS_ASSERT (Nodes[i1].pre[i2] >= 0); 00359 CS_ASSERT (Nodes[i1].pre[i2] < Nodes.Length()); 00360 bool reciprocal_post_exists = false; 00361 for (size_t i3=0 ; i3<Nodes[Nodes[i1].pre[i2]].post.Length() ; i3++) 00362 { 00363 if (Nodes[Nodes[i1].pre[i2]].post[i3] == i1) 00364 reciprocal_post_exists = true; 00365 } 00366 CS_ASSERT (reciprocal_post_exists); 00367 } 00368 for (size_t i2=0 ; i2<Nodes[i1].post.Length() ; i2++) 00369 { 00370 CS_ASSERT(Nodes[i1].post[i2] >= 0); 00371 CS_ASSERT(Nodes[i1].post[i2] < Nodes.Length()); 00372 bool reciprocal_pre_exists = false; 00373 for (size_t i3=0 ; i3<Nodes[Nodes[i1].post[i2]].pre.Length() ; i3++) 00374 { 00375 if (Nodes[Nodes[i1].post[i2]].pre[i3] == i1) 00376 reciprocal_pre_exists = true; 00377 } 00378 CS_ASSERT (reciprocal_pre_exists); 00379 } 00380 } 00381 typename csHash<size_t,const T>::GlobalIterator iter = 00382 NodeMap.GetIterator (); 00383 while (iter.HasNext()) 00384 { 00385 size_t index = iter.Next(); 00386 CS_ASSERT (index >= 0); 00387 CS_ASSERT (index < Nodes.Length()); 00388 } 00389 #endif /* CS_DEBUG */ 00390 } 00391 00392 bool CycleTest(const T& node) 00393 { 00394 size_t n = NodeMap.Get(node, csArrayItemNotFound); 00395 CS_ASSERT(n != csArrayItemNotFound); 00396 return InternalCycleTest(n); 00397 } 00398 00399 bool InternalIsEnabled(size_t i) 00400 { 00401 if (Nodes[i].marked) 00402 return false; 00403 for (size_t j=0 ; j<Nodes[i].pre.Length() ; j++) 00404 { 00405 if (!Nodes[Nodes[i].pre[j]].marked) 00406 return false; 00407 } 00408 return true; 00409 } 00410 00411 bool InternalCycleTest(size_t n1, size_t n2) 00412 { 00413 // n1 is the inserted node, see if n2 hits n1 again... 00414 if (n1==n2) 00415 return true; 00416 for (size_t i=0 ; i<Nodes[n2].post.Length() ; i++) 00417 { 00418 if (InternalCycleTest(n1, Nodes[n2].post[i])) 00419 return true; 00420 } 00421 return false; 00422 } 00423 bool InternalCycleTest(size_t n) 00424 { 00425 for (size_t i=0 ; i<Nodes[n].post.Length() ; i++) 00426 { 00427 if (InternalCycleTest(n, Nodes[n].post[i])) 00428 return true; 00429 } 00430 return false; 00431 } 00432 }; 00433 00434 #endif // __CS_UTIL_PO_H__
Generated for Crystal Space by doxygen 1.4.6