diff options
Diffstat (limited to 'src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h')
-rw-r--r-- | src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h | 390 |
1 files changed, 390 insertions, 0 deletions
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h new file mode 100644 index 00000000..920f8cb6 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -0,0 +1,390 @@ +/* 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_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ + +#include <gudhi/Skeleton_blocker_link_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h> +#include <gudhi/Skeleton_blocker/internal/Trie.h> +#include <gudhi/Debug_utils.h> + +#include <boost/iterator/iterator_facade.hpp> + +#include <memory> +#include <list> +#include <iostream> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + * Link may be Skeleton_blocker_link_complex<SkeletonBlockerComplex> to iterate over all + * simplices around a vertex OR + * Skeleton_blocker_superior_link_complex<SkeletonBlockerComplex> to iterate over all + * superior vertices around a vertex. + * The iteration is done by computing a trie with the link and doing a breadth-first traversal + * of the trie. + */ +template<typename SkeletonBlockerComplex, typename Link> +class Simplex_around_vertex_iterator : +public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> +, typename SkeletonBlockerComplex::Simplex +, boost::forward_traversal_tag +, typename SkeletonBlockerComplex::Simplex +> { + friend class boost::iterator_core_access; + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex Simplex; + + // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion + typedef typename Link::Vertex_handle Link_vertex_handle; + + typedef typename Gudhi::skeleton_blocker::Trie<Simplex> Trie; + + private: + const Complex* complex; + Vertex_handle v; + std::shared_ptr<Link> link_v; + std::shared_ptr<Trie> trie; + // TODO(DS): use a deque instead + std::list<Trie*> nodes_to_be_seen; + + public: + Simplex_around_vertex_iterator() : complex(0) { } + + Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_) : + complex(complex_), + v(v_), + link_v(new Link(*complex_, v_)), + trie(new Trie(v_)) { + compute_trie_and_nodes_to_be_seen(); + } + + // TODO(DS): avoid useless copy + // TODO(DS): currently just work if copy begin iterator + Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other) : + complex(other.complex), + v(other.v), + link_v(other.link_v), + trie(other.trie), + nodes_to_be_seen(other.nodes_to_be_seen) { + if (!other.is_end()) { + } + } + + /** + * returns an iterator to the end + */ + Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_, bool end) : + complex(complex_), + v(v_) { + set_end(); + } + + private: + void compute_trie_and_nodes_to_be_seen() { + // once we go through every simplices passing through v0 + // we remove v0. That way, it prevents from passing a lot of times + // though edges leaving v0. + // another solution would have been to provides an adjacency iterator + // to superior vertices that avoids lower ones. + while (!link_v->empty()) { + auto v0 = *(link_v->vertex_range().begin()); + trie->add_child(build_trie(v0, trie.get())); + link_v->remove_vertex(v0); + } + nodes_to_be_seen.push_back(trie.get()); + } + + Trie* build_trie(Link_vertex_handle link_vh, Trie* parent) { + Trie* res = new Trie(parent_vertex(link_vh), parent); + for (Link_vertex_handle nv : link_v->vertex_range(link_vh)) { + if (link_vh < nv) { + Simplex simplex_node_plus_nv(res->simplex()); + simplex_node_plus_nv.add_vertex(parent_vertex(nv)); + if (complex->contains(simplex_node_plus_nv)) { + res->add_child(build_trie(nv, res)); + } + } + } + return res; + } + + bool is_node_in_complex(Trie* trie) { + return true; + } + + Vertex_handle parent_vertex(Link_vertex_handle link_vh) const { + return complex->convert_handle_from_another_complex(*link_v, link_vh); + } + + public: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_around_vertex_iterator& savi) { + stream << savi.trie << std::endl; + stream << "(" << savi.nodes_to_be_seen.size() << ") nodes to see\n"; + return stream; + } + + bool equal(const Simplex_around_vertex_iterator& other) const { + bool same_complex = (complex == other.complex); + if (!same_complex) + return false; + + if (!(v == other.v)) + return false; + + bool both_empty = nodes_to_be_seen.empty() && other.nodes_to_be_seen.empty(); + if (both_empty) + return true; + + bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty(); + + // one is empty the other is not + if (!both_non_empty) return false; + + bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin())); + return same_node; + } + + void increment() { + assert(!is_end()); + Trie* first_node = nodes_to_be_seen.front(); + + nodes_to_be_seen.pop_front(); + + for (auto childs : first_node->childs) { + nodes_to_be_seen.push_back(childs.get()); + } + } + + Simplex dereference() const { + assert(!nodes_to_be_seen.empty()); + Trie* first_node = nodes_to_be_seen.front(); + return first_node->simplex(); + } + + Simplex get_trie_address() const { + assert(!nodes_to_be_seen.empty()); + return nodes_to_be_seen.front(); + } + + private: + void set_end() { + nodes_to_be_seen.clear(); + } + + bool is_end() const { + return nodes_to_be_seen.empty(); + } +}; + +template<typename SkeletonBlockerComplex> +class Simplex_iterator : +public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> +, typename SkeletonBlockerComplex::Simplex +, boost::forward_traversal_tag +, typename SkeletonBlockerComplex::Simplex +> { + typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link; + + friend class boost::iterator_core_access; + + template<class SkBlDS> friend class Skeleton_blocker_complex; + + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex Simplex; + typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; + typedef typename Link::Vertex_handle Link_vertex_handle; + + private: + const Complex* complex_; + Complex_vertex_iterator current_vertex_; + + typedef Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> SAVI; + SAVI current_simplex_around_current_vertex_; + SAVI simplices_around_current_vertex_end_; + + public: + Simplex_iterator() : complex_(0) { } + + Simplex_iterator(const Complex* complex) : + complex_(complex), + current_vertex_(complex->vertex_range().begin()), + current_simplex_around_current_vertex_(complex, *current_vertex_), + simplices_around_current_vertex_end_(complex, *current_vertex_, true) { + // should not be called if the complex is empty + assert(!complex->empty()); + } + + private: + Simplex_iterator(const Complex* complex, bool end) : + complex_(complex) { + set_end(); + } + + public: + Simplex_iterator(const Simplex_iterator& other) + : + complex_(other.complex_), + current_vertex_(other.current_vertex_), + current_simplex_around_current_vertex_(other.current_simplex_around_current_vertex_), + simplices_around_current_vertex_end_(other.simplices_around_current_vertex_end_) { } + + friend Simplex_iterator make_begin_iterator(const Complex* complex) { + if (complex->empty()) + return make_end_simplex_iterator(complex); + else + return Simplex_iterator(complex); + } + + friend Simplex_iterator make_end_simplex_iterator(const Complex* complex) { + return Simplex_iterator(complex, true); + } + + bool equal(const Simplex_iterator& other) const { + if (complex_ != other.complex_) return false; + if (current_vertex_ != other.current_vertex_) return false; + if (is_end() && other.is_end()) return true; + if (current_simplex_around_current_vertex_ != other.current_simplex_around_current_vertex_) + return false; + return true; + } + + void increment() { + if (current_simplex_around_current_vertex_ != simplices_around_current_vertex_end_) { + current_simplex_around_current_vertex_.increment(); + if (current_simplex_around_current_vertex_ == simplices_around_current_vertex_end_) + goto_next_vertex(); + } else { + goto_next_vertex(); + } + } + + void goto_next_vertex() { + current_vertex_.increment(); + if (!is_end()) { + current_simplex_around_current_vertex_ = SAVI(complex_, *current_vertex_); + simplices_around_current_vertex_end_ = SAVI(complex_, *current_vertex_, true); + } + } + + Simplex dereference() const { + return current_simplex_around_current_vertex_.dereference(); + } + + private: + void set_end() { + current_vertex_ = complex_->vertex_range().end(); + } + + bool is_end() const { + return (current_vertex_ == complex_->vertex_range().end()); + } +}; + +/** + * Iterator through the maximal faces of the coboundary of a simplex. + */ +template<typename SkeletonBlockerComplex, typename Link> +class Simplex_coboundary_iterator : +public boost::iterator_facade < Simplex_coboundary_iterator<SkeletonBlockerComplex, Link> +, typename SkeletonBlockerComplex::Simplex, boost::forward_traversal_tag, typename SkeletonBlockerComplex::Simplex> { + friend class boost::iterator_core_access; + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex Simplex; + typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; + + // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion + typedef typename Link::Vertex_handle Link_vertex_handle; + + private: + const Complex* complex; + const Simplex& sigma; + std::shared_ptr<Link> link; + Complex_vertex_iterator current_vertex; + Complex_vertex_iterator link_vertex_end; + + public: + Simplex_coboundary_iterator() : complex(0) { } + + Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_) : + complex(complex_), + sigma(sigma_), + // need only vertices of the link hence the true flag + link(new Link(*complex_, sigma_, false, true)) { + auto link_vertex_range = link->vertex_range(); + current_vertex = link_vertex_range.begin(); + link_vertex_end = link_vertex_range.end(); + } + + Simplex_coboundary_iterator(const Simplex_coboundary_iterator& other) : + complex(other.complex), + sigma(other.sigma), + link(other.link), + current_vertex(other.current_vertex), + link_vertex_end(other.link_vertex_end) { } + + // returns an iterator to the end + Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_, bool end) : + complex(complex_), + sigma(sigma_) { + // to represent an end iterator without having to build a useless link, we use + // the convection that link is not initialized. + } + + private: + Vertex_handle parent_vertex(Link_vertex_handle link_vh) const { + return complex->convert_handle_from_another_complex(*link, link_vh); + } + + public: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_coboundary_iterator& sci) { + return stream; + } + + // assume that iterator points to the same complex and comes from the same simplex + bool equal(const Simplex_coboundary_iterator& other) const { + assert(complex == other.complex && sigma == other.sigma); + if (is_end()) return other.is_end(); + if (other.is_end()) return is_end(); + return *current_vertex == *(other.current_vertex); + } + + void increment() { + ++current_vertex; + } + + Simplex dereference() const { + Simplex res(sigma); + res.add_vertex(parent_vertex(*current_vertex)); + return res; + } + + private: + bool is_end() const { + return !link || current_vertex == link_vertex_end; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ |