/*
 *  Main authors:
 *     Grégoire Dooms <dooms@info.ucl.ac.be>
 *
 *  Copyright:
 *     Grégoire Dooms (Université catholique de Louvain), 2005
 *
 *  Last modified:
 *     $Date: 2005-11-29 10:57:21 +0100 (Tue, 29 Nov 2005) $
 *     $Revision: 271 $
 *
 *  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 <list>
//using namespace boost;
//using namespace std;
namespace Gecode { namespace Graph {
template <class GView> 
    void pathdegree(Space *home, GView &g, int start, int end);
template <>
    void pathdegree(Space *home, OutAdjSetsGraphView &g, int start, int end){
        int numNodes = g.outN.size();
        BoolVarArray b(home,3*numNodes,0,1);
        #define iInNodes(i)  b[0+3*(i)]
        #define iNotInNodes(i) b[1+3*(i)]
        #define iOutsEmpty(i) b[2+3*(i)]
        Gecode::IntSet empty;

        for (int i=0 ; i<numNodes ; i++){
                //include(home,nodes,i,iInNodes(i));
                dom(home, g.nodes, SRT_SUP, i, iInNodes(i));
                bool_not(home, iInNodes(i), iNotInNodes(i));
                dom(home, g.outN[i], SRT_EQ, empty, iOutsEmpty(i)); 
        }
        cardinality(home,g.outN[end],0,0); 

        //outdegree(i) == i in nodes
        for (int i=0; i<numNodes; i++){
                if (i!=end)
                        cardinality(home,g.outN[i],iInNodes(i));
        }
        //indegree(i) == i in nodes
        //        selectDisjoint(home,outN,outN[numNodes]);
        //replaced with: 
        for (int i=0; i< numNodes; i++){
                IntVarArgs iinOuts(numNodes);
                for (int j=0 ; j< numNodes; j++){
                        BoolVar b(home,0,1);
                        iinOuts[j]=b;
                        dom(home,g.outN[j],SRT_SUP,i,b);
                }
                if (i !=start)
                        linear(home,iinOuts,IRT_EQ,iInNodes(i));
                else
                        linear(home,iinOuts,IRT_EQ,0);
        }
}

template <class GView>
PathDegreePropag<GView>::~PathDegreePropag(void){ 
        g.cancel(this, Gecode::Graph::PC_GRAPH_ANY);
}

template <class GView>
Actor* PathDegreePropag<GView>::copy(Space* home, bool share) {
        return new (home) PathDegreePropag(home,share,*this);
}

template <class GView>
PathDegreePropag<GView>::PathDegreePropag(Space* home, GView &g,int start, int end): Propagator(home), g(g), start(start), end(end) {
	g.subscribe(home,this, Gecode::Graph::PC_GRAPH_LUB);
}

template <class GView>
ExecStatus PathDegreePropag<GView>::post(Space* home, GView &g,int start, int end) {
        (void) new (home) PathDegreePropag(home,g, start, end);
        return ES_OK;
}

template <class GView>
PropCost PathDegreePropag<GView>::cost(void) const {
        return Gecode::PC_QUADRATIC_LO;
}

template <class GView>
        forceinline
        PathDegreePropag<GView>::PathDegreePropag(Space* home, bool share, PathDegreePropag& p)
: Propagator(home,share,p) { 
        g.update(home,share,p.g);
}

template <class GView>
ExecStatus PathDegreePropag<GView>::propagate(Space* home) {
// Pruning rules:
// if an arc is in LB remove other arcs (in UB) with same head or same tail
// Not implemented : if a node is in LB and there is only one arc with it as head or as tail then that arc gets in LB.

	map<int,int> tail; //head -> tail of arcs in LB
	map<int,int> head; //tail -> head

	typename GView::GlbArcIterator  l = g.iter_arcs_LB();
	for (; l(); ++l){
		int t,h;
        boost::tie(t,h) = l.val();
		head[t] = h;
		tail[h] = t;
	}

	list<pair<int,int> > removeArcs;
	typename GView::LubArcIterator  u = g.iter_arcs_UB();
	for (; u(); ++u){
		int t,h;
		boost::tie(t,h) = u.val();
        map<int,int>::iterator i;
		if (((i = head.find(t)) != head.end() && i->second != h) ||
            ((i = tail.find(h)) != tail.end() && i->second != t)) {
		    removeArcs.push_back(make_pair(t,h));
        }
	}
	// XXX TODO replace with an adequate removeArcs method
	for (list<pair<int,int> >::const_iterator k=removeArcs.begin(); k!=removeArcs.end(); ++k){
		GECODE_ME_CHECK(g._arcOut(home,k->first,k->second));
	}
    return ES_FIX;
}
} }