before rm Grid_Cell

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

Former-commit-id: bfa8c56429a2d4a9f38822ac9cfbe4c4b360cede

5 files changed, 39 insertions, 51 deletions

diff --git a/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h b/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h
index 9cd8d75a..5133646d 100644
--- a/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h
+++ b/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h
@@ -24,8 +24,6 @@
 #define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_
 
 #include <deque>
-#include <list>
-#include <vector>
 
 #include "Neighbors_finder.h"
 
diff --git a/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h b/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h
index 8745e6eb..f0b09b52 100644
--- a/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h
+++ b/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h
@@ -33,10 +33,7 @@ namespace Gudhi {
 
 namespace bipartite_graph_matching {
 
-/** \internal \brief TODO
- *
- * \ingroup bottleneck_distance
- */
+
 class Grid_cell {
 public:
     Grid_cell(double r);
@@ -139,7 +136,7 @@ inline int Grid_cell::pull_yi(int u_point_index){
 inline int Grid_cell::pull_yd(int u_point_index){
     return pull_contiguous_aux(yi_order, true, u_point_index);
 }
-/*
+
 inline int Grid_cell::pull_corner_aux(Corner_tree t, bool reverse, int u_point_index){
      if(xi_order.empty())
         return null_point_index();
@@ -158,7 +155,7 @@ inline int Grid_cell::pull_corner_aux(Corner_tree t, bool reverse, int u_point_i
         return v_point_index;
     }
     return null_point_index();
-}*/
+}
 
 inline int Grid_cell::pull_xi_yi(int u_point_index){
     for(auto it = xi_order.begin(); it!=xi_order.end(); ++it)
@@ -210,3 +207,4 @@ inline int Grid_cell::pull_xd_yd(int u_point_index){
 }  // namespace Gudhi
 
 #endif  // SRC_BOTTLENECK_INCLUDE_GUDHI_GRID_CELL_H_
+
diff --git a/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h b/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h
index cae47793..78b9debc 100644
--- a/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h
+++ b/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h
@@ -24,7 +24,6 @@
 #define SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_
 
 #include <unordered_set>
-#include <list>
 
 #include "Planar_neighbors_finder.h"
 
diff --git a/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h b/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h
index 1b23a1b2..a1fe9285 100644
--- a/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h
+++ b/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h
@@ -61,10 +61,6 @@ public:
     static int size();
     /** \internal \brief Returns the O(n^2) sorted distances between the points. */
     static std::unique_ptr< std::vector<double> > sorted_distances();
-    /** \internal \brief Compare points regarding x%r coordinate. Use v_point_index for V points and u_point_index + G::size() for U points.  */
-    struct Compare_x{double r; Compare_x(double r); bool operator()(const int point_index_1, const int point_index_2) const;};
-    /** \internal \brief Compare points regarding y%r coordinate. Use v_point_index for V points and u_point_index + G::size() for U points. */
-    struct Compare_y{double r; Compare_y(double r);bool operator()(const int point_index_1, const int point_index_2) const;};
 
 private:
     /** \internal \typedef \brief Internal_point is the internal points representation, indexes used outside. */
@@ -73,6 +69,8 @@ private:
     static std::vector<Internal_point> v;
     static Internal_point get_u_point(int u_point_index);
     static Internal_point get_v_point(int v_point_index);
+
+    friend class Naive_pnf;
 };
 
 /** \internal \typedef \brief Shorter alias */
@@ -157,32 +155,6 @@ inline G::Internal_point G::get_v_point(int v_point_index) {
     return Internal_point(x, x);
 }
 
-G::Compare_x::Compare_x(double r)
-    : r(r){ }
-
-G::Compare_y::Compare_y(double r)
-    : r(r){ }
-
-inline bool G::Compare_x::operator()(const int point_index_1, const int point_index_2) const{
-    G::Internal_point p1 = point_index_1 < G::size() ? G::get_v_point(point_index_1) : G::get_u_point(point_index_1 - G::size());
-    G::Internal_point p2 = point_index_2 < G::size() ? G::get_v_point(point_index_2) : G::get_u_point(point_index_2 - G::size());
-    double x1 = fmod(p1.first,r);
-    double x2 = fmod(p2.first,r);
-    if(x1 == x2)
-        return point_index_1 > point_index_2;
-    return x1 < x2;
-}
-
-inline bool G::Compare_y::operator()(const int point_index_1, const int point_index_2) const{
-    G::Internal_point p1 = point_index_1 < G::size() ? G::get_v_point(point_index_1) : G::get_u_point(point_index_1 - G::size());
-    G::Internal_point p2 = point_index_2 < G::size() ? G::get_v_point(point_index_2) : G::get_u_point(point_index_2 - G::size());
-    double y1 = fmod(p1.second,r);
-    double y2 = fmod(p2.second,r);
-    if(y1 == y2)
-        return  point_index_1 > point_index_2;
-    return y1 < y2;
-}
-
 }  // namespace bipartite_graph_matching
 
 }  // namespace Gudhi
diff --git a/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h b/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h
index 60a1dd96..50829be6 100644
--- a/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h
+++ b/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h
@@ -24,7 +24,7 @@
 #define SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_
 
 #include <list>
-#include <set>
+#include <map>
 
 #include "Persistence_diagrams_graph.h"
 #include "Grid_cell.h"
@@ -78,7 +78,8 @@ public:
     int pull_near(int u_point_index);
 
 private:
-    std::set<int> candidates;
+    std::pair<int,int> get_v_key(int v_point_index) const;
+    std::multimap<std::pair<int,int>,int> grid;
 };
 
 /** \internal \typedef \brief Planar_neighbors_finder is the used Abstract_planar_neighbors_finder's implementation. */
