#include <iostream>
using namespace std;

#include "dgp0.hh"
#include "global.hh"

extern Grammar grammar;
extern MGraph mgraph;
extern SGraph sgraph;

extern bool debug;

list<int> nodelist;
list<int>::iterator processed;


void print_sets(int n);


//====================================================================================================

void set_initial_constraints(int node)
{
  sgraph[node].prop.forbidden.reset();
  sgraph[node].prop.required=grammar.is_obl(sgraph.cat(node));
  sgraph[node].prop.attached.reset();
  sgraph[node].prop.flags=grammar.initial_flags(sgraph.cat(node));
}

//----------------------------------------------------------------------------------------------------

bool changing_constraints(int head, Role role)
{
  return grammar.is_sgl(role) || sgraph[head].prop.required[role];
}

//====================================================================================================

NodeProp compute_head_prop(NodeProp headprop, const Link& link, list<Boubble*> bs, FlagSet& depflags)
{
  NodeProp ret=headprop;

  if(grammar.is_sgl(link.role))
    {
      ret.forbidden.set(link.role);
      ret.attached.set(link.role);
    }
  ret.required.reset(link.role);

  ret.required |= (grammar.constr_include(link.role) & ~ret.attached);
  ret.forbidden |= grammar.constr_exclude(link.role);

  ret.boubbles.merge(bs); //DOBRZE
  ret.flags |= ( depflags & grammar.pass_flags(link.role) );

  if(link.props[Prop("INIT")]) ret.init_attached=true;
  if(link.props[Prop("FIN")]) ret.fin_attached=true;

  return ret;
}

//----------------------------------------------------------------------------------------------------

NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list<Boubble*> bs)
{
  NodeProp ret=depprop;
  ret.boubbles.merge(bs); //DOBRZE
  return ret;
}

//====================================================================================================

int find_existing_node(int mnodeind, NodeProp p, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLV)
{
  MNode& mnode = mgraph[mnodeind];
  int ret=-1;
  for(vector<int>::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps)
    {
      if(debug) fprintf(stderr,"#find existing node: checking %d ... \n", *ps);
      if(sgraph[*ps].prop==p)
	if(sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV)
	  {
	    ret = *ps;
	    fprintf(stderr,"#\tsucceeded because of LH/LV equality ()\n");
	  }
	else
	  {
	    fprintf(stderr,"#\tfailed beacause of LH/LV inequality\n");
	  }
    }

  if(debug) fprintf(stderr,"\n");
  return ret;
}

//====================================================================================================

list<Boubble*> receive_boubbles(int node, Role role, Dir dir)
{
  list<Boubble*> ret;
  for(list<Boubble*>::iterator b = sgraph[node].prop.boubbles.begin(); b!=sgraph[node].prop.boubbles.end(); b++)
    {
      Boubble* new_boubble = (*b)->step(role,dir);
      if(new_boubble)
	ret.push_back(new_boubble);
    }

  return ret;
}

//----------------------------------------------------------------------------------------------------

list<Boubble*> collect_head_boubbles(int head, int dep, Role role)
{
  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(dep),role,UP);
  
  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
    (*b)->src(dep);

  list<Boubble*> received_boubbles = receive_boubbles(dep,role,UP);

  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());

  return new_boubbles;
}

//----------------------------------------------------------------------------------------------------

list<Boubble*> collect_dep_boubbles(int head, int dep, Role role)
{
  list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(head), role, DOWN);
  
  for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++)
    (*b)->src(head);

  list<Boubble*> received_boubbles = receive_boubbles(head,role,DOWN);

  new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end());

  return new_boubbles;
}

//====================================================================================================

void copy_links(int i, int j)
{
  sgraph[j].heads = sgraph[i].heads;
  sgraph[j].deps = sgraph[i].deps;
}


void create_reverse_links(int n)
{
  for(vector<Arc>::iterator a=sgraph[n].heads.begin(); a != sgraph[n].heads.end(); a++)
    sgraph[a->dst].deps.push_back(Arc(n,a->role,a->headanc,a->depanc));

  for(vector<Arc>::iterator a=sgraph[n].deps.begin(); a != sgraph[n].deps.end(); a++)
    sgraph[a->dst].heads.push_back(Arc(n,a->role,a->headanc,a->depanc));
}

