#ifndef GLRSTACK

#define GLRSTACK

class glrStackNoPredsException {};

#include <glr/glrGuard.h>
#include <glr/glrNode.h>
#include <glr/glrState.h>

#ifdef DEBUG
#include <glr/glrSymbolTable.h>
extern glrSymbolTable* globalSymbols;
extern bool mergeInProgress;
#endif

#include <map>
#include <vector>
#include <deque>
#include <set>
#include <string>
#include <iostream>

using namespace std;

/**
 *
 * This class is used internally by the parser during parsing.
 * Class <tt>glrSymbolVertex</tt> is used to store all edges of the graph structured stack, which goes to
 * one state vertex over one symbol.
 *
 */
class glrSymbolVertex {
  private:
    map<class glrStateVertex*,vector<glrNode*> > nodesFromState;
    map<glrNode*,vector<class glrStateVertex*> > statesFromNode;
    // glrNode *epsilonNode;
  public:

    /**
     *
     * Constructor. Just necessary initialization.
     *
     */
    glrSymbolVertex(){
      // epsilonNode=(glrNode*)NULL;
    }
    
    /**
     *
     * Destrcutor. It calls <tt>release()</tt> function to all remembered state vertices.
     *
     */
    ~glrSymbolVertex(){
      for(map<glrStateVertex*,vector<glrNode*> >::iterator iState = nodesFromState.begin(); iState!=nodesFromState.end(); ++iState){
        for(vector<glrNode*>::iterator iEdge = iState->second.begin(); iEdge!=iState->second.end(); ++iEdge){
          ((glrGuard*)(iState->first))->release();
          (*iEdge)->release();
        }
      }
    }
    
    /**
     *
     * Function <tt>addPred</tt> stores the edge from the vertex <tt>pred</tt> over the node <tt>node</tt>.
     *
     */
    void addPred(glrStateVertex * const &pred,glrNode * const &node){

      nodesFromState[pred].push_back(node);
      statesFromNode[node].push_back(pred);

      node->shackle();
      ((glrGuard*)pred)->shackle();
    }

    /**
     *
     * Function <tt>nodeFromState_begin()</tt> returns the iterator to the begining of associative
     * container which stores edges from vertices. To each edge is associated apropriate node of packed shared forest.
     *
     */
    map<class glrStateVertex*,vector<glrNode*> >::const_iterator nodesFromState_begin() const {
      return nodesFromState.begin();
    }
    
    /**
     *
     * Function <tt>nodeFromState_end()</tt> returns the iterator to the end of the associative
     * container which stores edges from vertices. To each edge is associated apropriate node of packed shared forest.
     *
     */
    map<class glrStateVertex*,vector<glrNode*> >::const_iterator nodesFromState_end() const {
      return nodesFromState.end();
    }
    
    /**
     *
     * Function <tt>nodeFromState_find()</tt> returns the iterator to the element of associative
     * container which stores edges associated with apropriate node. The returned iterator
     * points to the element which represents an edge from the <tt>fromStack</tt>. If there doesn't exist
     * such edge, it returns the same value as <tt>nodeFromState_end()</tt> function.
     *
     */
    map<class glrStateVertex*,vector<glrNode*> >::const_iterator nodesFromState_find(glrStateVertex *fromStack) const {
      return nodesFromState.find(fromStack);
    }

    /**
     *
     * Function <tt>statesFromNode_begin()</tt> returns iterator to the begining of the asociative
     * container which stores <tt>vector</tt> of state vertices from which the edges comes over one node of
     * packed shared forest (which is the key).
     *
     */
    map<glrNode*,vector<class glrStateVertex*> >::const_iterator statesFromNode_begin() const {
      return statesFromNode.begin();
    }
    
    /**
     *
     * Function <tt>statesFromNode_end()</tt> returns iterator to the end of the asociative
     * container which stores <tt>vector</tt> of state vertices from which the edges comes over one node of
     * packed shared forest (which is the key).
     *
     */
    map<glrNode*,vector<class glrStateVertex*> >::const_iterator statesFromNode_end() const {
      return statesFromNode.end();
    }

