Make annotations_in_boundary a vector, sorted once after construction, with entries sharing the same annotation accumulated as we go.

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

Former-commit-id: 34b2ae74dc017c18a90e08caee6f707b6b0d4cc2

1 files changed, 22 insertions, 11 deletions

diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
index d096792f..3875afc6 100644
--- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
+++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
@@ -431,9 +431,13 @@ class Persistent_cohomology {
       std::map<Simplex_key, Arith_element> & map_a_ds, Simplex_handle sigma,
       int dim_sigma) {
     // traverses the boundary of sigma, keeps track of the annotation vectors,
-    // with multiplicity, in a map.
-    std::map<Column *, int> annotations_in_boundary;
-    std::pair<typename std::map<Column *, int>::iterator, bool> result_insert_bound;
+    // with multiplicity.
+#if 0
+    std::vector<std::pair<Column *, int>> annotations_in_boundary;
+#else
+    static std::vector<std::pair<Column *, int>> annotations_in_boundary;
+    annotations_in_boundary.clear();
+#endif
     int sign = 1 - 2 * (dim_sigma % 2);  // \in {-1,1} provides the sign in the
                                          // alternate sum in the boundary.
     Simplex_key key;
@@ -445,22 +449,29 @@ class Persistent_cohomology {
         // Find its annotation vector
         curr_col = ds_repr_[dsets_.find_set(key)];
         if (curr_col != NULL) {  // and insert it in annotations_in_boundary with multyiplicative factor "sign".
-          result_insert_bound = annotations_in_boundary.insert(std::pair<Column *, int>(curr_col, sign));
-          if (!(result_insert_bound.second)) {
-            result_insert_bound.first->second += sign;
-          }
+	  annotations_in_boundary.emplace_back(curr_col, sign);
         }
       }
       sign = -sign;
     }
+    std::sort(annotations_in_boundary.begin(),annotations_in_boundary.end(),[](auto&a,auto&b){return a.first<b.first;});
     // Sum the annotations with multiplicity, using a map<key,coeff>
     // to represent a sparse vector.
     std::pair<typename std::map<Simplex_key, Arith_element>::iterator, bool> result_insert_a_ds;
 
-    for (auto ann_ref : annotations_in_boundary) {
-      if (ann_ref.second != coeff_field_.additive_identity()) {  // For all columns in the boundary,
-        for (auto cell_ref : ann_ref.first->col_) {  // insert every cell in map_a_ds with multiplicity
-          Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, ann_ref.second);  // coefficient * multiplicity
+    auto ann_it = annotations_in_boundary.begin();
+    while (ann_it != annotations_in_boundary.end()) {
+      auto col = ann_it->first;
+      int coef = ann_it->second;
+      for (;;) {
+	if (++ann_it == annotations_in_boundary.end() || ann_it->first != col)
+	  break;
+	coef += ann_it->second;
+      }
+      // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0.
+      if (coef != coeff_field_.additive_identity()) {  // For all columns in the boundary,
+        for (auto cell_ref : col->col_) {  // insert every cell in map_a_ds with multiplicity
+          Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, coef);  // coefficient * multiplicity
 
           if (w_y != coeff_field_.additive_identity()) {  // if != 0
             result_insert_a_ds = map_a_ds.insert(std::pair<Simplex_key, Arith_element>(cell_ref.key_, w_y));