Index: src/dgp/dgp1.cc
===================================================================
--- src/dgp/dgp1.cc	(revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac)
+++ src/dgp/dgp1.cc	(revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac)
@@ -0,0 +1,424 @@
+#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 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=bs;
+  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=bs;
+  return ret;
+}
+
+//====================================================================================================
+
+int find_existing_node(int mnodeind, NodeProp p, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLV)
+{
+  MNode& mnode = mgraph[mnodeind];
+  for(vector<int>::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps)
+    if(sgraph[*ps].prop==p && sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV)      return *ps;
+  return -1;
+}
+
+//====================================================================================================
+
+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;
+}
+
+//====================================================================================================
+
+int create_new_head_node_left(list<int>::iterator h, NodeProp& newheadprop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
+{
+  int newheadind = sgraph.clone(*h,newheadprop);
+  list<int>::iterator nextit=h; ++nextit;
+  nodelist.insert(nextit,newheadind);
+  sgraph[newheadind].LH=newheadLH;
+  sgraph[newheadind].LD = newheadLD;
+  sgraph[newheadind].in_LH=true;
+  sgraph[newheadind].LV.reset();
+  
+  if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h);
+  
+  return newheadind;
+}
+
+int create_new_dep_node_left(list<int>::iterator d, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
+{
+  int newind = sgraph.clone(*d,prop);
+  list<int>::iterator nextit=d; ++nextit;
+  nodelist.insert(nextit,newind);
+  sgraph[newind].LH.reset();
+  sgraph[newind].LD=LD;
+  sgraph[newind].in_LH=false; //???????
+  sgraph[newind].LV.reset();
+  
+  if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d);
+  
+  return newind;
+}
+
+int create_new_head_node_right(list<int>::iterator h, NodeProp& newheadprop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV)
+{
+  int newheadind = sgraph.clone(*h,newheadprop);
+  list<int>::iterator nextit=h; ++nextit;
+  nodelist.insert(nextit,newheadind);
+  sgraph[newheadind].LH=newheadLH;
+  sgraph[newheadind].LD=newheadLD;
+  sgraph[newheadind].in_LH=false;
+  sgraph[newheadind].LV=newheadLV;
+  
+  if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h);
+  
+  return newheadind;
+}
+
+int create_new_dep_node_right(list<int>::iterator d, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV)
+{
+  int newind = sgraph.clone(*d,prop);
+  list<int>::iterator nextit=d; ++nextit;
+  nodelist.insert(nextit,newind);
+  sgraph[newind].LH=LH;
+  sgraph[newind].LD=LD;
+  sgraph[newind].in_LH=true; //???????
+  sgraph[newind].LV.reset();
+  
+  if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d);
+  
+  return newind;
+}
+
+//====================================================================================================
+
+void connect_left(list<int>::iterator h, list<int>::iterator 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 )
+      sgraph[newheadind].LD |= newheadLD;
+    else
+      newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV);
+  }
+
+
+
+  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 )
+      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
+    else
+      newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV);
+  }
+
+  sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,*h,*d));
+  
+  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,newheadind,*d,l.role,0);
+  if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,*h);
+  if(debug) sgraph.print_node_debug(stderr,"U ",*d,*d);
+}
+
+//----------------------------------------------------------------------------------------------------
+
+void connect_right(list<int>::iterator h, list<int>::iterator 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( newheadind >= 0 )
+      sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD
+    else
+      newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV);
+  }
+
+  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( newdepind >= 0 )
+      sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD
+    else
+      newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV);
+  }
+
+
+
+  
+  sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,*h,*d));
+
+  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,newheadind,newdepind,l.role,1);
+  if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,*h);
+  if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,*d);
+  
+}
+
+//====================================================================================================
+
+bool check_boubbles_at_target(list<Boubble*> boubbles, int node)
+{
+  for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b++)
+    if( (*b)->is_at_target() && !grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()))
+      return false;
+  return true;
+}
+
+//====================================================================================================
+
+void try_connect_dependents(list<int>::iterator j)
+{
+  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
+    if(sgraph.visible(*i,*j) && sgraph.saturated(*i))
+    {
+      if(debug) {fprintf(stderr,"## %d <-- %d ... ",*i,*j); }
+
+      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(!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_boubbles_at_target(new_head_boubbles,*j) && check_boubbles_at_target(new_dep_boubbles,*i)) )
+		  { if(debug) fprintf(stderr,"boubbles failed\n"); }
+		else
+		  {
+		    if(debug) fprintf(stderr,"success\n");
+		    connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles);
+		  }
+	      }
+	}
+    }
+}
+
+
+//----------------------------------------------------------------------------------------------------
+
+void try_connect_heads(list<int>::iterator j)
+{
+  for(list<int>::iterator i(j); i!=nodelist.begin(); --i)
+    if(sgraph.visible(*i,*j))
+    {
+      if(debug) fprintf(stderr, "## %d --> %d ... ",*i,*j);
+
+      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( !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_boubbles_at_target(new_head_boubbles,*i) && check_boubbles_at_target(new_dep_boubbles,*j)) )
+		  { if(debug) fprintf(stderr,"boubbles failed\n"); }
+		else
+		  {
+		    if(debug) fprintf(stderr,"success\n");
+		    connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles );
+		  }
+	      }
+	}
+    }
+}
+  
+//====================================================================================================
+
+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,"B ",basenode,-1);} // STDOUT!!!
+
+    list<int>::iterator cursor=processed;
+    while(++cursor != nodelist.end())
+    {
+      try_connect_dependents(cursor);
+      try_connect_heads(cursor);
+      processed=cursor;
+    }
+
+  }
+  reverse_links();
+}