    /**
     *
     * Function <tt>statesFromNode_find()</tt> returns iterator to the element of the asociative
     * container which stores <tt>vector</tt> of state vertices from which comes edges over node <tt>fromNode</tt>.
     *
     */
    map<glrNode*,vector<class glrStateVertex*> >::const_iterator statesFromNode_find(glrNode *fromNode) const {
      return statesFromNode.find(fromNode);
    }
    
//    /**
//     *
//     * Function <tt>getEpsilonRule</tt> returns pointer to the node asociated with stored edge which was created
//     * by epsilon rule. Note that there may be only one such node to any state vertex.
//     *
//     */
//    glrNode* const &getEpsilonNode(){
//      return epsilonNode;
//    }
};

/**
 *
 * Class <tt>glrStateVertex</tt> is used internaly by the parser to represent one state vertex of the graph stack.
 *
 */
class glrStateVertex : public glrGuard {
  public:
    #ifdef DEBUG
    static int numStateVertices;
    static int maxStateVertexId;
    int vertexId;

    int const& getId() const { return vertexId; }
    
    #endif
  private:
    class glrState *state;			// stav, ke kteremu patri dany stateVertex
    int iToken;					// poradove cislo symbolu na vstupu, ktere bylo aktualni ve chvili vzniku tohoto vrcholu
    map<glrSymbolTable::glrSymbol,glrSymbolVertex> pred;	// predkove v zasobniku daneho vrholu klicovani podle symbolu patricimu hrane
    bool bottomFlag;
//  map<const void*,set<deque<glrNode*> > > reductionsMade;
//  map<const void*,map<deque<glrNode*>,glrNode*> > reductionsMade;
  public:

/*    bool performReductions(const void* rule,const deque<glrNode*> &subtree){
      pair<set<deque<glrNode*> >::iterator,bool> ret = reductionsMade[rule].insert(subtree);
      #ifdef DEBUG
      if(!ret.second){
        cerr << "bool glrStateVertex::performReductions(const void* rule,const deque<glrNode*> &subtree): \
	         refusing attempt to make same reduction twice" << endl;
      }
      #endif
      return ret.second;
    }*/

/*    glrNode* findParentForEdge(void *rule,const deque<glrNode*> &subtree){
      map<deque<glrNode*>,glrNode*>::iterator ret = reductionsMade[rule].find(subtree);
      if(ret==reductionsMade[rule].end()){
        return NULL;
      }else{
        return ret->second;
      }
    }*/

    virtual ~glrStateVertex(){
      #ifdef DEBUG
      --numStateVertices;
      cerr << "deleting state vertex with id " << vertexId << endl;
      #endif
    }

    /**
     *
     * Contructor. <tt>iTokenA</tt> is actual number of token on input. <tt>stateA</tt> is the asociated state of automat. <tt>predA</tt>
     * and <tt>nodeA</tt> specifies new edge to create in the graph stack from the state vertex <tt>predA</tt> over the node <tt>nodeA</tt>.
     *
     */
    glrStateVertex(int const &iTokenA,class glrState* const &stateA,class glrStateVertex* const &predA,class glrNode* const &node){
      iToken=iTokenA;
      state=stateA;
      addPred(predA,node);
      bottomFlag = false;
      #ifdef DEBUG
      numStateVertices++;
      vertexId = (maxStateVertexId++);
      cerr << "creating state vertex with id " << vertexId << endl;
      #endif
    }

    bool bottom() const {
      return bottomFlag;
    }

    /** 
     *
     * Constructor. <tt>iTokenA</tt> is actual number of token on input. <tt>stateA</tt> is the asociated state of the automat.
     *
     */
    glrStateVertex(int const &iTokenA,class glrState* const &stateA){
      iToken=iTokenA;
      state=stateA;
      bottomFlag = false;
      #ifdef DEBUG
      ++numStateVertices;
      vertexId = (maxStateVertexId++);
      cerr << "creating state vertex with id " << vertexId << endl;
      #endif
    }

    /** 
     *
     * Constructor. <tt>iTokenA</tt> is actual number of token on input. <tt>stateA</tt> is the asociated state of the automat.
     * <tt>bottomFlagA</tt> should be set to <tt>true</tt> iff this vertex is the bottom of the graph structured stack.
     *
     */
    glrStateVertex(int const &iTokenA,class glrState* const &stateA, bool bottomFlagA){
      iToken=iTokenA;
      state=stateA;
      bottomFlag = bottomFlagA;
      #ifdef DEBUG
      ++numStateVertices;
      vertexId = (maxStateVertexId++);
      cerr << "creating state vertex with id " << vertexId << endl;
      #endif
    }

