Skeleton_blockers_simplices_iterators.h

 /*    This file is part of the Gudhi Library. The Gudhi library
  *    (Geometric Understanding in Higher Dimensions) is a generic C++
  *    library for computational topology.
  *
  *    Author(s):       David Salinas
  *
  *    Copyright (C) 2014  INRIA Sophia Antipolis-Mediterranee (France)
  *
  *    This program is free software: you can redistribute it and/or modify
  *    it under the terms of the GNU General Public License as published by
  *    the Free Software Foundation, either version 3 of the License, or
  *    (at your option) any later version.
  *
  *    This program is distributed in the hope that it will be useful,
  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  *    GNU General Public License for more details.
  *
  *    You should have received a copy of the GNU General Public License
  *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  */
#ifndef GUDHI_KELETON_BLOCKERS_SIMPLICES_ITERATORS_H_
#define GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_

#include <memory>
#include <list>
#include <iostream>
#include "gudhi/Utils.h"
#include "boost/iterator/iterator_facade.hpp"


#include "gudhi/Skeleton_blocker_link_complex.h"
#include "gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h"




namespace Gudhi {


namespace skbl {


template<typename SkeletonBlockerComplex,typename Link>
class Simplex_around_vertex_iterator :
        public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex,Link>
, typename SkeletonBlockerComplex::Simplex_handle
, boost::forward_traversal_tag
, typename SkeletonBlockerComplex::Simplex_handle
>
{
    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_handle Simplex_handle;


    typedef typename Link::Vertex_handle Link_vertex_handle;
    // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion


private:

    struct Trie{
        Vertex_handle v;
        std::vector<std::shared_ptr<Trie> > childs;
    private:
        const Trie* parent_;
    public:


        //std::list<std::unique_ptr<Trie> > childs; -> use of deleted function

        Trie():parent_(0){}
        Trie(Vertex_handle v_):v(v_),parent_(0){
        }

        Trie(Vertex_handle v_,Trie* parent):v(v_),parent_(parent){
        }


        bool operator==(const Trie& other) const{
            return (v == other.v) ;
        }

        void add_child(Trie* child){
            if(child){
                std::shared_ptr<Trie> ptr_to_add(child);
                childs.push_back(ptr_to_add);
                child->parent_ = this;
            }
        }


        friend std::ostream& operator<<(std::ostream& stream, const Trie& trie){
            stream<< "T( "<< trie.v<< " ";
            for(auto t : trie.childs)
                stream << *t ;
            stream<<")";
            return stream;
        }

        // goes to the root in the trie to consitute simplex
        void add_vertices_up_to_the_root(Simplex_handle& res) const{
            res.add_vertex(v);
            if(parent_)
                parent_->add_vertices_up_to_the_root(res);
        }

        Simplex_handle simplex() const{
            Simplex_handle res;
            add_vertices_up_to_the_root(res);
            return res;
        }

        bool is_leaf() const{
            return childs.empty();
        }

        bool is_root() const{
            return parent_==0;
        }

        const Trie* parent() {
            return parent_;
        }

        void remove_leaf() {
            assert(is_leaf);
            if(!is_root())
                parent_->childs.erase(this);
        }

    private:


    public:

        Trie* go_bottom_left(){
            if(is_leaf())
                return this;
            else
                return (*childs.begin())->go_bottom_left();
        }

    };

private:
    const Complex* complex;
    Vertex_handle v;
    std::shared_ptr<Link> link_v;
    std::shared_ptr<Trie> trie;
    std::list<Trie*> nodes_to_be_seen; // todo regrouper

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 avoid useless copy
    // todo 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()){
        }
    }

    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_handle 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();

        if(!both_non_empty) return false; //one is empty the other is not

        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_handle dereference() const{
        assert(!nodes_to_be_seen.empty());
        Trie* first_node = nodes_to_be_seen.front();
        return first_node->simplex();
    }

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_handle
, boost::forward_traversal_tag
, typename SkeletonBlockerComplex::Simplex_handle
>
{
    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_handle Simplex_handle;

    typedef typename Complex::CVI CVI;


    typedef typename Link::Vertex_handle Link_vertex_handle;

private:

    const Complex* complex_;
    CVI 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){}

    // should not be called if the complex is empty
    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)
    {
        assert(!complex->empty());
    }

private:
    // todo return to 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_handle 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());
    }
};


}

} // namespace GUDHI





#endif /* SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ */