source: src/dgp/sgraph.hh @ acbabee

#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"
#include "global.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 Edge
//====================================================================================================

class Edge
{
public:
  Edge() : _self(false) { }
  Edge(const Edge& e, int map_self) { assign(e,map_self); }

  bool self() const { return _self; }
  list<int>& others() { return _others; }

  void insert_self(bool b=true) { _self=b; }
  void insert(int n) { list<int>::iterator i=others().begin(); while(i!=others().end() && *i<n) ++i; others().insert(i,n);}
  void insert(list<int> l) { for(list<int>::const_iterator i=l.begin(); i!=l.end(); i++) insert(*i); }

  void assign(const Edge& e, int map_self=-1) { _others = e._others; if(e.self()) { _self = false; insert(map_self); } }
  const bool operator==(const Edge& e) const { return _self == e._self && _others == e._others; }
  
private:
  bool _self;
  list<int> _others;
};

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

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

  int mnode;

  NodeProp prop;

  Edge edge;
  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();

  // void edge_clear()               { edge.clear(); edge_contains_self=false;}
  // void edge_set(int i)            { edge.clear(); edge_contains_self=false; edge.push_back(i); }
  // void edge_set(vector<int>& v)   { edge.assign(v.begin(),v.end()); edge_contains_self=false; }
  // void edge_set_self(bool b=true) { edge.clear(); edge_contains_self=b; }
  // void edge_add(int i)            { edge.push_back(i); }
  // void edge_add(vector<int>& v)   { edge.insert(edge.end(),v.begin(),v.end()); }
  // void edge_add_self(bool b=true) { edge_contains_self=b; }
};

//----------------------------------------------------------------------------------------------------
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, Edge edge);
  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, const char* msg, 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();
  void update_edge(SGraph& sg, int e);

private:
  int snode;
  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) : snode(n), sgraph(sg), mgraph(sg.mgraph), strict(s)
{
  if(sg[n].edge.self())
    {
      push_ld(n);
      push_ln(n);
    }

  for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i)
    {
      push_ld(*i);
      push_ln(*i);
      
    }
}

inline void LViterator::update_edge(SGraph& sg, int n)
{
  if(sg[n].edge.self()) 
    {
      push_ld(n);
      push_ln(n);
    }

  for(list<int>::iterator i=sg[n].edge.others().begin(); i!=sg[n].edge.others().end(); ++i)
    {
      push_ld(*i);
      push_ln(*i);
    }
}

inline int LViterator::next()
{
  if(wayup.empty())
    {
      if(waydown.empty())
        {
          if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1);
          return -1; // 
        }
      else
        {
          int k = waydown.top();
          waydown.pop();
          push_ld(k);
          push_ln(k);
          if(wayup.empty())
            {
              if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,-1);
              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);
              if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,i);
              return i;
            }
        }
      
    }
  else
    {
      int i = wayup.top();
      wayup.pop();
      push_lh(i);
      if(debug) fprintf(stderr,"\t\tLViterator(%d)\treturn %d\n",snode,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);
        if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LD waydown %d\n",snode,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);
        if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LH wayup %d\n",snode,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);
            if(debug) fprintf(stderr,"\t\tLViterator(%d)\tPUSH_LN wayup %d\n",snode, *sp);
          }
    }
}


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

class LNiterator
{
public:
  LNiterator(SGraph& sg, int n);

  int next();

private:
  int snode;
  SGraph& sgraph;
  MGraph& mgraph;
  stack<int> wayup;

  void push_ln(int i);
};

inline LNiterator::LNiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(n)
{
  push_ln(n);
}

inline int LNiterator::next()
{
  if(wayup.empty())
    {
      if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,-1);
      return -1;
    }
  else
    {
      int i = wayup.top();
      wayup.pop();
      if(debug) fprintf(stderr,"\t\tLNiterator(%d)\treturn %d\n",snode,i);
      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);
          if(debug) fprintf(stderr,"\t\tLNiterator(%d)\tPUSH %d\n",snode,-1);
        }
    }
}


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

class LHiterator
{
public:
  LHiterator(SGraph& sg, int n);

  int next();

private:
  int snode;
  SGraph& sgraph;
  MGraph& mgraph;
  stack<int> wayup;

  void push_lh(int i);
};

inline LHiterator::LHiterator(SGraph& sg, int n) : snode(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);
        if(debug) fprintf(stderr,"\t\tLHiterator(%d)\tPUSH %d\n",snode,-1);
      }
}

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

class LDiterator
{
public:
  LDiterator(SGraph& sg, int n);

  int next();

private:
  int snode;
  SGraph& sgraph;
  MGraph& mgraph;
  stack<int> waydown;

  void push_ld(int i);
};

inline LDiterator::LDiterator(SGraph& sg, int n) : sgraph(sg), mgraph(sg.mgraph), snode(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[snode].mnode].pos)
      {
        waydown.push(a->dst);
        if(debug) fprintf(stderr,"\t\tLDiterator(%d)\tPUSH %d\n",snode,-1);
      }
}

#endif