1 files changed, 362 insertions, 0 deletions
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h
new file mode 100644
index 00000000..12fe6469
--- /dev/null
+++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h
@@ -0,0 +1,362 @@
+/*    This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ *    See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ *    Author(s):       David Salinas
+ *
+ *    Copyright (C) 2014 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_
+#define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_
+
+#include <cassert>
+#include <iostream>
+#include <set>
+#include <vector>
+#include <initializer_list>
+#include <string>
+#include <algorithm>
+
+namespace Gudhi {
+
+namespace skeleton_blocker {
+
+/**
+ *@brief Abstract simplex used in Skeleton blockers data-structure.
+ *
+ * An abstract simplex is represented as an ordered set of T elements,
+ * each element representing a vertex.
+ * 
+ * The element representing a vertex can be SkeletonBlockerDS::Vertex_handle or SkeletonBlockerDS::Root_vertex_handle.
+ *
+ *
+ */
+template<typename T>
+
+class Skeleton_blocker_simplex {
+ private:
+  std::set<T> simplex_set;
+
+ public:
+  typedef typename T::boost_vertex_handle boost_vertex_handle;
+
+  typedef T Vertex_handle;
+
+  typedef typename std::set<T>::const_iterator Simplex_vertex_const_iterator;
+  typedef typename std::set<T>::iterator Simplex_vertex_iterator;
+
+  /** @name Constructors / Destructors / Initialization
+   */
+  //@{
+
+  void clear() {
+    simplex_set.clear();
+  }
+
+  Skeleton_blocker_simplex(std::initializer_list<T>& list) {
+    std::for_each(list.begin(), list.end(), [&] (T const& elt) {
+      add_vertex(elt);
+    });
+  }
+
+  template<typename ... Args>
+  explicit Skeleton_blocker_simplex(Args ... args) {
+    add_vertices(args...);
+  }
+
+  template<typename ... Args>
+  void add_vertices(T v, Args ... args) {
+    add_vertex(v);
+    add_vertices(args...);
+  }
+
+  void add_vertices(T v) {
+    add_vertex(v);
+  }
+
+  void add_vertices() { }
+
+  /**
+   * Initialize a simplex with a string such as {0,1,2}
+   */
+  explicit Skeleton_blocker_simplex(std::string token) {
+    clear();
+    if ((token[0] == '{') && (token[token.size() - 1] == '}')) {
+      token.erase(0, 1);
+      token.erase(token.size() - 1, 1);
+      while (token.size() != 0) {
+        int coma_position = token.find_first_of(',');
+        // cout << "coma_position:"<<coma_position<<endl;
+        std::string n = token.substr(0, coma_position);
+        // cout << "token:"<<token<<endl;
+        token.erase(0, n.size() + 1);
+        add_vertex((T) (atoi(n.c_str())));
+      }
+    }
+  }
+
+  //@}
+
+  /** @name Simplex manipulation
+   */
+  //@{
+  /**
+   * Add the vertex v to the simplex:
+   * Note that adding two times the same vertex is
+   * the same that adding it once.
+   */
+  void add_vertex(T v) {
+    simplex_set.insert(v);
+  }
+
+  /**
+   * Remove the vertex v from the simplex:
+   */
+  void remove_vertex(T v) {
+    simplex_set.erase(v);
+  }
+
+  /**
+   * Intersects the simplex with the simplex a.
+   */
+  void intersection(const Skeleton_blocker_simplex & a) {
+    std::vector<T> v;
+    v.reserve((std::min)(simplex_set.size(), a.simplex_set.size()));
+
+    set_intersection(simplex_set.begin(), simplex_set.end(),
+                     a.simplex_set.begin(), a.simplex_set.end(),
+                     std::back_inserter(v));
+    clear();
+    for (auto i : v)
+      simplex_set.insert(i);
+  }
+
+  /**
+   * Substracts a from the simplex.
+   */
+  void difference(const Skeleton_blocker_simplex & a) {
+    std::vector<T> v;
+    v.reserve(simplex_set.size());
+
+    set_difference(simplex_set.begin(), simplex_set.end(),
+                   a.simplex_set.begin(), a.simplex_set.end(),
+                   std::back_inserter(v));
+
+    clear();
+    for (auto i : v)
+      simplex_set.insert(i);
+  }
+
+  /**
+   * Add vertices of a to the simplex.
+   */
+  void union_vertices(const Skeleton_blocker_simplex & a) {
+    std::vector<T> v;
+    v.reserve(simplex_set.size() + a.simplex_set.size());
+
+    set_union(simplex_set.begin(), simplex_set.end(), a.simplex_set.begin(),
+              a.simplex_set.end(), std::back_inserter(v));
+    clear();
+    simplex_set.insert(v.begin(), v.end());
+  }
+
+  typename std::set<T>::const_iterator begin() const {
+    return simplex_set.cbegin();
+  }
+
+  typename std::set<T>::const_iterator end() const {
+    return simplex_set.cend();
+  }
+
+  typename std::set<T>::const_reverse_iterator rbegin() const {
+    return simplex_set.crbegin();
+  }
+
+  typename std::set<T>::const_reverse_iterator rend() const {
+    return simplex_set.crend();
+  }
+
+  typename std::set<T>::iterator begin() {
+    return simplex_set.begin();
+  }
+
+  typename std::set<T>::iterator end() {
+    return simplex_set.end();
+  }
+
+  //@}
+
+  /** @name Queries
+   */
+  //@{
+  /**
+   * Returns the dimension of the simplex.
+   */
+  int dimension() const {
+    return (simplex_set.size() - 1);
+  }
+
+  bool empty() const {
+    return simplex_set.empty();
+  }
+
+  /**
+   * Returns the first and smallest vertex of the simplex.
+   *
+   * Be careful : assumes the simplex is non-empty.
+   */
+  T first_vertex() const {
+    assert(!empty());
+    return *(begin());
+  }
+
+  /**
+   * Returns the last and greatest vertex of the simplex.
+   *
+   * Be careful : assumes the simplex is non-empty.
+   */
+  T last_vertex() const {
+    assert(!empty());
+    return *(simplex_set.rbegin());
+  }
+
+  /**
+   * @return true iff the simplex contains the simplex a.
+   */
+  bool contains(const Skeleton_blocker_simplex & a) const {
+    return includes(simplex_set.cbegin(), simplex_set.cend(),
+                    a.simplex_set.cbegin(), a.simplex_set.cend());
+  }
+
+  /**
+   * @return true iff the simplex contains the difference \f$ a \setminus b \f$.
+   */
+  bool contains_difference(const Skeleton_blocker_simplex& a,
+                           const Skeleton_blocker_simplex& b) const {
+    auto first1 = begin();
+    auto last1 = end();
+
+    auto first2 = a.begin();
+    auto last2 = a.end();
+
+    while (first2 != last2) {
+      // we ignore vertices of b
+      if (b.contains(*first2)) {
+        ++first2;
+      } else {
+        if ((first1 == last1) || (*first2 < *first1))
+          return false;
+        if (!(*first1 < *first2))
+          ++first2;
+        ++first1;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * @return true iff the simplex contains the difference \f$ a \setminus \{ x \} \f$.
+   */
+  bool contains_difference(const Skeleton_blocker_simplex& a, T x) const {
+    auto first1 = begin();
+    auto last1 = end();
+
+    auto first2 = a.begin();
+    auto last2 = a.end();
+
+    while (first2 != last2) {
+      // we ignore vertices x
+      if (x == *first2) {
+        ++first2;
+      } else {
+        if ((first1 == last1) || (*first2 < *first1))
+          return false;
+        if (!(*first1 < *first2))
+          ++first2;
+        ++first1;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * @return true iff the simplex contains the difference \f$ a \setminus \{ x,y \} \f$.
+   */
+  bool contains_difference(const Skeleton_blocker_simplex& a, T x, T y) const {
+    auto first1 = begin();
+    auto last1 = end();
+
+    auto first2 = a.begin();
+    auto last2 = a.end();
+
+    while (first2 != last2) {
+      // we ignore vertices of x,y
+      if (x == *first2 || y == *first2) {
+        ++first2;
+      } else {
+        if ((first1 == last1) || (*first2 < *first1))
+          return false;
+        if (!(*first1 < *first2))
+          ++first2;
+        ++first1;
+      }
+    }
+    return true;
+  }
+
+  bool contains(T v) const {
+    return (simplex_set.find(v) != simplex_set.end());
+  }
+
+  bool disjoint(const Skeleton_blocker_simplex& a) const {
+    std::vector<T> v;
+    v.reserve(std::min(simplex_set.size(), a.simplex_set.size()));
+
+    set_intersection(simplex_set.cbegin(), simplex_set.cend(),
+                     a.simplex_set.cbegin(), a.simplex_set.cend(),
+                     std::back_inserter(v));
+
+    return (v.size() == 0);
+  }
+
+  bool operator==(const Skeleton_blocker_simplex& other) const {
+    return (this->simplex_set == other.simplex_set);
+  }
+
+  bool operator!=(const Skeleton_blocker_simplex& other) const {
+    return (this->simplex_set != other.simplex_set);
+  }
+
+  bool operator<(const Skeleton_blocker_simplex& other) const {
+    return (std::lexicographical_compare(this->simplex_set.begin(),
+                                         this->simplex_set.end(), other.begin(),
+                                         other.end()));
+  }
+
+  //@}
+
+  friend std::ostream& operator<<(std::ostream& o,
+                                  const Skeleton_blocker_simplex & sigma) {
+    bool first = true;
+    o << "{";
+    for (auto i : sigma) {
+      if (first)
+        first = false;
+      else
+        o << ",";
+      o << i;
+    }
+    o << "}";
+    return o;
+  }
+};
+
+}  // namespace skeleton_blocker
+
+namespace skbl = skeleton_blocker;
+
+}  // namespace Gudhi
+
+#endif  // SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_