/*
 *  Main authors:
 *     Grégoire Dooms <dooms@info.ucl.ac.be>
 *
 *  Copyright:
 *     Grégoire Dooms (Université catholique de Louvain), 2005
 *
 *  Last modified:
 *     $Date: 2006-01-26 14:18:00 +0100 (Thu, 26 Jan 2006) $
 *     $Revision: 318 $
 *
 *  This file is part of CP(Graph)
 *
 *  See the file "contribs/graph/LICENSE" for information on usage and
 *  redistribution of this file, and for a
 *     DISCLAIMER OF ALL WARRANTIES.
 *
 */


#include <stdio.h>
#include <vector>
#include <list>
#include <iostream>
#include <fstream>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/visitors.hpp>

#include "graph.hh"

#include "prop.icc"
//using namespace boost;
//using namespace std;

namespace Gecode { namespace Graph {

NodeArcSetsGraphView::NodeArcSetsGraphView(void){
}
NodeArcSetsGraphView::NodeArcSetsGraphView(const NodeArcSetsGraphView& x): nodes(x.nodes), arcs(x.arcs), an(x.an){
}

NodeArcSetsGraphView::NodeArcSetsGraphView(Space *home, ArcNode *arcnode, SetVar nodes, SetVar arcs): nodes(nodes), arcs(arcs), an(arcnode){
    arcImpliesNodes(home);
}
NodeArcSetsGraphView::NodeArcSetsGraphView(Space *home, ArcNode *arcnode, int numNodes): nodes(home,IntSet::empty,0,numNodes-1), arcs(home, IntSet::empty, 0, arcnode->max_arc()), an(arcnode) {
    arcImpliesNodes(home);
}
#ifndef  TRACE 
#define TRACE 
#endif
NodeArcSetsGraphView::NodeArcSetsGraphView(Space *home, ArcNode *arcnode, const pair<vector<int>,vector<pair<int,int> > >& graph):an(arcnode){ 
//FIXME node values ignored, still have to translate nodes to [0, numNodes-1]

        const vector<pair<int,int> >& arcsV =  graph.second;
        
        int numarcs = arcsV.size();
        std::vector<int> arcids(numarcs);
        std::vector<std::pair<int,int> >::const_iterator it = arcsV.begin();
        int numNodes = graph.first.size();
        for  (int i=0;  it != arcsV.end(); ++it, ++i){
                assert(it->first < numNodes);
                assert(it->second < numNodes);
                arcids[i] = an->id(it->first,it->second); 
        }
        

        // Create the nodes variable
        SetVar nodesVar(home, IntSet::empty, 0, numNodes-1);
        // update the nodes var
        nodes = nodesVar;

        // create the arcs variable
        sort(arcids.begin(),arcids.end()); 
        IntSet a(&arcids[0], numarcs);
        arcs = SetVar(home, IntSet::empty, a);
        arcImpliesNodes(home);
}



void NodeArcSetsGraphView::distrib(Space * home){ //FIXME
        /*
        SetVarArgs nargs(1);
          nargs[0]=nodes;
          branch(home,nargs,SETBVAR_NONE, SETBVAL_MIN);
          */
          

        SetVarArgs args(2);
        args[0] = nodes;
        args[1] = arcs;
        branch(home,args,SETBVAR_NONE, SETBVAL_MIN);
}

void NodeArcSetsGraphView::arcImpliesNodes(Space * home){ 
        ArcImpliesNodes<NodeArcSetsGraphView>::post(home,*this);
}
void NodeArcSetsGraphView::instantiateUB(Space * home){ 
        Set::SetView a(arcs);
	GECODE_ME_FAIL(home,a.cardMin(home,a.cardMax()));
        assert(arcs.assigned());
        Set::SetView n(nodes);
	GECODE_ME_FAIL(home,n.cardMin(home,n.cardMax()));
        assert(nodes.assigned());
}



/** Stuff for propagators */

/** Returns the PropCond for the nodes and the arcs according to the graph propCond*/
std::pair<PropCond,PropCond> NodeArcSetsGraphView::pc_g_to_set(PropCond pc){
    return make_pair(Set::PC_SET_ANY,Set::PC_SET_ANY);
}
/** subscribes all implem variables with the propagator */
void NodeArcSetsGraphView::subscribe(Space* home, Propagator* p, PropCond pc){
        PropCond npc,apc;
       boost::tie(npc,apc) = pc_g_to_set(pc);
        Set::SetView nodesV(nodes);
        nodesV.subscribe(home,p,npc);
        Set::SetView arcsV(arcs);
        arcsV.subscribe(home,p,apc);
}
void NodeArcSetsGraphView::cancel(Propagator* p, PropCond pc){
        PropCond npc,apc;
       boost::tie(npc,apc) = pc_g_to_set(pc);
        Set::SetView arcsV(arcs);
        arcsV.cancel(p,apc);
        // arcsV.cancel(p,apc); // not possible because building a ViewArray from a VarArgArray needs the home
        Set::SetView nodesV(nodes);
        nodesV.cancel(p,npc);
}




void NodeArcSetsGraphView::update(Space* home, bool share, NodeArcSetsGraphView& x){
        arcs.update(home, share, x.arcs);
        nodes.update(home, share, x.nodes);
        an = x.an;
        
}
/* basic tells for propagators */

forceinline ModEvent NodeArcSetsGraphView::_arcIn(Space* home, int a, int b){
#ifdef CPGCHECKTELLS
        bool in = && ! arcIsInLB(a,b);
        if (! arcIsInUB(a,b)){ 
                TRACE(cout << "returning arcIn" << a << " "<< b<< " ME_GRAPH_FAILED"<< endl);
                return Set::ME_GRAPH_FAILED;
        }   //XXX

        if (arcIsInLB(a,b)){ 
                TRACE(cout << "returning arcIn" << a << " "<< b<< " ME_GRAPH_NONE"<< endl);
                return Set::ME_GRAPH_NONE;
        }   //XXX
#endif
        Set::SetView av(arcs);
        return av.include(home,an->id(a,b));
}


forceinline ModEvent NodeArcSetsGraphView::_arcOut(Space* home, int a, int b){
#ifdef CPGCHECKTELLS
        if (arcIsInLB(a,b)){ 
                TRACE(cout << "returning arcOut" << a << " "<< b<< " ME_GRAPH_FAILED"<< endl);
                return Set::ME_GRAPH_FAILED;
        }   //XXX
        if (!arcIsInUB(a,b)){ 
                TRACE(cout << "returning arcOut" << a << " "<< b<< " ME_GRAPH_NONE"<< endl);
                return Set::ME_GRAPH_NONE;
        }   //XXX
#endif

        Set::SetView av(arcs);
        return av.exclude(home,an->id(a,b));
}
forceinline ModEvent NodeArcSetsGraphView::_nodeIn(Space* home, int a){
#ifdef CPGCHECKTELLS
        if (!nodeIsInUB(a)){ 
                TRACE(cout << "returning nodeIn" << a <<  " ME_GRAPH_FAILED"<< endl);
                return Set::ME_GRAPH_FAILED;
        }   //XXX
        if (nodeIsInLB(a)){ 
                TRACE(cout << "returning nodeIn" << a <<  " ME_GRAPH_NONE"<< endl);
                return Set::ME_GRAPH_NONE;
        }   //XXX
#endif
        Set::SetView v(nodes);
        return v.include(home,a);
}

forceinline ModEvent NodeArcSetsGraphView::_nodeOut(Space* home, int a){
#ifdef CPGCHECKTELLS
        if (nodeIsInLB(a)){ 
                TRACE(cout << "returning nodeOut" << a <<  " ME_GRAPH_FAILED"<< endl);
                return Set::ME_GRAPH_FAILED;
        }   //XXX
        if (!nodeIsInUB(a)){ 
                TRACE(cout << "returning nodeOut" << a <<  " ME_GRAPH_NONE"<< endl);
                return Set::ME_GRAPH_NONE;
        }   //XXX
#endif
        Set::SetView v(nodes);
        return v.exclude(home,a);
}

template <class It>
forceinline ModEvent NodeArcSetsGraphView::_nodesOut(Space* home, It &i){
        Iter::Values::ToRanges<It> r(i);
        Set::SetView v(nodes);
        return v.excludeI(home,i);
}
template <class It>
forceinline ModEvent NodeArcSetsGraphView::_nodesIn(Space* home, It &i){
        Iter::Values::ToRanges<It> r(i);
        Set::SetView v(nodes);
        return v.includeI(home,r);
}
template <class It>
forceinline ModEvent NodeArcSetsGraphView::_arcsIn(Space* home, It &i){
        PairToArcIdGecodeIterator<It> i2(an,i);
        Iter::Values::ToRanges<PairToArcIdGecodeIterator<It> > i3(i2);
        Set::SetView v(arcs);
        return v.includeI(home,i3);
}
template <class It>
forceinline ModEvent NodeArcSetsGraphView::_arcsOut(Space* home, It &i){
        PairToArcIdGecodeIterator<It> i2(an,i);
        Iter::Values::ToRanges<PairToArcIdGecodeIterator<It> > i3(i2);
        Set::SetView v(arcs);
        return v.excludeI(home,i3);
}
/// \brief Arc iterator for the NodeArcSetsGraphView
template <class It>
class NodeArcSetsGraphView::_int_pair_gecode_iterator_2vars {
        const NodeArcSetsGraphView *gp;
        int N;
        It arcRanges; //no matching function for call to 'Gecode::Iter::Ranges::ToValues<Gecode::SetVarGlbRanges>::ToValues(Gecode::SetVarGlbRanges)
        Iter::Ranges::ToValues<It> arcIter;
        public:
        _int_pair_gecode_iterator_2vars(const NodeArcSetsGraphView * g): gp(g),N(0),arcRanges(g->arcs),arcIter(arcRanges) {}
        bool operator() (void) { // has next
                return  arcIter();
        }
        pair<int,int>  val (void){
                return gp->an->end_nodes(arcIter.val());
        }

