[519eaf5] | 1 | #include <iostream> |
---|
| 2 | using namespace std; |
---|
| 3 | |
---|
[e7de6cc] | 4 | #include "dgp0.hh" |
---|
| 5 | #include "global.hh" |
---|
| 6 | |
---|
| 7 | extern Grammar grammar; |
---|
| 8 | extern MGraph mgraph; |
---|
| 9 | extern SGraph sgraph; |
---|
| 10 | |
---|
| 11 | extern bool debug; |
---|
| 12 | |
---|
| 13 | list<int> nodelist; |
---|
| 14 | list<int>::iterator processed; |
---|
| 15 | |
---|
[3b02b04] | 16 | |
---|
| 17 | void print_sets(int n); |
---|
| 18 | |
---|
| 19 | |
---|
[e7de6cc] | 20 | //==================================================================================================== |
---|
| 21 | |
---|
| 22 | void set_initial_constraints(int node) |
---|
| 23 | { |
---|
| 24 | sgraph[node].prop.forbidden.reset(); |
---|
| 25 | sgraph[node].prop.required=grammar.is_obl(sgraph.cat(node)); |
---|
| 26 | sgraph[node].prop.attached.reset(); |
---|
| 27 | sgraph[node].prop.flags=grammar.initial_flags(sgraph.cat(node)); |
---|
| 28 | } |
---|
| 29 | |
---|
| 30 | //---------------------------------------------------------------------------------------------------- |
---|
| 31 | |
---|
| 32 | bool changing_constraints(int head, Role role) |
---|
| 33 | { |
---|
| 34 | return grammar.is_sgl(role) || sgraph[head].prop.required[role]; |
---|
| 35 | } |
---|
| 36 | |
---|
| 37 | //==================================================================================================== |
---|
| 38 | |
---|
| 39 | NodeProp compute_head_prop(NodeProp headprop, const Link& link, list<Boubble*> bs, FlagSet& depflags) |
---|
| 40 | { |
---|
| 41 | NodeProp ret=headprop; |
---|
| 42 | |
---|
| 43 | if(grammar.is_sgl(link.role)) |
---|
| 44 | { |
---|
| 45 | ret.forbidden.set(link.role); |
---|
| 46 | ret.attached.set(link.role); |
---|
| 47 | } |
---|
| 48 | ret.required.reset(link.role); |
---|
| 49 | |
---|
| 50 | ret.required |= (grammar.constr_include(link.role) & ~ret.attached); |
---|
| 51 | ret.forbidden |= grammar.constr_exclude(link.role); |
---|
| 52 | |
---|
[3b02b04] | 53 | ret.boubbles.merge(bs); //DOBRZE |
---|
[e7de6cc] | 54 | ret.flags |= ( depflags & grammar.pass_flags(link.role) ); |
---|
| 55 | |
---|
| 56 | if(link.props[Prop("INIT")]) ret.init_attached=true; |
---|
| 57 | if(link.props[Prop("FIN")]) ret.fin_attached=true; |
---|
| 58 | |
---|
| 59 | return ret; |
---|
| 60 | } |
---|
| 61 | |
---|
| 62 | //---------------------------------------------------------------------------------------------------- |
---|
| 63 | |
---|
| 64 | NodeProp compute_dep_prop(NodeProp depprop, const Link& link, list<Boubble*> bs) |
---|
| 65 | { |
---|
| 66 | NodeProp ret=depprop; |
---|
[3b02b04] | 67 | ret.boubbles.merge(bs); //DOBRZE |
---|
[e7de6cc] | 68 | return ret; |
---|
| 69 | } |
---|
| 70 | |
---|
| 71 | //==================================================================================================== |
---|
| 72 | |
---|
| 73 | int find_existing_node(int mnodeind, NodeProp p, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLV) |
---|
| 74 | { |
---|
| 75 | MNode& mnode = mgraph[mnodeind]; |
---|
[3b02b04] | 76 | int ret=-1; |
---|
[e7de6cc] | 77 | for(vector<int>::iterator ps=mnode.snodes.begin(); ps!=mnode.snodes.end(); ++ps) |
---|
[3b02b04] | 78 | { |
---|
| 79 | if(debug) fprintf(stderr,"#find existing node: checking %d ... \n", *ps); |
---|
| 80 | if(sgraph[*ps].prop==p) |
---|
| 81 | if(sgraph[*ps].LH==newheadLH && sgraph[*ps].LV==newheadLV) |
---|
| 82 | { |
---|
| 83 | ret = *ps; |
---|
[d484a32] | 84 | if(debug) fprintf(stderr,"#\tsucceeded because of LH/LV equality ()\n"); |
---|
[3b02b04] | 85 | } |
---|
| 86 | else |
---|
| 87 | { |
---|
[d484a32] | 88 | if(debug) fprintf(stderr,"#\tfailed beacause of LH/LV inequality\n"); |
---|
[3b02b04] | 89 | } |
---|
| 90 | } |
---|
| 91 | |
---|
| 92 | if(debug) fprintf(stderr,"\n"); |
---|
| 93 | return ret; |
---|
[e7de6cc] | 94 | } |
---|
| 95 | |
---|
| 96 | //==================================================================================================== |
---|
| 97 | |
---|
| 98 | list<Boubble*> receive_boubbles(int node, Role role, Dir dir) |
---|
| 99 | { |
---|
| 100 | list<Boubble*> ret; |
---|
| 101 | for(list<Boubble*>::iterator b = sgraph[node].prop.boubbles.begin(); b!=sgraph[node].prop.boubbles.end(); b++) |
---|
| 102 | { |
---|
| 103 | Boubble* new_boubble = (*b)->step(role,dir); |
---|
| 104 | if(new_boubble) |
---|
| 105 | ret.push_back(new_boubble); |
---|
| 106 | } |
---|
[3b02b04] | 107 | |
---|
[e7de6cc] | 108 | return ret; |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | //---------------------------------------------------------------------------------------------------- |
---|
| 112 | |
---|
| 113 | list<Boubble*> collect_head_boubbles(int head, int dep, Role role) |
---|
| 114 | { |
---|
| 115 | list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(dep),role,UP); |
---|
| 116 | |
---|
| 117 | for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++) |
---|
| 118 | (*b)->src(dep); |
---|
| 119 | |
---|
| 120 | list<Boubble*> received_boubbles = receive_boubbles(dep,role,UP); |
---|
| 121 | |
---|
| 122 | new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end()); |
---|
| 123 | |
---|
| 124 | return new_boubbles; |
---|
| 125 | } |
---|
| 126 | |
---|
| 127 | //---------------------------------------------------------------------------------------------------- |
---|
| 128 | |
---|
| 129 | list<Boubble*> collect_dep_boubbles(int head, int dep, Role role) |
---|
| 130 | { |
---|
| 131 | list<Boubble*> new_boubbles = grammar.trigger_boubbles(sgraph.cat(head), role, DOWN); |
---|
| 132 | |
---|
| 133 | for(list<Boubble*>::iterator b = new_boubbles.begin(); b != new_boubbles.end(); b++) |
---|
| 134 | (*b)->src(head); |
---|
| 135 | |
---|
| 136 | list<Boubble*> received_boubbles = receive_boubbles(head,role,DOWN); |
---|
| 137 | |
---|
| 138 | new_boubbles.insert(new_boubbles.begin(),received_boubbles.begin(),received_boubbles.end()); |
---|
| 139 | |
---|
| 140 | return new_boubbles; |
---|
| 141 | } |
---|
| 142 | |
---|
| 143 | //==================================================================================================== |
---|
| 144 | |
---|
[3b02b04] | 145 | void copy_links(int i, int j) |
---|
[e7de6cc] | 146 | { |
---|
[3b02b04] | 147 | sgraph[j].heads = sgraph[i].heads; |
---|
| 148 | sgraph[j].deps = sgraph[i].deps; |
---|
| 149 | } |
---|
| 150 | |
---|
| 151 | |
---|
| 152 | void create_reverse_links(int n) |
---|
| 153 | { |
---|
| 154 | for(vector<Arc>::iterator a=sgraph[n].heads.begin(); a != sgraph[n].heads.end(); a++) |
---|
| 155 | sgraph[a->dst].deps.push_back(Arc(n,a->role,a->headanc,a->depanc)); |
---|
| 156 | |
---|
| 157 | for(vector<Arc>::iterator a=sgraph[n].deps.begin(); a != sgraph[n].deps.end(); a++) |
---|
| 158 | sgraph[a->dst].heads.push_back(Arc(n,a->role,a->headanc,a->depanc)); |
---|
| 159 | } |
---|
| 160 | |
---|
| 161 | //==================================================================================================== |
---|
| 162 | |
---|
[519eaf5] | 163 | int create_new_head_node_left(int anc, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV) |
---|
[3b02b04] | 164 | { |
---|
[519eaf5] | 165 | int newheadind = sgraph.clone(anc,prop); |
---|
[3b02b04] | 166 | nodelist.push_back(newheadind); |
---|
[519eaf5] | 167 | sgraph[newheadind].LH = LH; |
---|
| 168 | sgraph[newheadind].LD = LD; |
---|
| 169 | sgraph[newheadind].in_LH = true; |
---|
[e7de6cc] | 170 | sgraph[newheadind].LV.reset(); |
---|
[3b02b04] | 171 | |
---|
[519eaf5] | 172 | copy_links(anc,newheadind); |
---|
[3b02b04] | 173 | create_reverse_links(newheadind); |
---|
[e7de6cc] | 174 | |
---|
[519eaf5] | 175 | if(debug) sgraph.print_node_debug(stderr,"add new",newheadind,anc); |
---|
[b97a556] | 176 | // if(debug) print_sets(newheadind); |
---|
[e7de6cc] | 177 | return newheadind; |
---|
| 178 | } |
---|
| 179 | |
---|
[519eaf5] | 180 | int create_new_dep_node_left(int anc, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV) |
---|
[e7de6cc] | 181 | { |
---|
[519eaf5] | 182 | int newind = sgraph.clone(anc,prop); |
---|
[3b02b04] | 183 | nodelist.push_back(newind); |
---|
[e7de6cc] | 184 | sgraph[newind].LH.reset(); |
---|
| 185 | sgraph[newind].LD=LD; |
---|
| 186 | sgraph[newind].in_LH=false; //??????? |
---|
| 187 | sgraph[newind].LV.reset(); |
---|
[3b02b04] | 188 | |
---|
[519eaf5] | 189 | copy_links(anc,newind); |
---|
[3b02b04] | 190 | create_reverse_links(newind); |
---|
[e7de6cc] | 191 | |
---|
[519eaf5] | 192 | if(debug) sgraph.print_node_debug(stderr,"add new",newind,anc); |
---|
[b97a556] | 193 | // if(debug) print_sets(newind); |
---|
[e7de6cc] | 194 | |
---|
| 195 | return newind; |
---|
| 196 | } |
---|
| 197 | |
---|
[519eaf5] | 198 | int create_new_head_node_right(int anc, NodeProp& prop, bitset<MAXNODES>& newheadLH, bitset<MAXNODES>& newheadLD, bitset<MAXNODES>& newheadLV) |
---|
[e7de6cc] | 199 | { |
---|
[519eaf5] | 200 | int newheadind = sgraph.clone(anc,prop); |
---|
[3b02b04] | 201 | nodelist.push_back(newheadind); |
---|
[e7de6cc] | 202 | sgraph[newheadind].LH=newheadLH; |
---|
| 203 | sgraph[newheadind].LD=newheadLD; |
---|
| 204 | sgraph[newheadind].in_LH=false; |
---|
| 205 | sgraph[newheadind].LV=newheadLV; |
---|
| 206 | |
---|
[519eaf5] | 207 | copy_links(anc,newheadind); |
---|
[3b02b04] | 208 | create_reverse_links(newheadind); |
---|
| 209 | |
---|
[519eaf5] | 210 | if(debug) sgraph.print_node_debug(stderr,"add new",newheadind,anc); |
---|
[b97a556] | 211 | // if(debug) print_sets(newheadind); |
---|
[e7de6cc] | 212 | |
---|
| 213 | return newheadind; |
---|
| 214 | } |
---|
| 215 | |
---|
[519eaf5] | 216 | int create_new_dep_node_right(int anc, NodeProp& prop, bitset<MAXNODES>& LH, bitset<MAXNODES>& LD, bitset<MAXNODES>& LV) |
---|
[e7de6cc] | 217 | { |
---|
[519eaf5] | 218 | int newind = sgraph.clone(anc,prop); |
---|
[3b02b04] | 219 | nodelist.push_back(newind); |
---|
[e7de6cc] | 220 | sgraph[newind].LH=LH; |
---|
| 221 | sgraph[newind].LD=LD; |
---|
| 222 | sgraph[newind].in_LH=true; //??????? |
---|
| 223 | sgraph[newind].LV.reset(); |
---|
| 224 | |
---|
[519eaf5] | 225 | copy_links(anc,newind); |
---|
[3b02b04] | 226 | create_reverse_links(newind); |
---|
| 227 | |
---|
[519eaf5] | 228 | if(debug) sgraph.print_node_debug(stderr,"ADD NEW",newind,anc); |
---|
[b97a556] | 229 | // if(debug) print_sets(newind); |
---|
[e7de6cc] | 230 | |
---|
| 231 | return newind; |
---|
| 232 | } |
---|
| 233 | |
---|
| 234 | //==================================================================================================== |
---|
| 235 | |
---|
[3b02b04] | 236 | void connect_left(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles) |
---|
[e7de6cc] | 237 | { |
---|
| 238 | |
---|
[3b02b04] | 239 | NodeProp &oldheadprop = sgraph[h].prop; |
---|
| 240 | NodeProp &olddepprop = sgraph[d].prop; |
---|
[e7de6cc] | 241 | |
---|
| 242 | NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles,olddepprop.flags); |
---|
| 243 | |
---|
| 244 | int newheadind; |
---|
| 245 | if(oldheadprop==newheadprop) |
---|
[3b02b04] | 246 | newheadind = h; |
---|
[e7de6cc] | 247 | else |
---|
| 248 | { |
---|
[3b02b04] | 249 | bitset<MAXNODES> newheadLH = sgraph[h].LH; |
---|
| 250 | bitset<MAXNODES> newheadLV = sgraph[d].LV; |
---|
| 251 | bitset<MAXNODES> newheadLD = sgraph[h].LD; |
---|
| 252 | |
---|
| 253 | newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV); |
---|
| 254 | if( newheadind >= 0) // W£¡CZONE |
---|
[e7de6cc] | 255 | sgraph[newheadind].LD |= newheadLD; |
---|
| 256 | else |
---|
[3b02b04] | 257 | { |
---|
| 258 | newheadind = create_new_head_node_left(h,newheadprop,newheadLH,newheadLD,newheadLV); |
---|
| 259 | sgraph[newheadind].edge.clear(); |
---|
| 260 | sgraph[newheadind].edge_contains_self = false; |
---|
| 261 | } |
---|
| 262 | |
---|
[e7de6cc] | 263 | } |
---|
| 264 | |
---|
| 265 | NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); |
---|
| 266 | |
---|
| 267 | int newdepind; |
---|
| 268 | |
---|
| 269 | if(olddepprop==newdepprop) |
---|
[3b02b04] | 270 | newdepind = d; |
---|
[e7de6cc] | 271 | else |
---|
| 272 | { |
---|
[3b02b04] | 273 | bitset<MAXNODES> newdepLH = sgraph[d].LH; |
---|
| 274 | bitset<MAXNODES> newdepLV = sgraph[d].LV; |
---|
| 275 | bitset<MAXNODES> newdepLD = sgraph[d].LD; |
---|
[e7de6cc] | 276 | |
---|
[3b02b04] | 277 | newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV); |
---|
| 278 | if( newdepind >= 0) // W£¡CZONE |
---|
[e7de6cc] | 279 | sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD |
---|
| 280 | else |
---|
[3b02b04] | 281 | { |
---|
| 282 | newdepind = create_new_dep_node_left(d,newdepprop,newdepLH,newdepLD,newdepLV); |
---|
| 283 | sgraph[newdepind].edge.clear(); |
---|
| 284 | //sgraph[newdepind].edge.push_back(newdepind); // TO |
---|
| 285 | sgraph[newdepind].edge_contains_self = true; // LUB TO |
---|
| 286 | } |
---|
[e7de6cc] | 287 | } |
---|
[3b02b04] | 288 | |
---|
[e7de6cc] | 289 | |
---|
[3b02b04] | 290 | sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d)); |
---|
| 291 | sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d)); |
---|
| 292 | sgraph[newheadind].edge.push_back(newdepind); |
---|
[e7de6cc] | 293 | |
---|
[3b02b04] | 294 | if(sgraph[d].saturated()) sgraph[newheadind].LV |= sgraph[d].LV; |
---|
[e7de6cc] | 295 | |
---|
[3b02b04] | 296 | sgraph[newheadind].LD.set(d); |
---|
| 297 | if(sgraph[d].saturated()) sgraph[newheadind].LD |= sgraph[d].LD; |
---|
[e7de6cc] | 298 | |
---|
[519eaf5] | 299 | if(debug) sgraph.print_arc(stderr,"new link",newheadind,d,l.role,0); |
---|
| 300 | if(debug) sgraph.print_node_debug(stderr,"update",newheadind,h); |
---|
[b97a556] | 301 | // if(debug) print_sets(newheadind); |
---|
[519eaf5] | 302 | if(debug) sgraph.print_node_debug(stderr,"update",newdepind,d); |
---|
[b97a556] | 303 | // if(debug) print_sets(newdepind); |
---|
[e7de6cc] | 304 | } |
---|
| 305 | |
---|
| 306 | //---------------------------------------------------------------------------------------------------- |
---|
| 307 | |
---|
[3b02b04] | 308 | void connect_right(int h, int d, const Link& l, list<Boubble*>& new_head_boubbles, list<Boubble*>& new_dep_boubbles) |
---|
[e7de6cc] | 309 | { |
---|
[3b02b04] | 310 | NodeProp &oldheadprop = sgraph[h].prop; |
---|
[e7de6cc] | 311 | |
---|
[3b02b04] | 312 | NodeProp newheadprop = compute_head_prop(oldheadprop,l,new_head_boubbles, sgraph[d].prop.flags); |
---|
[e7de6cc] | 313 | |
---|
| 314 | int newheadind; |
---|
| 315 | |
---|
| 316 | if(oldheadprop==newheadprop) |
---|
[3b02b04] | 317 | newheadind = h; |
---|
[e7de6cc] | 318 | else |
---|
| 319 | { |
---|
[3b02b04] | 320 | bitset<MAXNODES> newheadLH = sgraph[h].LH; |
---|
| 321 | bitset<MAXNODES> newheadLV = sgraph[h].LV; |
---|
| 322 | bitset<MAXNODES> newheadLD = sgraph[h].LD; |
---|
| 323 | |
---|
| 324 | newheadind = find_existing_node(sgraph[h].mnode, newheadprop, newheadLH, newheadLV); |
---|
[e7de6cc] | 325 | |
---|
[3b02b04] | 326 | if(debug) fprintf(stderr,"#HEAD EXISTS %d\n",newheadind); |
---|
| 327 | |
---|
| 328 | if( newheadind >= 0) // W£¡CZONE |
---|
[e7de6cc] | 329 | sgraph[newheadind].LD |= newheadLD; // TYLKO DLA LD |
---|
| 330 | else |
---|
[3b02b04] | 331 | { |
---|
| 332 | newheadind = create_new_head_node_right(h,newheadprop,newheadLH,newheadLD,newheadLV); |
---|
| 333 | //if(!sgraph[h].edge.empty()) sgraph[newheadind].edge.push_back(newheadind); // TO |
---|
| 334 | sgraph[newheadind].edge_contains_self = sgraph[h].edge_contains_self; // LUB TO |
---|
| 335 | sgraph[newheadind].visible_as_neighbour = false; |
---|
| 336 | } |
---|
[e7de6cc] | 337 | } |
---|
| 338 | |
---|
[3b02b04] | 339 | NodeProp &olddepprop = sgraph[d].prop; |
---|
[e7de6cc] | 340 | NodeProp newdepprop = compute_dep_prop(olddepprop,l,new_dep_boubbles); |
---|
| 341 | |
---|
| 342 | int newdepind; |
---|
| 343 | |
---|
| 344 | if(olddepprop==newdepprop) |
---|
[3b02b04] | 345 | newdepind = d; |
---|
[e7de6cc] | 346 | else |
---|
| 347 | { |
---|
[3b02b04] | 348 | bitset<MAXNODES> newdepLH = sgraph[d].LH; |
---|
| 349 | bitset<MAXNODES> newdepLV = sgraph[d].LV; |
---|
| 350 | bitset<MAXNODES> newdepLD = sgraph[d].LD; |
---|
| 351 | |
---|
| 352 | newdepind = find_existing_node(sgraph[d].mnode, newdepprop, newdepLH, newdepLV); |
---|
| 353 | |
---|
| 354 | if(debug) fprintf(stderr,"#DEP EXISTS %d\n",newdepind); |
---|
[e7de6cc] | 355 | |
---|
[3b02b04] | 356 | if( newdepind >= 0) // W£¡CZONE |
---|
[e7de6cc] | 357 | sgraph[newdepind].LD |= newdepLD; // TYLKO DLA LD |
---|
| 358 | else |
---|
[3b02b04] | 359 | { |
---|
| 360 | newdepind = create_new_dep_node_right(d,newdepprop,newdepLH,newdepLD,newdepLV); |
---|
| 361 | sgraph[newdepind].edge.clear(); |
---|
| 362 | sgraph[newdepind].edge_contains_self = false; |
---|
| 363 | } |
---|
[e7de6cc] | 364 | } |
---|
| 365 | |
---|
| 366 | |
---|
[3b02b04] | 367 | sgraph[newdepind].heads.push_back(Arc(newheadind,l.role,h,d)); |
---|
| 368 | sgraph[newheadind].deps.push_back(Arc(newdepind,l.role,h,d)); |
---|
| 369 | //sgraph[newdepind].edge.push_back(newheadind); |
---|
[e7de6cc] | 370 | |
---|
| 371 | sgraph[newdepind].LH.set(newheadind); |
---|
| 372 | |
---|
| 373 | // sgraph[*d].prop.merge_boubbles(new_dep_boubbles); |
---|
| 374 | |
---|
| 375 | if(sgraph[newheadind].saturated()) sgraph[newdepind].LH |= sgraph[newheadind].LH; |
---|
| 376 | |
---|
[519eaf5] | 377 | if(debug) sgraph.print_arc(stderr,"new link",newheadind,newdepind,l.role,1); |
---|
| 378 | if(debug) sgraph.print_node_debug(stderr,"update",newheadind,h); |
---|
| 379 | if(debug) sgraph.print_node_debug(stderr,"update",newdepind,d); |
---|
[e7de6cc] | 380 | |
---|
| 381 | } |
---|
| 382 | |
---|
| 383 | //==================================================================================================== |
---|
| 384 | |
---|
[519eaf5] | 385 | // bool check_meeting_boubles(list<Boubble*>& hboubbles, list<Boubble*>& dboubbles) |
---|
| 386 | // { |
---|
| 387 | // bool hremove=false; // czy usun±æ ostatnio sprawdzany b±bel |
---|
| 388 | // bool dremove=false; // czy usun±æ ostatnio sprawdzany b±bel |
---|
| 389 | |
---|
| 390 | // for(list<Boubble*>::iterator hb = hboubbles.begin(); hb != hboubbles.end(); hb = hremove ? hboubbles.erase(hb) : ++hb ) |
---|
| 391 | // { |
---|
| 392 | // hremove=false; |
---|
| 393 | // for(list<Boubble*>::iterator db = dboubbles.begin(); db != dboubbles.end(); db = dremove ? dboubbles.erase(db) : ++db ) |
---|
| 394 | // { |
---|
| 395 | // dremove=false; |
---|
| 396 | // if( (*hb)->rel()==(*db)->rel() && (*hb)->dir()==DOWN && (*db)->dir()==UP && (*hb)->reverse()!=(*db)->reverse() ) |
---|
| 397 | // { |
---|
| 398 | // int srcnode,dstnode; |
---|
| 399 | // if( (*hb)->reverse()==false ) |
---|
| 400 | // srcnode = (*hb)->src(), dstnode = (*db)->src(); |
---|
| 401 | // else |
---|
| 402 | // srcnode = (*db)->src(), dstnode = (*hb)->src(); |
---|
| 403 | // if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) ) |
---|
| 404 | // { |
---|
| 405 | // hremove=dremove=true; |
---|
| 406 | // if(debug) fprintf(stderr,"BOUBBLES MET!!!\n"); |
---|
| 407 | // } |
---|
| 408 | // else |
---|
| 409 | // { |
---|
| 410 | // if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n"); |
---|
| 411 | // return false; |
---|
| 412 | // } |
---|
| 413 | // } |
---|
| 414 | // } |
---|
| 415 | // } |
---|
| 416 | // return true; |
---|
| 417 | // } |
---|
| 418 | |
---|
| 419 | //==================================================================================================== |
---|
| 420 | |
---|
| 421 | bool check_meeting_boubles(list<Boubble*>& boubbles) |
---|
| 422 | { |
---|
| 423 | bool hremove=false; // czy usun±æ ostatnio sprawdzany b±bel |
---|
| 424 | bool dremove=false; // czy usun±æ ostatnio sprawdzany b±bel |
---|
| 425 | |
---|
| 426 | for(list<Boubble*>::iterator hb = boubbles.begin(); hb != boubbles.end(); hb = hremove ? boubbles.erase(hb) : ++hb ) |
---|
| 427 | { |
---|
| 428 | cout << endl << "hb:" << **hb ; |
---|
| 429 | hremove=false; |
---|
| 430 | for(list<Boubble*>::iterator db = hb; db != boubbles.end(); db = dremove ? boubbles.erase(db) : ++db ) |
---|
| 431 | { |
---|
| 432 | cout << " db:" << **db; |
---|
| 433 | dremove=false; |
---|
| 434 | if( (*hb)->rel()==(*db)->rel() && (*hb)->reverse()!=(*db)->reverse() ) |
---|
| 435 | { |
---|
| 436 | cout << "Z"; |
---|
| 437 | int srcnode,dstnode; |
---|
| 438 | if( (*hb)->reverse()==false ) |
---|
| 439 | srcnode = (*hb)->src(), dstnode = (*db)->src(); |
---|
| 440 | else |
---|
| 441 | srcnode = (*db)->src(), dstnode = (*hb)->src(); |
---|
| 442 | if( grammar.check_longrel(sgraph.cat(srcnode), sgraph.cat(dstnode), (*hb)->rel()) ) |
---|
| 443 | { |
---|
| 444 | cout << " REMOVE "; |
---|
| 445 | hremove=dremove=true; |
---|
| 446 | if(debug) fprintf(stderr,"BOUBBLES MET!!!\n"); |
---|
| 447 | } |
---|
| 448 | else |
---|
| 449 | { |
---|
| 450 | cout << " FAIL "; |
---|
| 451 | if(debug) fprintf(stderr,"BOUBBLES' MEETING FAILED!!!\n"); |
---|
| 452 | return false; |
---|
| 453 | } |
---|
| 454 | } |
---|
| 455 | } |
---|
| 456 | } |
---|
| 457 | return true; |
---|
| 458 | } |
---|
| 459 | |
---|
| 460 | //==================================================================================================== |
---|
| 461 | |
---|
[a15e59b] | 462 | // sprawdza czy te, spo¶ród b±bli, które dotar³y do celu node |
---|
| 463 | // daj± wynik prawdziwy, dodatkowo - usuwa je z listy boubbles |
---|
| 464 | |
---|
| 465 | bool check_boubbles_at_target(list<Boubble*>& boubbles, int node) |
---|
[e7de6cc] | 466 | { |
---|
[a15e59b] | 467 | bool remove=false; // czy usun±æ ostatnio sprawdzany b±bel |
---|
| 468 | |
---|
| 469 | for(list<Boubble*>::iterator b = boubbles.begin(); b != boubbles.end(); b = remove ? boubbles.erase(b) : ++b ) |
---|
| 470 | if( (*b)->is_at_target() ) |
---|
| 471 | if( grammar.check_longrel(sgraph.cat((*b)->src()), sgraph.cat(node), (*b)->rel()) ) |
---|
[519eaf5] | 472 | { |
---|
| 473 | cout << endl << "REMOVE ChBatT " << **b << endl; |
---|
| 474 | remove=true; |
---|
| 475 | } |
---|
[a15e59b] | 476 | else |
---|
| 477 | return false; |
---|
| 478 | else |
---|
| 479 | remove=false; |
---|
| 480 | |
---|
[e7de6cc] | 481 | return true; |
---|
| 482 | } |
---|
| 483 | |
---|
| 484 | //==================================================================================================== |
---|
| 485 | |
---|
[3b02b04] | 486 | void try_connect_dependents(int j) |
---|
[e7de6cc] | 487 | { |
---|
[3b02b04] | 488 | LViterator lvi(sgraph,j); |
---|
| 489 | int i; |
---|
| 490 | while((i=lvi.next()) >= 0) |
---|
[519eaf5] | 491 | { |
---|
| 492 | //if(debug) sgraph.print_node_debug(stderr,"D-CUR>",i,-1); |
---|
[3b02b04] | 493 | |
---|
[519eaf5] | 494 | if(sgraph.saturated(i)) |
---|
[e7de6cc] | 495 | { |
---|
[519eaf5] | 496 | if(debug) {fprintf(stderr,"%d <--",i); } |
---|
| 497 | |
---|
| 498 | list<const Link*> ji_links = grammar.connectable2( sgraph.cat(j), sgraph.cat(i), sgraph[j].prop.flags, sgraph[i].prop.flags); // ref do Roles!!! |
---|
| 499 | list<const Link*>::iterator ri = ji_links.begin(); |
---|
| 500 | if(ri == ji_links.end()) { if(debug) fprintf(stderr," no roles\n"); } |
---|
| 501 | else |
---|
| 502 | { |
---|
| 503 | for(; ri != ji_links.end(); ++ri ) |
---|
| 504 | { |
---|
| 505 | if(debug) fprintf(stderr," %s",(*ri)->role.str()); |
---|
| 506 | if(!grammar.check_constr2(sgraph[j].prop,sgraph[i].prop,0,**ri )) |
---|
| 507 | { if(debug) fprintf(stderr," ...constraints failed\n"); } |
---|
| 508 | else |
---|
| 509 | { |
---|
| 510 | list<Boubble*> new_head_boubbles = collect_head_boubbles(j,i,(*ri)->role); |
---|
| 511 | list<Boubble*> new_dep_boubbles = collect_dep_boubbles(j,i,(*ri)->role); |
---|
| 512 | if( check_meeting_boubles(new_head_boubbles) && |
---|
| 513 | check_meeting_boubles(new_dep_boubbles) && |
---|
| 514 | check_boubbles_at_target(new_head_boubbles,j) && |
---|
| 515 | check_boubbles_at_target(new_dep_boubbles,i) ) |
---|
| 516 | { |
---|
| 517 | if(debug) fprintf(stderr," ...SUCCESS!\n"); |
---|
| 518 | connect_left( j, i, **ri, new_head_boubbles, new_dep_boubbles); |
---|
[d484a32] | 519 | lvi.update_edge(sgraph,i); |
---|
[519eaf5] | 520 | } |
---|
| 521 | else |
---|
| 522 | { if(debug) fprintf(stderr," ...boubbles failed\n"); } |
---|
| 523 | } |
---|
| 524 | } |
---|
| 525 | } |
---|
[e7de6cc] | 526 | } |
---|
[519eaf5] | 527 | else |
---|
| 528 | if(debug) {fprintf(stderr,"%d <-- unsaturated\n",i); } |
---|
[e7de6cc] | 529 | } |
---|
[519eaf5] | 530 | |
---|
[e7de6cc] | 531 | } |
---|
| 532 | //---------------------------------------------------------------------------------------------------- |
---|
| 533 | |
---|
[3b02b04] | 534 | void try_connect_heads(int j) |
---|
[e7de6cc] | 535 | { |
---|
[3b02b04] | 536 | LViterator lvi(sgraph,j); |
---|
| 537 | int i; |
---|
| 538 | while((i=lvi.next()) >= 0) |
---|
[e7de6cc] | 539 | { |
---|
[519eaf5] | 540 | // if(debug) sgraph.print_node_debug(stderr,"H-CUR> ",i,-1); |
---|
| 541 | if(sgraph.saturated(j)) |
---|
[e7de6cc] | 542 | { |
---|
[519eaf5] | 543 | if(debug) fprintf(stderr, "%d -->",i); |
---|
| 544 | |
---|
| 545 | list<const Link*> ij_links = grammar.connectable2( sgraph.cat(i), sgraph.cat(j), sgraph[i].prop.flags, sgraph[j].prop.flags ); |
---|
| 546 | list<const Link*>::iterator ri = ij_links.begin(); |
---|
| 547 | if(ri == ij_links.end()) { if(debug) fprintf(stderr," no roles\n"); } |
---|
| 548 | else |
---|
| 549 | { |
---|
| 550 | for(; ri != ij_links.end(); ++ri ) |
---|
| 551 | { |
---|
| 552 | if(debug) fprintf(stderr," %s",(*ri)->role.str()); |
---|
| 553 | if( !grammar.check_constr2( sgraph[i].prop, sgraph[j].prop, 1, **ri ) ) |
---|
| 554 | { if(debug) fprintf(stderr," ...constraints failed\n"); } |
---|
| 555 | else |
---|
| 556 | { |
---|
| 557 | list<Boubble*> new_head_boubbles = collect_head_boubbles(i,j,(*ri)->role); |
---|
| 558 | list<Boubble*> new_dep_boubbles = collect_dep_boubbles(i,j,(*ri)->role); |
---|
| 559 | |
---|
| 560 | if( check_meeting_boubles(new_head_boubbles) && |
---|
| 561 | check_meeting_boubles(new_dep_boubbles) && |
---|
| 562 | check_boubbles_at_target(new_head_boubbles,i) && |
---|
| 563 | check_boubbles_at_target(new_dep_boubbles,j) ) |
---|
| 564 | { |
---|
| 565 | if(debug) fprintf(stderr," ...SUCCESS!\n"); |
---|
| 566 | connect_right( i, j, **ri, new_head_boubbles, new_dep_boubbles ); |
---|
| 567 | } |
---|
| 568 | else |
---|
| 569 | { if(debug) fprintf(stderr," ...bubbles failed\n",i); } |
---|
| 570 | } |
---|
| 571 | } |
---|
| 572 | } |
---|
[e7de6cc] | 573 | } |
---|
[519eaf5] | 574 | else |
---|
| 575 | if(debug) {fprintf(stderr,"%d <-- unsaturated\n",j); } |
---|
[e7de6cc] | 576 | } |
---|
| 577 | } |
---|
[3b02b04] | 578 | |
---|
| 579 | //==================================================================================================== |
---|
| 580 | |
---|
| 581 | void update_sets() |
---|
| 582 | { |
---|
| 583 | for(int n=0; n<sgraph.size(); ++n) |
---|
| 584 | { |
---|
| 585 | LViterator lvi(sgraph,n,false); |
---|
| 586 | LHiterator lhi(sgraph,n); |
---|
| 587 | LDiterator ldi(sgraph,n); |
---|
| 588 | int i; |
---|
| 589 | |
---|
| 590 | // printf("UPDATING LV[%d]:",n); |
---|
| 591 | while((i=lvi.next())>=0) |
---|
| 592 | { |
---|
| 593 | // printf(" %d",i); |
---|
| 594 | sgraph[n].LV.set(i); |
---|
| 595 | } |
---|
| 596 | // printf("\n"); |
---|
| 597 | |
---|
| 598 | while((i=lhi.next())>=0) sgraph[n].LH.set(i); |
---|
| 599 | while((i=ldi.next())>=0) sgraph[n].LD.set(i); |
---|
| 600 | } |
---|
| 601 | } |
---|
| 602 | |
---|
| 603 | //==================================================================================================== |
---|
| 604 | |
---|
| 605 | void print_sets(int n) |
---|
| 606 | { |
---|
| 607 | LViterator lvi(sgraph,n); |
---|
| 608 | LHiterator lhi(sgraph,n); |
---|
| 609 | LDiterator ldi(sgraph,n); |
---|
[e7de6cc] | 610 | |
---|
[3b02b04] | 611 | int i; |
---|
| 612 | printf("LV[%d]: ",n); |
---|
| 613 | while((i=lvi.next())>=0) |
---|
| 614 | { |
---|
| 615 | printf("%d ",i); |
---|
| 616 | sgraph[n].LV.set(i); |
---|
| 617 | } |
---|
| 618 | |
---|
| 619 | printf("LH[%d]: ",n); |
---|
| 620 | while((i=lhi.next())>=0) |
---|
| 621 | { |
---|
| 622 | printf("%d ",i); |
---|
| 623 | sgraph[n].LH.set(i); |
---|
| 624 | } |
---|
| 625 | printf("LD[%d]: ",n); |
---|
| 626 | while((i=ldi.next())>=0) |
---|
| 627 | { |
---|
| 628 | printf("%d ",i); |
---|
| 629 | sgraph[n].LD.set(i); |
---|
| 630 | } |
---|
| 631 | printf("\n"); |
---|
| 632 | } |
---|
| 633 | |
---|
[e7de6cc] | 634 | //==================================================================================================== |
---|
| 635 | |
---|
| 636 | void reverse_links() |
---|
| 637 | { |
---|
| 638 | list<int>::iterator i = nodelist.begin(); |
---|
| 639 | for(++i; i!=nodelist.end(); ++i) |
---|
| 640 | { |
---|
| 641 | for(vector<Arc>::iterator da=sgraph[*i].deps.begin()--; da!=sgraph[*i].deps.end(); ++da) |
---|
| 642 | sgraph[da->dst].heads.push_back(Arc(*i,da->role,da->headanc,da->depanc)); |
---|
| 643 | for(vector<Arc>::iterator ha=sgraph[*i].heads.begin(); ha!=sgraph[*i].heads.end(); ++ha) |
---|
| 644 | sgraph[ha->dst].deps.push_back(Arc(*i,ha->role,ha->headanc,ha->depanc)); |
---|
| 645 | } |
---|
| 646 | } |
---|
| 647 | |
---|
| 648 | //==================================================================================================== |
---|
| 649 | |
---|
| 650 | void dgp1() |
---|
| 651 | { |
---|
| 652 | |
---|
| 653 | nodelist.clear(); |
---|
| 654 | nodelist.push_back(0); // BOS |
---|
| 655 | processed=nodelist.begin(); |
---|
| 656 | |
---|
| 657 | for(int m=0; m<mgraph.size() ; ++m) |
---|
| 658 | { |
---|
| 659 | int basenode = sgraph.add_base_snode(m); // ma zwracaæ SNode* |
---|
| 660 | |
---|
| 661 | set_initial_constraints(basenode); |
---|
| 662 | nodelist.push_back(basenode); |
---|
| 663 | |
---|
[519eaf5] | 664 | if(debug) sgraph.print_node_debug(stderr,"add base",basenode,-1); // STDOUT!!! |
---|
| 665 | // if(debug) print_sets(basenode); |
---|
[e7de6cc] | 666 | |
---|
| 667 | list<int>::iterator cursor=processed; |
---|
| 668 | while(++cursor != nodelist.end()) |
---|
| 669 | { |
---|
[519eaf5] | 670 | if(debug) sgraph.print_node_debug(stderr,"MAIN-CUR> ",*cursor,-1); |
---|
[3b02b04] | 671 | try_connect_dependents(*cursor); |
---|
| 672 | try_connect_heads(*cursor); |
---|
[e7de6cc] | 673 | processed=cursor; |
---|
| 674 | } |
---|
| 675 | |
---|
| 676 | } |
---|
[3b02b04] | 677 | // reverse_links(); |
---|
| 678 | update_sets(); |
---|
[e7de6cc] | 679 | } |
---|