source: src/dgp/sgraph.hh @ b97a556

Last change on this file since b97a556 was 3b02b04, checked in by Tomasz Obrebski <to@…>, 12 years ago

prawie ca�kiem nowe dgc, du�e zmiany w dgp, pomniejsze poprawki

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