#include "semcheck.h"

/****************************************************************
**    FileName :  LEFT_RECURSION_FREE.c                        **
*****************************************************************/

int Cd_graph::LEFT_RECURSION_FREE()
{
   int result = 1;
   /* make a copy in order to avoid affecting the following checks */
   cout << "\nChecking whether there is some left recursion ..." << endl;
   Adjacency_Nlist *adjacencies_copy=(Adjacency_Nlist *)adjacencies->g_copy();
   adjacencies_copy->find_nullable_vertices();
   adjacencies_copy->LEFT_RECURSION_FREE(result);
   return (result);
}

void Adjacency_Nlist::LEFT_RECURSION_FREE(int& result)
{
  Adjacency_list_iterator next(*this);
  Adjacency*              each;
  Adjacency_List*        stack = NULL;

  while (each=next())
    if (each->get_dfs()==NULL)
      {
	stack = new Adjacency_List();
	each->LEFT_RECURSION_FREE(this,stack,result);
      }
}


void Adjacency::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{

 if (dfs==NULL)
 {
     dfs = new DemNumber(0);
     stack->append(this);
     ns->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
     dfs->set_val(1);
     Adjacency_List* newstack = new Adjacency_List();
     Adjacency_list_iterator  next(*stack);
     Adjacency*               each;
     while (each = next())
       if (each != this)
          newstack->append(each);
     stack = newstack;
 }
 else
 if (dfs->get_val()==0)    //It is still on the path
 {
     stack->LEFT_RECURSION_FREE_PRINT(this);
     result = 0;
 }
}

void Neighbors::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
}

void Repetit_n::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
    sandwiched->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Kernel_Sandwich::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
   int r = NULLABLE;
   first->nullable(r);
   if (r==NULLABLE)
     inner->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Kernel::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
 if (nonempty)
     nonempty->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
 else
     repeated->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Term_Sandwich::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
    int r = NULLABLE;
    first->nullable(r);
    if (r==NULLABLE)
	inner->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}



void Construct_ns::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
   this->get_construct_ns()->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Alternat_ns::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
   alternat_ns->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Any_vertex_List::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
   Any_vertex_list_iterator next(*this);
   Any_vertex*              each;
   int r = NULLABLE;

   while (each= next())
   {
     each->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
     each->nullable(adj_Nlist,r);
     if (r == NONEMPTY) break;
   }
}

void Any_vertex::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
}


void Opt_labeled_term::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
    this->get_vertex()->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}


void Optional_term::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
   opt->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Opt_labeled_term_Sandwich::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
   int r = NULLABLE;
   first->nullable(r);
   if (r==NULLABLE)
      inner->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}

void Term_Bar_list::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
 Term_list_iterator next(*this);
 Term*              each;
 while (each=next())
   each->LEFT_RECURSION_FREE(adj_Nlist,stack,result);
}


void Term::LEFT_RECURSION_FREE(Adjacency_Nlist *adj_Nlist,Adjacency_List*&stack,int& result)
{
    adj_Nlist->LEFT_RECURSION_FREE(this->get_vertex(),stack,result);
}

Adjacency *Adjacency_Nlist::LEFT_RECURSION_FREE(Vertex *v,Adjacency_List*&stack,int& result)
{
      Adjacency_list_iterator next(*this);
      Adjacency*              each;
      while (each=next())
	if (v->g_equal(each->get_source()))
	     each->LEFT_RECURSION_FREE(this,stack,result);
	return NULL;
}


void Adjacency_List::LEFT_RECURSION_FREE_PRINT(Adjacency*a)
{
    static int count = 1;
    Adjacency_list_iterator next(*this);
    Adjacency*              each;
    while (each=next())
       if (each->get_source()->g_equal(a->get_source()))
          break;
    cout << "Find a left recursion(" << count++ << ") :\n";
    while (each)
    {
       each->LEFT_RECURSION_PRINT();
       each=next();
    }
}

void  Adjacency::LEFT_RECURSION_PRINT()
{
    cout << "        ";
    source->pp();
    ns->pp();
    cout << ".\n";
}