CrystalSpace

Public API Reference

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 "csutil/eventhandlers.h"
00036 #include <iostream>
00037 #endif /* ADB_DEBUG */
00038 
00051 template <class T>
00052 class CS_CRYSTALSPACE_EXPORT 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   // This code is particular to the csHandlerID scheduler.
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 /* ADB_DEBUG */
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     // delete all posts pointing to node
00172     for (size_t iter=0 ; iter<Nodes[p].pre.GetSize () ; iter++) 
00173     {
00174       Nodes[Nodes[p].pre[iter]].post.Delete(p);
00175     }
00176     // delete node's pre's
00177     Nodes[p].pre.DeleteAll();
00178     // delete all pres pointing to node
00179     for (size_t iter=0 ; iter<Nodes[p].post.GetSize () ; iter++) 
00180     {
00181       Nodes[Nodes[p].post[iter]].pre.Delete(p);
00182     }
00183     // delete node's post's
00184     Nodes[p].post.DeleteAll();
00185     // delete node p, move the node at the end of the csArray into its place...
00186     Nodes.DeleteIndexFast(p);
00187 
00188     // update NodeMap accordingly by killing the lookup for the deleted node
00189     // and updating the lookup for the node that moved into its place...
00190     NodeMap.Delete(node, p);
00191     if (Nodes.GetSize () > p)
00192     {
00193       // who got moved into "p"?
00194       size_t moved = NodeMap.Get(Nodes[p].self, csArrayItemNotFound);
00195       CS_ASSERT (moved != csArrayItemNotFound);
00196 
00197       // change references to "moved" to reference "p"
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     /* make the forward link "n1->n2" */
00233     Nodes[n1].post.Push(n2);
00234     
00235     if (InternalCycleTest(n1)) 
00236     {
00237       /* undo our mischief and report failure */
00238       Nodes[n1].post.Pop();
00239       return false;
00240     } 
00241     else 
00242     {
00243       /* make the paired pre link "n2<-n1" */
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 /* CS_DEBUG */
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     // n1 is the inserted node, see if n2 hits n1 again...
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__

Generated for Crystal Space 1.2.1 by doxygen 1.5.3