[5f4d9c3] | 1 | #ifndef _SGRAPH_HH |
---|
| 2 | #define _SGRAPH_HH |
---|
| 3 | |
---|
| 4 | #include <stdio.h> |
---|
| 5 | |
---|
| 6 | #include <list> |
---|
| 7 | #include <vector> |
---|
| 8 | #include <bitset> |
---|
[3b02b04] | 9 | #include <stack> |
---|
[5f4d9c3] | 10 | |
---|
| 11 | #include "const.hh" |
---|
[e7de6cc] | 12 | #include "mgraph.hh" |
---|
[5f4d9c3] | 13 | #include "thesymbols.hh" |
---|
[e7de6cc] | 14 | #include "boubble.hh" |
---|
[acbabee] | 15 | #include "global.hh" |
---|
[5f4d9c3] | 16 | |
---|
[e7de6cc] | 17 | using namespace std; |
---|
[5f4d9c3] | 18 | |
---|
[e7de6cc] | 19 | //==================================================================================================== |
---|
| 20 | // CLASS Arc |
---|
| 21 | //==================================================================================================== |
---|
[5f4d9c3] | 22 | struct Arc |
---|
| 23 | { |
---|
| 24 | int dst; |
---|
| 25 | Role role; |
---|
[e7de6cc] | 26 | int headanc; |
---|
| 27 | int depanc; |
---|
[5f4d9c3] | 28 | |
---|
[e7de6cc] | 29 | Arc(int d, Role r, int ha, int da) : dst(d), role(r), headanc(ha), depanc(da) {}; |
---|
| 30 | }; |
---|
[5f4d9c3] | 31 | |
---|
[e7de6cc] | 32 | //==================================================================================================== |
---|
| 33 | // CLASS NodeProp |
---|
| 34 | //==================================================================================================== |
---|
[5f4d9c3] | 35 | |
---|
| 36 | struct NodeProp |
---|
| 37 | { |
---|
[e7de6cc] | 38 | NodeProp(); |
---|
| 39 | NodeProp(const NodeProp& p); |
---|
| 40 | ~NodeProp(); |
---|
| 41 | |
---|
| 42 | bool operator==(const NodeProp& p); |
---|
| 43 | NodeProp& operator=(const NodeProp& p); |
---|
| 44 | |
---|
| 45 | void clear_boubbles(); |
---|
| 46 | void merge_boubbles(list<Boubble*> new_boubbles); |
---|
[5f4d9c3] | 47 | |
---|
[e7de6cc] | 48 | void copy(const NodeProp& p); |
---|
| 49 | void clear(); |
---|
[5f4d9c3] | 50 | |
---|
[e7de6cc] | 51 | RoleSet required; |
---|
| 52 | RoleSet forbidden; |
---|
| 53 | RoleSet attached; |
---|
[5f4d9c3] | 54 | |
---|
[e7de6cc] | 55 | bool init_attached; |
---|
| 56 | bool fin_attached; |
---|
[854bece] | 57 | bool visible_as_neighbour; |
---|
| 58 | bool has_head; |
---|
[e7de6cc] | 59 | |
---|
| 60 | FlagSet flags; |
---|
| 61 | |
---|
| 62 | list<Boubble*> boubbles; |
---|
[5f4d9c3] | 63 | }; |
---|
| 64 | |
---|
[e7de6cc] | 65 | //---------------------------------------------------------------------------------------------------- |
---|
| 66 | |
---|
| 67 | inline |
---|
| 68 | bool NodeProp::operator==(const NodeProp& p) |
---|
| 69 | { |
---|
| 70 | if(required != p.required) return false; |
---|
| 71 | if(forbidden != p.forbidden) return false; |
---|
| 72 | if(attached != p.attached) return false; |
---|
| 73 | if(flags != p.flags) return false; |
---|
| 74 | if(init_attached != p.init_attached) return false; |
---|
| 75 | if(fin_attached != p.fin_attached) return false; |
---|
[854bece] | 76 | if(visible_as_neighbour != p.visible_as_neighbour) return false; |
---|
| 77 | if(has_head != p.has_head) return false; |
---|
[3b02b04] | 78 | |
---|
| 79 | list<Boubble*>::const_iterator b,b1; |
---|
| 80 | for(b=boubbles.begin(), b1=p.boubbles.begin(); b != boubbles.end() && b1 != p.boubbles.end(); b++,b1++) |
---|
| 81 | if(!(**b == **b1)) |
---|
| 82 | return false; |
---|
| 83 | if(b != boubbles.end() || b1 != p.boubbles.end()) |
---|
[e7de6cc] | 84 | return false; |
---|
[3b02b04] | 85 | |
---|
[e7de6cc] | 86 | return true; |
---|
| 87 | } |
---|
| 88 | |
---|
| 89 | //---------------------------------------------------------------------------------------------------- |
---|
| 90 | |
---|
| 91 | inline |
---|
| 92 | void NodeProp::clear_boubbles() |
---|
| 93 | { |
---|
| 94 | for(list<Boubble*>::iterator b = boubbles.begin(); b!=boubbles.end(); b++) |
---|
| 95 | delete *b; |
---|
| 96 | boubbles.clear(); |
---|
| 97 | } |
---|
| 98 | |
---|
| 99 | //---------------------------------------------------------------------------------------------------- |
---|
| 100 | |
---|
| 101 | inline |
---|
| 102 | void NodeProp::merge_boubbles(list<Boubble*> new_boubbles) |
---|
| 103 | { |
---|
| 104 | boubbles.merge(new_boubbles); |
---|
| 105 | } |
---|
| 106 | |
---|
| 107 | //---------------------------------------------------------------------------------------------------- |
---|
| 108 | |
---|
| 109 | inline |
---|
| 110 | void NodeProp::copy(const NodeProp& p) |
---|
| 111 | { |
---|
[854bece] | 112 | required = p.required; |
---|
| 113 | forbidden = p.forbidden; |
---|
| 114 | attached = p.attached; |
---|
| 115 | flags = p.flags; |
---|
| 116 | init_attached = p.init_attached; |
---|
| 117 | fin_attached = p.fin_attached; |
---|
| 118 | visible_as_neighbour = p.visible_as_neighbour; |
---|
| 119 | has_head = p.has_head; |
---|
[e7de6cc] | 120 | for(list<Boubble*>::const_iterator b = p.boubbles.begin(); b!=p.boubbles.end(); b++) |
---|
| 121 | boubbles.push_back(new Boubble(**b)); |
---|
| 122 | } |
---|
| 123 | |
---|
[acbabee] | 124 | inline NodeProp::~NodeProp() { clear_boubbles(); } |
---|
| 125 | inline NodeProp::NodeProp() { clear(); } |
---|
| 126 | inline NodeProp::NodeProp(const NodeProp& p) { copy(p); } |
---|
| 127 | inline NodeProp& NodeProp::operator=(const NodeProp& p) { clear(); copy(p); return *this; } |
---|
| 128 | inline void NodeProp::clear() |
---|
[e7de6cc] | 129 | { |
---|
[acbabee] | 130 | required.reset(); |
---|
| 131 | forbidden.reset(); |
---|
| 132 | attached.reset(); |
---|
| 133 | init_attached=false; |
---|
| 134 | fin_attached=false; |
---|
[854bece] | 135 | visible_as_neighbour=true; |
---|
| 136 | has_head=false; |
---|
[e7de6cc] | 137 | clear_boubbles(); |
---|
| 138 | } |
---|
| 139 | |
---|
[acbabee] | 140 | //==================================================================================================== |
---|
| 141 | // CLASS Edge |
---|
| 142 | //==================================================================================================== |
---|
[e7de6cc] | 143 | |
---|
[acbabee] | 144 | class Edge |
---|
[e7de6cc] | 145 | { |
---|
[acbabee] | 146 | public: |
---|
| 147 | Edge() : _self(false) { } |
---|
| 148 | Edge(const Edge& e, int map_self) { assign(e,map_self); } |
---|
[e7de6cc] | 149 | |
---|
[acbabee] | 150 | bool self() const { return _self; } |
---|
| 151 | list<int>& others() { return _others; } |
---|
[e7de6cc] | 152 | |
---|
[acbabee] | 153 | void insert_self(bool b=true) { _self=b; } |
---|
| 154 | void insert(int n) { list<int>::iterator i=others().begin(); while(i!=others().end() && *i<n) ++i; others().insert(i,n);} |
---|
| 155 | void insert(list<int> l) { for(list<int>::const_iterator i=l.begin(); i!=l.end(); i++) insert(*i); } |
---|
[e7de6cc] | 156 | |
---|
[acbabee] | 157 | void assign(const Edge& e, int map_self=-1) { _others = e._others; if(e.self()) { _self = false; insert(map_self); } } |
---|
| 158 | const bool operator==(const Edge& e) const { return _self == e._self && _others == e._others; } |
---|
| 159 | |
---|
| 160 | private: |
---|
| 161 | bool _self; |
---|
| 162 | list<int> _others; |
---|
| 163 | }; |
---|
[e7de6cc] | 164 | |
---|
| 165 | //==================================================================================================== |
---|
| 166 | // CLASS SNode |
---|
| 167 | //==================================================================================================== |
---|
[5f4d9c3] | 168 | |
---|
| 169 | struct SNode |
---|
| 170 | { |
---|
[854bece] | 171 | SNode() { prop.clear(); } |
---|
[3b02b04] | 172 | |
---|
[e7de6cc] | 173 | int mnode; |
---|
[5f4d9c3] | 174 | |
---|
| 175 | NodeProp prop; |
---|
[acbabee] | 176 | Edge edge; |
---|
[3b02b04] | 177 | |
---|
[5f4d9c3] | 178 | bitset<MAXNODES> LV; |
---|
| 179 | bitset<MAXNODES> LH; |
---|
| 180 | bitset<MAXNODES> LD; |
---|
| 181 | bool in_LH; |
---|
| 182 | |
---|
| 183 | vector<Arc> heads; |
---|
| 184 | vector<Arc> deps; |
---|
| 185 | |
---|
[854bece] | 186 | void clear() { prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); } |
---|
| 187 | bool saturated() { return prop.required.none(); } |
---|
| 188 | |
---|
[acbabee] | 189 | |
---|
| 190 | // void edge_clear() { edge.clear(); edge_contains_self=false;} |
---|
| 191 | // void edge_set(int i) { edge.clear(); edge_contains_self=false; edge.push_back(i); } |
---|
| 192 | // void edge_set(vector<int>& v) { edge.assign(v.begin(),v.end()); edge_contains_self=false; } |
---|
| 193 | // void edge_set_self(bool b=true) { edge.clear(); edge_contains_self=b; } |
---|
| 194 | // void edge_add(int i) { edge.push_back(i); } |
---|
| 195 | // void edge_add(vector<int>& v) { edge.insert(edge.end(),v.begin(),v.end()); } |
---|
| 196 | // void edge_add_self(bool b=true) { edge_contains_self=b; } |
---|
[5f4d9c3] | 197 | }; |
---|
| 198 | |
---|
[e7de6cc] | 199 | //==================================================================================================== |
---|
| 200 | // SGraph CLASS |
---|
| 201 | //==================================================================================================== |
---|
[5f4d9c3] | 202 | |
---|
| 203 | class SGraph |
---|
| 204 | { |
---|
| 205 | public: |
---|
| 206 | |
---|
[e7de6cc] | 207 | enum Output { HEADS=1, DEPS=2, SETS=4, CONSTRAINTS=8, BOUBBLES=16 }; |
---|
[5f4d9c3] | 208 | |
---|
[e7de6cc] | 209 | SGraph(MGraph& mg) : mgraph(mg) { clear(); } |
---|
[5f4d9c3] | 210 | |
---|
[e7de6cc] | 211 | SNode& operator[](const int i) { return nodes[i]; } |
---|
[5f4d9c3] | 212 | |
---|
[e7de6cc] | 213 | void clear() { nodes.clear(); } |
---|
| 214 | int add_base_snode(int mnodeind); |
---|
[acbabee] | 215 | int clone(int ancind, NodeProp newprop, Edge edge); |
---|
[5f4d9c3] | 216 | void update_left(int headind, int depind); |
---|
| 217 | void update_right(int headind, int depind); |
---|
[854bece] | 218 | bool visible(int left, int right) { return nodes[right].LV[left]; } |
---|
| 219 | bool saturated(int node) { return nodes[node].saturated(); } |
---|
| 220 | bool has_head(int node) { return nodes[node].prop.has_head; } |
---|
[5f4d9c3] | 221 | |
---|
[e7de6cc] | 222 | Cat cat(int i) const { return mgraph[nodes[i].mnode].cat; } |
---|
| 223 | char* form(int i) const { return mgraph[nodes[i].mnode].form; } |
---|
[5f4d9c3] | 224 | |
---|
| 225 | int print_node(FILE* f, int n, unsigned int info); |
---|
[e7de6cc] | 226 | int print_node_debug(FILE* f, const char* pref, int n, int anc); |
---|
[5f4d9c3] | 227 | |
---|
[519eaf5] | 228 | void print_arc(FILE* f, const char* msg, int left, int right, Role role, int dir); // 0 - left, 1 - right |
---|
[5f4d9c3] | 229 | |
---|
[e7de6cc] | 230 | //private: |
---|
| 231 | |
---|
| 232 | int size() {return nodes.size(); } |
---|
| 233 | |
---|
[3b02b04] | 234 | friend class LViterator; |
---|
| 235 | friend class LHiterator; |
---|
| 236 | friend class LDiterator; |
---|
| 237 | friend class LNiterator; |
---|
| 238 | |
---|
[e7de6cc] | 239 | private: |
---|
| 240 | |
---|
| 241 | MGraph& mgraph; |
---|
| 242 | |
---|
| 243 | vector<SNode> nodes; |
---|
| 244 | |
---|
| 245 | int lastnodeind() { return nodes.size()-1; } |
---|
| 246 | SNode& makenewnode() { nodes.push_back(SNode()); nodes.back().clear(); return nodes.back(); } |
---|
| 247 | |
---|
| 248 | int sprint_node(char* buf, int n, int anc, unsigned int info); |
---|
| 249 | int sprint_node_debug(char* buf, const char* pref, int n, int anc); |
---|
[5f4d9c3] | 250 | }; |
---|
| 251 | |
---|
[e7de6cc] | 252 | //---------------------------------------------------------------------------------------------------- |
---|
[3b02b04] | 253 | //---------------------------------------------------------------------------------------------------- |
---|
| 254 | |
---|
| 255 | class XXiterator |
---|
| 256 | { |
---|
| 257 | protected: |
---|
| 258 | |
---|
| 259 | bool checked(int i) { return _checked[i]; } |
---|
| 260 | void check(int i) { _checked.set(i); } |
---|
| 261 | |
---|
| 262 | void push(stack<int>& s, int i) |
---|
| 263 | { |
---|
| 264 | if(!checked(i)) |
---|
| 265 | { |
---|
| 266 | s.push(i); |
---|
| 267 | check(i); |
---|
| 268 | } |
---|
| 269 | } |
---|
| 270 | |
---|
| 271 | bitset<MAXNODES> _checked; |
---|
| 272 | }; |
---|
| 273 | |
---|
| 274 | //---------------------------------------------------------------------------------------------------- |
---|
| 275 | //---------------------------------------------------------------------------------------------------- |
---|
| 276 | |
---|
| 277 | class LViterator : public XXiterator |
---|
| 278 | { |
---|
| 279 | public: |
---|
| 280 | LViterator(SGraph& sg, int n, bool s); |
---|
| 281 | int next(); |
---|
[d484a32] | 282 | void update_edge(SGraph& sg, int e); |
---|
[3b02b04] | 283 | |
---|
| 284 | private: |
---|
[acbabee] | 285 | int snode; |
---|
[3b02b04] | 286 | SGraph& sgraph; |
---|
| 287 | MGraph& mgraph; |
---|
| 288 | stack<int> waydown; |
---|
| 289 | stack<int> wayup; |
---|
| 290 | bool strict; |
---|
| 291 | |
---|
| 292 | void push_ld(int i); |
---|
| 293 | void push_lh(int i); |
---|
| 294 | void push_ln(int i); |
---|
[d484a32] | 295 | |
---|
[3b02b04] | 296 | }; |
---|
| 297 | |
---|
[acbabee] | 298 | inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : snode(n), sgraph(sg), mgraph(sg.mgraph), strict(s) |
---|
[3b02b04] | 299 | { |
---|
[acbabee] | 300 | if(sg[n].edge.self()) |
---|
[3b02b04] | 301 | { |
---|
| 302 | push_ld(n); |
---|
| 303 | push_ln(n); |
---|
| 304 | } |
---|
| 305 | |
---|
[acbabee] | 306 | for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i) |
---|
[3b02b04] | 307 | { |
---|
[acbabee] | 308 | push_ld(*i); |
---|
| 309 | push_ln(*i); |
---|
[3b02b04] | 310 | |
---|
| 311 | } |
---|
| 312 | } |
---|
| 313 | |
---|
[d484a32] | 314 | inline void LViterator::update_edge(SGraph& sg, int n) |
---|
| 315 | { |
---|
[acbabee] | 316 | if(sg[n].edge.self()) |
---|
| 317 | { |
---|
| 318 | push_ld(n); |
---|
| 319 | push_ln(n); |
---|
| 320 | } |
---|
| 321 | |
---|
| 322 | for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i) |
---|
[d484a32] | 323 | { |
---|
| 324 | push_ld(*i); |
---|
| 325 | push_ln(*i); |
---|
| 326 | } |
---|
| 327 | } |
---|
| 328 | |
---|
[3b02b04] | 329 | inline int LViterator::next() |
---|
| 330 | { |
---|
| 331 | if(wayup.empty()) |
---|
| 332 | { |
---|
| 333 | if(waydown.empty()) |
---|
[acbabee] | 334 | { |
---|
| 335 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1); |
---|
| 336 | return -1; // |
---|
| 337 | } |
---|
[3b02b04] | 338 | else |
---|
| 339 | { |
---|
| 340 | int k = waydown.top(); |
---|
| 341 | waydown.pop(); |
---|
| 342 | push_ld(k); |
---|
| 343 | push_ln(k); |
---|
| 344 | if(wayup.empty()) |
---|
[acbabee] | 345 | { |
---|
| 346 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1); |
---|
| 347 | return -1; // k NIE MA POPRZEDNIKÓW, NIE MO¯E TE¯ ZATEM MIEÆ LEWOSTRONNYCH PODRZÊDNIKÓW |
---|
| 348 | } |
---|
[3b02b04] | 349 | else |
---|
| 350 | { |
---|
| 351 | int i = wayup.top(); |
---|
| 352 | wayup.pop(); |
---|
| 353 | push_lh(i); |
---|
[acbabee] | 354 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i); |
---|
[3b02b04] | 355 | return i; |
---|
| 356 | } |
---|
| 357 | } |
---|
| 358 | |
---|
| 359 | } |
---|
| 360 | else |
---|
| 361 | { |
---|
| 362 | int i = wayup.top(); |
---|
| 363 | wayup.pop(); |
---|
| 364 | push_lh(i); |
---|
[acbabee] | 365 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i); |
---|
[3b02b04] | 366 | return i; |
---|
| 367 | }; |
---|
| 368 | } |
---|
| 369 | |
---|
| 370 | inline void LViterator::push_ld(int i) |
---|
| 371 | { |
---|
| 372 | vector<Arc>& arcs = sgraph[i].deps; |
---|
| 373 | for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) |
---|
| 374 | if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) |
---|
[acbabee] | 375 | { |
---|
| 376 | push(waydown,a->dst); |
---|
| 377 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LD waydown %d\n",snode,a->dst); |
---|
| 378 | } |
---|
[3b02b04] | 379 | } |
---|
| 380 | |
---|
| 381 | inline void LViterator::push_lh(int i) |
---|
| 382 | { |
---|
| 383 | vector<Arc>& arcs = sgraph[i].heads; |
---|
| 384 | for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) |
---|
| 385 | if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) |
---|
[acbabee] | 386 | { |
---|
| 387 | push(wayup,a->dst); |
---|
| 388 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LH wayup %d\n",snode,a->dst); |
---|
| 389 | } |
---|
[3b02b04] | 390 | } |
---|
| 391 | |
---|
| 392 | inline void LViterator::push_ln(int i) |
---|
| 393 | { |
---|
| 394 | vector<int>& mpredecessors = mgraph[sgraph[i].mnode].pred; |
---|
| 395 | for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph |
---|
| 396 | { |
---|
| 397 | vector<int>& spredecessors = mgraph[*mp].snodes; |
---|
| 398 | for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) |
---|
[854bece] | 399 | if(sgraph[*sp].prop.visible_as_neighbour || !strict) |
---|
[acbabee] | 400 | { |
---|
| 401 | push(wayup,*sp); |
---|
| 402 | if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LN wayup %d\n",snode, *sp); |
---|
| 403 | } |
---|
[3b02b04] | 404 | } |
---|
| 405 | } |
---|
| 406 | |
---|
| 407 | |
---|
| 408 | //---------------------------------------------------------------------------------------------------- |
---|
| 409 | //---------------------------------------------------------------------------------------------------- |
---|
| 410 | |
---|
| 411 | class LNiterator |
---|
| 412 | { |
---|
| 413 | public: |
---|
| 414 | LNiterator(SGraph& sg, int n); |
---|
| 415 | |
---|
| 416 | int next(); |
---|
| 417 | |
---|
| 418 | private: |
---|
[acbabee] | 419 | int snode; |
---|
[3b02b04] | 420 | SGraph& sgraph; |
---|
| 421 | MGraph& mgraph; |
---|
| 422 | stack<int> wayup; |
---|
| 423 | |
---|
| 424 | void push_ln(int i); |
---|
| 425 | }; |
---|
| 426 | |
---|
[acbabee] | 427 | inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n) |
---|
[3b02b04] | 428 | { |
---|
| 429 | push_ln(n); |
---|
| 430 | } |
---|
| 431 | |
---|
| 432 | inline int LNiterator::next() |
---|
| 433 | { |
---|
| 434 | if(wayup.empty()) |
---|
[acbabee] | 435 | { |
---|
| 436 | if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,-1); |
---|
| 437 | return -1; |
---|
| 438 | } |
---|
[3b02b04] | 439 | else |
---|
| 440 | { |
---|
| 441 | int i = wayup.top(); |
---|
| 442 | wayup.pop(); |
---|
[acbabee] | 443 | if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,i); |
---|
[3b02b04] | 444 | return i; |
---|
| 445 | }; |
---|
| 446 | } |
---|
| 447 | |
---|
| 448 | inline void LNiterator::push_ln(int i) |
---|
| 449 | { |
---|
| 450 | vector<int>& mpredecessors = mgraph[sgraph[i].mnode].pred; |
---|
| 451 | for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph |
---|
| 452 | { |
---|
| 453 | vector<int>& spredecessors = mgraph[*mp].snodes; |
---|
| 454 | for(vector<int>::iterator sp = spredecessors.begin(); sp != spredecessors.end(); ++sp ) |
---|
[acbabee] | 455 | { |
---|
[3b02b04] | 456 | wayup.push(*sp); |
---|
[acbabee] | 457 | if(debug) fprintf(stderr,"\t\tLNiterator(%d)\tPUSH %d\n",snode,-1); |
---|
| 458 | } |
---|
[3b02b04] | 459 | } |
---|
| 460 | } |
---|
| 461 | |
---|
| 462 | |
---|
| 463 | //---------------------------------------------------------------------------------------------------- |
---|
| 464 | //---------------------------------------------------------------------------------------------------- |
---|
| 465 | |
---|
| 466 | class LHiterator |
---|
| 467 | { |
---|
| 468 | public: |
---|
| 469 | LHiterator(SGraph& sg, int n); |
---|
| 470 | |
---|
| 471 | int next(); |
---|
| 472 | |
---|
| 473 | private: |
---|
[acbabee] | 474 | int snode; |
---|
[3b02b04] | 475 | SGraph& sgraph; |
---|
| 476 | MGraph& mgraph; |
---|
| 477 | stack<int> wayup; |
---|
| 478 | |
---|
| 479 | void push_lh(int i); |
---|
| 480 | }; |
---|
| 481 | |
---|
[acbabee] | 482 | inline LHiterator::LHiterator(SGraph& sg, int n) : snode(n), sgraph(sg), mgraph(sg.mgraph) |
---|
[3b02b04] | 483 | { |
---|
| 484 | push_lh(n); |
---|
| 485 | } |
---|
| 486 | |
---|
| 487 | inline int LHiterator::next() |
---|
| 488 | { |
---|
| 489 | if(wayup.empty()) |
---|
| 490 | return -1; |
---|
| 491 | else |
---|
| 492 | { |
---|
| 493 | int i = wayup.top(); |
---|
| 494 | wayup.pop(); |
---|
| 495 | push_lh(i); |
---|
| 496 | return i; |
---|
| 497 | }; |
---|
| 498 | } |
---|
| 499 | |
---|
| 500 | inline void LHiterator::push_lh(int i) |
---|
| 501 | { |
---|
| 502 | vector<Arc>& arcs = sgraph[i].heads; |
---|
| 503 | for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) |
---|
| 504 | if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[i].mnode].pos) |
---|
[acbabee] | 505 | { |
---|
| 506 | wayup.push(a->dst); |
---|
| 507 | if(debug) fprintf(stderr,"\t\tLHiterator(%d)\tPUSH %d\n",snode,-1); |
---|
| 508 | } |
---|
[3b02b04] | 509 | } |
---|
| 510 | |
---|
| 511 | //---------------------------------------------------------------------------------------------------- |
---|
| 512 | //---------------------------------------------------------------------------------------------------- |
---|
| 513 | |
---|
| 514 | class LDiterator |
---|
| 515 | { |
---|
| 516 | public: |
---|
| 517 | LDiterator(SGraph& sg, int n); |
---|
| 518 | |
---|
| 519 | int next(); |
---|
| 520 | |
---|
| 521 | private: |
---|
[acbabee] | 522 | int snode; |
---|
[3b02b04] | 523 | SGraph& sgraph; |
---|
| 524 | MGraph& mgraph; |
---|
| 525 | stack<int> waydown; |
---|
| 526 | |
---|
| 527 | void push_ld(int i); |
---|
| 528 | }; |
---|
| 529 | |
---|
[acbabee] | 530 | inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n) |
---|
[3b02b04] | 531 | { |
---|
| 532 | push_ld(n); |
---|
| 533 | } |
---|
| 534 | |
---|
| 535 | inline int LDiterator::next() |
---|
| 536 | { |
---|
| 537 | if(waydown.empty()) |
---|
| 538 | return -1; |
---|
| 539 | else |
---|
| 540 | { |
---|
| 541 | int k = waydown.top(); |
---|
| 542 | waydown.pop(); |
---|
| 543 | push_ld(k); |
---|
| 544 | return k; |
---|
| 545 | } |
---|
| 546 | } |
---|
| 547 | |
---|
| 548 | inline void LDiterator::push_ld(int i) |
---|
| 549 | { |
---|
| 550 | vector<Arc>& arcs = sgraph[i].deps; |
---|
| 551 | for(vector<Arc>::iterator a = arcs.begin(); a != arcs.end(); ++a) |
---|
[acbabee] | 552 | if(mgraph[sgraph[a->dst].mnode].pos < mgraph[sgraph[snode].mnode].pos) |
---|
| 553 | { |
---|
| 554 | waydown.push(a->dst); |
---|
| 555 | if(debug) fprintf(stderr,"\t\tLDiterator(%d)\tPUSH %d\n",snode,-1); |
---|
| 556 | } |
---|
[3b02b04] | 557 | } |
---|
| 558 | |
---|
[5f4d9c3] | 559 | #endif |
---|