#ifndef GLRPARSER

#define GLRPARSER

#include <glr/glrSymbolTable.h>
#include <glr/glrGuard.h>
#include <glr/glrStack.h>
#include <glr/glrGrammar.h>
#include <glr/glrNode.h>
#include <glr/glrState.h>

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

#ifdef DEBUG
#include <fstream>
#endif

using namespace std;

/**
 *
 * Class <tt>glrItem</tt> is used internally by the parser during the glr table computation.
 * It represents the item of the item automat.
 *
 */
class glrItem {
  public:
    /**
     *
     * <tt>dot</tt> is the position of the dot in the right side of the rule.
     *
     */
    int dot;
    
    /**
     *
     * <tt>notRecursed</tt> is the flag which denotes that the rule was not walked through
     * during computation of the item set cap.
     *
     */
    bool notRecursed;

    /**
     *
     * The <tt>compRule</tt> is asociated grammar rule.
     *
     */
    glrCompRule *compRule;

    /**
     *
     * Constructor. <tt>dotA</tt> is the position of the dot, <tt>compRuleA</tt> is the associated
     * grammar rule and the <tt>notRecursedA</tt> argument is the initialization value to the <tt>notRecursed</tt>
     * field.
     *
     */
    glrItem(const int &dotA,glrCompRule* const& compRuleA,const bool &notRecursedA){
      dot=dotA;
      compRule=compRuleA;
      notRecursed=notRecursedA;
    }
};

/**
 *
 * Class <tt>glrItemCompare</tt> is the functor which is used to compare two object of the type
 * <tt>glrItem</tt>.
 *
 */
class glrItemCompare {
  public:

    /**
     *
     * The only field of this class. It compares two items.
     *
     */
    bool operator () (const glrItem &first, const glrItem &second) const {
      return ((first.dot<second.dot)||((first.dot==second.dot)&&(first.compRule<second.compRule)));
    }
};


/**
 *
 * Class <tt>glrItemSet</tt> is used during the glr table computation. It stores a set of the items of
 * the item automat.
 *
 */
class glrItemSet : public set<glrItem,glrItemCompare> {
  private:
    glrSymbolTable::glrSymbolType symbolType;
  public:
    /**
     *
     * Contructor. <tt>symbolTypeA</tt> is the type of the symbol behind the dot of all
     * stored items.
     *
     */
    glrItemSet(const glrSymbolTable::glrSymbolType &symbolTypeA){ symbolType=symbolTypeA; }

    /**
     *
     * Function <tt>getSymbolType</tt> returns the type of the symbol behind the dot
     * of all stored items.
     *
     */
    const glrSymbolTable::glrSymbolType &getSymbolType() const { return symbolType; }
};

/**
 *
 * Class glrItemSetCompare is the functor which is used to compare two poiters to item sets.
 *
 */
class glrItemSetCompare {
  public:
    /**
     *
     * The only field of this class. Note that it does not just compare addresses
     * in arguments, but it compares the item sets logicaly.
     *
     */
    bool operator () (const glrItemSet* const& first, const glrItemSet* const& second) const {
      if((!first)&&(second))return true;
      if((first)&&(second)){
        if(first->size()<second->size())return true;
        if(first->size()==second->size()){
          glrItemSet::iterator iFirst=first->begin();
          glrItemSet::iterator iSecond=second->begin();
          while(iFirst!=first->end()){
            if (((*iFirst).dot<(*iSecond).dot)||(((*iFirst).dot==(*iSecond).dot)&&((*iFirst).compRule<(*iSecond).compRule))) return true;
            else if (! (((*iFirst).dot==(*iSecond).dot)&&((*iFirst).compRule==(*iSecond).compRule)) ) break;
              ++iFirst;
              ++iSecond;
          }
        }
      }
      return false;
    }
};

/**
 *
 * Template <tt>glrCompState</tt> is used during the glr table computation. It reresents created
 * state of the item automat (simply one line of the glr table).
 * <tt>glrStateType</tt> is class which is used by the parser to sore state of item automat
 * (line of glr table).
 *
 */
template<class glrStateType> class glrCompState {
  public:
    /**
     *
     * <tt>transitions</tt> are the transitions over symbols in the line of the glr table. Each transition
     * will be either the item of ''goto'' part of line or ''shift'' part of line.
     *
     */
    map<glrSymbolTable::glrSymbol,glrItemSet*> transitions;

    /**
     *
     * <tt>state</tt> is the asociated state (line of the glr table) which is used by the parser during parsing
     *
     */
    glrStateType* state;

    /**
     *
     * Constructor. <tt>stateA</tt> is asociated state (line of the glr table) in the parser.
     *
     */
    glrCompState(glrStateType *stateA);
};

/**
 *
 * Template <tt>glrCompStatesMap</tt> is used during the glr table computation to discover to which
 * state make transition when the cap of item set is computed.
 * <tt>glrStateType</tt> is the class which is used by the parser to sore the state of the item automat
 * (line of the glr table).
 *
 */
template<class glrStateType> class glrCompStatesMap : public map<glrItemSet*,glrStateType*,glrItemSetCompare> {
  public:
    /**
     *
     * Function <tt>releaseItemSets</tt> dealocates all item sets which are used as key in the map.
     *
     */
    void releaseItemSets();
};

/**
 *
 * Template <tt>glrParser</tt> stays in the center of The glrParser template library. It represents the own parser.
 * <tt>glrNodeType</tt> is the class which should represent the internal node of the packed shared forest.
 * <tt>glrNodeType</tt> have to be derived from the <tt>glrNode</tt> class. <tt>glrStateType</tt> is the class which
 * will be used by the parser to represent one line of the glr table (the state). The glrParser template library
 * provides the default implementation -- the <tt>glrVectorState</tt> class and the alternative implementation
 * -- the <tt>glrMapState</tt> class.
 *
 *  @see glrNode
 *  @see glrVectorState
 *  @see glrMapState
 *  @see glrState
 */
