FTRPropagation.h

Go to the documentation of this file.

 
 
#pragma once
 
// local include
#include "FTRAtomicUF.h"
#include "FTRCommon.h"
 
// base code includes
#include <Triangulation.h>
 
// library include
#include <boost/heap/fibonacci_heap.hpp>
 
// C++ includes
#include <deque>
#include <unordered_map>
 
namespace ttk {
  namespace ftr {
    class Propagation {
    private:
      // cache current simplex
      idVertex curVert_;
      idSuperArc nbArcs_;
 
      // comparison function
      VertCompFN comp_;
      // come from min/max leaf
      bool goUp_;
 
      // priority deque
      boost::heap::fibonacci_heap<idVertex, boost::heap::compare<VertCompFN>>
        propagation_;
 
      // representant (pos in array)
      AtomicUF id_;
 
    public:
      Propagation(idVertex startVert, const VertCompFN &vertComp, bool up)
        : curVert_{nullVertex}, nbArcs_{1}, comp_{vertComp}, goUp_{up},
          propagation_{vertComp}, id_{this} {
        propagation_.emplace(startVert);
      }
 
      Propagation(const Propagation &other) = delete;
 
      idVertex getCurVertex() const {
        return curVert_;
      }
 
      // used to avoid the fibonacci heaps the local propagation is only
      // used to store comp and current vert during a sequential pass using
      // the reference alforithm and so it's a mock propagation used for
      // compliance with the rest of the code
      void setCurvert(const idVertex v) {
        curVert_ = v;
      }
 
      idSuperArc getNbArcs() const {
        return nbArcs_;
      }
 
      void moreArc(const idSuperArc a = 1) {
        nbArcs_ += a;
        // std::cout << " - new nb arc " << nbArcs_ << " added " << a <<
        // std::endl;
      }
 
      void lessArc(const idSuperArc a = 1) {
        nbArcs_ -= a;
        // std::cout << " - new nb arc " << nbArcs_ << " removed " << a <<
        // std::endl;
      }
 
      AtomicUF *getId() {
        return id_.find();
      }
 
      idVertex nextVertex() {
        curVert_ = propagation_.top();
        removeDuplicates(curVert_);
        return curVert_;
      }
 
      idVertex getNextVertex() const {
#ifndef TTK_ENABLE_KAMIKAZE
        if(propagation_.empty()) {
          std::cerr << "[FTR]: Propagation get next on empty structure"
                    << std::endl;
          return nullVertex;
        }
#endif
        return propagation_.top();
      }
 
      void removeDuplicates(const idVertex d) {
        while(!propagation_.empty() && propagation_.top() == d) {
          propagation_.pop();
        }
      }
 
      void removeBelow(const idVertex d, const VertCompFN &comp) {
        while(!propagation_.empty() && comp(propagation_.top(), d)) {
          propagation_.pop();
        }
      }
 
      void addNewVertex(const idVertex v) {
        propagation_.emplace(v);
      }
 
      void merge(Propagation &other) {
        if(&other == this)
          return;
        propagation_.merge(other.propagation_);
        AtomicUF::makeUnion(&id_, &other.id_);
        nbArcs_ += other.nbArcs_;
        // std::cout << " ~ new nb arc " << nbArcs_ << " added " <<
        // other.nbArcs_ << std::endl;
        // TODO once after all the merge ?
        id_.find()->setPropagation(this);
      }
 
      bool empty() const {
        return propagation_.empty();
      }
 
      void clear() {
        propagation_.clear();
      }
 
      bool compare(const idVertex a, const idVertex b) const {
        return comp_(b, a);
      }
 
      // true if propagation initiated form a min leaf
      bool goUp() const {
        return goUp_;
      }
 
      bool goDown() const {
        return !goUp_;
      }
 
      // DEBUG ONLY
 
      bool find(idVertex v) const {
        return std::find(propagation_.begin(), propagation_.end(), v)
               != propagation_.end();
      }
 
      std::size_t size() const {
        return propagation_.size();
      }
 
      std::string print() const {
        std::stringstream res;
        res << " localProp " << curVert_ << " : ";
#ifndef NDEBUG
        // only if perf are not important: copy
        boost::heap::fibonacci_heap<idVertex, boost::heap::compare<VertCompFN>>
          tmp(propagation_);
        while(!tmp.empty()) {
          res << tmp.top() << " ";
          tmp.pop();
        }
#else
        res << "...";
#endif
        return res.str();
      }
    };
  } // namespace ftr
} // namespace ttk