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