//====================================================================================================

int create_new_head_node_left(int anc, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
{
  int newheadind = sgraph.clone(anc,prop);
  nodelist.push_back(newheadind);
  sgraph[newheadind].LH = LH;
  sgraph[newheadind].LD = LD;
  sgraph[newheadind].in_LH = true;
  sgraph[newheadind].LV.reset();

  copy_links(anc,newheadind);
  create_reverse_links(newheadind);
  
  if(debug) sgraph.print_node_debug(stderr,"add new",newheadind,anc);
  // if(debug) print_sets(newheadind);
  return newheadind;
}

int create_new_dep_node_left(int anc, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
{
  int newind = sgraph.clone(anc,prop);
  nodelist.push_back(newind);
  sgraph[newind].LH.reset();
  sgraph[newind].LD=LD;
  sgraph[newind].in_LH=false; //???????
  sgraph[newind].LV.reset();

  copy_links(anc,newind);
  create_reverse_links(newind);
  
  if(debug) sgraph.print_node_debug(stderr,"add new",newind,anc);
  // if(debug) print_sets(newind);
  
  return newind;
}

int create_new_head_node_right(int anc, NodeProp& prop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
{
  int newheadind = sgraph.clone(anc,prop);
  nodelist.push_back(newheadind);
  sgraph[newheadind].LH=newheadLH;
  sgraph[newheadind].LD=newheadLD;
  sgraph[newheadind].in_LH=false;
  sgraph[newheadind].LV=newheadLV;
  
  copy_links(anc,newheadind);
  create_reverse_links(newheadind);

  if(debug) sgraph.print_node_debug(stderr,"add new",newheadind,anc);
  // if(debug) print_sets(newheadind);
  
  return newheadind;
}

int create_new_dep_node_right(int anc, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
{
  int newind = sgraph.clone(anc,prop);
  nodelist.push_back(newind);
  sgraph[newind].LH=LH;
  sgraph[newind].LD=LD;
  sgraph[newind].in_LH=true; //???????
  sgraph[newind].LV.reset();
  
  copy_links(anc,newind);
  create_reverse_links(newind);

  if(debug) sgraph.print_node_debug(stderr,"ADD NEW",newind,anc);
  // if(debug) print_sets(newind);
  
  return newind;
}

//====================================================================================================

void connect_left(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
{

  NodeProp &oldheadprop = sgraph[h].prop;
  NodeProp &olddepprop = sgraph[d].prop;

  NodeProp newheadprop  = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags);
  
  int newheadind;
  if(oldheadprop==newheadprop)
    newheadind = h;
  else
  {
    bitset<MAXNODES> newheadLH = sgraph[h].LH;
    bitset<MAXNODES> newheadLV = sgraph[d].LV;
    bitset<MAXNODES> newheadLD = sgraph[h].LD;

    newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV);
    if( newheadind >= 0) // W£¡CZONE
      sgraph[newheadind].LD |= newheadLD;
    else
      {
	newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV);
	sgraph[newheadind].edge.clear();
	sgraph[newheadind].edge_contains_self = false;
      }
    
  }

  NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles);

  int newdepind;
  
  if(olddepprop==newdepprop)
    newdepind = d;
  else
  {
    bitset<MAXNODES> newdepLH = sgraph[d].LH;
    bitset<MAXNODES> newdepLV = sgraph[d].LV;
    bitset<MAXNODES> newdepLD = sgraph[d].LD;

    newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV);
    if( newdepind >= 0) // W£¡CZONE
      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
    else
      {
	newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV);
	sgraph[newdepind].edge.clear();
	//sgraph[newdepind].edge.push_back(newdepind); // TO
	sgraph[newdepind].edge_contains_self = true; // LUB TO
      }
  }
  

  sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d));
  sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d));
  sgraph[newheadind].edge.push_back(newdepind);
  
  if(sgraph[d].saturated()) sgraph[newheadind].LV |= sgraph[d].LV;

  sgraph[newheadind].LD.set(d);
  if(sgraph[d].saturated()) sgraph[newheadind].LD |= sgraph[d].LD;
  
  if(debug) sgraph.print_arc(stderr,"new link",newheadind,d,l.role,0);
  if(debug) sgraph.print_node_debug(stderr,"update",newheadind,h);
  // if(debug) print_sets(newheadind);
  if(debug) sgraph.print_node_debug(stderr,"update",newdepind,d);
  // if(debug) print_sets(newdepind);
}