    /**
     *
     * The function <tt>getToken()</tt> returns the number of token on input which was actual when the vertex was created.
     *
     */
    int const &getToken(){ return iToken; }

    /**
     *
     * Function <tt>addPred</tt> adds edge to the graph stack from vertex <tt>fromVertex</tt>
     * over node <tt>overNode</tt>.
     *
     */
    void addPred(glrStateVertex* const &fromVertex,glrNode* const &overNode){
      #ifdef DEBUG
      if(!mergeInProgress){
        cerr << "creating edge from vertex " << fromVertex->getState()->getNumber() << " (" << fromVertex->getToken() << ") "
             << "to vertex " << getState()->getNumber() << " (" << getToken() << ") over symbol ,,"
	     << globalSymbols->getStringFromSymbol(overNode->getSymbol()) << "''" << endl;
      }
      #endif
      glrSymbolVertex &predsFromSymbol=pred[overNode->getSymbol()];
      predsFromSymbol.addPred(fromVertex,overNode);
    }
    
    /**
     *
     * Function <tt>getPreds</tt> returns reference to the object of type <tt>glrSymbolVertex</tt>,
     * where all edges over symbol <tt>symbol</tt> to this vertex are stored. If there
     * is not such edge, new <tt>glrSymbolVertex</tt> object is created and stored.
     *
     */
    glrSymbolVertex &getPreds(glrSymbolTable::glrSymbol const &symbol){
      return pred[symbol];
    }
    
    /**
     *
     * Function <tt>findPreds</tt> returns reference to the object of type <tt>glrSymbolVertex</tt>,
     * where all edges over symbol <tt>symbol</tt> to this vertex are stored. If there
     * is not such edge the exception <tt>glrStackNoPredsException</tt> is throwed.
     *
     */
    glrSymbolVertex const& findPreds(glrSymbolTable::glrSymbol const &symbol) const {
      map<glrSymbolTable::glrSymbol,glrSymbolVertex>::const_iterator iSym=pred.find(symbol);
      if(iSym==pred.end())throw glrStackNoPredsException();
      return iSym->second;
    }

    /**
     *
     * The function <tt>getState()</tt> returns the state asociated with this vertex.
     *
     */
    class glrState* const &getState(){
      return state;
    }
    
    /**
     *
     * Function <tt>merge</tt> adds all stored edges to state vertex specified by <tt>where</tt>.
     *
     */
    void merge(glrStateVertex* const &where){
      #ifdef DEBUG
      if((state!=where->getState())||(iToken!=where->getToken())){
        cerr << "error: can\'t merge stack with different state or iToken" << endl;
	return;
      }
      mergeInProgress = true;
      #endif
      for(map<glrSymbolTable::glrSymbol,glrSymbolVertex>::iterator iSym=pred.begin();iSym!=pred.end();++iSym){
        for(map<class glrStateVertex*,vector<glrNode*> >::const_iterator iStack = iSym->second.nodesFromState_begin();
	    iStack!=iSym->second.nodesFromState_end(); ++iStack){
	  for(vector<glrNode*>::const_iterator iNode = iStack->second.begin(); iNode!=iStack->second.end(); ++iNode){
            where->addPred(iStack->first, *iNode);
	    if(iStack->first->getToken()==where->getToken()){
	      iStack->first->getState()->crossEdges.push_back(pair<glrNode*, glrState*>(*iNode, getState()));
	    }
	  }
        }
      }
      #ifdef DEBUG
      mergeInProgress = false;
      #endif
    }

    void addCrossEdges(){
      for(map<glrSymbolTable::glrSymbol,glrSymbolVertex>::iterator iSym=pred.begin();iSym!=pred.end();++iSym){
        for(map<class glrStateVertex*,vector<glrNode*> >::const_iterator iStack = iSym->second.nodesFromState_begin();iStack!=iSym->second.nodesFromState_end(); ++iStack){
	  if(iStack->first->getToken()==getToken()){
	    for(vector<glrNode*>::const_iterator iNode = iStack->second.begin(); iNode!=iStack->second.end(); ++iNode){
	      iStack->first->getState()->crossEdges.push_back(pair<glrNode*, glrState*>(*iNode, getState()));
	    }
	  }
	}
      }
    }
	    
	  
};

#endif