00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
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 "csutil/eventhandlers.h"
00036 #include <iostream>
00037 #endif
00038
00051 template <class T>
00052 class csPartialOrder
00053 {
00054 protected:
00055 class Node
00056 {
00057 public:
00058 Node(const Node &other)
00059 : self(other.self), output(other.output),
00060 marked(other.marked),
00061 pre(other.pre), post(other.post)
00062 { }
00063 Node(const T &id)
00064 : self(id), output(false), marked(false),
00065 pre(), post()
00066 { }
00067 const T self;
00068 bool output;
00069 bool marked;
00070 csArray<size_t> pre;
00071 csArray<size_t> post;
00072 };
00073 csArray<Node> Nodes;
00074 csHash<size_t,const T> NodeMap;
00075
00076 public:
00078 csPartialOrder ()
00079 : Nodes (), NodeMap()
00080 {
00081 return;
00082 }
00083
00085 csPartialOrder(const csPartialOrder &other)
00086 : Nodes (other.Nodes), NodeMap (other.NodeMap)
00087 {
00088 return;
00089 }
00090
00091 #ifdef ADB_DEBUG
00092
00093 void Dump (iObjectRegistry *objreg)
00094 {
00095 std::cerr << "Dumping PO Graph..." << std::endl;
00096 for (size_t i=0 ; i<Nodes.GetSize () ; i++)
00097 {
00098 std::cerr << " NODE: " << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Nodes[i].self) << std::endl;
00099 std::cerr << " pre: ";
00100 for (size_t j=0 ; j<Nodes[i].pre.GetSize () ; j++)
00101 {
00102 std::cerr << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Nodes[Nodes[i].pre[j]].self) << " ";
00103 }
00104 std::cerr << std::endl << " post: ";
00105 for (size_t j=0 ; j<Nodes[i].post.GetSize () ; j++)
00106 {
00107 std::cerr << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Nodes[Nodes[i].post[j]].self) << " ";
00108 }
00109 std::cerr << std::endl;
00110 }
00111 std::cerr << "End PO Graph, printing a solution..." << std::endl;
00112 csList<const T> Solution;
00113 Solve (Solution);
00114 while (!Solution.IsEmpty ())
00115 {
00116 std::cerr << csEventHandlerRegistry::GetRegistry(objreg)->GetString(Solution.Front()) << " ";
00117 Solution.PopFront();
00118 }
00119 std::cerr << std::endl << "Done." << std::endl << std::endl;
00120 }
00121 #endif
00122
00124 csPartialOrder(const csPartialOrder *other)
00125 : Nodes (other->Nodes), NodeMap (other->NodeMap)
00126 {
00127 return;
00128 }
00129
00131 void Add (const T& node)
00132 {
00133 SanityCheck();
00134 if (NodeMap.Get(node, csArrayItemNotFound) == csArrayItemNotFound)
00135 {
00136 NodeMap.PutUnique(node, Nodes.Push(node));
00137 }
00138 SanityCheck();
00139 }
00140
00142 bool Contains (const T& node)
00143 {
00144 return (NodeMap.Get(node, csArrayItemNotFound) != csArrayItemNotFound);
00145 }
00146
00148 bool Contains (const T& pre, const T& post)
00149 {
00150 if (!Contains (pre) || !Contains (post))
00151 return false;
00152 size_t PreIdx = NodeMap.Get (pre, csArrayItemNotFound);
00153 size_t PostIdx = NodeMap.Get (post, csArrayItemNotFound);
00154 for (size_t i=0 ; i<Nodes[PreIdx].post.GetSize () ; i++)
00155 {
00156 if (Nodes[PreIdx].post[i] == PostIdx)
00157 {
00158 return true;
00159 }
00160 }
00161 return false;
00162 }
00163
00165 void Delete (const T& node)
00166 {
00167 SanityCheck();
00168 size_t p = NodeMap.Get(node, csArrayItemNotFound);
00169 CS_ASSERT(p!=csArrayItemNotFound);
00170 CS_ASSERT(p < Nodes.GetSize ());
00171
00172 for (size_t iter=0 ; iter<Nodes[p].pre.GetSize () ; iter++)
00173 {
00174 Nodes[Nodes[p].pre[iter]].post.Delete(p);
00175 }
00176
00177 Nodes[p].pre.DeleteAll();
00178
00179 for (size_t iter=0 ; iter<Nodes[p].post.GetSize () ; iter++)
00180 {
00181 Nodes[Nodes[p].post[iter]].pre.Delete(p);
00182 }
00183
00184 Nodes[p].post.DeleteAll();
00185
00186 Nodes.DeleteIndexFast(p);
00187
00188
00189
00190 NodeMap.Delete(node, p);
00191 if (Nodes.GetSize () > p)
00192 {
00193
00194 size_t moved = NodeMap.Get(Nodes[p].self, csArrayItemNotFound);
00195 CS_ASSERT (moved != csArrayItemNotFound);
00196
00197
00198 for (size_t iter=0 ; iter<Nodes.GetSize () ; iter++)
00199 {
00200 for (size_t iter2=0 ; iter2<Nodes[iter].pre.GetSize () ; iter2++)
00201 {
00202 if (Nodes[iter].pre[iter2] == moved)
00203 Nodes[iter].pre[iter2] = p;
00204 }
00205 for (size_t iter2=0 ; iter2<Nodes[iter].post.GetSize () ; iter2++)
00206 {
00207 if (Nodes[iter].post[iter2] == moved)
00208 Nodes[iter].post[iter2] = p;
00209 }
00210 }
00211 NodeMap.Delete(Nodes[p].self, moved);
00212 NodeMap.PutUnique(Nodes[p].self, p);
00213 }
00214
00215 SanityCheck();
00216 }
00217
00224 bool AddOrder (const T& node1, const T& node2)
00225 {
00226 SanityCheck();
00227 size_t n1 = NodeMap.Get(node1, csArrayItemNotFound);
00228 size_t n2 = NodeMap.Get(node2, csArrayItemNotFound);
00229 CS_ASSERT(n1 != csArrayItemNotFound);
00230 CS_ASSERT(n2 != csArrayItemNotFound);
00231
00232
00233 Nodes[n1].post.Push(n2);
00234
00235 if (InternalCycleTest(n1))
00236 {
00237
00238 Nodes[n1].post.Pop();
00239 return false;
00240 }
00241 else
00242 {
00243
00244 Nodes[n2].pre.Push(n1);
00245 return true;
00246 }
00247 SanityCheck();
00248 }
00249
00251 void DeleteOrder (const T& node1, const T& node2)
00252 {
00253 SanityCheck();
00254 size_t n1 = NodeMap.Get(node1, csArrayItemNotFound);
00255 size_t n2 = NodeMap.Get(node2, csArrayItemNotFound);
00256 CS_ASSERT(n1 != csArrayItemNotFound);
00257 CS_ASSERT(n2 != csArrayItemNotFound);
00258 Nodes[n2].pre.DeleteFast(n1);
00259 Nodes[n1].post.DeleteFast(n2);
00260 SanityCheck();
00261 }
00262
00264 size_t Size ()
00265 {
00266 return Nodes.GetSize ();
00267 }
00268
00270 const T GetByIndex(size_t i)
00271 {
00272 return Nodes[i].self;
00273 }
00274
00279 void Solve (csList<const T> & result)
00280 {
00281 SanityCheck();
00282 for (size_t iter=0 ; iter<Nodes.GetSize () ; iter++)
00283 {
00284 Nodes[iter].output = false;
00285 }
00286 result.DeleteAll();
00287 bool done;
00288 do
00289 {
00290 done = true;
00291 for (size_t iter=0 ; iter<Nodes.GetSize () ; iter++)
00292 {
00293 if (Nodes[iter].output == false)
00294 {
00295 int canoutput = true;
00296 for (size_t i2=0 ; i2<Nodes[iter].pre.GetSize () ; i2++)
00297 {
00298 if (!Nodes[Nodes[iter].pre[i2]].output)
00299 {
00300 canoutput = false;
00301 break;
00302 }
00303 }
00304 if (canoutput)
00305 {
00306 result.PushBack(Nodes[iter].self);
00307 Nodes[iter].output = true;
00308 }
00309 else
00310 {
00311 done = false;
00312 }
00313 }
00314 }
00315 }
00316 while (!done);
00317 SanityCheck();
00318 }
00319
00324 void Mark (const T& node)
00325 {
00326 size_t i = NodeMap.Get(node, csArrayItemNotFound);
00327 CS_ASSERT(i != csArrayItemNotFound);
00328 CS_ASSERT(i < Nodes.GetSize ());
00329 Nodes[i].marked = true;
00330 }
00331
00335 bool IsMarked (const T& node)
00336 {
00337 size_t i = NodeMap.Get(node, csArrayItemNotFound);
00338 CS_ASSERT(i != csArrayItemNotFound);
00339 CS_ASSERT(i < Nodes.GetSize ());
00340 return Nodes[i].marked;
00341 }
00342
00346 void ClearMark (const T& node)
00347 {
00348 size_t i = NodeMap.Get(node, csArrayItemNotFound);
00349 CS_ASSERT(i != csArrayItemNotFound);
00350 CS_ASSERT(i < Nodes.GetSize ());
00351 Nodes[i].marked = false;
00352 }
00353
00357 void ClearMark ()
00358 {
00359 for (size_t i=0 ; i<Nodes.GetSize () ; i++)
00360 {
00361 Nodes[i].marked = false;
00362 }
00363 }
00364
00369 bool IsEnabled(const T& node)
00370 {
00371 size_t i = NodeMap.Get(node, csArrayItemNotFound);
00372 CS_ASSERT(i != csArrayItemNotFound);
00373 return InternalIsEnabled(i);
00374 }
00375
00379 bool HasEnabled()
00380 {
00381 for (size_t i=0 ; i<Nodes.GetSize () ; i++)
00382 {
00383 if (InternalIsEnabled(i))
00384 return true;
00385 }
00386 return false;
00387 }
00388
00392 const T GetEnabled(T fail)
00393 {
00394 for (size_t i=0 ; i<Nodes.GetSize () ; i++)
00395 {
00396 if (InternalIsEnabled(i))
00397 return Nodes[i].self;
00398 }
00399 return fail;
00400 }
00401
00402 protected:
00403 void SanityCheck ()
00404 {
00405 #ifdef CS_DEBUG
00406 CS_ASSERT_MSG ("NodeMap has different size from Node list",
00407 NodeMap.GetSize() == Nodes.GetSize ());
00408 for (size_t i1=0; i1<Nodes.GetSize () ; i1++)
00409 {
00410 CS_ASSERT_MSG ("NodeMap names wrong location for node",
00411 NodeMap.Get(Nodes[i1].self, csArrayItemNotFound) == i1);
00412 for (size_t i2=0 ; i2<Nodes[i1].pre.GetSize () ; i2++)
00413 {
00414 CS_ASSERT_MSG ("Node prefix index less than zero",
00415 Nodes[i1].pre[i2] >= 0);
00416 CS_ASSERT_MSG ("Node prefix index larger than Nodes list",
00417 Nodes[i1].pre[i2] < Nodes.GetSize ());
00418 bool reciprocal_post_exists = false;
00419 for (size_t i3=0 ; i3<Nodes[Nodes[i1].pre[i2]].post.GetSize () ; i3++)
00420 {
00421 if (Nodes[Nodes[i1].pre[i2]].post[i3] == i1)
00422 {
00423 reciprocal_post_exists = true;
00424 break;
00425 }
00426 }
00427 CS_ASSERT_MSG ("Node prefix does not have reciprocal postfix",
00428 reciprocal_post_exists);
00429 }
00430 for (size_t i2=0 ; i2<Nodes[i1].post.GetSize () ; i2++)
00431 {
00432 CS_ASSERT_MSG ("Node postfix index less than zero",
00433 Nodes[i1].post[i2] >= 0);
00434 CS_ASSERT_MSG ("Node postfix index larger than Nodes list",
00435 Nodes[i1].post[i2] < Nodes.GetSize ());
00436 bool reciprocal_pre_exists = false;
00437 for (size_t i3=0 ; i3<Nodes[Nodes[i1].post[i2]].pre.GetSize () ; i3++)
00438 {
00439 if (Nodes[Nodes[i1].post[i2]].pre[i3] == i1)
00440 {
00441 reciprocal_pre_exists = true;
00442 break;
00443 }
00444 }
00445 CS_ASSERT_MSG ("Node postfix does not have reciprocal prefix",
00446 reciprocal_pre_exists);
00447 }
00448 }
00449 typename csHash<size_t,const T>::GlobalIterator iter =
00450 NodeMap.GetIterator ();
00451 while (iter.HasNext())
00452 {
00453 size_t idx = iter.Next();
00454 CS_ASSERT_MSG ("NodeMap contains an index larger than Nodes list",
00455 idx < Nodes.GetSize ());
00456 }
00457 #endif
00458 }
00459
00460 bool CycleTest(const T& node)
00461 {
00462 size_t n = NodeMap.Get(node, csArrayItemNotFound);
00463 CS_ASSERT(n != csArrayItemNotFound);
00464 return InternalCycleTest(n);
00465 }
00466
00467 bool InternalIsEnabled(size_t i)
00468 {
00469 if (Nodes[i].marked)
00470 return false;
00471 for (size_t j=0 ; j<Nodes[i].pre.GetSize () ; j++)
00472 {
00473 if (!Nodes[Nodes[i].pre[j]].marked)
00474 return false;
00475 }
00476 return true;
00477 }
00478
00479 bool InternalCycleTest(size_t n1, size_t n2)
00480 {
00481
00482 if (n1==n2)
00483 return true;
00484 for (size_t i=0 ; i<Nodes[n2].post.GetSize () ; i++)
00485 {
00486 if (InternalCycleTest(n1, Nodes[n2].post[i]))
00487 return true;
00488 }
00489 return false;
00490 }
00491 bool InternalCycleTest(size_t n)
00492 {
00493 for (size_t i=0 ; i<Nodes[n].post.GetSize () ; i++)
00494 {
00495 if (InternalCycleTest(n, Nodes[n].post[i]))
00496 return true;
00497 }
00498 return false;
00499 }
00500 };
00501
00502 #endif // __CS_UTIL_PO_H__