Index: src/dgp/boubble.hh =================================================================== --- src/dgp/boubble.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/boubble.hh (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -26,4 +26,5 @@ Boubble(list u, list d, LongRel l, int s=-1); Boubble(const char* pathstr, const char* l, int s=-1); + // Boubble(const Boubble& b) {_src=b._src; _upath=b._upath; _dpath=b._dpath; _rel=b._rel; }; Dir dir(); @@ -138,5 +139,5 @@ } - if(d==DOWN && _upath.empty() && !_dpath.empty()) + if(d==DOWN && _upath.empty() && !_dpath.empty() && _dpath.front() == r) { Boubble* newboubble = new Boubble(_upath,_dpath,_rel,_src); Index: src/dgp/dgp1.cc =================================================================== --- src/dgp/dgp1.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/dgp1.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -10,4 +10,8 @@ list nodelist; list::iterator processed; + + +void print_sets(int n); + //==================================================================================================== @@ -44,5 +48,5 @@ ret.forbidden |= grammar.constr_exclude(link.role); - ret.boubbles=bs; + ret.boubbles.merge(bs); //DOBRZE ret.flags |= ( depflags & grammar.pass_flags(link.role) ); @@ -58,5 +62,5 @@ { NodeProp ret=depprop; - ret.boubbles=bs; + ret.boubbles.merge(bs); //DOBRZE return ret; } @@ -67,7 +71,22 @@ { MNode& mnode = mgraph[mnodeind]; + int ret=-1; for(vector::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; + { + 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,"FIND EXISTING NODE SUCCEEDED BEACAUSE OF LH/LV equality ()\n"); + } + else + { + // fprintf(stderr,"FIND EXISTING NODE FAILED BEACAUSE OF LH/LV inequality\n"); + } + } + + if(debug) fprintf(stderr,"\n"); + return ret; } @@ -83,4 +102,5 @@ ret.push_back(new_boubble); } + return ret; } @@ -120,39 +140,67 @@ //==================================================================================================== -int create_new_head_node_left(list::iterator h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) -{ - int newheadind = sgraph.clone(*h,newheadprop); - list::iterator nextit=h; ++nextit; - nodelist.insert(nextit,newheadind); +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::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::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 h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) +{ + int newheadind = sgraph.clone(h,newheadprop); + // list::iterator nextit=h; ++nextit; + // nodelist.insert(nextit,newheadind); + nodelist.push_back(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); - + + copy_links(h,newheadind); + create_reverse_links(newheadind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,h); + if(debug) print_sets(newheadind); return newheadind; } -int create_new_dep_node_left(list::iterator d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newind = sgraph.clone(*d,prop); - list::iterator nextit=d; ++nextit; - nodelist.insert(nextit,newind); +int create_new_dep_node_left(int d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) +{ + int newind = sgraph.clone(d,prop); + // list::iterator nextit=d; ++nextit; + // nodelist.insert(nextit,newind); + nodelist.push_back(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); + + copy_links(d,newind); + create_reverse_links(newind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newind,d); + if(debug) print_sets(newind); return newind; } -int create_new_head_node_right(list::iterator h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) -{ - int newheadind = sgraph.clone(*h,newheadprop); - list::iterator nextit=h; ++nextit; - nodelist.insert(nextit,newheadind); +int create_new_head_node_right(int h, NodeProp& newheadprop, bitset& newheadLH, bitset& newheadLD, bitset& newheadLV) +{ + int newheadind = sgraph.clone(h,newheadprop); + // list::iterator nextit=h; ++nextit; + // nodelist.insert(nextit,newheadind); + nodelist.push_back(newheadind); sgraph[newheadind].LH=newheadLH; sgraph[newheadind].LD=newheadLD; @@ -160,14 +208,17 @@ sgraph[newheadind].LV=newheadLV; - if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,*h); + copy_links(h,newheadind); + create_reverse_links(newheadind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newheadind,h); + if(debug) print_sets(newheadind); return newheadind; } -int create_new_dep_node_right(list::iterator d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) -{ - int newind = sgraph.clone(*d,prop); - list::iterator nextit=d; ++nextit; - nodelist.insert(nextit,newind); +int create_new_dep_node_right(int d, NodeProp& prop, bitset& LH, bitset& LD, bitset& LV) +{ + int newind = sgraph.clone(d,prop); + nodelist.push_back(newind); sgraph[newind].LH=LH; sgraph[newind].LD=LD; @@ -175,5 +226,9 @@ sgraph[newind].LV.reset(); - if(debug) sgraph.print_node_debug(stderr,"C ",newind,*d); + copy_links(d,newind); + create_reverse_links(newind); + + if(debug) sgraph.print_node_debug(stderr,"C ",newind,d); + if(debug) print_sets(newind); return newind; @@ -182,9 +237,9 @@ //==================================================================================================== -void connect_left(list::iterator h, list::iterator d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) -{ - - NodeProp &oldheadprop = sgraph[*h].prop; - NodeProp &olddepprop = sgraph[*d].prop; +void connect_left(int h, int d, const Link& l, list& new_head_boubbles, list& 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); @@ -192,20 +247,25 @@ int newheadind; if(oldheadprop==newheadprop) - newheadind = *h; + newheadind = h; else { - bitset newheadLH = sgraph[*h].LH; - bitset newheadLV = sgraph[*d].LV; - bitset newheadLD = sgraph[*h].LD; - - newheadind = find_existing_node(sgraph[*h].mnode, newheadprop, newheadLH, newheadLV); - if( newheadind >= 0 ) + bitset newheadLH = sgraph[h].LH; + bitset newheadLV = sgraph[d].LV; + bitset newheadLD = sgraph[h].LD; + + // vector newedge; + + 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); + { + 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); @@ -213,56 +273,74 @@ if(olddepprop==newdepprop) - newdepind = *d; + newdepind = d; else { - bitset newdepLH = sgraph[*d].LH; - bitset newdepLV = sgraph[*d].LV; - bitset newdepLD = sgraph[*d].LD; - - newdepind = find_existing_node(sgraph[*d].mnode, newdepprop, newdepLH, newdepLV); - if( newdepind >= 0 ) + bitset newdepLH = sgraph[d].LH; + bitset newdepLV = sgraph[d].LV; + bitset 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); + { + 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)); - - 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); + + + 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,newheadind,d,l.role,0); + if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,h); + if(debug) print_sets(newheadind); + if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,d); + if(debug) print_sets(newdepind); } //---------------------------------------------------------------------------------------------------- -void connect_right(list::iterator h, list::iterator d, const Link& l, list& new_head_boubbles, list& new_dep_boubbles) -{ - NodeProp &oldheadprop = sgraph[*h].prop; - - NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[*d].prop.flags); +void connect_right(int h, int d, const Link& l, list& new_head_boubbles, list& 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; + newheadind = h; else { - bitset newheadLH = sgraph[*h].LH; - bitset newheadLV = sgraph[*h].LV; - bitset newheadLD = sgraph[*h].LD; - - newheadind = find_existing_node(sgraph[*h].mnode, newheadprop, newheadLH, newheadLV); - if( newheadind >= 0 ) + bitset newheadLH = sgraph[h].LH; + bitset newheadLV = sgraph[h].LV; + bitset 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); + { + 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 &olddepprop = sgraph[d].prop; NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); @@ -270,22 +348,29 @@ if(olddepprop==newdepprop) - newdepind = *d; + newdepind = d; else { - bitset newdepLH = sgraph[*d].LH; - bitset newdepLV = sgraph[*d].LV; - bitset newdepLD = sgraph[*d].LD; - - newdepind = find_existing_node(sgraph[*d].mnode, newdepprop, newdepLH, newdepLV); - if( newdepind >= 0 ) + bitset newdepLH = sgraph[d].LH; + bitset newdepLV = sgraph[d].LV; + bitset 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); + { + 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[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); @@ -296,6 +381,6 @@ 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); + if(debug) sgraph.print_node_debug(stderr,"U ",newheadind,h); + if(debug) sgraph.print_node_debug(stderr,"U ",newdepind,d); } @@ -323,22 +408,18 @@ } -// bool check_boubbles_at_target(list boubbles, int node) -// { -// for(list::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::iterator j) -{ - for(list::iterator i(j); i!=nodelist.begin(); --i) - if(sgraph.visible(*i,*j) && sgraph.saturated(*i)) - { - if(debug) {fprintf(stderr,"## %d <-- %d ... ",*i,*j); } - - list ji_links = grammar.connectable2( sgraph.cat(*j), sgraph.cat(*i), sgraph[*j].prop.flags, sgraph[*i].prop.flags); // ref do Roles!!! +//==================================================================================================== + +void try_connect_dependents(int j) +{ + // for(list::iterator i(j); i!=nodelist.begin(); --i) + // if(sgraph.visible(*i,*j) && sgraph.saturated(*i)) + LViterator lvi(sgraph,j); + int i; + while((i=lvi.next()) >= 0) + if(sgraph.saturated(i)) + { + if(debug) {fprintf(stderr,"## %d <-- %d ... ",i,j); } + + list ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!! list::iterator ri = ji_links.begin(); if(ri == ji_links.end()) { if(debug) fprintf(stderr,"no roles\n"); } @@ -346,12 +427,12 @@ { for(; ri != ji_links.end(); ++ri ) - if(!grammar.check_constr2(sgraph[*j].prop,sgraph[*i].prop,0,**ri )) + if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri )) { if(debug) fprintf(stderr,"constraints failed\n"); } else { - list new_head_boubbles = collect_head_boubbles(*j,*i,(*ri)->role); - list new_dep_boubbles = collect_dep_boubbles(*j,*i,(*ri)->role); + list new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role); + list 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( !(check_boubbles_at_target(new_head_boubbles,j) && check_boubbles_at_target(new_dep_boubbles,i)) ) { if(debug) fprintf(stderr,"boubbles failed\n"); } else @@ -368,12 +449,17 @@ //---------------------------------------------------------------------------------------------------- -void try_connect_heads(list::iterator j) -{ - for(list::iterator i(j); i!=nodelist.begin(); --i) - if(sgraph.visible(*i,*j)) - { - if(debug) fprintf(stderr, "## %d --> %d ... ",*i,*j); - - list ij_links = grammar.connectable2( sgraph.cat(*i), sgraph.cat(*j), sgraph[*i].prop.flags, sgraph[*j].prop.flags ); +void try_connect_heads(int j) +{ + // for(list::iterator i(j); i!=nodelist.begin(); --i) + // if(sgraph.visible(*i,*j) && sgraph.saturated(*j)) + + LViterator lvi(sgraph,j); + int i; + while((i=lvi.next()) >= 0) + if(sgraph.saturated(j)) + { + if(debug) fprintf(stderr, "## %d --> %d ... ",i,j); + + list ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags ); list::iterator ri = ij_links.begin(); if(ri == ij_links.end()) { if(debug) fprintf(stderr,"no roles\n"); } @@ -381,12 +467,12 @@ { for(; ri != ij_links.end(); ++ri ) - if( !grammar.check_constr2( sgraph[*i].prop, sgraph[*j].prop, 1, **ri ) ) + if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) ) { if(debug) fprintf(stderr,"constraints failed\n"); } else { - list new_head_boubbles = collect_head_boubbles(*i,*j,(*ri)->role); - list new_dep_boubbles = collect_dep_boubbles(*i,*j,(*ri)->role); + list new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role); + list 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( !(check_boubbles_at_target(new_head_boubbles,i) && check_boubbles_at_target(new_dep_boubbles,j)) ) { if(debug) fprintf(stderr,"boubbles failed\n"); } else @@ -399,5 +485,60 @@ } } - + +//==================================================================================================== + +void update_sets() +{ + for(int n=0; n=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"); +} + //==================================================================================================== @@ -430,15 +571,18 @@ nodelist.push_back(basenode); - if(debug) {sgraph.print_node_debug(stderr,"B ",basenode,-1);} // STDOUT!!! + if(debug) sgraph.print_node_debug(stderr,"B ",basenode,-1); // STDOUT!!! + if(debug) print_sets(basenode); list::iterator cursor=processed; while(++cursor != nodelist.end()) { - try_connect_dependents(cursor); - try_connect_heads(cursor); + if(debug) sgraph.print_node_debug(stderr,"> ",*cursor,-1); + try_connect_dependents(*cursor); + try_connect_heads(*cursor); processed=cursor; } } - reverse_links(); -} + // reverse_links(); + update_sets(); +} Index: src/dgp/grammar.cc =================================================================== --- src/dgp/grammar.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/grammar.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -298,10 +298,35 @@ { char cat1[MAXLINE],flags1[MAXLINE],cat2[MAXLINE],flags2[MAXLINE],type[MAXLINE],props[MAXLINE]; - - if(sscanf(arg1,"%[^;];%s",cat1,flags1)==1) *flags1='\0'; - if(sscanf(arg2,"%[^;];%s",cat2,flags2)==1) *flags2='\0'; - if(sscanf(arg3,"%[^&]%s",type,props)==1) *props='\0'; + char* double_slash_position; + // pierwszy argument + // if(sscanf(arg1,"%[^;];%s",cat1,flags1)==1) *flags1='\0'; + if((double_slash_position=strstr(arg1,"//")) != NULL) // czy s± flagi + { + int cat_length=double_slash_position-arg1; + strncpy(cat1, arg1, cat_length); cat1[cat_length]='\0'; + strcpy(flags1, arg1+cat_length+2); + } + else + { + strcpy(cat1, arg1); + flags1[0]='\0'; + } + // drugi argument + // if(sscanf(arg2,"%[^;];%s",cat2,flags2)==1) *flags2='\0'; + if((double_slash_position=strstr(arg2,"//")) != NULL) // czy s± flagi + { + int cat_length=double_slash_position-arg2; + strncpy(cat2, arg2, cat_length); cat2[cat_length]='\0'; + strcpy(flags2, arg2+cat_length+2); + } + else + { + strcpy(cat2,arg2); + flags2[0]='\0'; + } + // trzeci argument + if(sscanf(arg3,"%[^&]%s",type,props)==1) props[0]='\0'; - // printf("line=%s\n\tcat1=%s flags1=%s cat2=%s flags2=%s type=%s props=%s\n",line,cat1,flags1,cat2,flags2,type,props); + // printf("line=%s\n\tcat1=<%s> flags1=%s cat2=<%s> flags2=%s type=<%s> props=%s\n",line,cat1,flags1,cat2,flags2,type,props); if( chk_cat(cat1) && chk_cat(cat2) && chk_type(type) ) @@ -346,5 +371,5 @@ // compute_gt(); - + return true; Index: src/dgp/main.cc =================================================================== --- src/dgp/main.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/main.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -38,4 +38,5 @@ bool printtimeinfo=false; + void output(); @@ -43,4 +44,5 @@ { gengetopt_args_info args; + struct timeval readgrammar_starttime,readgrammar_endtime; if(cmdline_parser(argc,argv,&args) != 0) @@ -71,11 +73,19 @@ } + gettimeofday(&readgrammar_starttime,NULL); + grammar.read(grammarf); fclose(grammarf); + gettimeofday(&readgrammar_endtime,NULL); + if(printtimeinfo) + fprintf(stderr,"### START TIME: %10.2fms\n", (float)MICROSECONDSELAPSED(readgrammar_starttime,readgrammar_endtime)/1000 ); +//////////////////////////////////////////////////////////////////////////////////////////////////// +// TESTOWANIE POPRAWNOŠCI ODCZYTU GRAMATYKI // grammar.write(cout); // exit(0); +//////////////////////////////////////////////////////////////////////////////////////////////////// struct timeval starttime,afterinput,afterparse,endtime; @@ -101,5 +111,7 @@ { gettimeofday(&afterinput,NULL); + dgp1(); // parametry!!! MGraph, SGraph, Grammar + gettimeofday(&afterparse,NULL); output(); Index: src/dgp/sgraph.cc =================================================================== --- src/dgp/sgraph.cc (revision a15e59b825ae3aa1d5f3555afaf4cdbf22beda62) +++ src/dgp/sgraph.cc (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -28,4 +28,6 @@ newnode.in_LH=true; + newnode.edge.push_back(lastnodeind()); + return lastnodeind(); } @@ -55,6 +57,4 @@ SNode &newnode=makenewnode(); SNode &ancnode = nodes[ancind]; - - newnode.prop=newprop; @@ -178,4 +178,9 @@ buf+=sprint_node(buf,n,anc,HEADS|DEPS|SETS|CONSTRAINTS); + + buf+=sprintf(buf,"/"); + for(vector::iterator e = nodes[n].edge.begin(); e != nodes[n].edge.end(); e++ ) + buf += sprintf(buf,"%d ", *e); + buf+=sprintf(buf,"\n"); return buf-buf0; Index: src/dgp/sgraph.hh =================================================================== --- src/dgp/sgraph.hh (revision e7de6cc88c605c4f810cbc852e843294b4b0e8ac) +++ src/dgp/sgraph.hh (revision 3b02b04ff9c7c3446ca477cd84c2bc7f737c38b4) @@ -7,4 +7,5 @@ #include #include +#include #include "const.hh" @@ -71,16 +72,12 @@ if(init_attached != p.init_attached) return false; if(fin_attached != p.fin_attached) return false; - - list::const_iterator b1 = p.boubbles.begin(); - for(list::const_iterator b = boubbles.begin(); b != boubbles.end(); b++) - { - if(b1 == p.boubbles.end()) - return false; - if(!(**b == **b1)) - return false; - } - if(b1 != p.boubbles.end()) + + list::const_iterator b,b1; + for(b=boubbles.begin(), b1=p.boubbles.begin(); b != boubbles.end() && b1 != p.boubbles.end(); b++,b1++) + if(!(**b == **b1)) + return false; + if(b != boubbles.end() || b1 != p.boubbles.end()) return false; - + return true; } @@ -172,7 +169,13 @@ { + SNode() { visible_as_neighbour = true; } + int mnode; NodeProp prop; + + vector edge; + bool edge_contains_self; + bool visible_as_neighbour; bitset LV; @@ -231,4 +234,9 @@ int size() {return nodes.size(); } + friend class LViterator; + friend class LHiterator; + friend class LDiterator; + friend class LNiterator; + private: @@ -259,4 +267,274 @@ //---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class XXiterator +{ +protected: + + bool checked(int i) { return _checked[i]; } + void check(int i) { _checked.set(i); } + + void push(stack& s, int i) + { + if(!checked(i)) + { + s.push(i); + check(i); + } + } + + bitset _checked; +}; + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LViterator : public XXiterator +{ +public: + LViterator(SGraph& sg, int n, bool s); + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + stack waydown; + stack wayup; + bool strict; + + void push_ld(int i); + void push_lh(int i); + void push_ln(int i); +}; + +inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : sgraph(sg), mgraph(sg.mgraph), strict(s) +{ + if(sg[n].edge_contains_self) // TO DODAÆ PO PRZEJŠCIU NA EDGE_CONTAINS_SELF + { + push_ld(n); + push_ln(n); + } + + for(vector::iterator i=sg[n].edge.begin(); i!=sg[n].edge.end(); ++i) + { + if(*i != n) + { + push_ld(*i); + push_ln(*i); + } + + } + // if(!strict) + // { + // push_ld(n); + // push_ln(n); + // } +} + +inline int LViterator::next() +{ + if(wayup.empty()) + { + if(waydown.empty()) + return -1; // + else + { + int k = waydown.top(); + waydown.pop(); + push_ld(k); + push_ln(k); + if(wayup.empty()) + return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + return i; + } + } + + } + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + return i; + }; +} + +inline void LViterator::push_ld(int i) +{ + vector& arcs = sgraph[i].deps; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + push(waydown,a->dst); +} + +inline void LViterator::push_lh(int i) +{ + vector& arcs = sgraph[i].heads; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + push(wayup,a->dst); +} + +inline void LViterator::push_ln(int i) +{ + vector& mpredecessors = mgraph[sgraph[i].mnode].pred; + for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph + { + vector& spredecessors = mgraph[*mp].snodes; + for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) + if(sgraph[*sp].visible_as_neighbour || !strict) + push(wayup,*sp); + } +} + + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LNiterator +{ +public: + LNiterator(SGraph& sg, int n); + + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + int thenode; + stack wayup; + + void push_ln(int i); +}; + +inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) +{ + push_ln(n); +} + +inline int LNiterator::next() +{ + if(wayup.empty()) + return -1; + else + { + int i = wayup.top(); + wayup.pop(); + return i; + }; +} + +inline void LNiterator::push_ln(int i) +{ + vector& mpredecessors = mgraph[sgraph[i].mnode].pred; + for(vector::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph + { + vector& spredecessors = mgraph[*mp].snodes; + for(vector::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) + wayup.push(*sp); + } +} + + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LHiterator +{ +public: + LHiterator(SGraph& sg, int n); + + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + stack wayup; + + void push_lh(int i); +}; + +inline LHiterator::LHiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph) +{ + push_lh(n); +} + +inline int LHiterator::next() +{ + if(wayup.empty()) + return -1; + else + { + int i = wayup.top(); + wayup.pop(); + push_lh(i); + return i; + }; +} + +inline void LHiterator::push_lh(int i) +{ + vector& arcs = sgraph[i].heads; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) + wayup.push(a->dst); +} + +//---------------------------------------------------------------------------------------------------- +//---------------------------------------------------------------------------------------------------- + +class LDiterator +{ +public: + LDiterator(SGraph& sg, int n); + + int next(); + +private: + + SGraph& sgraph; + MGraph& mgraph; + int thenode; + stack waydown; + + void push_ld(int i); +}; + +inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), thenode(n) +{ + push_ld(n); +} + +inline int LDiterator::next() +{ + if(waydown.empty()) + return -1; + else + { + int k = waydown.top(); + waydown.pop(); + push_ld(k); + return k; + } +} + +inline void LDiterator::push_ld(int i) +{ + vector& arcs = sgraph[i].deps; + for(vector::iterator a = arcs.begin(); a != arcs.end(); ++a) + if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[thenode].mnode].pos) + waydown.push(a->dst); +} + + #endif