        void operator++ (void){ // go to next
                ++arcIter;
        }
};


forceinline
NodeArcSetsGraphView::GlbArcIterator NodeArcSetsGraphView::iter_arcs_LB() const {
        NodeArcSetsGraphView::GlbArcIterator  it(this);
        return it; 
}

forceinline
NodeArcSetsGraphView::LubArcIterator NodeArcSetsGraphView::iter_arcs_UB() const {
        NodeArcSetsGraphView::LubArcIterator  it(this);
        return it; 
}

forceinline
NodeArcSetsGraphView::GlbNodeRangesIterator NodeArcSetsGraphView::iter_nodes_ranges_LB(){
        SetVarGlbRanges l(nodes);
        return l;
}

forceinline
NodeArcSetsGraphView::LubNodeRangesIterator NodeArcSetsGraphView::iter_nodes_ranges_UB(){
        SetVarLubRanges u(nodes);
        return u;
}

forceinline
NodeArcSetsGraphView::GlbNodeIterator NodeArcSetsGraphView::iter_nodes_LB(){
        SetVarGlbRanges l(nodes);
        Iter::Ranges::ToValues<SetVarGlbRanges> lv(l) ;
        return lv;
}

forceinline
NodeArcSetsGraphView::LubNodeIterator NodeArcSetsGraphView::iter_nodes_UB(){
        SetVarLubRanges u(nodes);
        Iter::Ranges::ToValues<SetVarLubRanges> uv(u);
        return uv;
}

/* Reflexion */
int NodeArcSetsGraphView::lubOrder(){
        return nodes.lubSize();
}
int NodeArcSetsGraphView::glbOrder(){
        return nodes.glbSize();
}
int NodeArcSetsGraphView::lubSize(){
        return arcs.lubSize();
}
int NodeArcSetsGraphView::glbSize(){
        return arcs.glbSize();
}
int NodeArcSetsGraphView::maxNodeId(){
        return nodes.lubMax();
}
bool NodeArcSetsGraphView::nodeIsInUB(int a){
        return !nodes.notContains(a);
}
bool NodeArcSetsGraphView::nodeIsInLB(int a){
        return nodes.contains(a);
}
bool NodeArcSetsGraphView::arcIsInUB(int a, int b){
        return ! arcs.notContains(an->id(a,b));

}
bool NodeArcSetsGraphView::arcIsInLB(int a, int b){
        return  arcs.contains(an->id(a,b));
}

void NodeArcSetsGraphView::inNeighboursUB(int a, vector<int> &nei){
        SetVarLubRanges nodesU(nodes);
        Iter::Ranges::ToValues<SetVarLubRanges> nodesIter(nodesU);
        nei.clear();
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInUB(i,a))
                        nei.push_back(i);
        }
}


