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