Index: src/work/johanna/kruskal.h
===================================================================
--- src/work/johanna/kruskal.h	(revision 246)
+++ src/work/johanna/kruskal.h	(revision 349)
@@ -3,163 +3,73 @@
 #define HUGO_KRUSKAL_H
 
-#include "unionfind.h"
 #include <algorithm>
+#include <unionfind.h>
+#include <for_each_macros.h>
 
 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
+  /// Kruskal's algorithm to compute a minimum cost tree
+
+  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
+  typename InputEdgeOrder::ValueType
+  Kruskal(Graph const& G, InputEdgeOrder const& edges, 
+	  OutBoolMap& out_map)
   {
-
-    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) {}
+    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_map.set(edges.first(p), true);
+	tot_cost += edges.second(p);
+      }
+      else {
+	out_map.set(edges.first(p), false);
+      }
+    }
+    return tot_cost;
+  }
+
+
   
-
-    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: 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 receive
+  /// the value "true".
+  /// \warning Not a regular property map, as it doesn't know its KeyType
+
+  template<typename Iterator>
+  class SequenceOutput {
+    Iterator it;
+
+  public:
+    typedef bool ValueType;
+
+    SequenceOutput(Iterator const &_it) : it(_it) {}
+
+    template<typename KeyType>
+    void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} }
   };
 
-  
-  /* ** ** 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 &it;
-
-  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);      
-    }
-  };
-
+  template<typename Iterator>
+  inline
+  SequenceOutput<Iterator>
+  makeSequenceOutput(Iterator it) {
+    return SequenceOutput<Iterator>(it);
+  }
 
   /* ** ** InputSource -ok ** ** */
 
   template<typename Key, typename Val>
-  class PairVec : public std::vector< std::pair<Key,Val> > {
+  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
 
   public:
@@ -172,7 +82,5 @@
     typedef typename Parent::const_iterator const_iterator;
 
-
   private:
-
     class comparePair {
     public:
@@ -185,5 +93,5 @@
 
     // FIXME: kell ez?
-    // PairVec(Parent const& p) : Parent(p) {}
+    // KruskalPairVec(Parent const& p) : Parent(p) {}
     
     void sort() {
@@ -193,16 +101,14 @@
     // FIXME: nem nagyon illik ez ide...
     template<typename Graph, typename Map>
-    void readGraphEdgeMap(Graph const& G, Map const& m) {
+    KruskalPairVec(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)) {
+      FOR_EACH_LOC(EdgeIt, e, G) {
+      // 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; }
@@ -213,36 +119,91 @@
   };
 
+
+  template <typename Map>
+  class KruskalMapVec : public std::vector<typename Map::KeyType> {
+  public:
+
+    typedef typename Map::KeyType KeyType;
+    typedef typename Map::ValueType ValueType;
+
+    typedef typename std::vector<KeyType> Parent;
+    typedef typename Parent::iterator iterator;
+    typedef typename Parent::const_iterator const_iterator;
+
+  private:
+
+    const Map &m;
+
+    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_EACH_LOC(EdgeIt, e, G) {
+      // 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.
   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>
+  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
+				   EdgeCostMap const& edge_costs,
+				   RetEdgeBoolMap &ret_bool_map) {
+
+    typedef KruskalPairVec<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();
-  }
-
+    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.
   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>
+  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
+				    EdgeCostMap const& edge_costs,
+				    RetIterator ret_iterator) {
+    typedef SequenceOutput<RetIterator> OutMap;
+    OutMap out(ret_iterator);
+
+    typedef KruskalPairVec<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();    
+    InputVec iv(G, edge_costs);
+
+    return Kruskal(G, iv, out);
   }
 
