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

 #ifndef HUGO_KRUSKAL_H

 #define HUGO_KRUSKAL_H

 #include <algorithm>

 #include <hugo/unionfind.h>

 /**

 @defgroup spantree Minimum Cost Spanning Tree Algorithms

 \brief This group containes the algorithms for finding a minimum cost spanning

 tree in a graph

 @ingroup galgs

 */

 ///\ingroup spantree

 ///\file

 ///\brief Kruskal's algorithm to compute a minimum cost tree

 namespace hugo {

   /// \addtogroup spantree

   /// @{

   /// Kruskal's algorithm to find a minimum cost tree of a graph.

   /// This function runs Kruskal's algorithm to find a minimum cost tree.

   /// \param G The graph the algorithm runs on.

   /// \param in This object is used to describe the edge costs. It must

   /// be an STL 'forward container'

   /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,

   /// where X is the type of the costs. It must contain every edge in

   /// cost-ascending order.

   /// \retval out This must be a writeable EdgeMap. After running the algorithm

   /// this will contain the found minimum cost spanning tree: the value of an

   /// edge will be set to \c true if it belongs to the tree, otherwise it will

   /// be set to \c false. The value of each edge will be set exactly once.\n

   /// For the sake of simplicity, there is a helper class KruskalPairVec,

   /// which converts a

   /// simple EdgeMap to an input of this form. Alternatively, you can use

   /// the function \ref kruskalEdgeMap to compute the minimum cost tree if

   /// the edge costs are given by an EdgeMap.

   /// \return The cost of the found tree.

   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>

   typename InputEdgeOrder::value_type::second_type

   kruskal(Graph const& G, InputEdgeOrder const& in, 

 		 OutBoolMap& out)

   {

     typedef typename InputEdgeOrder::value_type::second_type EdgeCost;

     typedef typename Graph::template NodeMap<int> NodeIntMap;

     typedef typename Graph::Node Node;

     NodeIntMap comp(G, -1);

     UnionFind<Node,NodeIntMap> uf(comp); 

     EdgeCost tot_cost = 0;

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

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

       if ( uf.join(G.head((*p).first),

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

 	out.set((*p).first, true);

 	tot_cost += (*p).second;

       }

       else {

 	out.set((*p).first, false);

       }

     }

     return tot_cost;

   }

   /* A work-around for running Kruskal with const-reference bool maps... */

   template<typename Map>

   class NonConstMapWr {

     const Map &m;

   public:

     typedef typename Map::ValueType ValueType;

     NonConstMapWr(const Map &_m) : m(_m) {}

     template<typename KeyType>

     void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }

   };

   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>

   inline

   typename InputEdgeOrder::ValueType

   kruskal(Graph const& G, InputEdgeOrder const& edges, 

 	  OutBoolMap const& out_map)

   {

     NonConstMapWr<OutBoolMap> map_wr(out_map);

     return kruskal(G, edges, map_wr);

   }  

   /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */

   /// A writable bool-map that makes a sequence of "true" keys

   /// A writable bool-map that creates a sequence out of keys that receives

   /// the value "true".

   /// \warning Not a regular property map, as it doesn't know its KeyType

   template<typename Iterator>

   class SequenceOutput {

     mutable Iterator it;

   public:

     typedef bool ValueType;

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

     template<typename KeyType>

     void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }

   };

   template<typename Iterator>

   inline

   SequenceOutput<Iterator>

   makeSequenceOutput(Iterator it) {

     return SequenceOutput<Iterator>(it);

   }

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

   /// Kruskal input source.

   /// Kruskal input source.

   ///

   template<typename Graph, typename Map>

   class KruskalMapInput

     : public std::vector< std::pair<typename Graph::Edge,

 				    typename Map::ValueType> > {

   public:

     typedef std::vector< std::pair<typename Graph::Edge,

 				   typename Map::ValueType> > Parent;

     typedef typename Parent::value_type value_type;

 //     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()(const value_type& a,

 		      const value_type& b) {

 	return a.second < b.second;

       }

     };

   public:

     // FIXME: kell ez?

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

     void sort() {

       std::sort(this->begin(), this->end(), comparePair());

     }

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

     KruskalMapInput(Graph const& G, Map const& m) {

       typedef typename Graph::EdgeIt EdgeIt;

       this->clear();

       for(EdgeIt e(G);G.valid(e);G.next(e)) {

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

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

       }

       sort();

     }

 //     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; }

   };

 //   template<typename Graph, typename Map>

 //   class KruskalMapVec {

 //   public:

 //     typedef std::pair<typename Map::KeyType, Map::ValueType> value_type;

 //     typedef std::vector<KeyType> Container;

 //     Container container;

 //     std::vector<typename Map::KeyType> container

 //     const Map &m;

 //     class iterator

 //     {

 //       Container::iterator i;

 //     public:

 //       iterator &operator ++() {++i;return *this;}

 //       valuetype operator *() {return value_type(container(i),m[container(i)]);}

 //       bool operator==(iterator b) {return i==b.i;}

 //       iterator() {}

 //       iterator(Container::iterator _i) i(_i) {}

 //     };

 //     class const_iterator

 //     {

 //       Container::const_iterator i;

 //     public:

 //       iterator &operator ++() {++i;return *this;}

 //       valuetype operator *() {return value_type(container(i),m[container(i)]);}

 //       bool operator==(iterator b) {return i==b.i;}

 //       const_iterator() {}

 //       const_iterator(Container::iterator _i) i(_i) {}

 //     };

 //     iterator begin() { return iterator(container.begin());}

 //     const_iterator begin() const { return iterator(container.begin());}

 //     iterator end() { return iterator(container.end());}

 //     const_iterator end() const { return iterator(container.end());}

 //   private:

 //     class compareKeys {

 //       const Map &m;

 //     public:

 //       compareKeys(Map const &_m) : m(_m) {}

 //       bool operator()(KeyType const& a, KeyType const& b) {

 // 	return m[a] < m[b];

 //       }

 //     };

 //   public:

 //     KruskalMapVec(Map const& _m) : m(_m) {}

 //     void sort() {

 //       std::sort(begin(), end(), compareKeys(m));

 //     }

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

 //     template<typename Graph>

 //     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {

 //       typedef typename Graph::EdgeIt EdgeIt;

 //       clear();

 //       for(EdgeIt e(G);G.valid(e);G.next(e)) {

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

 // 	push_back(e);

 //       }

 //       sort();

 //     }

 //     KeyType const& first(const_iterator i) const { return *i; }

 //     KeyType& first(iterator i) { return *i; }

 //     ValueType const& second(const_iterator i) const { return m[*i]; }

 //     ValueType& second(iterator i) { return m[*i]; }

 //   };

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

   /// \brief Wrapper to Kruskal().

   /// Input is from an EdgeMap, output is a plain boolmap.

   ///\todo some more words would be nice here.

   ///

   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>

   inline

   typename EdgeCostMap::ValueType

   kruskalEdgeMap(Graph const& G,

 			EdgeCostMap const& edge_costs,

 			RetEdgeBoolMap &ret_bool_map) {

     typedef KruskalMapInput<Graph,EdgeCostMap> InputVec;

     InputVec iv(G, edge_costs);

     return kruskal(G, iv, ret_bool_map);

   }

   /// \brief Wrapper to Kruskal().

   /// Input is from an EdgeMap, output is to a sequence.

   ///\todo it does not follow the naming convention.

   ///

   template <typename Graph, typename EdgeCostMap, typename RetIterator>

   inline

   typename EdgeCostMap::ValueType

   kruskalEdgeMap_IteratorOut(const Graph& G,

 			     const EdgeCostMap& edge_costs,

 			     RetIterator ret_iterator)

   {

     typedef typename EdgeCostMap::ValueType ValueType;

     typedef SequenceOutput<RetIterator> OutMap;

     OutMap out(ret_iterator);

     typedef KruskalMapInput<Graph, EdgeCostMap> InputVec;

     InputVec iv(G, edge_costs);

     return kruskal(G, iv, out);

   }

   /// @}

 } //namespace hugo

 #endif //HUGO_KRUSKAL_H