// -*- C++ -*-

//kell hogy tree_edge invalid elekbol alljon, Szep 
//lenne ha az elejen a konstrualas ilyet adna, de
//ugy fest nem igy lesz, ekkor invalidalni kell

/* 
 *template <Graph, T, Heap=FibHeap>
 *
 *Constructor: 
 *
 *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
 *
 *
 *Methods:
 *
 *void run()
 *
 *  The followings functions should be used after run() was already run.
 *
 *T weight() : returns the minimum weight of a spanning tree of the
 *   component of the root. 
 *
 *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
 *   to the root. Returns an invalid iterator if v=s or v is 
 *   not reachable from the root.
 *
 *bool conn() : true iff G is connected
 *
 *bool reach(NodeIt v) : true iff v is in the same component as the root
 *
 *NodeIt root() : returns the root
 *
 */

#ifndef PRIM_H
#define PRIM_H

#include <fib_heap.h>

#include <iostream>

namespace hugo {

  template <typename Graph, typename T, 
    typename Heap=FibHeap<typename Graph::NodeIt, T, 
    typename Graph::NodeMap<int> > >
    class Prim{
      typedef typename Graph::NodeIt NodeIt;
      typedef typename Graph::EachNodeIt EachNodeIt;
      typedef typename Graph::EdgeIt EdgeIt;
      typedef typename Graph::OutEdgeIt OutEdgeIt;
      typedef typename Graph::InEdgeIt InEdgeIt;  

      Graph& G;
      NodeIt r;
      typename Graph::NodeMap<EdgeIt> tree_edge;
      typename Graph::NodeMap<T> min_weight;
      typename Graph::EdgeMap<T>& edge_weight;
      typename Graph::NodeMap<bool> reached;
          
  public :

      Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight, 
	   NodeIt const _r) : 
      G(_G), r(_r), tree_edge(G), min_weight(G), 
      edge_weight(_edge_weight), reached(G, false) { }

      Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) : 
      G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
      { 
	EachNodeIt _r;	   //FIXME
	G.getFirst(_r);
	r=_r;
      }


      void run() {

	typename Graph::NodeMap<bool> scanned(G, false);
	typename Graph::NodeMap<int> heap_map(G,-1);
	
	Heap heap(heap_map);

	heap.push(r,0); 
	reached.set(r, true);

	while ( !heap.empty() ) {

	  NodeIt v=heap.top(); 
	  min_weight.set(v, heap.get(v));
	  heap.pop();
	  scanned.set(v,true);

	  OutEdgeIt e;
	  for( G.getFirst(e,v); G.valid(e); G.next(e)) {
	    NodeIt w=G.head(e); 
	    
	    if ( !scanned.get(w) ) {
	      if ( !reached.get(w) ) {
		reached.set(w,true);
		heap.push(w, edge_weight.get(e)); 
		tree_edge.set(w,e);
	      } else if ( edge_weight.get(e) < heap.get(w) ) {
		tree_edge.set(w,e);
		heap.decrease(w, edge_weight.get(e)); 
	      }
	    }
	  }

	  InEdgeIt f;
	  for( G.getFirst(f,v); G.valid(f); G.next(f)) {
	    NodeIt w=G.tail(f); 
	    
	    if ( !scanned.get(w) ) {
	      if ( !reached.get(w) ) {
		reached.set(w,true);
		heap.push(w, edge_weight.get(f)); 
		tree_edge.set(w,f);
	      } else if ( edge_weight.get(f) < heap.get(w) ) {
		tree_edge.set(w,f);
		heap.decrease(w, edge_weight.get(f)); 
	      }
	    }
	  }
	}
      } 
 

      T weight() {
	T w=0;
	EachNodeIt u;
	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
	return w;
      }
     

      EdgeIt tree(NodeIt v) {
	return tree_edge.get(v);
      } 


      bool conn() {
	bool c=true;
	EachNodeIt u;
	for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) 
	  if ( !reached.get(u) ) { 
	    c=false;
	    break;
	  }
	return c;
      }


      bool reach(NodeIt v) {
	return reached.get(v);
      }


      NodeIt root() {
	return r;
      }

    };

}

#endif