// -*- c++ -*- //

 #ifndef HUGO_KRUSKAL_H

 #define HUGO_KRUSKAL_H

 #include "unionfind.h"

 #include <algorithm>

 namespace hugo {

   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>

   typename EdgeCostMap::ValueType

   kruskal1(Graph const& G, EdgeCostMap const& edge_costs,

 	   RetEdgeBoolMap &ret_bool_map);

   template <typename Graph, typename EdgeCostMap, typename RetIterator>

   typename EdgeCostMap::ValueType

   kruskal2(Graph const& G, EdgeCostMap const& edge_costs,

 	   RetIterator ret_iterator);

   // FIXME: ret_iterator nem lehet referencia!!!

   template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>

   typename EdgeCostPairVec::value_type::second_type

   kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,

 	   RetEdgeBoolMap &ret_bool_map);

   template <typename Graph, typename EdgeCostPairVec, typename RetIterator>

   typename EdgeCostPairVec::value_type::second_type

   kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,

 	   RetIterator &ret_iterator);

   template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>

   int

   kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,

 	   RetEdgeBoolMap &ret_bool_map);

   template <typename Graph, typename EdgePairVec, typename RetIterator>

   int

   kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,

 	   RetIterator &ret_iterator);

   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,

 	    typename RetIterator>

   typename EdgeCostMap::ValueType

   kruskal7(Graph const& G, EdgeCostMap const& edge_costs,

 	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);

   template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,

 	    typename RetIterator>

   typename EdgeCostPairVec::value_type::second_type

   kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,

 	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);

   template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,

 	    typename RetIterator>

   int

   kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,

 	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);

   template <typename Graph, typename InputEdgeOrder, typename OutputObserver>

   class MinCostTreeKruskal

   {

     typedef typename Graph::EdgeIt EdgeIt;

     typedef typename Graph::Edge Edge;

   public:

     typedef typename InputEdgeOrder::ValueType EdgeCost;

   private:

     Graph const &G;

     InputEdgeOrder const &edges;

     OutputObserver &out_obs;

   public:

     MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 

 		       OutputObserver& _out_obs) : 

       G(_G), edges(_edges), out_obs(_out_obs) {}

     EdgeCost run()

     {

       typedef typename Graph::NodeMap<int> NodeIntMap;

       typedef typename Graph::Node Node;

       NodeIntMap comp_map(G, -1);

       UnionFind<Node,NodeIntMap> uf(comp_map); 

       EdgeCost tot_cost = 0;

       for (typename InputEdgeOrder::const_iterator p = edges.begin(); 

 	   p!=edges.end(); ++p ) {

 	if ( uf.joinComponents(G.head(edges.first(p)),

 			       G.tail(edges.first(p))) ) {

 	  out_obs.setTrue(edges.first(p));

 	  tot_cost += edges.second(p);

 	}

 	else {

 	  out_obs.setFalse(edges.first(p));

 	}

       }

       return tot_cost;

     }

   };

   /* ** ** Output-objektumok (Observerek (?)) ** ** */

   template <typename BoolMap>

   class BoolMapOutput {

     BoolMap &bm;

     typedef typename BoolMap::KeyType KeyType;

   public:

     BoolMapOutput(BoolMap &_bm) : bm(_bm) {}

     void setTrue(KeyType const& k) { bm.set(k, true); }

     void setFalse(KeyType const& k) { bm.set(k, false); }

   };

   template <typename Iterator>

   class SequenceOutput {

     Iterator ⁢

   public:

     SequenceOutput(Iterator &_it) : it(_it) {}

     template<typename KeyType>

     void setTrue(KeyType const& k) { *it=k; ++it; }

     template<typename KeyType>

     void setFalse(KeyType const& k) {}

   };

   template <typename BoolMap, typename Iterator>

   class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {

     typedef BoolMapOutput<BoolMap> BMO;

     typedef SequenceOutput<Iterator> SO;

   public:

     CombinedOutput(BoolMap &_bm, Iterator &_it) :

       BMO(_bm), SO(_it) {}

     template<typename KeyType>

     void setTrue(KeyType const& k) {

       BMO::setTrue(k); 

       SO::setTrue(k);

     }

     template<typename KeyType>

     void setFalse(KeyType const& k) {

       BMO::setFalse(k); 

       SO::setFalse(k);      

     }

   };

   /* ** ** InputSource -ok ** ** */

   template<typename Key, typename Val>

   class PairVec : public std::vector< std::pair<Key,Val> > {

   public:

     typedef std::vector< std::pair<Key,Val> > Parent;

     typedef Key KeyType;

     typedef Val ValueType;

     typedef std::pair<Key,Val> PairType;

     typedef typename Parent::iterator iterator;

     typedef typename Parent::const_iterator const_iterator;

   private:

     class comparePair {

     public:

       bool operator()(PairType const& a, PairType const& b) {

 	return a.second < b.second;

       }

     };

   public:

     // FIXME: kell ez?

     // PairVec(Parent const& p) : Parent(p) {}

     void sort() {

       std::sort(begin(), end(), comparePair());

     }

     // FIXME: nem nagyon illik ez ide...

     template<typename Graph, typename Map>

     void readGraphEdgeMap(Graph const& G, Map const& m) {

       typedef typename Graph::EdgeIt EdgeIt;

       clear();

       for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {

 	push_back(make_pair(e, m[e]));

       }

       sort();

     }

     int alma() { return 5; /* FIXME */ }

     Key const& first(const_iterator i) const { return i->first; }

     Key& first(iterator i) { return i->first; }

     Val const& second(const_iterator i) const { return i->second; }

     Val& second(iterator i) { return i->second; }

   };

   /* ** ** Wrapper fuggvenyek ** ** */

   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>

   typename EdgeCostMap::ValueType

   kruskal1(Graph const& G, EdgeCostMap const& edge_costs,

 	   RetEdgeBoolMap &ret_bool_map) {

     typedef BoolMapOutput<RetEdgeBoolMap> OutObs;

     OutObs out(ret_bool_map);

     typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>

       InputVec;

     InputVec iv;

     iv.readGraphEdgeMap(G, edge_costs);

     MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);

     return mctk.run();

   }

   template <typename Graph, typename EdgeCostMap, typename RetIterator>

   typename EdgeCostMap::ValueType

   kruskal2(Graph const& G, EdgeCostMap const& edge_costs,

 	   RetIterator ret_iterator) {

     typedef SequenceOutput<RetIterator> OutObs;

     OutObs out(ret_iterator);

     typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>

       InputVec;

     InputVec iv;

     iv.readGraphEdgeMap(G, edge_costs);

     MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);

     return mctk.run();    

   }

 } //namespace hugo

 #endif //HUGO_KRUSKAL_H