source: src/dgp/sgraph.hh @ 18e1952

#ifndef _SGRAPH_HH
#define _SGRAPH_HH

#include <stdio.h>

#include <list>
#include <vector>
#include <bitset>
#include <stack>

#include "const.hh"
#include "mgraph.hh"
#include "thesymbols.hh"
#include "boubble.hh"


using namespace std;

//====================================================================================================
// CLASS Arc
//====================================================================================================
struct Arc
{
  int dst;
  Role role;
  int headanc;
  int depanc;
 
  Arc(int d, Role r, int ha, int da) : dst(d), role(r), headanc(ha), depanc(da) {};
};

//====================================================================================================
// CLASS NodeProp
//====================================================================================================

struct NodeProp
{
  NodeProp();
  NodeProp(const NodeProp& p);
  ~NodeProp();

  bool operator==(const NodeProp& p);
  NodeProp& operator=(const NodeProp& p);

  void clear_boubbles();
  void merge_boubbles(list<Boubble*> new_boubbles);

  void copy(const NodeProp& p);
  void clear();

  RoleSet required;
  RoleSet forbidden;
  RoleSet attached;

  bool init_attached;
  bool fin_attached;
  
  FlagSet flags;

  list<Boubble*>   boubbles;
};

//----------------------------------------------------------------------------------------------------

inline
bool NodeProp::operator==(const NodeProp& p)
{
  if(required != p.required) return false;
  if(forbidden != p.forbidden) return false;
  if(attached != p.attached) return false;
  if(flags != p.flags) return false;
  if(init_attached != p.init_attached) return false;
  if(fin_attached != p.fin_attached) return false;

  list<Boubble*>::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;
}

//----------------------------------------------------------------------------------------------------

inline
void NodeProp::clear_boubbles()
{
  for(list<Boubble*>::iterator b = boubbles.begin(); b!=boubbles.end(); b++)
    delete *b;
  boubbles.clear();
}

//----------------------------------------------------------------------------------------------------

inline
void NodeProp::merge_boubbles(list<Boubble*> new_boubbles)
{
  boubbles.merge(new_boubbles);
}

//----------------------------------------------------------------------------------------------------

inline
void NodeProp::copy(const NodeProp& p)
{
  required=p.required;
  forbidden=p.forbidden;
  attached=p.attached;
  flags=p.flags;
  init_attached=p.init_attached;
  fin_attached=p.fin_attached;
  for(list<Boubble*>::const_iterator b = p.boubbles.begin(); b!=p.boubbles.end(); b++)
    boubbles.push_back(new Boubble(**b));
}

//----------------------------------------------------------------------------------------------------

inline
NodeProp::~NodeProp()
{
  clear_boubbles();
}
//----------------------------------------------------------------------------------------------------

inline
NodeProp::NodeProp()
{
  clear();
}

//----------------------------------------------------------------------------------------------------

inline
NodeProp::NodeProp(const NodeProp& p)
{
  copy(p);
}

//----------------------------------------------------------------------------------------------------

inline
NodeProp& NodeProp::operator=(const NodeProp& p)
{
  clear();
  copy(p);
  return *this;
}

//----------------------------------------------------------------------------------------------------

inline
void NodeProp::clear()
{
  required.reset();
  forbidden.reset();
  attached.reset();
  init_attached=false;
  fin_attached=false;
  clear_boubbles();
}

//====================================================================================================
// CLASS SNode
//====================================================================================================

struct SNode
{
  
  SNode() { visible_as_neighbour = true; }

  int mnode;

  NodeProp prop;

  vector<int> edge;
  bool        edge_contains_self;
  bool visible_as_neighbour;

  bitset<MAXNODES> LV;
  bitset<MAXNODES> LH;
  bitset<MAXNODES> LD;
  bool in_LH;

  vector<Arc> heads;
  vector<Arc> deps;

  void clear();
  bool saturated();
};

//----------------------------------------------------------------------------------------------------
inline
void SNode::clear()
{ prop.clear(), LV.reset(), LD.reset(), LH.reset(), heads.clear(), deps.clear(); }
//----------------------------------------------------------------------------------------------------
inline
bool SNode::saturated()
{ return prop.required.none(); }

//====================================================================================================
// SGraph CLASS
//====================================================================================================

class SGraph
{
public:

  enum Output { HEADS=1, DEPS=2, SETS=4, CONSTRAINTS=8, BOUBBLES=16 };

  SGraph(MGraph& mg) : mgraph(mg)               { clear(); }

  SNode& operator[](const int i)                { return nodes[i]; }

  void clear()                                  { nodes.clear(); }
  int  add_base_snode(int mnodeind);
  int  clone(int ancind, NodeProp newprop);
  void update_left(int headind, int depind);
  void update_right(int headind, int depind);
  bool visible(int left, int right);
  bool saturated(int node);

  Cat  cat(int i) const { return mgraph[nodes[i].mnode].cat; }    
  char* form(int i) const { return mgraph[nodes[i].mnode].form; }

  int print_node(FILE* f, int n, unsigned int info);
  int print_node_debug(FILE* f, const char* pref, int n, int anc);

  void print_arc(FILE* f, int left, int right, Role role, int dir); // 0 - left, 1 - right

  //private:

  int size()              {return nodes.size(); }

  friend class LViterator;
  friend class LHiterator;
  friend class LDiterator;
  friend class LNiterator;

private:

  MGraph& mgraph;
  
  vector<SNode> nodes;

  int lastnodeind()       { return nodes.size()-1; }
  SNode& makenewnode()    { nodes.push_back(SNode()); nodes.back().clear(); return nodes.back(); }

  int sprint_node(char* buf, int n, int anc, unsigned int info);
  int sprint_node_debug(char* buf, const char* pref, int n, int anc);
};

//----------------------------------------------------------------------------------------------------

inline bool SGraph::visible(int left, int right)
{
  return nodes[right].LV[left];
}

//----------------------------------------------------------------------------------------------------

inline bool SGraph::saturated(int node)
{
  return nodes[node].saturated();
}

//----------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------

class XXiterator
{
protected:

  bool checked(int i) { return _checked[i]; }
  void check(int i)   { _checked.set(i); }

  void push(stack<int>& s, int i)
  {
    if(!checked(i))
      {
        s.push(i);
        check(i);
      }
  }

  bitset<MAXNODES> _checked;
};

//----------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------

class LViterator : public XXiterator
{
public:
  LViterator(SGraph& sg, int n, bool s);
  int next();

private:

  SGraph& sgraph;
  MGraph& mgraph;
  stack<int> waydown;
  stack<int> 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<int>::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<Arc>& arcs = sgraph[i].deps;
  for(vector<Arc>::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<Arc>& arcs = sgraph[i].heads;
  for(vector<Arc>::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<int>& mpredecessors = mgraph[sgraph[i].mnode].pred;
  for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph
    {
      vector<int>& spredecessors = mgraph[*mp].snodes;
      for(vector<int>::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<int> 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<int>& mpredecessors = mgraph[sgraph[i].mnode].pred;
  for(vector<int>::iterator mp = mpredecessors.begin(); mp != mpredecessors.end(); ++mp) // poprzedniki w mgraph
    {
      vector<int>& spredecessors = mgraph[*mp].snodes;
      for(vector<int>::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<int> 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<Arc>& arcs = sgraph[i].heads;
  for(vector<Arc>::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<int> 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<Arc>& arcs = sgraph[i].deps;
  for(vector<Arc>::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