//----------------------------------------------------------------------------------------------------

void connect_right(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles)
{
  NodeProp &oldheadprop = sgraph[h].prop;

  NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[d].prop.flags);

  int newheadind;
  
  if(oldheadprop==newheadprop)
    newheadind = h;
  else
  {
    bitset<MAXNODES> newheadLH = sgraph[h].LH;
    bitset<MAXNODES> newheadLV = sgraph[h].LV;
    bitset<MAXNODES> newheadLD = sgraph[h].LD;

    newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV);

    if(debug) fprintf(stderr,"#HEAD EXISTS %d\n",newheadind);

    if( newheadind >= 0) // W£¡CZONE
      sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD
    else
      {
	newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV);
	//if(!sgraph[h].edge.empty()) sgraph[newheadind].edge.push_back(newheadind); // TO
	sgraph[newheadind].edge_contains_self = sgraph[h].edge_contains_self;      // LUB TO
	sgraph[newheadind].visible_as_neighbour = false;
      }
  }

  NodeProp &olddepprop = sgraph[d].prop;
  NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles);

  int newdepind;
  
  if(olddepprop==newdepprop)
    newdepind = d;
  else
  {
    bitset<MAXNODES> newdepLH = sgraph[d].LH;
    bitset<MAXNODES> newdepLV = sgraph[d].LV;
    bitset<MAXNODES> newdepLD = sgraph[d].LD;

    newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV);

    if(debug) fprintf(stderr,"#DEP EXISTS %d\n",newdepind);

    if( newdepind >= 0) // W£¡CZONE
      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
    else
      {
	newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV);
	sgraph[newdepind].edge.clear();
	sgraph[newdepind].edge_contains_self = false;
      }
  }


  sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d));
  sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d));
  //sgraph[newdepind].edge.push_back(newheadind);

  sgraph[newdepind].LH.set(newheadind);

  //  sgraph[*d].prop.merge_boubbles(new_dep_boubbles);
  
  if(sgraph[newheadind].saturated()) sgraph[newdepind].LH |= sgraph[newheadind].LH;

  if(debug) sgraph.print_arc(stderr,"new link",newheadind,newdepind,l.role,1);
  if(debug) sgraph.print_node_debug(stderr,"update",newheadind,h);
  if(debug) sgraph.print_node_debug(stderr,"update",newdepind,d);
  
}

//====================================================================================================

// bool check_meeting_boubles(list<Boubble*>& hboubbles, list<Boubble*>& dboubbles)
// {
//   bool hremove=false;             // czy usun±æ ostatnio sprawdzany b±bel
//   bool dremove=false;             // czy usun±æ ostatnio sprawdzany b±bel

//   for(list<Boubble*>::iterator hb = hboubbles.begin(); hb != hboubbles.end(); hb = hremove ? hboubbles.erase(hb) : ++hb )
//     {
//       hremove=false;
//       for(list<Boubble*>::iterator db = dboubbles.begin(); db != dboubbles.end(); db = dremove ? dboubbles.erase(db) : ++db )
// 	{
// 	  dremove=false;
// 	  if( (*hb)->rel()==(*db)->rel() && (*hb)->dir()==DOWN && (*db)->dir()==UP && (*hb)->reverse()!=(*db)->reverse() )
// 	    {
// 	      int srcnode,dstnode;
// 	      if( (*hb)->reverse()==false )
// 		srcnode = (*hb)->src(), dstnode = (*db)->src();
// 	      else
// 		srcnode = (*db)->src(), dstnode = (*hb)->src();
// 	      if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) )
// 		{
// 		  hremove=dremove=true;
// 		  if(debug) fprintf(stderr,"BOUBBLES MET!!!\n");
// 		}
// 	      else
// 		{
// 		  if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n");
// 		  return false;
// 		}
// 	    }
// 	}
//     }
//   return true;
// }

