#include <string>

#include <iostream>

#include <map>

#include <kruskal.h>

#include <list_graph.h>

using namespace std;

using namespace hugo;

class string_int_map : public map<string,int> {

public:

  int get(const string &s) {

    // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy

    // hogy is mukodik ez a map :)

    if( count(s) == 0 ) {

      operator[](s) = -1;

    }

    return operator[](s);

  }

  void set(const string &s, int i) {

      operator[](s) = i;

  }

};

// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.

// Valami elegansabb megoldas kene a Kruskalban...

template <typename K, typename V>

class DummyMap {

public:

  typedef K KeyType;

  typedef V ValueType;

};

int main() {

  typedef ListGraph::Node Node;

  typedef ListGraph::Edge Edge;

  typedef ListGraph::NodeIt NodeIt;

  typedef ListGraph::EdgeIt EdgeIt;

  ListGraph G;

  Node s=G.addNode();

  Node v1=G.addNode();

  Node v2=G.addNode();

  Node v3=G.addNode();

  Node v4=G.addNode();

  Node t=G.addNode();

  Edge e1 = G.addEdge(s, v1);

  Edge e2 = G.addEdge(s, v2);

  Edge e3 = G.addEdge(v1, v2);

  Edge e4 = G.addEdge(v2, v1);

  Edge e5 = G.addEdge(v1, v3);

  Edge e6 = G.addEdge(v3, v2);

  Edge e7 = G.addEdge(v2, v4);

  Edge e8 = G.addEdge(v4, v3);

  Edge e9 = G.addEdge(v3, t);

  Edge e10 = G.addEdge(v4, t);

  typedef ListGraph::EdgeMap<double> ECostMap;

  typedef ListGraph::EdgeMap<bool> EBoolMap;

  ECostMap edge_cost_map(G, 2);

  EBoolMap tree_map(G);

  typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;

  MCTK mctk(G, edge_cost_map, tree_map);

  double k0lts = mctk.run();

  cout << "Uniform 2-es koltseggel: " << k0lts << endl;

  // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:

  typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;

  MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);

  MCTK2::EdgeCostVector ecv;

  ecv.push_back(make_pair(e1, 10));

  ecv.push_back(make_pair(e2, 9));

  ecv.push_back(make_pair(e3, 8));

  ecv.push_back(make_pair(e4, 7));

  ecv.push_back(make_pair(e5, 6));

  ecv.push_back(make_pair(e6, 5));

  ecv.push_back(make_pair(e7, 4));

  ecv.push_back(make_pair(e8, 3));

  ecv.push_back(make_pair(e9, 2));

  ecv.push_back(make_pair(e10, 1));

  k0lts = mctk2.run(ecv);

  cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "

       << k0lts << endl;

  return 0;

}