source: src/dgp/sgraph.hh

Last change on this file was 854bece, checked in by Tomasz Obrebski <obrebski@…>, 10 years ago

has_head prop added, visible_as_neighbour moved to prop

  • Property mode set to 100644
File size: 14.2 KB
Line 
1#ifndef _SGRAPH_HH
2#define _SGRAPH_HH
3
4#include <stdio.h>
5
6#include <list>
7#include <vector>
8#include <bitset>
9#include <stack>
10
11#include "const.hh"
12#include "mgraph.hh"
13#include "thesymbols.hh"
14#include "boubble.hh"
15#include "global.hh"
16
17using namespace std;
18
19//====================================================================================================
20// CLASS Arc
21//====================================================================================================
22struct Arc
23{
24  int dst;
25  Role role;
26  int headanc;
27  int depanc;
28 
29  Arc(int d, Role r, int ha, int da) : dst(d), role(r), headanc(ha), depanc(da) {};
30};
31
32//====================================================================================================
33// CLASS NodeProp
34//====================================================================================================
35
36struct NodeProp
37{
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);
47
48  void copy(const NodeProp& p);
49  void clear();
50
51  RoleSet required;
52  RoleSet forbidden;
53  RoleSet attached;
54
55  bool init_attached;
56  bool fin_attached;
57  bool visible_as_neighbour;
58  bool has_head;
59 
60  FlagSet flags;
61
62  list<Boubble*>   boubbles;
63};
64
65//----------------------------------------------------------------------------------------------------
66
67inline
68bool 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;
76  if(visible_as_neighbour != p.visible_as_neighbour) return false;
77  if(has_head != p.has_head) return false;
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())
84    return false;
85
86  return true;
87}
88
89//----------------------------------------------------------------------------------------------------
90
91inline
92void 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
101inline
102void NodeProp::merge_boubbles(list<Boubble*> new_boubbles)
103{
104  boubbles.merge(new_boubbles);
105}
106
107//----------------------------------------------------------------------------------------------------
108
109inline
110void NodeProp::copy(const NodeProp& p)
111{
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;
120  for(list<Boubble*>::const_iterator b = p.boubbles.begin(); b!=p.boubbles.end(); b++)
121    boubbles.push_back(new Boubble(**b));
122}
123
124inline NodeProp::~NodeProp() { clear_boubbles(); }
125inline NodeProp::NodeProp() { clear(); }
126inline NodeProp::NodeProp(const NodeProp& p) { copy(p); }
127inline NodeProp& NodeProp::operator=(const NodeProp& p) { clear(); copy(p); return *this; }
128inline void NodeProp::clear()
129{
130  required.reset();
131  forbidden.reset();
132  attached.reset();
133  init_attached=false;
134  fin_attached=false;
135  visible_as_neighbour=true;
136  has_head=false;
137  clear_boubbles();
138}
139
140//====================================================================================================
141// CLASS Edge
142//====================================================================================================
143
144class Edge
145{
146public:
147  Edge() : _self(false) { }
148  Edge(const Edge& e, int map_self) { assign(e,map_self); }
149
150  bool self() const { return _self; }
151  list<int>& others() { return _others; }
152
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); }
156
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 
160private:
161  bool _self;
162  list<int> _others;
163};
164
165//====================================================================================================
166// CLASS SNode
167//====================================================================================================
168
169struct SNode
170{
171  SNode() { prop.clear(); }
172
173  int mnode;
174
175  NodeProp prop;
176  Edge edge;
177
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
186  void clear() { prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); }
187  bool saturated() { return prop.required.none(); }
188 
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; }
197};
198
199//====================================================================================================
200// SGraph CLASS
201//====================================================================================================
202
203class SGraph
204{
205public:
206
207  enum Output { HEADS=1, DEPS=2, SETS=4, CONSTRAINTS=8, BOUBBLES=16 };
208
209  SGraph(MGraph& mg) : mgraph(mg)               { clear(); }
210
211  SNode& operator[](const int i)                { return nodes[i]; }
212
213  void clear()                                  { nodes.clear(); }
214  int  add_base_snode(int mnodeind);
215  int  clone(int ancind, NodeProp newprop, Edge edge);
216  void update_left(int headind, int depind);
217  void update_right(int headind, int depind);
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; }
221
222  Cat  cat(int i) const { return mgraph[nodes[i].mnode].cat; }   
223  char* form(int i) const { return mgraph[nodes[i].mnode].form; }
224
225  int print_node(FILE* f, int n, unsigned int info);
226  int print_node_debug(FILE* f, const char* pref, int n, int anc);
227
228  void print_arc(FILE* f, const char* msg, int left, int right, Role role, int dir); // 0 - left, 1 - right
229
230  //private:
231
232  int size()              {return nodes.size(); }
233
234  friend class LViterator;
235  friend class LHiterator;
236  friend class LDiterator;
237  friend class LNiterator;
238
239private:
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);
250};
251
252//----------------------------------------------------------------------------------------------------
253//----------------------------------------------------------------------------------------------------
254
255class XXiterator
256{
257protected:
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
277class LViterator : public XXiterator
278{
279public:
280  LViterator(SGraph& sg, int n, bool s);
281  int next();
282  void update_edge(SGraph& sg, int e);
283
284private:
285  int snode;
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);
295
296};
297
298inline LViterator::LViterator(SGraph& sg, int n, bool s=true) : snode(n), sgraph(sg), mgraph(sg.mgraph), strict(s)
299{
300  if(sg[n].edge.self())
301    {
302      push_ld(n);
303      push_ln(n);
304    }
305
306  for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i)
307    {
308      push_ld(*i);
309      push_ln(*i);
310     
311    }
312}
313
314inline void LViterator::update_edge(SGraph& sg, int n)
315{
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)
323    {
324      push_ld(*i);
325      push_ln(*i);
326    }
327}
328
329inline int LViterator::next()
330{
331  if(wayup.empty())
332    {
333      if(waydown.empty())
334        {
335          if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1);
336          return -1; //
337        }
338      else
339        {
340          int k = waydown.top();
341          waydown.pop();
342          push_ld(k);
343          push_ln(k);
344          if(wayup.empty())
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            }
349          else
350            {
351              int i = wayup.top();
352              wayup.pop();
353              push_lh(i);
354              if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i);
355              return i;
356            }
357        }
358     
359    }
360  else
361    {
362      int i = wayup.top();
363      wayup.pop();
364      push_lh(i);
365      if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i);
366      return i;
367    };
368}
369
370inline 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)
375      {
376        push(waydown,a->dst);
377        if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LD waydown %d\n",snode,a->dst);
378      }
379}
380
381inline 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)
386      {
387        push(wayup,a->dst);
388        if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LH wayup %d\n",snode,a->dst);
389      }
390}
391
392inline 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 )
399        if(sgraph[*sp].prop.visible_as_neighbour || !strict)
400          {
401            push(wayup,*sp);
402            if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LN wayup %d\n",snode, *sp);
403          }
404    }
405}
406
407
408//----------------------------------------------------------------------------------------------------
409//----------------------------------------------------------------------------------------------------
410
411class LNiterator
412{
413public:
414  LNiterator(SGraph& sg, int n);
415
416  int next();
417
418private:
419  int snode;
420  SGraph& sgraph;
421  MGraph& mgraph;
422  stack<int> wayup;
423
424  void push_ln(int i);
425};
426
427inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n)
428{
429  push_ln(n);
430}
431
432inline int LNiterator::next()
433{
434  if(wayup.empty())
435    {
436      if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,-1);
437      return -1;
438    }
439  else
440    {
441      int i = wayup.top();
442      wayup.pop();
443      if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,i);
444      return i;
445    };
446}
447
448inline 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 )
455        {
456          wayup.push(*sp);
457          if(debug) fprintf(stderr,"\t\tLNiterator(%d)\tPUSH %d\n",snode,-1);
458        }
459    }
460}
461
462
463//----------------------------------------------------------------------------------------------------
464//----------------------------------------------------------------------------------------------------
465
466class LHiterator
467{
468public:
469  LHiterator(SGraph& sg, int n);
470
471  int next();
472
473private:
474  int snode;
475  SGraph& sgraph;
476  MGraph& mgraph;
477  stack<int> wayup;
478
479  void push_lh(int i);
480};
481
482inline LHiterator::LHiterator(SGraph& sg, int n) : snode(n), sgraph(sg), mgraph(sg.mgraph)
483{
484  push_lh(n);
485}
486
487inline 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
500inline 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)
505      {
506        wayup.push(a->dst);
507        if(debug) fprintf(stderr,"\t\tLHiterator(%d)\tPUSH %d\n",snode,-1);
508      }
509}
510
511//----------------------------------------------------------------------------------------------------
512//----------------------------------------------------------------------------------------------------
513
514class LDiterator
515{
516public:
517  LDiterator(SGraph& sg, int n);
518
519  int next();
520
521private:
522  int snode;
523  SGraph& sgraph;
524  MGraph& mgraph;
525  stack<int> waydown;
526
527  void push_ld(int i);
528};
529
530inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n)
531{
532  push_ld(n);
533}
534
535inline 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
548inline 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)
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      }
557}
558
559#endif
Note: See TracBrowser for help on using the repository browser.