//====================================================================================================

bool check_meeting_boubles(list<Boubble*>& boubbles)
{
  bool hremove=false;             // czy usun±æ ostatnio sprawdzany b±bel
  bool dremove=false;             // czy usun±æ ostatnio sprawdzany b±bel

  for(list<Boubble*>::iterator hb = boubbles.begin(); hb != boubbles.end(); hb = hremove ? boubbles.erase(hb) : ++hb )
    {
      cout << endl << "hb:" << **hb ;
      hremove=false;
      for(list<Boubble*>::iterator db = hb; db != boubbles.end(); db = dremove ? boubbles.erase(db) : ++db )
	{
	  cout << " db:" << **db;
	  dremove=false;
	  if( (*hb)->rel()==(*db)->rel() && (*hb)->reverse()!=(*db)->reverse() )
	    {
	      cout << "Z";
	      int srcnode,dstnode;
	      if( (*hb)->reverse()==false )
		srcnode = (*hb)->src(), dstnode = (*db)->src();
	      else
		srcnode = (*db)->src(), dstnode = (*hb)->src();
	      if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) )
		{
		  cout << " REMOVE ";
		  hremove=dremove=true;
		  if(debug) fprintf(stderr,"BOUBBLES MET!!!\n");
		}
	      else
		{
		  cout << " FAIL ";
		  if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n");
		  return false;
		}
	    }
	}
    }
  return true;
}

//====================================================================================================

// sprawdza czy te, spo¶ród b±bli, które dotar³y do celu node
// daj± wynik prawdziwy, dodatkowo - usuwa je z listy boubbles

bool check_boubbles_at_target(list<Boubble*>& boubbles, int node)
{
  bool remove=false;             // czy usun±æ ostatnio sprawdzany b±bel

  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b = remove ? boubbles.erase(b) : ++b )
    if( (*b)->is_at_target() )
      if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) )
	{
	  cout << endl << "REMOVE ChBatT " << **b << endl;
	  remove=true;
	}
      else
	return false;
    else
      remove=false;
      
  return true;
}

//====================================================================================================

void try_connect_dependents(int j)
{
  LViterator lvi(sgraph,j);
  int i;
  while((i=lvi.next()) >= 0)
    {
      //if(debug) sgraph.print_node_debug(stderr,"D-CUR>",i,-1);

      if(sgraph.saturated(i))
	{
	  if(debug) {fprintf(stderr,"%d <--",i); }
	  
	  list<const Link*> ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!!
	  list<const Link*>::iterator ri = ji_links.begin();
	  if(ri == ji_links.end()) { if(debug) fprintf(stderr,"     no roles\n"); }
	  else
	    {
	      for(; ri != ji_links.end(); ++ri )
		{
		  if(debug) fprintf(stderr,"     %s",(*ri)->role.str());
		  if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri ))
		    { if(debug) fprintf(stderr," ...constraints failed\n"); }
		  else
		    {
		      list<Boubble*> new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role);
		      list<Boubble*> new_dep_boubbles = collect_dep_boubbles(j,i,(*ri)->role);
		      if( check_meeting_boubles(new_head_boubbles) &&
			  check_meeting_boubles(new_dep_boubbles) &&
			  check_boubbles_at_target(new_head_boubbles,j) &&
			  check_boubbles_at_target(new_dep_boubbles,i) )
			{
			  if(debug) fprintf(stderr," ...SUCCESS!\n");
			  connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
			}
		      else
			{ if(debug) fprintf(stderr," ...boubbles failed\n"); }
		    }
		}
	    }
	}
      else
	  if(debug) {fprintf(stderr,"%d <--     unsaturated\n",i); }
    }
  
}
//----------------------------------------------------------------------------------------------------

