/*
 * This is a directional graph that inherits from the boost::graph subgraph adjacent list template.
 * Properties are internal, though public accessors are provided here that can be used within any subgraph
 * derived from this class via create_subgraph to access the base graph properties.
 * All graph mutators which affect these properties, are implemented as methods.
 */
#include "dataGraph.h"
#include <assert.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <iterator>
#include <set>
#include "pseudoClasses.h"
#include "dfsVisitor.h"

using namespace std;
using boost::tie;

DataGraph::DataGraph(DataGraphT& dataGraph)
  : dataGraph_(dataGraph)
{}

DataGraph::DataGraph(DataGraphT& dataGraph,const DataVertices& dataVertices)
  : dataGraph_(dataGraph)
{
  for (DataVertices::const_iterator iter=dataVertices.begin();iter!=dataVertices.end();++iter)
    boost::add_vertex(*iter,dataGraph_);
}

DataGraph::VertexData::VertexData(DataGraphT& dataGraph)
  : dataGraph_(dataGraph)
{
}

DataGraph::EdgeData::EdgeData(DataGraphT& dataGraph)
  : dataGraph_(dataGraph)
{
}

Vertex_Datum&
DataGraph::VertexData::operator[] (const DataVertex& index)
{
  return boost::get(boost::get(vertex_Datum, dataGraph_.root()),dataGraph_.local_to_global(index));
}

Edge_Datum&
DataGraph::EdgeData::operator[] (const DataEdge& index)
{
  return boost::get(boost::get(edge_Datum, dataGraph_.root()),dataGraph_.local_to_global(index));
}

DataEdge
DataGraph::add_edge(LayoutEdge* pLayoutEdge,DataVertex source,DataVertex target)
{
  typedef pair<DataEdge,bool> Result;
  Result result = boost::add_edge(source,target,dataGraph_);
  assert(result.second == true);
  boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_global(result.first),Edge_Datum(pLayoutEdge));
  return result.first;
}

DataEdge
DataGraph::add_edge(PseudoEdge* pPseudoEdge,DataVertex source,DataVertex target)
{
  typedef pair<DataEdge,bool> Result;
  Result result = boost::add_edge(source,target,dataGraph_);
  assert(result.second == true);
  boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_global(result.first),Edge_Datum(pPseudoEdge));
  return result.first;
}

DataEdge
DataGraph::add_edge(const Edge_Datum& edgeDatum,DataVertex source,DataVertex target)
{
  typedef pair<DataEdge,bool> Result;
  Result result = boost::add_edge(source,target,dataGraph_);
  assert(result.second == true);
  boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_global(result.first),edgeDatum);
  return result.first;
}

DataVertex
DataGraph::add_vertex(LayoutVertex *pLayoutVertex)
{
  assert(pLayoutVertex > (LayoutVertex*)100);
  DataVertex vertex = boost::add_vertex(dataGraph_);
  boost::put(boost::get(vertex_Datum,dataGraph_.root()),dataGraph_.local_to_global(vertex),Vertex_Datum(pLayoutVertex));
  return vertex;
}

DataVertex
DataGraph::add_vertex(PseudoVertex *pPseudoVertex)
{
  assert(pPseudoVertex > (PseudoVertex*)100);
  DataVertex vertex = boost::add_vertex(dataGraph_);
  boost::put(boost::get(vertex_Datum,dataGraph_.root()),dataGraph_.local_to_global(vertex),Vertex_Datum(pPseudoVertex));
  return vertex;
}

void
DataGraph::remove_edge(DataEdge edge)
{
  boost::remove_edge(edge,dataGraph_);
}

void
DataGraph::remove_vertex(DataVertex vertex)
{
  boost::remove_vertex(vertex,dataGraph_);
}
struct ltSubgraph : public std::binary_function<DataEdge,DataEdge,bool>
{
  bool operator() (const DataEdge& s1, const DataEdge& s2) const
  {
        return s1.m_source < s2.m_source || (!(s2.m_source < s1.m_source) && s1.m_target < s2.m_target);
  }
};

typedef set<DataEdge,ltSubgraph> SetEdges;

struct insert : public unary_function<SetEdges::value_type,void>
{
  insert(const DataGraphT& subGraph,SetEdges& container) : subGraph_(subGraph),container_(container) {}
  void operator() (const SetEdges::value_type& x)
  {
    container_.insert(subGraph_.local_to_global(x));
  }
public:
  const DataGraphT& subGraph_;
  SetEdges& container_;
};

