// -*- 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