void NodeArcSetsGraphView::inNeighboursLB(int a, vector<int> &nei){
        SetVarGlbRanges nodesL(nodes);
        Iter::Ranges::ToValues<SetVarGlbRanges> nodesIter(nodesL);
        nei.clear();
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInUB(i,a))
                        nei.push_back(i);
        }
}

void NodeArcSetsGraphView::outNeighboursUB(int a, vector<int> &nei){
        SetVarLubRanges nodesU(nodes);
        Iter::Ranges::ToValues<SetVarLubRanges> nodesIter(nodesU);
        nei.clear();
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInUB(a,i))
                        nei.push_back(i);
        }
}
void NodeArcSetsGraphView::outNeighboursLB(int a, vector<int> &nei){
        SetVarGlbRanges nodesL(nodes);
        Iter::Ranges::ToValues<SetVarGlbRanges> nodesIter(nodesL);
        nei.clear();
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInUB(a,i))
                        nei.push_back(i);
        }
}

//FIXME O(N2) is really too much !!
// use arc iterator
int NodeArcSetsGraphView::inDegreeUB(int a ){
        int d=0;
        SetVarLubRanges nodesU(nodes);
        Iter::Ranges::ToValues<SetVarLubRanges> nodesIter(nodesU);
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInUB(i,a)){ d++;}
        }
        return d;
}


