# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1362067994 -3600
# Node ID d3dcc49e64033041370e77c0c7488499bbf7241f
# Parent  dff32ce3db712f2d6e262e75fae4d9404798afa8
Use output iterator instead of a container (#386)
in tourNodes() functions of TSP algorithms

diff -r dff32ce3db71 -r d3dcc49e6403 lemon/christofides_tsp.h
--- a/lemon/christofides_tsp.h	Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/christofides_tsp.h	Thu Feb 28 17:13:14 2013 +0100
@@ -209,12 +209,23 @@
       /// \brief Gives back the node sequence of the found tour.
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
       
       /// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/greedy_tsp.h
--- a/lemon/greedy_tsp.h	Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/greedy_tsp.h	Thu Feb 28 17:13:14 2013 +0100
@@ -206,12 +206,23 @@
       /// \brief Gives back the node sequence of the found tour.
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
 
       /// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/insertion_tsp.h
--- a/lemon/insertion_tsp.h	Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/insertion_tsp.h	Thu Feb 28 17:13:14 2013 +0100
@@ -203,12 +203,23 @@
       /// \brief Gives back the node sequence of the found tour.
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_tour.begin(), _tour.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_tour.begin(), _tour.end(), out);
       }
 
       /// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/nearest_neighbor_tsp.h
--- a/lemon/nearest_neighbor_tsp.h	Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/nearest_neighbor_tsp.h	Thu Feb 28 17:13:14 2013 +0100
@@ -193,12 +193,23 @@
       /// \brief Gives back the node sequence of the found tour.
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
 
       /// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 lemon/opt2_tsp.h
--- a/lemon/opt2_tsp.h	Sun Jan 09 15:06:55 2011 +0100
+++ b/lemon/opt2_tsp.h	Thu Feb 28 17:13:14 2013 +0100
@@ -230,12 +230,23 @@
       /// \brief Gives back the node sequence of the found tour.
       ///
       /// This function copies the node sequence of the found tour into
-      /// the given standard container.
+      /// an STL container through the given output iterator. The
+      /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
+      /// For example,
+      /// \code
+      /// std::vector<FullGraph::Node> nodes(countNodes(graph));
+      /// tsp.tourNodes(nodes.begin());
+      /// \endcode
+      /// or
+      /// \code
+      /// std::list<FullGraph::Node> nodes;
+      /// tsp.tourNodes(std::back_inserter(nodes));
+      /// \endcode
       ///
       /// \pre run() must be called before using this function.
-      template <typename Container>
-      void tourNodes(Container &container) const {
-        container.assign(_path.begin(), _path.end());
+      template <typename Iterator>
+      void tourNodes(Iterator out) const {
+        std::copy(_path.begin(), _path.end(), out);
       }
 
       /// \brief Gives back the found tour as a path.
diff -r dff32ce3db71 -r d3dcc49e6403 test/tsp_test.cc
--- a/test/tsp_test.cc	Sun Jan 09 15:06:55 2011 +0100
+++ b/test/tsp_test.cc	Thu Feb 28 17:13:14 2013 +0100
@@ -61,21 +61,23 @@
 // }
 
 // Checks tour validity
-bool checkTour(const FullGraph &gr, const std::vector<FullGraph::Node> &p) {
+template <typename Container>
+bool checkTour(const FullGraph &gr, const Container &p) {
   FullGraph::NodeMap<bool> used(gr, false);
   
-  int nodes = 0;
-  for (int i = 0; i < int(p.size()); ++i) {
-    if (used[p[i]]) return false;
-    used[p[i]] = true;
-    ++nodes;
+  int node_cnt = 0;
+  for (typename Container::const_iterator it = p.begin(); it != p.end(); ++it) {
+    FullGraph::Node node = *it;
+    if (used[node]) return false;
+    used[node] = true;
+    ++node_cnt;
   }
   
-  return (nodes == gr.nodeNum());
+  return (node_cnt == gr.nodeNum());
 }
 
 // Checks tour validity
-bool checkTour(const FullGraph &gr, const Path<FullGraph> &p) {
+bool checkTourPath(const FullGraph &gr, const Path<FullGraph> &p) {
   FullGraph::NodeMap<bool> used(gr, false);
   
   if (!checkPath(gr, p)) return false;
@@ -134,21 +136,24 @@
     check(alg.run() == esize, alg_name + ": Wrong total cost");
     check(alg.tourCost() == esize, alg_name + ": Wrong total cost");
 
-    std::list<Node> list;
-    std::vector<Node> vec;
-    alg.tourNodes(list);
-    alg.tourNodes(vec);
-    check(list.size() == nsize, alg_name + ": Wrong node sequence");
-    check(vec.size() == nsize,  alg_name + ": Wrong node sequence");
-    check(alg.tourNodes().size() == nsize, alg_name + ": Wrong node sequence");
-    check(checkTour(g, vec), alg_name + ": Wrong node sequence");
-    check(checkCost(g, vec, constMap<Edge, int>(1), esize),
+    std::list<Node> list1(nsize), list2;
+    std::vector<Node> vec1(nsize), vec2;
+    alg.tourNodes(list1.begin());
+    alg.tourNodes(vec1.begin());
+    alg.tourNodes(std::front_inserter(list2));
+    alg.tourNodes(std::back_inserter(vec2));
+    check(checkTour(g, alg.tourNodes()), alg_name + ": Wrong node sequence");
+    check(checkTour(g, list1), alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec1), alg_name + ": Wrong node sequence");
+    check(checkTour(g, list2), alg_name + ": Wrong node sequence");
+    check(checkTour(g, vec2), alg_name + ": Wrong node sequence");
+    check(checkCost(g, vec1, constMap<Edge, int>(1), esize),
       alg_name + ": Wrong tour cost");
 
     SimplePath<FullGraph> path;
     alg.tour(path);
     check(path.length() == esize, alg_name + ": Wrong tour");
-    check(checkTour(g, path), alg_name + ": Wrong tour");
+    check(checkTourPath(g, path), alg_name + ": Wrong tour");
     check(checkCost(g, path, constMap<Edge, int>(1), esize),
       alg_name + ": Wrong tour cost");
   }
@@ -180,14 +185,14 @@
     check(alg.run() > 0, alg_name + ": Wrong total cost");
 
     std::vector<Node> vec;
-    alg.tourNodes(vec);
+    alg.tourNodes(std::back_inserter(vec));
     check(checkTour(g, vec), alg_name + ": Wrong node sequence");
     check(checkCost(g, vec, cost, alg.tourCost()),
       alg_name + ": Wrong tour cost");
 
     SimplePath<FullGraph> path;
     alg.tour(path);
-    check(checkTour(g, path), alg_name + ": Wrong tour");
+    check(checkTourPath(g, path), alg_name + ": Wrong tour");
     check(checkCost(g, path, cost, alg.tourCost()),
       alg_name + ": Wrong tour cost");