template<class glrNodeType,class glrStateType=glrVectorState> class glrParser {
  private:

    #ifdef CHECK_CONSISTENCY
    bool checkConsistency(const string &msg);
    #endif

    void makeCap(const glrGrammarMap &grammarMap,glrCompState<glrStateType> &compState,const glrItem &item);

    deque<glrStateType*> statesForReductions;
//    deque<glrStateType*> aditionalReductions;

    bool findEdgeAndNodeSetsForReductions (const vector<glrStateVertex*> &fromVertices, const glrRule* const& rule, glrEdgeSet& edgeSet, glrNodeSet& nodeSet);

    void runReductions();
//    void makeAditionalReductions();
    void recursiveCrossEdges(glrStateVertex *fromStack,deque<glrNode*> &succ,glrStateType *toState, unsigned int const& ttl);
    void recursiveReduce(const glrStateVertex* const& stack,const int& rulePos,deque<glrNode*> &succ,const glrRule* const& rule,const glrStateType* const& fromState);
    void makeReductions(vector<glrStateVertex*> const& fromVertices, const deque<glrNode*> &succ, const glrRule* const& rule, const glrStateType* const& fromState);
    
    void runTerminalReductions();
    void recursiveTermReduce(const glrStateVertex* const& stack,const int &rulePos,deque<glrNode*> &succ,const glrRule* const& rule,const glrStateType* const& fromState);
    void makeTerminalReductions(const vector<glrStateVertex*> &fromVertices, const deque<glrNode*> &succ, const glrRule* const& rule,const glrStateType* const& fromState );
    void epsilonReductions(glrStateType *state);	// provadi redukce podle epsilon-pravidel, vola se z runTerminalReductions
    							// nebo primo rekurzivne nebo z make[Terminal]Reductions
	  
    vector<glrStateType*> states;			// tabulka glr

    int iToken;					// cislo aktualniho symbolu na vstupu
    deque<glrStateType*> activeStates;		// aktivni stavy
    glrNodeType* forestRoot;
  protected:
    /**
     *
     * <tt>grammar</tt> is the pointer to the grammar which the parser uses. Note that you can make the parser to use
     * your own <tt>glrGrammar</tt> -- derived class by deriving the <tt>glrParser</tt> based class and
     * overriding the <tt>initGrammar</tt> function or by setting the grammar using the <tt>setGrammar</tt> function.
     *
     */
    glrGrammar *grammar;			// gramatika

    /**
     *
     * <tt>symbols</tt> is the parsers symbol table. You may use it in your overrided <tt>readToken</tt> function
     * or in some functions defined in your <tt>glrNode</tt> -- derived class to discover
     * which string representation of symbol matches the symbol in the forest node.
     *
     */
    glrSymbolTable symbols;			// symboly nachazejici se v gramatice a tabulce

    /**
     *
     * <tt>preterminals</tt> is used to store comming leafes of forest which matches the terminal on input.
     * Note that this parser can handle situations when more than one preterminal matches one terminal.
     * This is the reason why it is declared as vector and not just pointer to the <tt>glrNode</tt> -- type object.
     *
     */
    vector<glrNode*> preterminals;
    
    /**
     *
     * You have to override this function in your own <tt>glrParser</tt> -- derived class to read terminals from input.
     * Parser calls it whenewer it want to get new terminal from input. The function have to insert objects
     * of type <tt>glrNode</tt> which matches the terminal on input to vector <tt>preterminals</tt> (more than one
     * preterminal can match one terminal). If the vector <tt>preterminals</tt> is empty after return from this
     * function the parser assumes that it is at the end of the input.
     *
     */
    virtual void readToken();
  public:
    glrParser();

    /**
    *
    * Destructor just calls the releaseForestRoot function.
    *
    */
    virtual ~glrParser();

    /**
     *
     * Function <tt>initGrammar</tt> initializes the proteced field <tt>grammar</tt> to object
     * of type <tt>glrGrammar</tt> and reads the grammar from <tt>input</tt>.
     *
     */
    virtual void initGrammar(istream &input);

    /**
     *
     * Function <tt>releaseGrammar</tt> deletes the object in the <tt>grammar</tt> field.
     *
     */
    virtual void releaseGrammar();

    /**
     *
     * Function <tt>getGrammar</tt> returns the <tt>grammar</tt> field.
     *
     */
    virtual glrGrammar *getGrammar();

    /**
     *
     * Function <tt>setGrammar</tt> sets the <tt>grammar</tt> field.
     *
     */
    virtual void setGrammar(glrGrammar *grammarA);

    /**
     *
     * Function <tt>printGrammar</tt> prints the grammar to the <tt>output</tt>.
     *
     */
    virtual void printGrammar(ostream &output){
      grammar->print(symbols,output);
    }

    /**
     *
     * Function <tt>readTable</tt> reads the glr table from <tt>input</tt>.
     * Note that the <tt>grammar</tt> have to be already initialized when this function is called.
     *
     */
    void readTable(istream &input);

    /**
     *
     * Function <tt>printTable</tt> prints the glr table to <tt>output</tt>.
     *
     */
    void printTable(ostream &output);

    /**
     *
     * Function <tt>computeTable</tt> computes the glr table.
     * Note that the <tt>grammar</tt> field have to be already initialized when this function is called.
     *
     */
    void computeTable();

    /**
     *
     * Function <tt>clearTable</tt> clears the glr table stored in the parser.
     *
     */
    void clearTable();

    /**
     *
     * Function <tt>printStatus</tt> prints parser's status containing the number of grammar rules stored in
     * the grammar, the number of states in the glr table and the number of symbols in the symbol table.
     *
     */
    void printStatus(ostream &output);

    /**
     *
     * Function <tt>releaseForestRoot</tt> releases the <tt>glrNodeType</tt> object
     * (calls its <tt>release()</tt> function), if such has been found
     * as a result of parsing some input. The forest root object can be created only after
     * reduction using rule number 0 and covering the whole input. If forest root is NULL
     * (input was not accepted by the pareser), nothing is done.
     *
     */
    void releaseForestRoot();

    /**
     *
     * Function <tt>getForestRoot</tt> returns the <tt>glrNodeType</tt> object which was found
     * as the result of parsing the input. It could only be created using rule number 0
     * and covering the whole input. If the input was not accepted by the parser, NULL is returned.
     *
     */
    glrNodeType *getForestRoot();

    /**
     *
     * The function <tt>getNumOfTokens</tt> returns the number of tokens of input parsed from last start
     * of <tt>parse()</tt> function. You can use it in you provided <tt>readToken()</tt> function
     * to recognize number of tokens actualy read or after the finish of <tt>parse()</tt> function to
     * recognize how many tokens was read.
     *
     */
    int getNumOfTokens();

    /**
     *
     * Function <tt>parse()</tt> starts the own parsing. Note that it calls the <tt>releaseForestRoot()</tt>
     * function at its begining -- you can cyclicaly parsing any inputs without need of dealocating
     * potentinal forest found, but if you want one forest to survive next parsing, you have to store
     * a pointer returned by <tt>getForestRoot()</tt> function and call its <tt>shackle()</tt>
     * function (see <tt>glrGuard</tt>) class.
     *
     * This function is declared as <tt>virtual</tt> to make possible to override it in your <tt>glrParser<something></tt>
     * -- derived class. It is useful to make some (de)initializations before and after parsing. This function
     * should be called explicitly in the overrided function.
     *
     */
    virtual void parse();
};

template<class glrNodeType,class glrStateType> int
glrParser<glrNodeType,glrStateType>::getNumOfTokens
(){
  return iToken;
}

template<class glrNodeType,class glrStateType> glrNodeType*
glrParser<glrNodeType,glrStateType>::getForestRoot
(){
  return forestRoot;
}

