src/engine/Bloc.hxx

   1 #ifndef __BLOC_HXX__
   2 #define __BLOC_HXX__
   3
   4 #include "StaticDefinedComposedNode.hxx"
   5
   6 namespace YACS
   7 {
   8   namespace ENGINE
   9   {
  10 /*! \brief Class for bloc node
  11  *
  12  * \ingroup Nodes
  13  *
  14  *
  15  * \see ComposedNode
  16  */
  17     class Bloc : public StaticDefinedComposedNode
  18     {
  19     protected:
  20       std::set<Node *> _setOfNode;//OWNERSHIP OF ALL NODES
  21       //! For internal calculations
  22       mutable std::map<Node *,std::set<Node *> > *_fwLinks;
  23       //! For internal calculations
  24       mutable std::map<Node *,std::set<Node *> > *_bwLinks;
  25     protected:
  26       Node *simpleClone(ComposedNode *father, bool editionOnly=true) const;
  27     public:
  28       Bloc(const Bloc& other, ComposedNode *father, bool editionOnly);
  29       Bloc(const std::string& name);
  30       virtual ~Bloc();
  31       bool isFinished();
  32       int getNumberOfCFLinks() const;
  33       void init(bool start=true);
  34       void getReadyTasks(std::vector<Task *>& tasks);
  35       void exUpdateState();
  36       bool edAddChild(Node *node) throw(Exception);
  37       void edRemoveChild(Node *node) throw(Exception);
  38       std::set<Node *> getChildren() { return _setOfNode; }
  39       std::set<Node *> edGetDirectDescendants() const;
  40       Node *getChildByShortName(const std::string& name) const throw(Exception);
  41       void selectRunnableTasks(std::vector<Task *>& tasks);
  42       virtual void writeDot(std::ostream &os);
  43       void accept(Visitor *visitor);
  44       template<bool direction>
  45       void findAllPathsStartingFrom(Node *start, std::list< std::vector<Node *> >& vec, std::map<Node *, std::set<Node *> >& accelStr) const;
  46       template<bool direction>
  47       void findAllNodesStartingFrom(Node *start, std::set<Node *>& result, std::map<Node *, std::set<Node *> >& accelStr, LinkInfo& info) const;
  48     protected:
  49       bool areAllSubNodesFinished() const;
  50       bool areAllSubNodesDone() const;
  51       bool isNameAlreadyUsed(const std::string& name) const;
  52       void checkNoCyclePassingThrough(Node *node) throw(Exception);
  53       std::vector< std::pair<OutGate *, InGate *> > getSetOfInternalCFLinks() const;
  54       YACS::Event updateStateOnFinishedEventFrom(Node *node);
  55       YACS::Event updateStateOnFailedEventFrom(Node *node);
  56       void initComputation() const;
  57       void performCFComputations(LinkInfo& info) const;
  58       void destructCFComputations(LinkInfo& info) const;
  59       void checkControlDependancy(OutPort *start, InPort *end, bool cross,
  60                                   std::map < ComposedNode *,  std::list < OutPort * > >& fw,
  61                                   std::vector<OutPort *>& fwCross,
  62                                   std::map< ComposedNode *, std::list < OutPort *> >& bw,
  63                                   LinkInfo& info) const;
  64       bool areLinked(Node *start, Node *end, bool fw) const;
  65       bool arePossiblyRunnableAtSameTime(Node *start, Node *end) const;
  66       void checkCFLinks(const std::list< OutPort *>& starts, InputPort *end, unsigned char& alreadyFed, bool direction, LinkInfo& info) const;
  67       static void verdictForOkAndUseless1(const std::map<Node *,std::list <OutPort *> >& pool, InputPort *end, const std::vector<Node *>& candidates,
  68                                           unsigned char& alreadyFed, bool direction, LinkInfo& info);
  69       static void verdictForCollapses(const std::map<Node *,std::list <OutPort *> >& pool, InputPort *end, const std::set<Node *>& candidates,
  70                                       unsigned char& alreadyFed, bool direction, LinkInfo& info);
  71       void seekOkAndUseless1(std::vector<Node *>& okAndUseless1, std::set<Node *>& allNodes) const;
  72       void seekUseless2(std::vector<Node *>& useless2, std::set<Node *>& allNodes) const;
  73     private:
  74       static void findUselessLinksIn(const std::list< std::vector<Node *> >& res , LinkInfo& info);
  75       template<bool direction>
  76       static unsigned appendIfAlreadyFound(std::list< std::vector<Node *> >& res, const std::vector<Node *>& startRes, Node *node, std::map<Node *, std::set<Node *> >& fastFinder);
  77       static void updateWithNewFind(const std::vector<Node *>& path, std::map<Node *, std::set<Node *> >& fastFinder);
  78     };
  79
  80     template<bool direction>
  81     struct CFDirectionVisTraits
  82     {
  83     };
  84
  85     template<>
  86     struct CFDirectionVisTraits<true>
  87     {
  88       typedef std::map<InGate *,bool>::iterator Iterator;
  89       typedef std::map<InGate *,bool>& Nexts;
  90       static Nexts getNexts(Node *node) { return node->getOutGate()->edMapInGate(); }
  91     };
  92
  93
  94     template<>
  95     struct CFDirectionVisTraits<false>
  96     {
  97       typedef std::map<OutGate *,bool>::iterator Iterator;
  98       typedef std::map<OutGate *,bool>& Nexts;
  99       static Nexts getNexts(Node *node) { return node->getInGate()->edMapOutGate(); }
 100     };
 101
 102     /*!
 103      * Internal method for CF computation. Given 'fastFinder' it searched 'node' to see if an already found path in 'res' go through 'node'.
 104      * If true all paths are deduced and append to res and 'fastFinder' is updated for next turn.
 105      */
 106     template<bool direction>
 107     unsigned Bloc::appendIfAlreadyFound(std::list< std::vector<Node *> >& res, const std::vector<Node *>& startRes, Node *node, std::map<Node *, std::set<Node *> >& fastFinder)
 108     {
 109       std::map<Node *, std::set<Node *> >::const_iterator iter=fastFinder.find(node);
 110       if(iter==fastFinder.end())
 111         return 0;
 112       unsigned ret=0;
 113       std::vector<std::pair<std::set<Node *>::iterator, std::set<Node *>::iterator > > li;
 114       li.push_back(std::pair<std::set<Node *>::iterator, std::set<Node *>::iterator>(((*iter).second).begin(),((*iter).second).end()));
 115       std::vector<Node *> work(startRes);
 116       std::list< std::vector<Node *> >::iterator where=res.end(); where--;
 117       std::list< std::vector<Node *> >::iterator updates=where;
 118       while(!li.empty())
 119         {
 120           if(li.back().first!=li.back().second)
 121             {
 122               work.push_back(*(li.back().first));
 123               if(CFDirectionVisTraits<direction>::getNexts(work.back()).empty())
 124                 {
 125                   where=res.insert(where,work);
 126                   ret++;
 127                   li.back().first++;
 128                   work.pop_back();
 129                 }
 130               else
 131                 {
 132                   const std::set<Node *>& s=fastFinder[*(li.back().first)];
 133                   li.push_back(std::pair<std::set<Node *>::iterator, std::set<Node *>::iterator>(s.begin(),s.end()));
 134                 }
 135             }
 136           else
 137             {
 138               work.pop_back();
 139               li.pop_back();
 140               if(!li.empty())
 141                 li.back().first++;
 142             }
 143         }
 144       updates--;
 145       for(unsigned i=0;i<ret;i++,updates--)
 146         updateWithNewFind(*updates,fastFinder);
 147       return ret;
 148     }
 149
 150     template<bool direction>
 151     void Bloc::findAllNodesStartingFrom(Node *start, std::set<Node *>& result, std::map<Node *, std::set<Node *> >& accelStr, LinkInfo& info) const
 152     {
 153       std::list< std::vector<Node *> > li;
 154       findAllPathsStartingFrom<direction>(start,li,accelStr);
 155       for(std::list< std::vector<Node *> >::const_iterator iter=li.begin();iter!=li.end();iter++)
 156         for(std::vector<Node *>::const_iterator iter2=(*iter).begin()+1;iter2!=(*iter).end();iter2++)
 157           result.insert(*iter2);
 158       if(direction)
 159         findUselessLinksIn(li,info);
 160     }
 161
 162     /*!
 163      * Method for CF computation.DFS visitor is used.
 164      * \param start \b must be a direct descendant of 'this'.
 165      * \param direction if true forward visiting is perform, false backward is used.
 166      */
 167     template<bool direction>
 168     void Bloc::findAllPathsStartingFrom(Node *start, std::list< std::vector<Node *> >& vec, std::map<Node *, std::set<Node *> >& accelStr) const
 169     {
 170       initComputation();
 171       Node *current=start;
 172       int caseId=0;
 173       int idInCase=0;
 174       vec.push_back(std::vector<Node *>());
 175       typename CFDirectionVisTraits<direction>::Iterator iter;
 176       std::list< std::vector<Node *> >::iterator curLine=vec.begin();
 177       while(start->_colour!=YACS::Black)
 178         {
 179           (*curLine).push_back(current);
 180           idInCase++;
 181           //
 182           if(CFDirectionVisTraits<direction>::getNexts(current).empty())
 183             {
 184
 185               vec.push_back(std::vector<Node *>((*curLine)));
 186               updateWithNewFind(*curLine,accelStr);
 187               current->_colour=YACS::Black;
 188               curLine++;
 189               if(idInCase>1)
 190                 {
 191                   idInCase-=2;
 192                   current=(*curLine)[idInCase];
 193                   (*curLine).pop_back();
 194                   (*curLine).pop_back();
 195                 }
 196               continue;
 197             }
 198           if(current->_colour==YACS::Black)
 199             {
 200               appendIfAlreadyFound<direction>(vec,(*curLine),current,accelStr);
 201               curLine=vec.end(); curLine--;
 202               current->_colour=YACS::Black;
 203               if(idInCase>1)
 204                 {
 205                   idInCase-=2;
 206                   current=(*curLine)[idInCase];
 207                   (*curLine).pop_back();
 208                   (*curLine).pop_back();
 209                 }
 210               continue;
 211             }
 212           for(iter=CFDirectionVisTraits<direction>::getNexts(current).begin();iter!=CFDirectionVisTraits<direction>::getNexts(current).end();iter++)
 213             if(!(*iter).second)
 214               break;
 215           if(iter==CFDirectionVisTraits<direction>::getNexts(current).end())
 216             {//Fail this branch should be forgotten go rev
 217               current->_colour=YACS::Black;
 218               (*curLine).pop_back();
 219               if(idInCase>1)
 220                 {
 221                   idInCase-=2;
 222                   current=(*curLine)[idInCase];
 223                   (*curLine).pop_back();
 224                 }
 225             }
 226           else
 227             {
 228               //Nothing to signal continuing in this direction hoping to find
 229               current=(*iter).first->getNode();
 230               (*iter).second=true;
 231             }
 232         }
 233       vec.pop_back();
 234     }
 235   }
 236 }
 237
 238
 239 #endif