Use output iterator instead of a container (#386)
authorPeter Kovacs <kpeter@inf.elte.hu>
Thu, 28 Feb 2013 17:13:14 +0100
changeset 1037d3dcc49e6403
parent 1036 dff32ce3db71
child 1038 a2d142bb5d3c
Use output iterator instead of a container (#386)
in tourNodes() functions of TSP algorithms
lemon/christofides_tsp.h
lemon/greedy_tsp.h
lemon/insertion_tsp.h
lemon/nearest_neighbor_tsp.h
lemon/opt2_tsp.h
test/tsp_test.cc
     1.1 --- a/lemon/christofides_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     1.2 +++ b/lemon/christofides_tsp.h	Thu Feb 28 17:13:14 2013 +0100
     1.3 @@ -209,12 +209,23 @@
     1.4        /// \brief Gives back the node sequence of the found tour.
     1.5        ///
     1.6        /// This function copies the node sequence of the found tour into
     1.7 -      /// the given standard container.
     1.8 +      /// an STL container through the given output iterator. The
     1.9 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
    1.10 +      /// For example,
    1.11 +      /// \code
    1.12 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
    1.13 +      /// tsp.tourNodes(nodes.begin());
    1.14 +      /// \endcode
    1.15 +      /// or
    1.16 +      /// \code
    1.17 +      /// std::list<FullGraph::Node> nodes;
    1.18 +      /// tsp.tourNodes(std::back_inserter(nodes));
    1.19 +      /// \endcode
    1.20        ///
    1.21        /// \pre run() must be called before using this function.
    1.22 -      template <typename Container>
    1.23 -      void tourNodes(Container &container) const {
    1.24 -        container.assign(_path.begin(), _path.end());
    1.25 +      template <typename Iterator>
    1.26 +      void tourNodes(Iterator out) const {
    1.27 +        std::copy(_path.begin(), _path.end(), out);
    1.28        }
    1.29        
    1.30        /// \brief Gives back the found tour as a path.
     2.1 --- a/lemon/greedy_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     2.2 +++ b/lemon/greedy_tsp.h	Thu Feb 28 17:13:14 2013 +0100
     2.3 @@ -206,12 +206,23 @@
     2.4        /// \brief Gives back the node sequence of the found tour.
     2.5        ///
     2.6        /// This function copies the node sequence of the found tour into
     2.7 -      /// the given standard container.
     2.8 +      /// an STL container through the given output iterator. The
     2.9 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
    2.10 +      /// For example,
    2.11 +      /// \code
    2.12 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
    2.13 +      /// tsp.tourNodes(nodes.begin());
    2.14 +      /// \endcode
    2.15 +      /// or
    2.16 +      /// \code
    2.17 +      /// std::list<FullGraph::Node> nodes;
    2.18 +      /// tsp.tourNodes(std::back_inserter(nodes));
    2.19 +      /// \endcode
    2.20        ///
    2.21        /// \pre run() must be called before using this function.
    2.22 -      template <typename Container>
    2.23 -      void tourNodes(Container &container) const {
    2.24 -        container.assign(_path.begin(), _path.end());
    2.25 +      template <typename Iterator>
    2.26 +      void tourNodes(Iterator out) const {
    2.27 +        std::copy(_path.begin(), _path.end(), out);
    2.28        }
    2.29  
    2.30        /// \brief Gives back the found tour as a path.
     3.1 --- a/lemon/insertion_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     3.2 +++ b/lemon/insertion_tsp.h	Thu Feb 28 17:13:14 2013 +0100
     3.3 @@ -203,12 +203,23 @@
     3.4        /// \brief Gives back the node sequence of the found tour.
     3.5        ///
     3.6        /// This function copies the node sequence of the found tour into
     3.7 -      /// the given standard container.
     3.8 +      /// an STL container through the given output iterator. The
     3.9 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
    3.10 +      /// For example,
    3.11 +      /// \code
    3.12 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
    3.13 +      /// tsp.tourNodes(nodes.begin());
    3.14 +      /// \endcode
    3.15 +      /// or
    3.16 +      /// \code
    3.17 +      /// std::list<FullGraph::Node> nodes;
    3.18 +      /// tsp.tourNodes(std::back_inserter(nodes));
    3.19 +      /// \endcode
    3.20        ///
    3.21        /// \pre run() must be called before using this function.
    3.22 -      template <typename Container>
    3.23 -      void tourNodes(Container &container) const {
    3.24 -        container.assign(_tour.begin(), _tour.end());
    3.25 +      template <typename Iterator>
    3.26 +      void tourNodes(Iterator out) const {
    3.27 +        std::copy(_tour.begin(), _tour.end(), out);
    3.28        }
    3.29  
    3.30        /// \brief Gives back the found tour as a path.
     4.1 --- a/lemon/nearest_neighbor_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     4.2 +++ b/lemon/nearest_neighbor_tsp.h	Thu Feb 28 17:13:14 2013 +0100
     4.3 @@ -193,12 +193,23 @@
     4.4        /// \brief Gives back the node sequence of the found tour.
     4.5        ///
     4.6        /// This function copies the node sequence of the found tour into
     4.7 -      /// the given standard container.
     4.8 +      /// an STL container through the given output iterator. The
     4.9 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
    4.10 +      /// For example,
    4.11 +      /// \code
    4.12 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
    4.13 +      /// tsp.tourNodes(nodes.begin());
    4.14 +      /// \endcode
    4.15 +      /// or
    4.16 +      /// \code
    4.17 +      /// std::list<FullGraph::Node> nodes;
    4.18 +      /// tsp.tourNodes(std::back_inserter(nodes));
    4.19 +      /// \endcode
    4.20        ///
    4.21        /// \pre run() must be called before using this function.
    4.22 -      template <typename Container>
    4.23 -      void tourNodes(Container &container) const {
    4.24 -        container.assign(_path.begin(), _path.end());
    4.25 +      template <typename Iterator>
    4.26 +      void tourNodes(Iterator out) const {
    4.27 +        std::copy(_path.begin(), _path.end(), out);
    4.28        }
    4.29  
    4.30        /// \brief Gives back the found tour as a path.
     5.1 --- a/lemon/opt2_tsp.h	Sun Jan 09 15:06:55 2011 +0100
     5.2 +++ b/lemon/opt2_tsp.h	Thu Feb 28 17:13:14 2013 +0100
     5.3 @@ -230,12 +230,23 @@
     5.4        /// \brief Gives back the node sequence of the found tour.
     5.5        ///
     5.6        /// This function copies the node sequence of the found tour into
     5.7 -      /// the given standard container.
     5.8 +      /// an STL container through the given output iterator. The
     5.9 +      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
    5.10 +      /// For example,
    5.11 +      /// \code
    5.12 +      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
    5.13 +      /// tsp.tourNodes(nodes.begin());
    5.14 +      /// \endcode
    5.15 +      /// or
    5.16 +      /// \code
    5.17 +      /// std::list<FullGraph::Node> nodes;
    5.18 +      /// tsp.tourNodes(std::back_inserter(nodes));
    5.19 +      /// \endcode
    5.20        ///
    5.21        /// \pre run() must be called before using this function.
    5.22 -      template <typename Container>
    5.23 -      void tourNodes(Container &container) const {
    5.24 -        container.assign(_path.begin(), _path.end());
    5.25 +      template <typename Iterator>
    5.26 +      void tourNodes(Iterator out) const {
    5.27 +        std::copy(_path.begin(), _path.end(), out);
    5.28        }
    5.29  
    5.30        /// \brief Gives back the found tour as a path.
     6.1 --- a/test/tsp_test.cc	Sun Jan 09 15:06:55 2011 +0100
     6.2 +++ b/test/tsp_test.cc	Thu Feb 28 17:13:14 2013 +0100
     6.3 @@ -61,21 +61,23 @@
     6.4  // }
     6.5  
     6.6  // Checks tour validity
     6.7 -bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) {
     6.8 +template <typename Container>
     6.9 +bool checkTour(const FullGraph &gr, const Container &p) {
    6.10    FullGraph::NodeMap<bool> used(gr, false);
    6.11    
    6.12 -  int nodes = 0;
    6.13 -  for (int i = 0; i < int(p.size()); ++i) {
    6.14 -    if (used[p[i]]) return false;
    6.15 -    used[p[i]] = true;
    6.16 -    ++nodes;
    6.17 +  int node_cnt = 0;
    6.18 +  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
    6.19 +    FullGraph::Node node = *it;
    6.20 +    if (used[node]) return false;
    6.21 +    used[node] = true;
    6.22 +    ++node_cnt;
    6.23    }
    6.24    
    6.25 -  return (nodes == gr.nodeNum());
    6.26 +  return (node_cnt == gr.nodeNum());
    6.27  }
    6.28  
    6.29  // Checks tour validity
    6.30 -bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) {
    6.31 +bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
    6.32    FullGraph::NodeMap<bool> used(gr, false);
    6.33    
    6.34    if (!checkPath(gr, p)) return false;
    6.35 @@ -134,21 +136,24 @@
    6.36      check(alg.run() == esize, alg_name + ": Wrong total cost");
    6.37      check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
    6.38  
    6.39 -    std::list<Node> list;
    6.40 -    std::vector<Node> vec;
    6.41 -    alg.tourNodes(list);
    6.42 -    alg.tourNodes(vec);
    6.43 -    check(list.size() == nsize, alg_name + ": Wrong node sequence");
    6.44 -    check(vec.size() == nsize,  alg_name + ": Wrong node sequence");
    6.45 -    check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence");
    6.46 -    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
    6.47 -    check(checkCost(g, vec, constMap<Edge, int>(1), esize),
    6.48 +    std::list<Node> list1(nsize), list2;
    6.49 +    std::vector<Node> vec1(nsize), vec2;
    6.50 +    alg.tourNodes(list1.begin());
    6.51 +    alg.tourNodes(vec1.begin());
    6.52 +    alg.tourNodes(std::front_inserter(list2));
    6.53 +    alg.tourNodes(std::back_inserter(vec2));
    6.54 +    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
    6.55 +    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
    6.56 +    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
    6.57 +    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
    6.58 +    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
    6.59 +    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
    6.60        alg_name + ": Wrong tour cost");
    6.61  
    6.62      SimplePath<FullGraph> path;
    6.63      alg.tour(path);
    6.64      check(path.length() == esize, alg_name + ": Wrong tour");
    6.65 -    check(checkTour(g, path), alg_name + ": Wrong tour");
    6.66 +    check(checkTourPath(g, path), alg_name + ": Wrong tour");
    6.67      check(checkCost(g, path, constMap<Edge, int>(1), esize),
    6.68        alg_name + ": Wrong tour cost");
    6.69    }
    6.70 @@ -180,14 +185,14 @@
    6.71      check(alg.run() > 0, alg_name + ": Wrong total cost");
    6.72  
    6.73      std::vector<Node> vec;
    6.74 -    alg.tourNodes(vec);
    6.75 +    alg.tourNodes(std::back_inserter(vec));
    6.76      check(checkTour(g, vec), alg_name + ": Wrong node sequence");
    6.77      check(checkCost(g, vec, cost, alg.tourCost()),
    6.78        alg_name + ": Wrong tour cost");
    6.79  
    6.80      SimplePath<FullGraph> path;
    6.81      alg.tour(path);
    6.82 -    check(checkTour(g, path), alg_name + ": Wrong tour");
    6.83 +    check(checkTourPath(g, path), alg_name + ": Wrong tour");
    6.84      check(checkCost(g, path, cost, alg.tourCost()),
    6.85        alg_name + ": Wrong tour cost");
    6.86