UnfoldingStateTable.hh

Go to the documentation of this file.

#ifndef UNFOLDINGSTATETABLE_HH_
#define UNFOLDINGSTATETABLE_HH_
#include<list>
#include<diades/utils/Assertion.hh>
#include<diades/sdmdl/UnfoldingState.hh>
#include<diades/sdmdl/CubeGenerator.hh>

using namespace std;

namespace Diades
{
  namespace Sdmdl
  {

        template<class T>
        class StateNode {
        private:
          int _state; 
          T _inf;       
          bool _tag;    
          list<StateNode *> _children; 
                
                
        public:
          StateNode():_state(),_inf(),_tag(false),_children(){}
        
        
          StateNode(int i):_state(i),_inf(),_tag(false),_children(){
          }
                
          StateNode(int i,const T & inf):_state(i),_inf(inf),_tag(true),_children(){}
                
          bool isTagged() const { return _tag; }
                
          int state() const { return _state; }
                
          void setInfo(const T & inf) { 
                _inf = inf;
                _tag = true;
                        
          } 
                
          T  getInfo() const { 
                return _inf;
          }
                
          list<StateNode *> * children() { return &_children; }
                
          const list<StateNode *> * children() const { return &_children; }
                
        };

        template<typename T>
        inline ostream& operator<<(ostream &os, const StateNode<T> & stateNode)
        {
          os << "***************************************************" << endl;
          os << "Start StateNode: "   << &stateNode << endl;
          os << "***************************************************" << endl;
          os << "\t state: "    << stateNode.state() << endl;
          os << "\t children: " << endl;
          for(typename list<StateNode<T> *>::const_iterator it = stateNode.children()->begin();
                  it != stateNode.children()->end();
                  ++it)
                {
                  os << **it << endl;
                }
          os << "***************************************************" << endl;
          os << "End StateNode: "   << &stateNode << endl;
          os << "***************************************************" << endl;  
          return os;
        } 


        template <class T> 
        class UnfoldingStateTable {

        private:
          list<StateNode<T> *> roots;   
        
        public:
        
          UnfoldingStateTable():roots(){}
                
          T  getInfo(const UnfoldingState & s, bool & found) const;
        
          T insertIfNotFound(const UnfoldingState & s, 
                                                 const T & info, 
                                                 bool & found);
        
          void printTable() const;
                
        private:
        
          void insertCube(int * cube, int index, int size, 
                                          list<StateNode<T>*> & currentListNode,
                                          typename list< StateNode<T>* >::iterator & nodeIt,
                                          const T & info);
        };



        template<class T> T  UnfoldingStateTable<T>::getInfo(const UnfoldingState & s, bool & found) const
        {
          require(ComponentTypeInvalid, s.valid(), "UnfoldingStateTable<T>::getInfo: invalid unfolding state");
          T inf;        

          found = false;
          int * cube = s.cube();
          int size = s.cubeSize();
        
          int index = 0;
          const list<StateNode<T> *> * currentListNode = &roots;
          typename list<StateNode<T> *>::const_iterator currentNodeIt = currentListNode->begin();

          while(index < size)
                {
                  if(currentNodeIt == currentListNode->end())
                        {
                          found = false;
                        }
                  else
                        {
                          StateNode<T>  * currentNode = *currentNodeIt;
                          if( cube[index] < currentNode->state() )
                                {
                                  found = false;
                                } 
                          else
                                {       
                                  if(cube[index] == currentNode->state())
                                        {
                                          if(index + 1 != size)
                                                {                       
                                                  currentListNode = currentNode->children();
                                                  currentNodeIt = currentListNode->begin();
                                                }
                                          else
                                                {
                                                  found = currentNode->isTagged();
                                                  if(found)
                                                        {
                                                          inf = currentNode->getInfo();
                                                        }
                                                }
                                          ++index;
                                        }
                                  else
                                        {
                                          ++currentNodeIt;
                                        }       
                                }
                        }
                }
          return inf;   
        }