//FIXME O(N2) is really too much !!
// use arc iterator
int NodeArcSetsGraphView::inDegreeLB(int a ){
        int d=0;
        SetVarGlbRanges nodesL(nodes);
        Iter::Ranges::ToValues<SetVarGlbRanges> nodesIter(nodesL);
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInLB(i,a)){ d++;}
        }
        return d;
}

//FIXME O(N2) is really too much !!
// use arc iterator
int NodeArcSetsGraphView::outDegreeUB(int a ){
        int d=0;
        SetVarLubRanges nodesU(nodes);
        Iter::Ranges::ToValues<SetVarLubRanges> nodesIter(nodesU);
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInUB(a,i)){ d++;}
        }
        return d;
}
//FIXME O(N2) is really too much !!
// use arc iterator
int NodeArcSetsGraphView::outDegreeLB(int a ){
        int d=0;
        SetVarGlbRanges nodesL(nodes);
        Iter::Ranges::ToValues<SetVarGlbRanges> nodesIter(nodesL);
        for (; nodesIter(); ++nodesIter){
                int i = nodesIter.val();
                if (arcIsInLB(a,i)){ d++;}
        }
        return d;
}


bool NodeArcSetsGraphView::assigned(){
        return nodes.assigned() && arcs.assigned();
}
bool NodeArcSetsGraphView::nodeAssigned(){
        return nodes.assigned();
}

boost::tuple<vector<int>,vector<int>,vector<pair<int,int> >,vector<pair<int,int> > >   
NodeArcSetsGraphView::get_domain(){
        //Return values
        vector<int> nL;
        vector<int> nU;
        vector<pair<int,int> > aL;
        vector<pair<int,int> > aU;
        SetVarLubRanges nodesU(nodes);
        Iter::Ranges::ToValues<SetVarLubRanges > nodesUV(nodesU);
        for (;nodesUV();++nodesUV){
                nU.push_back(nodesUV.val());
        }
        SetVarGlbRanges nodesL(nodes);
        Iter::Ranges::ToValues<SetVarGlbRanges > nodesLV(nodesL);
        for (;nodesLV();++nodesLV){
                nL.push_back(nodesLV.val());
        }

        SetVarLubRanges arcsU(arcs);
        Iter::Ranges::ToValues<SetVarLubRanges > arcsUV(arcsU);
        for (;arcsUV();++arcsUV){
                aU.push_back(an->end_nodes(arcsUV.val()));
        }
        SetVarGlbRanges arcsL(arcs);
        Iter::Ranges::ToValues<SetVarGlbRanges > arcsLV(arcsL);
        for (;arcsLV();++arcsLV){
                aL.push_back(an->end_nodes(arcsLV.val()));
        }
        return boost::make_tuple(nL,nU,aL,aU);
}

} }
/**
 * \brief Print graph variable view
 * \relates Gecode::Graph::NodeArcSetsGraphView
 */
std::ostream&
operator<<(std::ostream& os, const Gecode::Graph::NodeArcSetsGraphView& g){
        os <<endl <<"########## Graph #########"<<endl;
        os <<"Nodes: "<< g.nodes<<endl;
        os <<"Arcs: ["<< endl;
        Gecode::Graph::NodeArcSetsGraphView::GlbArcIterator au=g.iter_arcs_LB();
        for (; au(); ++au){
                int i,j;
               boost::tie(i,j) = au.val();
                os << "("<<i<<","<<j<<"), " ;
        }
        os <<endl << "], ["<< endl;
        Gecode::Graph::NodeArcSetsGraphView::LubArcIterator al=g.iter_arcs_UB();
        for (; al(); ++al){
                int i,j;
               boost::tie(i,j) = al.val();
                os << "("<<i<<","<<j<<"), " ;
        }
        os <<endl << "]"<< endl;
        os <<"##########################"<<endl<<endl;
        return os;
}