struct InternalEdgeCantidate : public unary_function<DataEdge,bool>
{
  enum Edge_Type { in, out};
  InternalEdgeCantidate(Edge_Type edge_type, DataGraphT& subGraph) : edge_type_(edge_type),subGraph_(subGraph) {}
  bool operator()(const DataEdge& x) const
  {
    return (edge_type_==in)  ? !subGraph_.parent().find_vertex(x.m_source).second : !subGraph_.parent().find_vertex(x.m_target).second;
  }
private:
  Edge_Type edge_type_;
  DataGraphT&  subGraph_;
};

/* Return the external Edges (using global descriptors) */
void
DataGraph::handleExternalEdges(DataGraph::Edges& in_external_edges,DataGraph::Edges& out_external_edges)
{
  DataVertexIterator vi,vi_end;
  {
    SetEdges local_edges,global_edges;
    for (tie(vi,vi_end)=boost::vertices(dataGraph_);vi!=vi_end;++vi) {
      boost::graph_traits<DataGraphT>::in_edge_iterator ei, ei_end;
          tie(ei,ei_end)=boost::in_edges(*vi,dataGraph_);
      for_each(ei,ei_end,insert(dataGraph_,local_edges));
      tie(ei,ei_end)=boost::in_edges(dataGraph_.local_to_global(*vi),dataGraph_.root());
      for_each(ei,ei_end,insert(dataGraph_.root(),global_edges));
    }
    set_difference(global_edges.begin(),global_edges.end(),local_edges.begin(),local_edges.end(),insert_iterator<DataGraph::Edges>(in_external_edges,in_external_edges.end()),ltSubgraph());
    in_external_edges.erase(remove_if(in_external_edges.begin(),in_external_edges.end(),InternalEdgeCantidate(InternalEdgeCantidate::in,dataGraph_)),in_external_edges.end());
  }
  {
    SetEdges local_edges,global_edges;
    for (tie(vi,vi_end)=boost::vertices(dataGraph_);vi!=vi_end;++vi) {
      boost::graph_traits<DataGraphT>::out_edge_iterator ei, ei_end;
          tie(ei,ei_end)=boost::out_edges(*vi,dataGraph_);
      for_each(ei,ei_end,insert(dataGraph_,local_edges));
      tie(ei,ei_end)=boost::out_edges(dataGraph_.local_to_global(*vi),dataGraph_.root());
      for_each(ei,ei_end,insert(dataGraph_.root(),global_edges));
    }
    set_difference(global_edges.begin(),global_edges.end(),local_edges.begin(),local_edges.end(),insert_iterator<DataGraph::Edges>(out_external_edges,out_external_edges.end()),ltSubgraph());
    out_external_edges.erase(remove_if(out_external_edges.begin(),out_external_edges.end(),InternalEdgeCantidate(InternalEdgeCantidate::out,dataGraph_)),out_external_edges.end());
  }
}

void
DataGraph::handleParallelEdges(void)
{
  typedef multiset<DataEdge,ltSubgraph> Edges;
  Edges edges;
  boost::graph_traits<DataGraphT>::edge_iterator ei,ei_end;
  for (tie(ei,ei_end)=boost::edges(dataGraph_);ei!=ei_end;++ei)
    edges.insert(*ei);
  for (Edges::const_iterator iter1 = edges.begin(); iter1 != edges.end(); advance(iter1,edges.count(*iter1))) 
    if (edges.count(*iter1)>1) {
      Edge_Datum edgeDatum(new ParallelEdge());
      for (Edges::const_iterator iter2=edges.lower_bound(*iter1);iter2!=edges.upper_bound(*iter1);++iter2) {
        Edge_Datum& existing_datum = getEdgeData()[*iter2];
        existing_datum.setDeleted(true);
        edgeDatum.setOmega(edgeDatum.getOmega()+existing_datum.getOmega());
      }
      add_edge(edgeDatum,iter1->m_source,iter1->m_target);
    }
}

class back_edge_recorder : public boost::default_dfs_visitor
{
public:
  back_edge_recorder(DataGraph& dataGraph)
    : dataGraph_(dataGraph) {}
  void back_edge(DataEdge e, const DataGraphT &)
  {
    dataGraph_.getEdgeData()[e].setReversed(true);
  }
private:
  DataGraph& dataGraph_;
};

void
DataGraph::markBackEdges(void)
{
  dfsVisitor(dataGraph_,back_edge_recorder(*this));
}

string
DataGraph::label(DataVertex v)
{
  const LayoutVertex *pInterface;
  if (!getVertexData()[v].isPseudo()) {
    pInterface = getVertexData()[v].getLayoutInterface();
    assert(pInterface  != NULL);
        return pInterface->getLabel();
  } else
    return string();
}