void try_connect_heads(int j)
{
  LViterator lvi(sgraph,j);
  int i;
  while((i=lvi.next()) >= 0)
    {
      // if(debug) sgraph.print_node_debug(stderr,"H-CUR> ",i,-1);
      if(sgraph.saturated(j))
	{
	  if(debug) fprintf(stderr, "%d -->",i);
	  
	  list<const Link*> ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags );
	  list<const Link*>::iterator ri = ij_links.begin();
	  if(ri == ij_links.end()) { if(debug) fprintf(stderr,"     no roles\n"); }
	  else
	    {
	      for(; ri != ij_links.end(); ++ri )
		{
		  if(debug) fprintf(stderr,"     %s",(*ri)->role.str());
		  if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) )
		    { if(debug) fprintf(stderr," ...constraints failed\n"); }
		  else
		    {
		      list<Boubble*> new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role);
		      list<Boubble*> new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role);
		      
		      if( check_meeting_boubles(new_head_boubbles) &&
			  check_meeting_boubles(new_dep_boubbles) &&
			  check_boubbles_at_target(new_head_boubbles,i) &&
			  check_boubbles_at_target(new_dep_boubbles,j) )
			{
			  if(debug) fprintf(stderr," ...SUCCESS!\n");
			  connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
			}
		      else
			{ if(debug) fprintf(stderr," ...bubbles failed\n",i); }
		    }
		}
	    }
	}
      else
	  if(debug) {fprintf(stderr,"%d <--     unsaturated\n",j); }
    }
}

//====================================================================================================

void update_sets()
{
  for(int n=0; n<sgraph.size(); ++n)
    {
      LViterator lvi(sgraph,n,false);
      LHiterator lhi(sgraph,n);
      LDiterator ldi(sgraph,n);
      int i;

      // printf("UPDATING LV[%d]:",n);
      while((i=lvi.next())>=0)
	{
	  // printf(" %d",i);
	  sgraph[n].LV.set(i);
	}
      // printf("\n");

      while((i=lhi.next())>=0) sgraph[n].LH.set(i);
      while((i=ldi.next())>=0) sgraph[n].LD.set(i);
    }
}

//====================================================================================================

void print_sets(int n)
{
  LViterator lvi(sgraph,n);
  LHiterator lhi(sgraph,n);
  LDiterator ldi(sgraph,n);
  
  int i;  
  printf("LV[%d]: ",n);
  while((i=lvi.next())>=0)
	{
	  printf("%d ",i);
	  sgraph[n].LV.set(i);
	}

  printf("LH[%d]: ",n);
  while((i=lhi.next())>=0)
    {
      printf("%d ",i);
      sgraph[n].LH.set(i);
    }
  printf("LD[%d]: ",n);
  while((i=ldi.next())>=0)
    {
      printf("%d ",i);
      sgraph[n].LD.set(i);
    }
  printf("\n");
}

//====================================================================================================

void reverse_links()
{
  list<int>::iterator i = nodelist.begin();
  for(++i; i!=nodelist.end(); ++i)
    {
      for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da)
        sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc));
      for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha)
        sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc));
    }
}

//====================================================================================================

void dgp1()
{

  nodelist.clear();
  nodelist.push_back(0); // BOS
  processed=nodelist.begin();

  for(int m=0; m<mgraph.size() ; ++m)
  {
    int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode*

    set_initial_constraints(basenode);
    nodelist.push_back(basenode);

    if(debug) sgraph.print_node_debug(stderr,"add base",basenode,-1); // STDOUT!!!
    // if(debug) print_sets(basenode);

    list<int>::iterator cursor=processed;
    while(++cursor != nodelist.end())
    {
      if(debug) sgraph.print_node_debug(stderr,"MAIN-CUR> ",*cursor,-1);
      try_connect_dependents(*cursor);
      try_connect_heads(*cursor);
      processed=cursor;
    }

  }
   // reverse_links();
  update_sets();
}