        template<class T> 
        T UnfoldingStateTable<T>::insertIfNotFound(const UnfoldingState & s, const T & info, bool & found)
        {
          require(ComponentTypeInvalid, s.valid(), "UnfoldingStateTable<T>::insertIfNotFound: invalid unfolding state");
          T inf;
          int * cube = s.cube();
          int size = s.cubeSize();      
          int index = 0;

          found = false;
          list<StateNode<T> *> * currentListNode = &roots;
          typename list<StateNode<T> *>::iterator currentNodeIt = currentListNode->begin();

          while(index < size)
                {
                  if(currentNodeIt == currentListNode->end())
                        {
#ifdef __ASSERT
                          int previousSize = currentListNode->size();
#endif
                          insertCube(cube,index,size,*currentListNode,currentNodeIt,info);
                          assertion(ComponentTypeInvalid,currentListNode->size() - previousSize == 1,
                                                "UnfoldingStateTable<T>::insertState is buggy");
                          index = size; 
                          inf = info;
                        }
                  else
                        {
                          StateNode<T>  * currentNode = *currentNodeIt;
                          if( cube[index] < currentNode->state() )
                                {
                                  insertCube(cube,index,size,*currentListNode,currentNodeIt,info);
                                  index = size; 
                                  inf = info;
                                } 
                          else
                                {       
                                  if(cube[index] == currentNode->state())
                                        {
                                          if(index + 1 != size)
                                                {                       
                                                  currentListNode = currentNode->children();
                                                  currentNodeIt = currentListNode->begin();
                                                }
                                          else
                                                {
                                                  found = currentNode->isTagged();
                                                  if(found)
                                                        {
                                                          inf = currentNode->getInfo();
                                                        }
                                                  else
                                                        {
                                                          currentNode->setInfo(info);
                                                          inf = info;
                                                        }
                                                }
                                          ++index;
                                        }
                                  else
                                        {
                                          ++currentNodeIt;
                                        }       
                                }
                        }
                }
          return inf;   
        }


        template<class T> 
        void UnfoldingStateTable<T>::insertCube(int * cube, int index, int size,
                                                                                        list<StateNode<T> *> & currentListNode,
                                                                                        typename list<StateNode<T> *>::iterator & nodeIt,
                                                                                        const T & info)
        {
        
          list<StateNode<T> *> * currentListNodePtr = &currentListNode;
          typename list<StateNode<T> *>::iterator currentNodeIt = nodeIt;
          int index2 = index;
          while(index2 < size)
                {
                  StateNode<T> * node = 0;
                  if(index2 + 1 == size)
                        {
                          node = new StateNode<T>(cube[index2],info);
                        }
                  else
                        {
                          node = new StateNode<T>(cube[index2]);
                        }
                
#ifdef __ASSERT
                  int previousSize = currentListNodePtr-> size();
#endif
                  currentListNodePtr->insert(currentNodeIt,node);

                
                  assertion(ComponentTypeInvalid, currentListNodePtr->size() - previousSize == 1,
                                        "UnfoldingStateTable::insertState: the insertion has failed");
                  currentListNodePtr =  node->children();
                  assertion(ComponentTypeInvalid, currentListNodePtr->empty(),
                                        "insertBs: problem of memory managment");
                  currentNodeIt = currentListNodePtr->end();
                  ++index2;
                }

        }

        template<class T>
        void UnfoldingStateTable<T>::printTable() const
        {
          if(roots.empty())
                {
                  cout << "Empty table" << endl;
                }

          for(typename list< StateNode<T> * >::const_iterator rootsIt = roots.begin();
                  rootsIt != roots.end();
                  ++rootsIt)
                {
                  list< pair< const StateNode<T> *, typename list<StateNode<T> *>::const_iterator> > stack;
                  stack.push_back(make_pair(*rootsIt, (*rootsIt)->children()->begin()));
                  while(!stack.empty())
                        {
                          const StateNode<T> * currentNode = stack.back().first;
                          typename list<StateNode<T> *>::const_iterator currentChild = stack.back().second;
                          if(currentChild != currentNode->children()->end())
                                {
                                  stack.back().second++;
                                  stack.push_back(make_pair(*currentChild,(*currentChild)->children()->begin()));
                                }
                          else
                                {
                                  if(currentNode->isTagged())
                                        {
                                          cout << "( "; 
                                          for(typename list< pair< const StateNode<T> *, typename list<StateNode<T> *>::const_iterator> >::const_iterator 
                                                        stackIt= stack.begin();
                                                  stackIt != stack.end();
                                                  ++stackIt)
                                                {
                                                  cout << stackIt->first->state() <<    " ";
                                                }       
                                          cout << ")" << endl;
                                        }
                                  else
                                        {
                                          if((!currentNode->isTagged()) && (currentNode->children()->empty()))
                                                {
                                                  cout << "There is a full sequence in the table that does not represent a Unfolding state: " << endl;  
                                                  for(typename list< pair< const StateNode<T> *, 
                                                                                                   typename list<StateNode<T> *>::const_iterator> >::const_iterator stackIt= stack.begin();
                                                  stackIt != stack.end();
                                                  ++stackIt)
                                                        {
                                                          cout << stackIt->first->state() <<    " ";
                                                        }
                                        }
                                }
                                  stack.pop_back();
                        }
                }
        }
  }
























};
};
#endif /*UnfoldingSTATETABLE_HH_*/