RhodeCode

    };

    template <typename Graph, typename In, typename Out>

    struct KruskalInputSelector<Graph, In, Out,

      typename enable_if<MapInputIndicator<In>, void>::type > 

    {

      typedef typename In::Value Value;

      static Value kruskal(const Graph& graph, const In& in, Out& out) {

        typedef typename In::Key MapArc;

        typedef typename In::Value Value;

        typedef typename ItemSetTraits<Graph, MapArc>::ItemIt MapArcIt;

        typedef std::vector<std::pair<MapArc, Value> > Sequence;

        Sequence seq;

        for (MapArcIt it(graph); it != INVALID; ++it) {

          seq.push_back(std::make_pair(it, in[it]));

        }

        std::sort(seq.begin(), seq.end(), PairComp<Sequence>());

        return KruskalOutputSelector<Graph, Sequence, Out>::

          kruskal(graph, seq, out);

      }

    };

    template <typename Graph, typename In, typename Out>

    struct KruskalOutputSelector<Graph, In, Out,

      typename enable_if<SequenceOutputIndicator<Out>, void>::type > 

    {

      typedef typename In::value_type::second_type Value;

      static Value kruskal(const Graph& graph, const In& in, Out& out) {

        Map map(out);

        return _kruskal_bits::kruskal(graph, in, map);

      }

    };

    template <typename Graph, typename In, typename Out>

    struct KruskalOutputSelector<Graph, In, Out,

      typename enable_if<MapOutputIndicator<Out>, void>::type > 

    {

      typedef typename In::value_type::second_type Value;

      static Value kruskal(const Graph& graph, const In& in, Out& out) {

        return _kruskal_bits::kruskal(graph, in, out);

      }

    };

  }

  /// \ingroup spantree

  ///

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

  ///

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

{

  // Map concepts

  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();

  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();

  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();

  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();

  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();

  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();

  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();

  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();

  // NullMap

  {

    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();

    NullMap<A,B> map1;

    NullMap<A,B> map2 = map1;

    map1 = nullMap<A,B>();

  }

  // ConstMap

  {

    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();

    checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();

    ConstMap<A,B> map1;

    ConstMap<A,B> map3 = map1;

    map1 = constMap<A>(B());

    map1 = constMap<A,B>();

    map1.setAll(B());

    ConstMap<A,C> map4(C(1));

    ConstMap<A,C> map5 = map4;

    map4 = constMap<A>(C(2));

    map4.setAll(C(3));

    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();

    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");

    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();

    ConstMap<A,Const<int,10> > map6;

    ConstMap<A,Const<int,10> > map7 = map6;

    map6 = constMap<A,int,10>();

    map7 = constMap<A,Const<int,10> >();

    check(map6[A()] == 10 && map7[A()] == 10, "Something is wrong with ConstMap");

  }

  // IdentityMap

  {

    checkConcept<ReadMap<A,A>, IdentityMap<A> >();

    IdentityMap<A> map1;

  {

    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();

    RangeMap<B> map1;

    RangeMap<B> map2(10);

    RangeMap<B> map3(10,B());

    RangeMap<B> map4 = map1;

    RangeMap<B> map5 = rangeMap<B>();

    RangeMap<B> map6 = rangeMap<B>(10);

    RangeMap<B> map7 = rangeMap(10,B());

    checkConcept< ReferenceMap<int, double, double&, const double&>,

                  RangeMap<double> >();

    std::vector<double> v(10, 0);

    v[5] = 100;

    RangeMap<double> map8(v);

    RangeMap<double> map9 = rangeMap(v);

    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,

          "Something is wrong with RangeMap");

  }

  // SparseMap

  {

    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();

    SparseMap<A,B> map1;

    SparseMap<A,B> map3 = sparseMap<A,B>();

    SparseMap<A,B> map4 = sparseMap<A>(B());

    checkConcept< ReferenceMap<double, int, int&, const int&>,

                  SparseMap<double, int> >();

    std::map<double, int> m;

    SparseMap<double, int> map5(m);

    SparseMap<double, int> map6(m,10);

    SparseMap<double, int> map7 = sparseMap(m);

    SparseMap<double, int> map8 = sparseMap(m,10);

    check(map5[1.0] == 0 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 10,

          "Something is wrong with SparseMap");

    map5[1.0] = map6[3.14] = 100;

    check(map5[1.0] == 100 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 100,

          "Something is wrong with SparseMap");

  }

  // ComposeMap

  {

    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;

    checkConcept<ReadMap<B,double>, CompMap>();

    CompMap map1(DoubleMap(),ReadMap<B,A>());

    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());