template<class glrNodeType,class glrStateType>
glrParser<glrNodeType,glrStateType>::glrParser
(){
  forestRoot=NULL;
  grammar=NULL;
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::initGrammar
(istream &input){
  grammar=new glrGrammar;
  grammar->read(symbols,input);
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::setGrammar
(glrGrammar *grammarA){
  grammar=grammarA;
}

template<class glrNodeType,class glrStateType> glrGrammar*
glrParser<glrNodeType,glrStateType>::getGrammar
(){
  return grammar;
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::releaseGrammar
(){
  delete grammar;
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::readTable
(istream &input){
  int number,numStates;
  string item;
  glrStateType *state;
  const glrRule *rule;
  input >> numStates;
  states.resize(numStates);
  for(int i=0;i<numStates;++i)states[i]=new glrStateType(i,symbols);
  input >> item;
  while(input>>number){
    state=states[number];
    while((input>>item)&&(item!="|State|")){;
      if(item=="__reduce"){
        input >> number;
        rule=grammar->getRule(number);
        switch(rule->getType()){
          case glrEpsilonRule:
	    state->epsReduces.push_back(rule);
	    break;
	  case glrNonterminalRule:
	    state->reduces.push_back(rule);
	    break;
	  case glrPreterminalRule:
	    state->termReduces.push_back(rule);
	    break;
	  default:
	    cerr << "error: glrParser::readTable: unknown type of rule found in grammar" << endl;
	    break;
        }
      }else{
        glrSymbolTable::glrSymbol symbol=symbols.getSymbolFromString(item);
        input >> number;
        if(symbols.getSymbolType(symbol)==glrSymbolTable::glrNonterminal){
          state->gotos_insert(symbol,states[number]);
	}else{
          state->shifts_insert(symbol,states[number]);
	}
      }
    }
  }
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::printTable
(ostream &output){
  output << states.size() << endl;
  for(typename vector<glrStateType*>::iterator i=states.begin();i!=states.end();++i) {
    if(*i){
      (*i)->print(symbols,output);
    }else{
      cerr << "error: glrParser<glrNodeType,glrStateType>::printTable: state in glr table is NULL!" << endl;
    }
  }
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::printStatus
(ostream &output){
  output << "GLR parser status:" << endl;
  output << "\tnumber of grammar rules is " << grammar->size() << endl;
  output << "\tnumber of states is " << states.size() << endl;
  output << "\tnumber of symbols is " << symbols.size() << endl;
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::readToken
(){
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::parse
(){

  #ifdef DEBUG
  cerr << endl << "parsing is started" << endl << endl;
  glrStateVertex::maxStateVertexId = 0;
  glrStateVertex::numStateVertices = 0;
  #endif

  releaseForestRoot();

  iToken=0;

  #ifdef CHECK_CONSISTENCY
  checkConsistency("before inserting state 0(0) to stack");
  #endif

  states[0]->stack=new glrStateVertex(0, states[0], true);
  //states[0]->crossEdges.clear();
  //states[0]->queFlag = active;
  //states[0]->reducesFlag = false;
  activeStates.push_back(states[0]);

  #ifdef DEBUG
  cerr << "adding state 0 (0) to the active states" << endl;
  #endif

  epsilonReductions(states[0]);

  vector<glrNode*>::iterator term;
  glrStateType *state;

  while(!activeStates.empty()){

    #ifdef CHECK_CONSISTENCY
    checkConsistency("before runReductions()");
    #endif

    runReductions();

    #ifdef CHECK_CONSISTENCY
    checkConsistency("after runReductions()");
    #endif

    for(vector<glrNode*>::iterator term=preterminals.begin();term!=preterminals.end();++term)(*term)->release();
    preterminals.clear();

    readToken();

    if(preterminals.empty()) break; else{
      ++iToken;
      releaseForestRoot();

      int numberOfShifts=activeStates.size();
      while(numberOfShifts){
      
	state = activeStates.front();
	activeStates.pop_front();
	glrStateVertex *fromStack = state->stack;
	state->stack = NULL;
	state->crossEdges.clear();
	
        if((state->futureStack)&&(state->futureStack->getToken()==iToken)){
          state->stack = state->futureStack;
	  activeStates.push_back(state);
        }

	state->futureStack = NULL;

        for(vector<glrNode*>::iterator term=preterminals.begin();term!=preterminals.end();++term){
          glrStateType* const &shift=state->shifts_find((*term)->getSymbol());
          if(shift!=(glrStateType*)NULL){
	    #ifdef DEBUG
	    cerr << "making shift from state " << state->getNumber() << " (" << fromStack->getToken() << ")"
	         << " to state " << shift->getNumber() << " (" << iToken << ")" << endl;
            #endif
            if(shift->stack==NULL){
	      shift->stack = new glrStateVertex(iToken,shift,fromStack,(*term));
	      shift->crossEdges.clear();
	      activeStates.push_back(shift);
            }else{
              if(shift->stack->getToken()==iToken){
		shift->stack->addPred(fromStack, (*term));
              }else{
                if(shift->futureStack==NULL){
                  shift->futureStack=new glrStateVertex(iToken,shift, fromStack,(*term));
                }else{
		  shift->futureStack->addPred(fromStack,(*term));
         	}
              }
            }
          }
        }

	fromStack->release();
	
	numberOfShifts--;
      }
    }

    #ifdef CHECK_CONSISTENCY
    checkConsistency("before runTerminalReductions");
    #endif
    
    runTerminalReductions(); // provede redukce pomoci terminalnich pravidel na stavech, ktere jsou prave aktivni

  }


  for(typename deque<glrStateType*>::iterator state=activeStates.begin();state!=activeStates.end();++state){
    (*state)->stack->release();
    (*state)->stack=NULL;
    (*state)->crossEdges.clear();
    ///(*state)->queFlag = none;
    //(*state)->reducesFlag = false;
  }
  activeStates.clear();

  for(vector<glrNode*>::iterator term=preterminals.begin();term!=preterminals.end();++term)(*term)->release();
  preterminals.clear();

  statesForReductions.clear();

  grammar->resetEpsilonRules();
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::runReductions
(){
  vector<const glrRule*>::iterator iReduction;
  const glrRule *rule;
  glrStateType *fromState;
  deque<glrNode*> succ;
  int rulePos;
  while(!statesForReductions.empty()){
    fromState = statesForReductions.front();

    statesForReductions.pop_front();
    glrStateVertex *fromStack = fromState->futureStack;
    fromState->futureStack = NULL;

    #ifdef DEBUG
    cerr << "starting reductions from state " << fromState->getNumber() << " (" << fromStack->getToken() << ") [" << fromStack->getId() << "]" << endl;
    #endif

    if(fromState->stack){
      fromStack->merge(fromState->stack);
    }else{
      fromState->stack = fromStack;
      fromStack->shackle();
      activeStates.push_back(fromState);
      fromStack->addCrossEdges();
      epsilonReductions(fromState);
    }


    if(!fromState->crossEdges.empty()){
      deque<glrNode*> succ;
      for(vector<pair<glrNode*, glrState*> >::iterator i = fromState->crossEdges.begin(); i!=fromState->crossEdges.end(); ++i){
        succ.push_back(i->first);
        recursiveCrossEdges(fromStack, succ, (glrStateType*)(i->second), grammar->getMaxRuleLength()+1);
        succ.pop_back();
      }
    }

    for(iReduction = fromState->reduces.begin(); iReduction!=fromState->reduces.end(); ++iReduction){
      try{
	const glrSymbolVertex &predsFromSymbol = fromStack->findPreds((*iReduction)->right_back());
	rule = (*iReduction);
	rulePos = rule->right_size()-1;
	for(map<glrNode*,vector<glrStateVertex*> >::const_iterator iNode=predsFromSymbol.statesFromNode_begin();
	      iNode!=predsFromSymbol.statesFromNode_end();++iNode){
	  succ.push_front(iNode->first);
	  if(rulePos){
	    for(vector<glrStateVertex*>::const_iterator iStack=iNode->second.begin();iStack!=iNode->second.end();++iStack){
              #ifdef DEBUG
              cerr << "trying to walk the stack recursively through over the state " << (*iStack)->getState()->getNumber() 
	           << " (" << (*iStack)->getToken() << ")" << endl;
	      #endif
	      recursiveReduce(*iStack,rulePos-1,succ,rule,fromState);
    	    }
	  }else{
	    makeReductions(iNode->second,succ,rule,fromState);
	  }
	  succ.pop_front();
	}
      }catch(glrStackNoPredsException &ex){};
    }

    fromStack->release();
    
  }
}


template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::recursiveCrossEdges
(glrStateVertex *fromStack, deque<glrNode*> &succ, glrStateType *toState, unsigned int const& ttl){

    for(vector<const class glrRule*>::iterator iRule=toState->reduces.begin();iRule!=toState->reduces.end();++iRule){
    
      if((*iRule)->right_size()>succ.size()){

//        cerr << "jsem tu" << endl;

        deque<glrNode*>::reverse_iterator iNode;
        glrRuleRight::const_reverse_iterator iSymbol;
        for(iNode=succ.rbegin(),iSymbol=(*iRule)->right_rbegin();iNode!=succ.rend();++iNode,++iSymbol){
          if((*iSymbol)!=(*iNode)->getSymbol())break;
        }
        if(iNode==succ.rend()){
	  try{
	    const glrSymbolVertex &predsFromSymbol=fromStack->findPreds(*iSymbol);

//	    cerr << "jsem tu 1" << endl;
	    
            for(map<glrNode*,vector<glrStateVertex*> >::const_iterator iStates=predsFromSymbol.statesFromNode_begin();
	        iStates!=predsFromSymbol.statesFromNode_end();++iStates){
	      succ.push_front(iStates->first);
	      if(iSymbol==(*iRule)->right_rend()){
	        makeReductions(iStates->second,succ,*iRule,toState);
	      }else{
	        for(vector<glrStateVertex*>::const_iterator iStack=iStates->second.begin();iStack!=iStates->second.end();++iStack){
		  recursiveReduce(*iStack,(*iRule)->right_size()-succ.size()-1,succ,*iRule,toState);
		}
              }
	      succ.pop_front();
	    }
	  }catch(glrStackNoPredsException &ex){};
	}
      }
    }
  
  if(ttl){
    for(vector<pair<glrNode*,glrState*> >::iterator nextState=toState->crossEdges.begin();nextState!=toState->crossEdges.end();++nextState){
      succ.push_back(nextState->first);
      recursiveCrossEdges(fromStack, succ, (glrStateType*)(nextState->second), ttl-1);
      succ.pop_back();
    }
  }
}


/*template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::makeAditionalReductions
(){
  while(!aditionalReductions.empty()){
    glrStateType *state = aditionalReductions.front();
    state->reducesState = glrRedMakingAditional;
    if(!state->crossEdges.empty()){
      state->crossInProgress = true;
      deque<glrNode*> succ;
      for(vector<pair<glrNode*,glrStateType*> >::iterator i=state->crossEdges.begin();i!=state->crossEdges.end();++i){
        succ.push_back(i->first);
	recursiveCrossEdges(state,succ,i->second);
	succ.pop_back();
      }
      state->crossInProgress = false;
    }
    aditionalReductions.pop_front();
    glrStateVertex *futureStack = state->futureStack;
    state->futureStack = NULL;
    for(vector<const glrRule*>::iterator iReduction=state->reduces.begin();iReduction!=state->reduces.end();++iReduction){
      try{
	const glrSymbolVertex &predsFromSymbol=futureStack->findPreds((*iReduction)->right_back());
	deque<glrNode*> succ;
	const glrRule *rule=(*iReduction);
	int rulePos=rule->right_size()-1;
	for(map<glrNode*,vector<glrStateVertex*> >::const_iterator iNode=predsFromSymbol.statesFromNode_begin();
	    iNode!=predsFromSymbol.statesFromNode_end();++iNode){
	  succ.push_front(iNode->first);
	  if(rulePos){
	    for(vector<glrStateVertex*>::const_iterator iStack=iNode->second.begin();iStack!=iNode->second.end();++iStack){
              #ifdef DEBUG
              cerr << "trying to walk the stack recursively through over the state " << (*iStack)->getState()->getNumber() 
	           << " (" << (*iStack)->getToken() << ")" << endl;
	      #endif
	      recursiveReduce(*iStack,rulePos-1,succ,rule,state);
	    }
	  }else{
	    makeReductions(iNode->second,succ,rule,state);
	  }
	  succ.pop_front();
	}
      }catch(glrStackNoPredsException &ex){};
    }
    futureStack->merge(state->stack);
    futureStack->release();
    if(state->aditionalStack){
      state->futureStack=state->aditionalStack;
      state->aditionalStack=NULL;
    }
    if(state->futureStack){
      state->reducesState=glrRedWaitingForAditional;
    }else{
      state->reducesState=glrRedDone;
    }
  }
}*/

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::recursiveReduce
(const glrStateVertex* const& stack,const int& rulePos,deque<glrNode*> &succ,const glrRule* const& rule,const glrStateType* const& fromState){
  try{
    const glrSymbolVertex &predsFromSymbol=stack->findPreds(rule->right_at(rulePos));
    for(map<glrNode*,vector<glrStateVertex*> >::const_iterator iNode=predsFromSymbol.statesFromNode_begin();
	iNode!=predsFromSymbol.statesFromNode_end();++iNode){
      succ.push_front(iNode->first);
      if(rulePos){
	for(vector<glrStateVertex*>::const_iterator iStack=iNode->second.begin();iStack!=iNode->second.end();++iStack){
          #ifdef DEBUG
          cerr << "trying to walk the stack recursively through over the state " << (*iStack)->getState()->getNumber() 
	       << " (" << (*iStack)->getToken() << ")" << endl;
	  #endif
	  recursiveReduce(*iStack,rulePos-1,succ,rule,fromState);
	}
      }else{
	makeReductions(iNode->second,succ,rule,fromState);
      }
      succ.pop_front();
    }
  }catch (glrStackNoPredsException &ex) {}
}

template<class glrNodeType, class glrStateType> void
glrParser<glrNodeType, glrStateType>::makeReductions
(vector<glrStateVertex*> const& fromVertices, deque<glrNode*> const& succ, const glrRule* const& rule, const glrStateType* const& fromState){

  glrEdgeSet edgeSet;
  glrNodeSet nodeSet;
  
  if(findEdgeAndNodeSetsForReductions(fromVertices,rule,edgeSet,nodeSet)){
    if(forestRoot){
      forestRoot->addSubtree(rule,succ);
    }else{
      forestRoot = new glrNodeType(rule,succ);
    }
  }

  for(glrNodeSet::iterator iNode = nodeSet.begin(); (!edgeSet.empty())&&(iNode!=nodeSet.end()); ++iNode){
    if(edgeSet.containsSubset((*iNode)->edgeSet())){
      (*iNode)->addSubtree(rule,succ);
      edgeSet.substract((*iNode)->edgeSet());
    }
  }

  if(!edgeSet.empty()){
    glrNodeType *sharedNode = new glrNodeType(rule,succ);
    for(glrEdgeSet::iterator iEdge = edgeSet.begin(); iEdge!=edgeSet.end(); ++iEdge){

      glrStateType *gotoState = (glrStateType*)((*iEdge).to());
      glrStateVertex *fromStack = (glrStateVertex*)((*iEdge).from());
      sharedNode->addEdge(fromStack, gotoState);

      if(gotoState->futureStack){
        gotoState->futureStack->addPred(fromStack, sharedNode);
      } else {
        if(gotoState->reduces.empty()&&gotoState->epsReduces.empty()){
	  if(gotoState->stack){
	    gotoState->stack->addPred(fromStack, sharedNode);
	  }else{
	    gotoState->stack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	    gotoState->crossEdges.clear();
	    activeStates.push_back(gotoState);
	  }
	}else{
          gotoState->futureStack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	  if(gotoState->stack){
	    #ifdef BASIC_QUES_HANDLING
	    statesForReductions.push_back(gotoState);
	    #else
	    statesForReductions.push_front(gotoState);
	    #endif
	  }else{
	    statesForReductions.push_back(gotoState);
	  }
	}
      }

      /*switch(gotoState->queFlag){
      case none:
        gotoState->stack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	gotoState->reducesFlag = false;
	activeStates.push_back(gotoState);
	gotoState->crossEdges.clear();
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	  gotoState->queFlag = both;
	}else{
	  gotoState->queFlag = active;
	}
	if(fromStack->getToken()==iToken){
	  ((glrStateType*)(fromStack->getState()))->crossEdges.push_back(pair<glrNodeType*, glrStateType*>(sharedNode, gotoState));
	}
	epsilonReductions(gotoState);
	break;
      case active:
        if(gotoState->reducesFlag){
	  gotoState->futureStack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	  statesForReductions.push_front(gotoState);
	  gotoState->queFlag = both;
	}else{
	  gotoState->stack->addPred(fromStack, sharedNode);
	  if(!gotoState->reduces.empty()){
	    statesForReductions.push_back(gotoState);
	    gotoState->queFlag = both;
	  }
	  if(fromStack->getToken()==iToken){
	    ((glrStateType*)(fromStack->getState()))->crossEdges.push_back(pair<glrNodeType*, glrStateType*>(sharedNode, gotoState));
	  }
	}
	break;
      case both:
        if(gotoState->reducesFlag){
          gotoState->futureStack->addPred(fromStack, sharedNode);
	}else{
	  gotoState->stack->addPred(fromStack, sharedNode);
	}
	break;
      }*/

      /*if((gotoState->stack)&&(gotoState->stack->getToken()==iToken)){
        if(gotoState->stack->reductionsStarted()){
	  if((gotoState->futureStack)&&(gotoState->futureStack->getToken()==iToken)){
	    gotoState->futureStack->addPred(fromStack, sharedNode);
	    //if(fromStack->getToken()==iToken){
	    // ((glrStateType*)(fromStack->getState()))->crossEdges.push_back(pair<glrNodeType*, glrStateType*>(sharedNode, gotoState));
	    //}
	  }else{
	    gotoState->futureStack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	    statesForReductions.push_back(gotoState);
	    //if(fromStack->getToken()==iToken){
	    //  ((glrStateType*)(fromStack->getState()))->crossEdges.push_back(pair<glrNodeType*, glrStateType*>(sharedNode, gotoState));
	    //}
	  }
	}else{
	  gotoState->stack->addPred(fromStack, sharedNode);
	  statesForReductions.push_back(gotoState);
          if(fromStack->getToken()==iToken){
	    ((glrStateType*)(fromStack->getState()))->crossEdges.push_back(pair<glrNodeType*, glrStateType*>(sharedNode, gotoState));
	  }
	}
      }else{
        gotoState->stack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	activeStates.push_back(gotoState);
	gotoState->crossEdges.clear();
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	}
        if(fromStack->getToken()==iToken){
          ((glrStateType*)(fromStack->getState()))->crossEdges.push_back(pair<glrNodeType*, glrStateType*>(sharedNode, gotoState));
        }
 	epsilonReductions(gotoState);
      }*/
    }
    sharedNode->release();
  }
}

/*
template<class glrNodeType,class glrStateType> void 
glrParser<glrNodeType,glrStateType>::makeReductions
(vector<glrStateVertex*> &fromVertices,deque<glrNode*> &succ,const glrRule *rule,glrStateType *fromState){

  
  // glrReductionHint& reductionHint = rule->getReductionHint(succ,iToken);
  // reductionHint.setOwnParent(NULL);
  

  glrNodeType *sharedNode = NULL;

  #ifdef NODE_SHARING
  set<glrNode*> packedNodes;
  #endif

  if(!rule->getNumber()){
    #ifdef DEBUG
    cerr << "making nonterminal reduction from state " << fromState->getNumber() << " (" << fromState->stack->getToken() << "), "
         << "trying forest root using rule number " << rule->getNumber() << ": ";
    rule->print(symbols,cerr);
    cerr << endl;
    #endif
    if(forestRoot){
      #ifdef NODE_SHARING
      if(packedNodes.insert(forestRoot).second){ 
      #endif
        forestRoot->addSubtree(rule,succ); 
      #ifdef NODE_SHARING
      }
      #endif
    }else{
      forestRoot = new glrNodeType(rule,succ);
      #ifdef NODE_SHARING
      sharedNode = forestRoot;
      sharedNode->shackle();
      #endif
    }
  }


  vector<glrStateVertex*>::iterator iStack;
  map<glrStateVertex*,glrNode*>::iterator packedNode;

  #ifdef NODE_SHARING
  set<glrEdge,glrEdgeCompare> edges;
  #endif
  
  for(iStack=fromVertices.begin();iStack!=fromVertices.end();++iStack){

    #ifndef NODE_SHARING
    if(sharedNode){
      sharedNode->release();
      sharedNode = NULL;
    }
    #endif
  
    glrStateType* const &gotoState=((glrStateType*)((*iStack)->getState()))->gotos_find(rule->getLeft());
    if(gotoState!=(glrStateType*)NULL){
      #ifdef DEBUG
      cerr << "making nonterminal reduction from state " << fromState->getNumber() << " (" << fromState->stack->getToken() << "), "
           << "going from state " << (*iStack)->getState()->getNumber() << " (" << (*iStack)->getToken() << ") "
	   << "to state " << gotoState->getNumber();
      #endif
      if(gotoState->stack){

        #ifdef DEBUG
	cerr << " (" << gotoState->stack->getToken() << ") ";
        cerr << "along the rule number " << rule->getNumber() << ": ";
        rule->print(symbols,cerr);
        cerr << endl;
	#endif

	glrStateVertex *gotoStack=gotoState->stack;
	glrSymbolVertex *predsFromSymbol=&(gotoStack->getPreds(rule->getLeft()));
	packedNode=predsFromSymbol->nodeFromState_find(*iStack);
	
	if(packedNode==predsFromSymbol->nodeFromState_end()){
	  switch(gotoState->reducesState){
	    case glrRedMakingAditional:
	      if(!gotoState->aditionalStack){
	        gotoState->aditionalStack=new glrStateVertex(iToken,gotoState);
		aditionalReductions.push_back(gotoState);
              }
	      gotoStack=gotoState->aditionalStack;
	      predsFromSymbol=&(gotoStack->getPreds(rule->getLeft()));
	      packedNode=predsFromSymbol->nodeFromState_find(*iStack);
	      break;
	    case glrRedMaking:
	    case glrRedDone:
	    case glrRedWaitingForAditional:
	      if(!gotoState->futureStack){
	        gotoState->futureStack=new glrStateVertex(iToken,gotoState);
	        aditionalReductions.push_back(gotoState);
		gotoState->reducesState=glrRedWaitingForAditional;
	      }
	      gotoStack=gotoState->futureStack;
	      predsFromSymbol=&(gotoStack->getPreds(rule->getLeft()));
	      packedNode=predsFromSymbol->nodeFromState_find(*iStack);
	      break;
	    case glrRedWaiting:
	      break;
	    case glrRedNotNeed:
	      gotoState->reducesState=glrRedWaiting;
	      statesForReductions.push_back(gotoState);
	      break;
	    default:
	      cerr << "error: glrParser::makeReductions: reached unknown reduces state" << endl;
	  }
	}

        #ifdef NODE_SHARING
        edges.insert(glrEdge((*iStack)->getState()->getNumber(),(*iStack)->getToken(),
	                     gotoState->getNumber(),gotoState->stack->getToken()
			    )
		    );
        #endif

	if(packedNode!=predsFromSymbol->nodeFromState_end()){
	  #ifdef NODE_SHARING
	  if(packedNodes.insert(packedNode->second).second){
	  #endif
	    packedNode->second->addSubtree(rule,succ);
	  #ifdef NODE_SHARING
	  }
	  #endif
	}else{
	  if(!sharedNode){
	    sharedNode = new glrNodeType(rule,succ);
	  }
	  #ifdef DEBUG
	  cerr << "creating edge from vertex " << (*iStack)->getState()->getNumber() << " (" << (*iStack)->getToken() << ") "
	       << "to vertex " << gotoStack->getState()->getNumber() << " (" << gotoStack->getToken() << ") over symbol ,,"
	       << symbols.getStringFromSymbol(reductionHint.getOwnParent()->getSymbol()) << "''" << endl;
	  #endif

          #ifdef NODE_SHARING
	  sharedNode->addEdge((*iStack)->getState()->getNumber(),(*iStack)->getToken(),
	                      gotoState->getNumber(),gotoState->stack->getToken()
			     );
	  #endif
	  predsFromSymbol->addPred(*iStack,sharedNode);

          #ifdef CROSS_EDGES
          if((*iStack)->getToken()==getNumOfTokens()){
            ((glrStateType*)(*iStack)->getState())->crossEdges.push_back(
	      pair<glrNode*,glrStateType*>(reductionHint.getOwnParent(),gotoState)
	    );
	  }
	  #endif
        }
      }else{	// inactive state is actived

        #ifdef DEBUG
	cerr << " (" << iToken << ") ";
        cerr << "along the rule number " << rule->getNumber() << ": ";
        rule->print(symbols,cerr);
        cerr << endl;
	#endif
      
        if(!sharedNode){
	  sharedNode = new glrNodeType(rule,succ);
        }
	gotoState->stack=new glrStateVertex(iToken,gotoState,*iStack,sharedNode);

        #ifdef NODE_SHARING
        edges.insert(glrEdge((*iStack)->getState()->getNumber(),(*iStack)->getToken(),
	                     gotoState->getNumber(),gotoState->stack->getToken()
			    )
		    );
  	sharedNode->addEdge((*iStack)->getState()->getNumber(),(*iStack)->getToken(),
	                    gotoState->getNumber(),gotoState->stack->getToken()
			   );
	#endif

        #ifdef CROSS_EDGES
	gotoState->crossEdges.clear();
	#endif

	activeStates.push_back(gotoState);
	if(!gotoState->reduces.empty()){
	  gotoState->reducesState=glrRedWaiting;
	  statesForReductions.push_back(gotoState);
	}else{
	  gotoState->reducesState=glrRedNotNeed;
	}
	epsilonReductions(gotoState);
	
	#ifdef CROSS_EDGES
        if((*iStack)->getToken()==getNumOfTokens()){
          ((glrStateType*)(*iStack)->getState())->crossEdges.push_back(
	    pair<glrNode*,glrStateType*>(reductionHint.getOwnParent(),gotoState)
	  );
	}
	#endif

      }
    }
  }

  #ifdef NODE_SHARING
  set<glrNode*> &packedNodes = reductionHint.getPackedNodes();
  for(set<glrNode*>::iterator iNode = packedNodes.begin(); iNode!=packedNodes.end(); ++iNode){
    for(set<glrEdge,glrEdgeCompare>::iterator iEdge = (*iNode)->edgeSet().begin(); iEdge!=(*iNode)->edgeSet().end(); ++iEdge){
      if(edges.find(*iEdge)==edges.end()){
        cerr << "makeReductions: subtree added to node shared by nonvisited edges; the processed rule is ";
	rule->print(symbols,cerr);
	cerr << endl;
	cerr << "edges.size()=" << edges.size() << ", (*iNode)->edgeSet().size()=" << (*iNode)->edgeSet().size()
	     << ", (*iNode)->getNumOfPointers()=" << (*iNode)->getNumOfPointers() << endl;
	cerr << "rule->getNumber()=" << rule->getNumber() << ", fromState->getNumber()=" << fromState->getNumber() << endl;
	cerr << "reducesStates of target states are: ";
	for(set<glrEdge,glrEdgeCompare>::const_iterator i = edges.begin(); i!=edges.end(); ++i){
	  string textState;
	  switch(states[(*i).to().first]->reducesState){
	    case glrRedMaking: 
	      textState = "glrRedMaking";
	      break;
	    case glrRedMakingAditional:
	      textState = "glrRedMakingAditional";
	      break;
	    case glrRedNotNeed:
	      textState = "glrRedNotNeed";
	      break;
	    case glrRedDone:
	      textState = "glrRedDone";
	      break;
	    case glrRedWaiting:
	      textState = "glrRedWaiting";
	      break;
	    case glrRedWaitingForAditional:
	      textState = "glrRedWaitingForAditional";
	      break;
	    default:
	      textState = "error";
	      break;
	  }
	  cerr << textState << " ";
	}
	cerr << endl;
	cerr << "packed nodes are: ";
	for(set<glrEdge,glrEdgeCompare>::const_iterator i = edges.begin(); i!=edges.end(); ++i){
	  cerr << (*i).from().first << " (" << (*i).from().second << ") -> " << (*i).to().first << " (" << (*i).to().second << "), ";
	}
	cerr << endl;
	cerr << "nodes which share the node are: ";
	for(set<glrEdge,glrEdgeCompare>::const_iterator i = (*iNode)->edgeSet().begin(); i!=(*iNode)->edgeSet().end(); ++i){
	  cerr << (*i).from().first << " (" << (*i).from().second << ") -> " << (*i).to().first << " (" << (*i).to().second << "), ";
	}
	cerr << endl;
	break;
      }
    }
  }
  #endif

  if(sharedNode){
    sharedNode->release();
  }
}*/

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::releaseForestRoot
(){
  if(forestRoot){forestRoot->release();forestRoot=NULL;}
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::runTerminalReductions
(){

  int numStates=activeStates.size();
  vector<const glrRule*>::iterator iReduction;
  deque<glrNode*> succ;
  const glrRule *rule;
  glrStateType *fromState;
  int rulePos;
  int iState = 0;
  while(numStates){
    glrStateType *fromState = activeStates[iState];
    epsilonReductions(fromState);
    for(iReduction=fromState->termReduces.begin();iReduction!=fromState->termReduces.end();++iReduction){
        try{
	  succ.clear();
	  rule=(*iReduction);
	  rulePos=rule->right_size()-1;
	  const glrSymbolVertex &predsFromSymbol=fromState->stack->findPreds(rule->right_back());
	  for(map<glrNode*,vector<glrStateVertex*> >::const_iterator iNode=predsFromSymbol.statesFromNode_begin();
	      iNode!=predsFromSymbol.statesFromNode_end();++iNode){
	    succ.push_front(iNode->first);
		
	    #ifdef DEBUG
	    cerr << "starting terminal reduction from vertex " << fromState->getNumber() << " (" << fromState->stack->getToken() << ")" << endl;
	    #endif
	    
	    if(rulePos){
	      for(vector<glrStateVertex*>::const_iterator iStack=iNode->second.begin();iStack!=iNode->second.end();++iStack){
	        recursiveTermReduce(*iStack,rulePos-1,succ,rule,fromState);
    	      }
	    }else{
	      makeTerminalReductions(iNode->second,succ,rule,fromState);
	    }
	    succ.pop_front();
	  }
	}catch(glrStackNoPredsException &ex){};
    }
    --numStates;
    ++iState;
  }
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::epsilonReductions
(glrStateType *state){
  for(vector<const glrRule*>::iterator iReduction=state->epsReduces.begin();iReduction!=state->epsReduces.end();++iReduction){

    glrStateType* const &gotoState=state->gotos_find((*iReduction)->getLeft());
    glrNodeType *node;

    node = (glrNodeType*)((*iReduction)->getEpsilonNode(iToken));
    
    if(node==NULL){
      node = new glrNodeType(*iReduction);
      ((glrRule*)(*iReduction))->setEpsilonNode(iToken, node);
    } else {
      node->shackle();
    }

    node->addEdge(state->stack, gotoState);

    if(gotoState->futureStack){
      gotoState->futureStack->addPred(state->stack, node);
    }else{
      if(gotoState->reduces.empty()&&gotoState->epsReduces.empty()){
        if(gotoState->stack){
	  gotoState->stack->addPred(state->stack, node);
	}else{
	  gotoState->stack = new glrStateVertex(iToken, gotoState, state->stack, node);
	  gotoState->crossEdges.clear();
	  activeStates.push_back(gotoState);
	}
      }else{
        gotoState->futureStack = new glrStateVertex(iToken, gotoState, state->stack, node);
        if(gotoState->stack){
	  #ifdef BASIC_QUES_HANDLING
	  statesForReductions.push_back(gotoState);
	  #else
	  statesForReductions.push_front(gotoState);
	  #endif
        }else{
          statesForReductions.push_back(gotoState);
        }
      }
    }

    node->release();

    /*if(gotoState->queFlag==none){
      gotoState->stack = new glrStateVertex(iToken, gotoState, state->stack, node);
      gotoState->reducesFlag = false;
      activeStates.push_back(gotoState);
      gotoState->crossEdges.clear();
      if(!gotoState->reduces.empty()){
        statesForReductions.push_back(gotoState);
	gotoState->queFlag = both;
      }else{
        gotoState->queFlag = active;
      }
      state->crossEdges.push_back(pair<glrNode*,glrStateType*>(node, gotoState));
      epsilonReductions(gotoState);
    }else if(gotoState->queFlag==active){
      if(gotoState->reducesFlag){
        gotoState->futureStack = new glrStateVertex(iToken, gotoState, state->stack, node);
	statesForReductions.push_front(gotoState);
	gotoState->queFlag = both;
      }else{
        gotoState->stack->addPred(state->stack, node);
	state->crossEdges.push_back(pair<glrNode*,glrStateType*>(node, gotoState));
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	  gotoState->queFlag = both;
	}
      }
    }else if(gotoState->queFlag==both){
      gotoState->futureStack->addPred(state->stack, node);
    }*/

    // node->release();
      

    /*bool addCrossEdges = false;
    if((gotoState->stack)&&(gotoState->stack->getToken()==iToken)){
      if(gotoState->stack->reductionsStarted()){
        if((gotoState->futureStack)&&(gotoState->futureStack->getToken()==iToken)){
	  newNode = new glrNodeType(*iReduction);
	  newNode->addEdge(state->stack, gotoState);
	  gotoState->futureStack->addPred(state->stack, newNode);
	}else{
	  newNode = new glrNodeType(*iReduction);
	  newNode->addEdge(state->stack, gotoState);
	  gotoState->(futureStack = new glrStateVertex(iToken, gotoState, state->stack, newNode);
	  statesForReductions.push_back(gotoState);
	}
      }else{
	newNode = new glrNodeType(*iReduction);
	newNode->addEdge(state->stack, gotoState);
	gotoState->stack->addPred(state->stack, newNode);
	addCrossEdges = true;
      }
    }else{
      newNode = new glrNodeType(*iReduction);
      newNode->addEdge(state->stack, gotoState);
      gotoState->stack = new glrStateVertex(iToken, gotoState, state->stack, newNode);
      activeStates.push_back(gotoState);
      gotoState->crossEdges.clear();
      if(!gotoState->reduces.empty()){
        statesForReductions.push_back(gotoState);
      }
      epsilonReductions(gotoState);
      addCrossEdges = true;
    }
    if(addCrossEdges){
      state->crossEdges.push_back(pair<glrNode*,glrStateType*>(newNode, gotoState));
    }
    newNode->release();*/
      
    /*
    if(gotoState->stack){
      glrStateVertex *nextStack;
      switch(gotoState->reducesState){
        case glrRedNotNeed:
          gotoState->reducesState=glrRedWaiting;
          statesForReductions.push_back(gotoState);
	  nextStack=gotoState->stack;
          break;
        case glrRedMaking:
	case glrRedDone:
	case glrRedWaitingForAditional:
	case glrRedMakingAditional:
	  if(!gotoState->futureStack){
	    gotoState->futureStack = new glrStateVertex(iToken,gotoState);
	    statesForReductions.push_back(gotoState);
	    gotoState->reducesState = glrRedWaitingForAditional;
	  }
	  nextStack=gotoState->futureStack;
	  break;
        case glrRedWaiting:
	  nextStack=gotoState->stack;
          break;
        default:
          cerr << "error: glrParser::epsilonReductions: come to state with unknown reducesState" << endl;
      }  
      glrSymbolVertex &predsFromSymbol=nextStack->getPreds((*iReduction)->getLeft());

      glrNodeType *newNode = new glrNodeType(*iReduction);
      nextStack->addPred(state->stack,newNode);
      newNode->release();

      state->crossEdges.push_back(pair<glrNode*,glrStateType*>(newNode,gotoState));

      #ifdef DEBUG
      cerr << "making epsilon reduction from state " << state->getNumber() << " (" << state->stack->getToken() << ") " 
           << "to state " << gotoState->getNumber() << " (" << nextStack->getToken() << ") "
           << "over rule " << (*iReduction)->getNumber() << ": ";
      (*iReduction)->print(symbols,cerr);
      cerr << endl;
      #endif
    }else{
      #ifdef DEBUG
      cerr << "making epsilon reduction from state " << state->getNumber() << " (" << state->stack->getToken() << ") "
           << "to state " << gotoState->getNumber() << " (" << iToken << ") "
           << "over rule " << (*iReduction)->getNumber() << ": ";
      (*iReduction)->print(symbols,cerr);
      cerr << endl;
      #endif

      glrNodeType *newNode = new glrNodeType(*iReduction);
      gotoState->stack=new glrStateVertex(iToken,gotoState,state->stack,newNode);
      newNode->release();
      
      gotoState->crossEdges.clear();
      state->crossEdges.push_back(pair<glrNode*,glrStateType*>(newNode,gotoState));

      gotoState->reducesState=glrRedWaiting;
      activeStates.push_back(gotoState);
      statesForReductions.push_back(gotoState);
      epsilonReductions(gotoState);
    }*/
  }
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::recursiveTermReduce
(const glrStateVertex* const& stack,const int &rulePos,deque<glrNode*> &succ,const glrRule* const& rule,const glrStateType* const& fromState){
  try{
    const glrSymbolVertex &predsFromSymbol=stack->findPreds(rule->right_at(rulePos));
    for(map<glrNode*,vector<glrStateVertex*> >::const_iterator iNode=predsFromSymbol.statesFromNode_begin();
	iNode!=predsFromSymbol.statesFromNode_end();++iNode){
      succ.push_front(iNode->first);
      if(rulePos){
	for(vector<glrStateVertex*>::const_iterator iStack=iNode->second.begin();iStack!=iNode->second.end();++iStack){
          #ifdef DEBUG
          cerr << "trying to walk the stack recursively through over the state " << (*iStack)->getState()->getNumber() 
	       << " (" << (*iStack)->getToken() << ") (to make terminal reduction)" << endl;
	  #endif
	  recursiveTermReduce(*iStack,rulePos-1,succ,rule,fromState);
	}
      }else{
        makeTerminalReductions(iNode->second, succ, rule, fromState);
      }
      succ.pop_front();
    }
  }catch (glrStackNoPredsException &ex) {}
}

template<class glrNodeType, class glrStateType> bool
glrParser<glrNodeType, glrStateType>::findEdgeAndNodeSetsForReductions
(const vector<glrStateVertex*> &fromVertices, const glrRule* const& rule, glrEdgeSet& edgeSet, glrNodeSet& nodeSet){
  
  glrSymbolTable::glrSymbol const& symbol = rule->getLeft();
  bool ret = false;
  for(vector<glrStateVertex*>::const_iterator iStack = fromVertices.begin(); iStack!=fromVertices.end(); ++iStack){
    ret=((*iStack)->bottom())||ret;
    glrStateType *gotoState = ((glrStateType*)((*iStack)->getState()))->gotos_find(symbol);
    if(gotoState){
      edgeSet.insert(glrEdge(*iStack, gotoState));
      glrStateVertex *gotoStack;
      if(gotoState->stack){
        gotoStack = gotoState->stack;
      }else{
        gotoStack = gotoState->futureStack;
      }
      while(gotoStack){
        try{
          const glrSymbolVertex &predsFromSymbol = gotoStack->findPreds(symbol);
	  map<glrStateVertex*,vector<glrNode*> >::const_iterator nodesFromState = predsFromSymbol.nodesFromState_find(*iStack);
	  if(nodesFromState!=predsFromSymbol.nodesFromState_end()){
	    nodeSet.insert(nodesFromState->second);
	  }
	}catch(glrStackNoPredsException &e){}
	if(gotoStack==gotoState->stack) { gotoStack = gotoState->futureStack; }
	else gotoStack = NULL;
      }
    }
  }
//  ret = true;
  return ret&&(rule->getNumber()==0);
}
	  

template<class glrNodeType, class glrStateType> void
glrParser<glrNodeType, glrStateType>::makeTerminalReductions
(const vector<glrStateVertex*> &fromVertices, const deque<glrNode*> &succ, const glrRule* const& rule,const glrStateType* const& fromState ){

  glrEdgeSet edgeSet;
  glrNodeSet nodeSet;
  
  if(findEdgeAndNodeSetsForReductions(fromVertices,rule,edgeSet,nodeSet)){
    if(forestRoot){
      forestRoot->addSubtree(rule,succ);
    }else{
      forestRoot = new glrNodeType(rule,succ);
    }
  }

  for(glrNodeSet::iterator iNode = nodeSet.begin(); (!edgeSet.empty())&&(iNode!=nodeSet.end()); ++iNode){
    if(edgeSet.containsSubset((*iNode)->edgeSet())){
      (*iNode)->addSubtree(rule,succ);
      edgeSet.substract((*iNode)->edgeSet());
    }
  }

  if(!edgeSet.empty()){
    glrNodeType *sharedNode = new glrNodeType(rule,succ);
    for(glrEdgeSet::iterator iEdge = edgeSet.begin(); iEdge!=edgeSet.end(); ++iEdge){

      glrStateType *gotoState = (glrStateType*)((*iEdge).to());
      glrStateVertex *fromStack = (glrStateVertex*)((*iEdge).from());
      sharedNode->addEdge(fromStack, gotoState);

      if(gotoState->futureStack){
        gotoState->futureStack->addPred(fromStack, sharedNode);
      } else {
        if(gotoState->reduces.empty()&&gotoState->epsReduces.empty()){
	  if(gotoState->stack){
	    gotoState->stack->addPred(fromStack, sharedNode);
	  }else{
	    gotoState->stack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	    gotoState->crossEdges.clear();
	    activeStates.push_back(gotoState);
	  }
	}else{
          gotoState->futureStack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	  statesForReductions.push_back(gotoState);
	}
      }

      /*if(gotoState->queFlag==none){
        gotoState->stack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	activeStates.push_back(gotoState);
	gotoState->crossEdges.clear();
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	  gotoState->queFlag = both;
	}else{
	  gotoState->queFlag = active;
	}
	gotoState->reducesFlag = false;
	epsilonReductions(gotoState);
      } else if (gotoState->queFlag==active) {
        gotoState->stack->addPred(fromStack, sharedNode);
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	  gotoState->queFlag = both;
	}
      } else if (gotoState->queFlag==both){
        gotoState->stack->addPred(fromStack, sharedNode);
      }*/

      /*if((gotoState->stack)&&(gotoState->stack->getToken()==iToken)){
        gotoState->stack->addPred(fromStack, sharedNode);
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	}
      }else{
        gotoState->stack = new glrStateVertex(iToken, gotoState, fromStack, sharedNode);
	activeStates.push_back(gotoState);
	gotoState->crossEdges.clear();
	if(!gotoState->reduces.empty()){
	  statesForReductions.push_back(gotoState);
	}
	epsilonReductions(gotoState);
      }*/

      /*if(gotoState->reduces.empty()){
      }else if(gotoState->reducesState!=glrRedWaiting){
        gotoState->reducesState = glrRedWaiting;
        statesForReductions.push_back(gotoState);
      }
      if(!gotoState->stack){
        gotoState->stack = new glrStateVertex(getNumOfTokens(),gotoState);
	activeStates.push_back(gotoState);
	gotoState->crossEdges.clear();
	epsilonReductions(gotoState);
      }*/

    }
    sharedNode->release();
  }
}

/*
template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::makeTerminalReductions
(vector<glrStateVertex*> &fromVertices,deque<glrNode*> &succ,const glrRule *rule,glrStateType *fromState){

  
  //glrReductionHint& reductionHint = rule->getReductionHint(succ,iToken);
  //reductionHint.setOwnParent(NULL);
  

  glrNodeType *sharedNode = NULL;

  #ifdef NODE_SHARING
  set<glrNode*> packedNodes;
  #endif

  if(!rule->getNumber()){
    #ifdef DEBUG
    cerr << "making terminal reduction from state " << fromState->getNumber() << " (" << fromState->stack->getToken() << "), "
         << "trying forest root using rule number " << rule->getNumber() << ": ";
    rule->print(symbols,cerr);
    cerr << endl;
    #endif
    if(forestRoot){
      #ifdef NODE_SHARING
      if(packedNodes.insert(forestRoot).second){
      #endif
        forestRoot->addSubtree(rule,succ);
      #ifdef NODE_SHARING
      }
      #endif
    }else{
      forestRoot = new glrNodeType(rule,succ);
      #ifdef NODE_SHARING
      sharedNode = forestRoot;
      sharedNode->shackle();
      #endif
    }
  }

  vector<glrStateVertex*>::iterator iStack;
  map<glrStateVertex*,glrNode*>::iterator packedNode;

  for(iStack=fromVertices.begin();iStack!=fromVertices.end();++iStack){

    #ifndef NODE_SHARING
    if(sharedNode){
      sharedNode->release();
      sharedNode = NULL;
    }
    #endif
  
    glrStateType* const &gotoState=((glrStateType*)((*iStack)->getState()))->gotos_find(rule->getLeft());
    if(gotoState!=(glrStateType*)NULL){
      #ifdef DEBUG
      cerr << "making terminal reduction from state " << fromState->getNumber() << " (" << fromState->stack->getToken() << "), "
           << "going from state " << (*iStack)->getState()->getNumber() << " (" << (*iStack)->getToken() << ") "
	   << "to state " << gotoState->getNumber();
      #endif
      if(gotoState->stack){
        #ifdef DEBUG
	cerr << "(" << gotoState->stack->getToken() << ")";
        cerr << " along rule number " << rule->getNumber() << ": ";
        rule->print(symbols,cerr);
        cerr << endl;
	#endif
	glrSymbolVertex &predsFromSymbol=gotoState->stack->getPreds(rule->getLeft());
	packedNode=predsFromSymbol.nodeFromState_find(*iStack);
	if(packedNode!=predsFromSymbol.nodeFromState_end()){
	  #ifdef NODE_SHARING
	  if(packedNodes.insert(packedNode->second).second){
	  #endif
	    packedNode->second->addSubtree(rule,succ);
	  #ifdef NODE_SHARING
	  }
	  #endif
	}else{
	  if(!sharedNode){
	    sharedNode = new glrNodeType(rule,succ);
	  }
	  #ifdef DEBUG
	  cerr << "creating edge from vertex " << (*iStack)->getState()->getNumber() << " (" << (*iStack)->getToken() << ") "
	       << "to vertex " << gotoState->getNumber() << " (" << gotoState->stack->getToken() << ") over symbol ,,"
	       << symbols.getStringFromSymbol(reductionHint.getOwnParent()->getSymbol()) << "''" << endl;
	  #endif
	  predsFromSymbol.addPred(*iStack,sharedNode);
	  if((!gotoState->reduces.empty())&&(gotoState->reducesState!=glrRedWaiting)){
	    gotoState->reducesState = glrRedWaiting;
	    statesForReductions.push_back(gotoState);
	  }
        }
      }else{

       	#ifdef DEBUG
	cerr << "(" << iToken << ")";
        cerr << " along rule number " << rule->getNumber() << ": ";
        rule->print(symbols,cerr);
        cerr << endl;
	#endif

       if(!sharedNode){
	  sharedNode = new glrNodeType(rule,succ);
        }
	gotoState->stack=new glrStateVertex(iToken,gotoState,*iStack,sharedNode);

	#ifdef CROSS_EDGES
	gotoState->crossEdges.clear();
	#endif

	gotoState->reducesState=glrRedNotNeed;
	activeStates.push_back(gotoState);
	if(!gotoState->reduces.empty()){
	  gotoState->reducesState=glrRedWaiting;
	  statesForReductions.push_back(gotoState);
	}
	epsilonReductions(gotoState);
      }
    }
  }
  if(sharedNode){
    sharedNode->release();
  }
}*/

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::computeTable
(){

  clearTable();

  glrCompStatesMap<glrStateType> compStatesMap;
  glrGrammarMap grammarMap;
  glrCompRule *grammarHead=grammar->initGrammarMap(symbols,grammarMap);
  deque<glrCompState<glrStateType>*> compStatesQue;
  glrStateType *firstRealState=new glrStateType(0,symbols);
  states.push_back(firstRealState);
  glrCompState<glrStateType> *firstState=new glrCompState<glrStateType>(firstRealState);
  compStatesQue.push_back(firstState);
  compStatesMap.insert(pair<glrItemSet*,glrStateType*>((glrItemSet*)NULL,firstRealState));
  firstState->transitions[grammar->getRule(0)->right_at(0)]=new glrItemSet(grammarHead->symbolType_at(0));
  firstState->transitions[grammar->getRule(0)->right_at(0)]->insert(glrItem(0,grammarHead,true));
  int stateNumber=0;
  
  while(!compStatesQue.empty()){

    glrCompState<glrStateType> *compState=compStatesQue.front();
    compStatesQue.pop_front();

    for(map<glrSymbolTable::glrSymbol,glrItemSet*>::iterator tran=compState->transitions.begin();tran!=compState->transitions.end();++tran){
      for(glrItemSet::iterator item=tran->second->begin();item!=tran->second->end();++item){
        if(item->notRecursed){
	  makeCap(grammarMap,*compState,*item);
	}
      }
    }

    for(map<glrSymbolTable::glrSymbol,glrItemSet*>::iterator tran=compState->transitions.begin();tran!=compState->transitions.end();++tran){
      typename glrCompStatesMap<glrStateType>::iterator iNextState=compStatesMap.find(tran->second);
      if(iNextState==compStatesMap.end()){

	glrStateType *newState=new glrStateType(states.size(),symbols);
	states.push_back(newState);
	glrCompState<glrStateType> *nextState=new glrCompState<glrStateType>(newState);
        compStatesQue.push_back(nextState);
	compStatesMap[tran->second]=newState;

        if(tran->second->getSymbolType()==glrSymbolTable::glrPreterminal){
          compState->state->shifts_insert(tran->first,nextState->state);
        }else{
          compState->state->gotos_insert(tran->first,nextState->state);
        }
        for(glrItemSet::iterator item=tran->second->begin();item!=tran->second->end();++item){
          if((item->dot+1)==item->compRule->rule->right_size()){
	    if(item->compRule->symbolTypes_back()==glrSymbolTable::glrPreterminal){
	      nextState->state->termReduces.push_back(item->compRule->rule);
	    }else{
	      nextState->state->reduces.push_back(item->compRule->rule);
	    }
	  }else{
            if(nextState->transitions.find(item->compRule->rule->right_at(item->dot+1))==nextState->transitions.end()){
	      nextState->transitions[item->compRule->rule->right_at(item->dot+1)]=new glrItemSet(item->compRule->symbolType_at(item->dot+1));
	    }
	    nextState->transitions[item->compRule->rule->right_at(item->dot+1)]->insert(glrItem(item->dot+1,item->compRule,true));
	  }
        }
      }else{
        glrStateType *nextState=iNextState->second;
	if(tran->second->getSymbolType()==glrSymbolTable::glrPreterminal){
          compState->state->shifts_insert(tran->first,nextState);
        }else{
          compState->state->gotos_insert(tran->first,nextState);
        }
	delete tran->second;
      }
    }
    ++stateNumber;
    delete compState;
  }
  grammarMap.releaseCompRules();
  compStatesMap.releaseItemSets();
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::makeCap
(const glrGrammarMap &grammarMap,glrCompState<glrStateType> &compState,const glrItem &item){
  if(item.compRule->symbolType_at(item.dot)==glrSymbolTable::glrNonterminal){
    const vector<glrCompRule*> &rules=grammarMap[item.compRule->rule->right_at(item.dot)];
    for(vector<glrCompRule*>::const_iterator compRule=rules.begin();compRule!=rules.end();++compRule){
      if((*compRule)->rule->getType()==glrEpsilonRule){
	vector<const glrRule*>::const_iterator iRule;
        for(iRule=compState.state->epsReduces.begin();iRule!=compState.state->epsReduces.end();++iRule)
	  if((*compRule)->rule==(*iRule))break;
	if(iRule==compState.state->epsReduces.end())
          compState.state->epsReduces.push_back((*compRule)->rule);
      }else{
        glrItem newItem(0,*compRule,false);
	glrItemSet *destSet;
	if(compState.transitions.find((*compRule)->rule->right_at(0))==compState.transitions.end()){
	  destSet=new glrItemSet((*compRule)->symbolType_at(0));
	  compState.transitions[(*compRule)->rule->right_at(0)]=destSet;
	}else{
	  destSet=compState.transitions[(*compRule)->rule->right_at(0)];
	} 
	if(destSet->find(newItem)==destSet->end()){
	  destSet->insert(newItem);
	  makeCap(grammarMap,compState,newItem);
	}
      }
    }
  }
}

template<class glrNodeType,class glrStateType> void
glrParser<glrNodeType,glrStateType>::clearTable
(){
  for(typename vector<glrStateType*>::iterator iState=states.begin();iState!=states.end();++iState){
    delete (*iState);
  }
  states.clear();
}

template<class glrNodeType,class glrStateType>
glrParser<glrNodeType,glrStateType>::~glrParser
(){
  releaseForestRoot();
}

template<class glrStateType>
glrCompState<glrStateType>::glrCompState
(glrStateType *stateA){
  state=stateA;
}

template<class glrStateType> void
glrCompStatesMap<glrStateType>::releaseItemSets
(){
  for(typename glrCompStatesMap<glrStateType>::iterator i=this->begin();i!=this->end();++i)delete i->first;
  this->clear();
}

#ifdef CHECK_CONSISTENCY
template<class glrNodeType,class glrStateType> bool
glrParser<glrNodeType,glrStateType>::checkConsistency
(const string &msg){
  for(vector<glrStateType*>::iterator iState = states.begin(); iState!=states.end(); ++iState){
    int numActiveQue = 0;
    int numReducesQue = 0;
    for(deque<glrStateType*>::iterator i = activeStates.begin(); i!=activeStates.end(); ++i){
      if((*i)==(*iState)){
        numActiveQue++;
      }
    }
    for(deque<glrStateType*>::iterator i = statesForReductions.begin(); i!=statesForReductions.end(); ++i){
      if((*i)==(*iState)){
        numReducesQue++;
      }
    }
    if(
       ( ! ( (numActiveQue==1)&&(numReducesQue==1)&&((*iState)->stack)&&((*iState)->stack->getToken()==iToken)&&((*iState)->futureStack)&&((*iState)->futureStack->getToken()==iToken)&&((*iState)->stack!=(*iState)->futureStack))   ) &&
       ( ! ( (numActiveQue==1)&&(numReducesQue==0)&&((*iState)->stack)&&((*iState)->stack->getToken()==iToken)&&((*iState)->futureStack==NULL)   ) &&
       ( ! ( (numActiveQue==0)&&(numReducesQue==0)&&((*iState)->stack==NULL)&&((*iState)->futureStack==NULL)   ) ) ) &&
       ( ! ( (numActiveQue==0)&&(numReducesQue==1)&&((*iState)->stack==NULL)&&((*iState)->futureStack)&&((*iState)->futureStack->getToken()==iToken) ) )
      ){
      cerr << "error in consistency: " << msg << ": state: " << (*iState)->getNumber() << endl;
      cerr << "\tnumActiveQue = " << numActiveQue << endl;
      cerr << "\tnumRedQue = " << numReducesQue << endl;
      cerr << "\tstack = " << (*iState)->stack << endl;
      if ((*iState)->stack) cerr << "\tstack->getToken() == " << (*iState)->stack->getToken() << endl;
      cerr << "\tfutureStack = " << (*iState)->futureStack << endl;
      if ((*iState)->futureStack) cerr << "\tfutureStack->getToken() == " << (*iState)->futureStack->getToken() << endl;
    }
  }
}
#endif

#endif