## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# 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__