@@ -101,27 +102,47 @@ inline std::unique_ptr< std::list<int> > Abstract_planar_neighbors_finder::pull_
 }
 
 inline Naive_pnf::Naive_pnf(double r) :
-    Abstract_planar_neighbors_finder(r), candidates() { }
+    Abstract_planar_neighbors_finder(r), grid() { }
+
+
+inline std::pair<int,int> Naive_pnf::get_v_key(int v_point_index) const{
+    G::Internal_point v_point = G::get_v_point(v_point_index);
+    return std::make_pair(static_cast<int>(v_point.first/r), static_cast<int>(v_point.second/r));
+}
 
 inline void Naive_pnf::add(int v_point_index) {
-    candidates.emplace(v_point_index);
+    grid.emplace(get_v_key(v_point_index),v_point_index);
 }
 
 inline void Naive_pnf::remove(int v_point_index) {
-    candidates.erase(v_point_index);
+    for(auto it = grid.find(get_v_key(v_point_index)); it!=grid.end(); it++)
+        if(it->second==v_point_index){
+            grid.erase(it);
+            return;
+        }
 }
 
 inline bool Naive_pnf::contains(int v_point_index) const {
-    return (candidates.count(v_point_index) > 0);
+    if(v_point_index == null_point_index())
+        return false;
+    for(auto it = grid.find(get_v_key(v_point_index)); it!=grid.end(); it++)
+        if(it->second==v_point_index)
+            return true;
+    return false;
 }
 
 inline int Naive_pnf::pull_near(int u_point_index) {
-    for (auto it = candidates.begin(); it != candidates.end(); ++it)
-        if (G::distance(u_point_index, *it) <= r) {
-            int tmp = *it;
-            candidates.erase(it);
-            return tmp;
-        }
+    G::Internal_point u_point = G::get_u_point(u_point_index);
+    int i0 = static_cast<int>(u_point.first/r);
+    int j0 = static_cast<int>(u_point.second/r);
+    for(int i = i0 -1; i<= i0 + 1; i++)
+        for(int j = j0 -1; j<= j0 + 1; j++)
+            for(auto it = grid.find(std::make_pair(i,j)); it!=grid.end(); it++)
+                if (G::distance(u_point_index, it->second) <= r) {
+                    int tmp = it->second;
+                    grid.erase(it);
+                    return tmp;
+                }
     return null_point_index();
 }