Revert previous commit, was supposed to go to a branch !!!

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@2106 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 59183c46120a19ad0a840dd57b7a4706a4d44bdd

2 files changed, 45 insertions, 55 deletions

diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
index a77d0cd7..5e908090 100644
--- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h
+++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
@@ -25,10 +25,16 @@
 
 #include <boost/range.hpp>
 
-#include <gudhi/Null_output_iterator.h>
+#include <gudhi/Kd_tree_search.h>
+
 #include <gudhi/Clock.h>
 
+#include <CGAL/Search_traits.h>
+#include <CGAL/Search_traits_adapter.h>
+#include <CGAL/Fuzzy_sphere.h>
+
 #include <iterator>
+#include <algorithm>  // for sort
 #include <vector>
 #include <random>
 #include <limits>  // for numeric_limits<>
@@ -41,7 +47,7 @@ namespace subsampling {
  *  \ingroup subsampling
  *  \brief Subsample by a greedy strategy of iteratively adding the farthest point from the
  *  current chosen point set to the subsampling. 
- *  The iteration starts with the landmark `starting point` or, if `starting point==-1`, with a random landmark.
+ *  The iteration starts with the landmark `starting point`.
  *  \tparam Kernel must provide a type Kernel::Squared_distance_d which is a model of the 
  *          concept <a target="_blank"
  *   href="http://doc.cgal.org/latest/Kernel_d/classKernel__d_1_1Squared__distance__d.html">Kernel_d::Squared_distance_d</a>
@@ -49,30 +55,24 @@ namespace subsampling {
  *  It must also contain a public member 'squared_distance_d_object' of this type.
  *  \tparam Point_range Range whose value type is Kernel::Point_d.  It must provide random-access 
  *         via `operator[]` and the points should be stored contiguously in memory.
- *  \tparam PointOutputIterator Output iterator whose value type is Kernel::Point_d.
- *  \tparam DistanceOutputIterator Output iterator for distances.
- *  \details It chooses `final_size` points from a random access range
- *  `input_pts` and outputs them in the output iterator `output_it`. It also
- *  outputs the distance from each of those points to the set of previous
- *  points in `dist_it`.
+ *  \tparam OutputIterator Output iterator whose value type is Kernel::Point_d.
+ *  \details It chooses `final_size` points from a random access range `input_pts` and
+ *  outputs it in the output iterator `output_it`.
  * @param[in] k A kernel object.
  * @param[in] input_pts Const reference to the input points.
  * @param[in] final_size The size of the subsample to compute.
  * @param[in] starting_point The seed in the farthest point algorithm.
- * @param[out] output_it The output iterator for points.
- * @param[out] dist_it The optional output iterator for distances.
+ * @param[out] output_it The output iterator.
  *  
  */
 template < typename Kernel,
 typename Point_range,
-typename PointOutputIterator,
-typename DistanceOutputIterator=Null_output_iterator>
+typename OutputIterator>
 void choose_n_farthest_points(Kernel const &k,
                               Point_range const &input_pts,
                               std::size_t final_size,
                               std::size_t starting_point,
-                              PointOutputIterator output_it,
-                              DistanceOutputIterator dist_it={}) {
+                              OutputIterator output_it) {
   std::size_t nb_points = boost::size(input_pts);
   if (final_size > nb_points)
     final_size = nb_points;
@@ -81,14 +81,6 @@ void choose_n_farthest_points(Kernel const &k,
   if (final_size < 1)
     return;
 
-  if (starting_point == std::size_t(-1)) {
-    // Choose randomly the first landmark
-    std::random_device rd;
-    std::mt19937 gen(rd());
-    std::uniform_int_distribution<std::size_t> dis(0, (input_pts.size() - 1));
-    starting_point = dis(gen);
-  }
-
   typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
 
   std::size_t current_number_of_landmarks = 0;  // counter for landmarks
@@ -100,7 +92,6 @@ void choose_n_farthest_points(Kernel const &k,
   for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
     // curr_max_w at this point is the next landmark
     *output_it++ = input_pts[curr_max_w];
-    *dist_it++ = dist_to_L[curr_max_w];
     std::size_t i = 0;
     for (auto& p : input_pts) {
       double curr_dist = sqdist(p, *(std::begin(input_pts) + curr_max_w));
@@ -130,7 +121,7 @@ void choose_n_farthest_points(Kernel const &k,
  *  It must also contain a public member 'squared_distance_d_object' of this type.
  *  \tparam Point_range Range whose value type is Kernel::Point_d.  It must provide random-access 
  *         via `operator[]` and the points should be stored contiguously in memory.
- *  \tparam PointOutputIterator Output iterator whose value type is Kernel::Point_d.
+ *  \tparam OutputIterator Output iterator whose value type is Kernel::Point_d.
  *  \details It chooses `final_size` points from a random access range `input_pts` and
  *  outputs it in the output iterator `output_it`.
  * @param[in] k A kernel object.
@@ -141,12 +132,22 @@ void choose_n_farthest_points(Kernel const &k,
  */
 template < typename Kernel,
 typename Point_range,
-typename PointOutputIterator>
+typename OutputIterator>
 void choose_n_farthest_points(Kernel const& k,
                               Point_range const &input_pts,
-                              std::size_t final_size,
-                              PointOutputIterator output_it) {
-  choose_n_farthest_points(k, input_pts, final_size, -1, output_it);
+                              unsigned final_size,
+                              OutputIterator output_it) {
+  // Tests to the limit
+  if ((final_size < 1) || (input_pts.size() == 0))
+    return;
+
+  // Choose randomly the first landmark
+  std::random_device rd;
+  std::mt19937 gen(rd());
+  std::uniform_int_distribution<> dis(0, (input_pts.size() - 1));
+  std::size_t starting_point = dis(gen);
+
+  choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it);
 }
 
 }  // namespace subsampling
diff --git a/src/Subsampling/test/test_choose_n_farthest_points.cpp b/src/Subsampling/test/test_choose_n_farthest_points.cpp
index 6bc5f7b0..0bc0dff4 100644
--- a/src/Subsampling/test/test_choose_n_farthest_points.cpp
+++ b/src/Subsampling/test/test_choose_n_farthest_points.cpp
@@ -70,45 +70,34 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point_limits, Kernel, list_of
   typedef typename Kernel::FT FT;
   typedef typename Kernel::Point_d Point_d;
   std::vector< Point_d > points, landmarks;
-  std::vector< FT > distances;
   landmarks.clear();
   Kernel k;
   // Choose -1 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, std::back_inserter(landmarks));
   BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear(); distances.clear();
+  landmarks.clear();
   // Choose 0 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, std::back_inserter(landmarks));
   BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear(); distances.clear();
+  landmarks.clear();
   // Choose 1 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, std::back_inserter(landmarks));
   BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear(); distances.clear();
+  landmarks.clear();
 
   std::vector<FT> point({0.0, 0.0, 0.0, 0.0});
   points.push_back(Point_d(point.begin(), point.end()));
-  // Choose -1 farthest points in a one point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
-  BOOST_CHECK(landmarks.size() == 1 && distances.size() == 1);
-  BOOST_CHECK(distances[0] == std::numeric_limits<FT>::infinity());
-  landmarks.clear(); distances.clear();
+  // Choose -1 farthest points in an empty point cloud
+  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, std::back_inserter(landmarks));
+  BOOST_CHECK(landmarks.size() == 1);
+  landmarks.clear();
   // Choose 0 farthest points in a one point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances));
-  BOOST_CHECK(landmarks.size() == 0 && distances.size() == 0);
-  landmarks.clear(); distances.clear();
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, std::back_inserter(landmarks));
+  BOOST_CHECK(landmarks.size() == 0);
+  landmarks.clear();
   // Choose 1 farthest points in a one point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
-  BOOST_CHECK(landmarks.size() == 1 && distances.size() == 1);
-  BOOST_CHECK(distances[0] == std::numeric_limits<FT>::infinity());
-  landmarks.clear(); distances.clear();
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, std::back_inserter(landmarks));
+  BOOST_CHECK(landmarks.size() == 1);
+  landmarks.clear();
 
-  std::vector<FT> point2({1.0, 0.0, 0.0, 0.0});
-  points.push_back(Point_d(point2.begin(), point2.end()));
-  // Choose all farthest points in a one point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
-  BOOST_CHECK(landmarks.size() == 2 && distances.size() == 2);
-  BOOST_CHECK(distances[0] == std::numeric_limits<FT>::infinity());
-  BOOST_CHECK(distances[1] == 1);
-  landmarks.clear(); distances.clear();
 }