//-*-c++-*-
#ifndef Tulip_Sugiyama_H
#define Tulip_Sugiyama_H
#include <tulip/TulipPlugin.h>


class SelfLoops {
public:
  SelfLoops(node n1,node n2,edge ee1, edge ee2,edge ee3,edge old)
  {
    ghostNode1=n1;
    ghostNode2=n2;
    e1=ee1;
    e2=ee2;
    e3=ee3;
    oldEdge=old;
  }
  ~SelfLoops(){}
  node ghostNode1,ghostNode2;
  edge e1,e2,e3,oldEdge;  
};


class LessThanNode2 {
public:
  MetricProxy *metric;
  bool operator() (node n1,node n2){return (metric->getNodeValue(n1) < metric->getNodeValue(n2));}
};

struct LR
{
  int L;
  int R;
};
///
class Sugiyama:public Layout
{ 

public:
  Sugiyama(PropertyContext *);
  ~Sugiyama();
  
  bool run();

private:
  void makeAcyclic(SuperGraph*,std::set<edge> &,std::list<SelfLoops> &);
  node makeSimpleSource(SuperGraph* superGraph);
  void makeProperDag(SuperGraph* superGraph,std::list<node> &, STL_EXT_NS::hash_map<edge,edge> &);
  void buildGrid(SuperGraph*);
  bool assert_twoLayerCrossReduction(unsigned int freeLayer,bool sense);
  unsigned int degree(SuperGraph*,node,bool);
  void forceNoTwoLayerCross(SuperGraph*,unsigned int freeLayer,bool sense);
  void twoLayerCrossReduction(SuperGraph*,unsigned int freeLayer,bool sense);
  void crossReduction(SuperGraph*);
  void coordAssign(SuperGraph*,LayoutProxy *layout);
  node getOpposite(SuperGraph *superGraph,node n,bool sense);
  void initCross(SuperGraph*superGraph,node n, STL_EXT_NS::hash_map<node,bool> &visited,int &id);
  void minimize(SuperGraph* superGraph, STL_EXT_NS::hash_map<node,double> &xcoord,double maxW,bool bary);
  void forceAlignBends(SuperGraph* superGraph, STL_EXT_NS::hash_map<node,double> &xcoord,bool sense);
  std::list<SelfLoops> selfloops;
  std::set<edge> reversedEdges;
  std::vector< std::vector<node> > grid;
  STL_EXT_NS::hash_map <node, std::pair<node,node> > bends;
  LessThanNode2 lessNode;
  MetricProxy *metricProxy;
};

#endif