Complex1.h

Go to the documentation of this file.

#ifndef Complex1_HEADER
#define Complex1_HEADER

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include "SimplicialComplex.h"
#include <boost/iterator/iterator_facade.hpp>

template <class Vertex_, class SimplexData_, class VertexPrinter_>
class SimplicialComplex<1, Vertex_, SimplexData_, VertexPrinter_> {

  public:
  typedef Vertex_ Vertex; 
  typedef VertexPrinter_ VertexPrinter; 
  typedef SimplexData_ SimplexData; 
  typedef typename hudson::Bucket<SimplexData>::reference data_ref; 
  typedef typename hudson::Bucket<SimplexData>::const_reference data_const_ref; 
  class Star;
  class Cavity;

  private:
  enum Index { LEFT, RIGHT, DONE };
  enum Status { BORN = 0, IN = 1, DEAD = 2 }; // must fit in 2 bits

  template <class Derived, class OutType, class Reference>
  class iterator_base : public boost::iterator_facade
                                < Derived
                                , OutType
                                , boost::bidirectional_traversal_tag
                                , Reference >
  {
    private:
      //
      // Curiously Recurring Template interface.
      //
      Derived& derived() { return *static_cast<Derived*>(this); }
      Derived const& derived() const { return *static_cast<Derived const*>(this); }

    protected:
      Index index_;
      iterator_base(Index index): index_(index) { }

    public:
      void increment() { assert(index_ < DONE); index_ = Index(unsigned(index_) + 1); }
      void decrement() { assert(index_ > LEFT); index_ = Index(unsigned(index_) - 1); }
      bool equal(const Derived& other) const { return index_ == other.index_; }
      Reference dereference() const {
        switch(index_) {
          case LEFT: return derived().getLeft();
          case RIGHT: return derived().getRight();
          case DONE: assert(0 && "dereferencing end()");
          default:   assert(0 && "major bug");
                     return derived().getLeft();
        }
      }
  };

  class ISimplex {
    ISimplex *left_;
    ISimplex *right_;
    Vertex *leftV_;

    size_t refcount_:(sizeof(size_t)*8 - 2);
    Status status_:2;

    public:
    hudson::Bucket<SimplexData> data_;

    ISimplex() {
      left_ = right_ = 0;
      leftV_ = 0;
      refcount_ = 0;
      status_ = BORN/*0*/;
    }

    bool isDummy() const { return right_ == 0; }

    ISimplex *getLeft() const { return left_; }
    ISimplex *getRight() const {
      assert(right_);
      if (right_->isDummy()) {
        return 0;
      } else return right_;
    }
    ISimplex *getRightOrDummy() const { return right_; }

    Vertex *getLeftV() const {
      return leftV_;
    }
    Vertex *getRightV() const {
      assert(!isDummy());
      return getRightOrDummy()->getLeftV();
    }

    Status getStatus() const { return status_; }



    void setLeft(ISimplex *left)  { left_ = left; }
    void setRight(ISimplex *right) { right_ = right; }
    void setVertex(Vertex *v) { leftV_ = v; }
    void setStatus(Status stat) {
      status_ = stat;
      switch(status_) {
        case IN:   add_ref(this); break;
        case DEAD: release(this); break;
        case BORN: break;
      }
    }

    /* Refcounting */
    static void add_ref(ISimplex *s) {
      s->refcount_++;
    }
    static void release(ISimplex *s) {
      s->refcount_--;
      if (s->refcount_ == 0) {
        delete s;
      }
    }
  };

  public:
  class Simplex {
    hudson::IntrusivePtr<ISimplex> s_;

    friend class Cavity;
    friend class Star;
    friend class SimplicialComplex;
    ISimplex *get() const { return s_.get(); }
    ISimplex *operator->() const { return get(); }
    void set(ISimplex *is) { s_ = is; }

    public:
    Simplex(const Simplex& other): s_(other.s_) { }

    static const size_t dimension = 1;

    Simplex(ISimplex *s): s_(s) { }

    size_t hash() const { return hudson::hashWord((size_t)get()); }
    std::string toString() const {
      VertexPrinter printer;
      return std::string("<") + printer(s_->getLeftV()) + " " + printer(s_->getRightV()) + ">";
    }

    class vertex_iterator : public iterator_base<vertex_iterator, Vertex*, Vertex*> {
      const Simplex& s;
      typedef iterator_base<vertex_iterator, Vertex*, Vertex*> super;
      friend class /*super*/ iterator_base<vertex_iterator, Vertex*, Vertex*>;
      friend class Simplex;
      Vertex *getLeft() const { return s->getLeftV(); }
      Vertex *getRight() const { return s->getRightV(); }
      vertex_iterator(const Simplex& s, Index i): super(i), s(s) { }
    };
    friend class vertex_iterator;
    typedef vertex_iterator iterator;
    typedef vertex_iterator const_iterator;

    vertex_iterator begin() const { return vertex_iterator(*this, LEFT); }
    vertex_iterator end() const { return vertex_iterator(*this, DONE); }

    Vertex *operator[](size_t i) const {
      switch(i) {
        case 0: return s_->getLeftV();
        case 1: return s_->getRightV();
        default: assert(0); return s_->getLeftV();
      }
    }

    bool has(const Vertex *v) const {
      return v == s_->getLeftV() || v == s_->getRightV();
    }
    template <class BinaryPredicate>
    bool has(const Vertex *v, const BinaryPredicate& pred) const {
      return pred(v, s_->getLeftV()) || pred(v, s_->getRightV());
    }

    bool operator== (const Simplex& other) const { return s_.get() == other.get(); }
    bool operator!= (const Simplex& other) const { return s_.get() != other.get(); }
  };

  /***************************************************************************
    Construction.
   ***************************************************************************/
  private:
  void init(Vertex *leftV, Vertex *rightV) {
    ISimplex *left = handle_.get();
    ISimplex *right = new ISimplex;

    left->setVertex(leftV);
    right->setVertex(rightV);
    left->setLeft(0);
    left->setRight(right);
    right->setLeft(left);
    right->setRight(0);

    left->setStatus(IN);
  }

  public:
  SimplicialComplex(Vertex *leftV, Vertex *rightV) : handle_(new ISimplex) {
    init(leftV, rightV);
  }

  SimplicialComplex(const vector<Vertex*>& verts) : handle_(new ISimplex) {
    assert(verts.size() == 2);
    init(verts[0], verts[1]);
  }

  /*
  SimplicialComplex(const vector<Vertex*>& verts, const vector<vector<unsigned> >& elts, int zeroindex) {
  // TODO
  }
  */

  /***************************************************************************
    Dimension
   ***************************************************************************/

  public:
  static size_t dim() { return 1; }
  static const size_t dimension = 1;


  /***************************************************************************
    Insert/remove
   ***************************************************************************/
  public:
  struct Cavity {
    typedef const Simplex *iterator;
    typedef const Simplex *const_iterator;

    Cavity(): s_(NULL) { }

    iterator begin() const { return &s_; }
    iterator end() const { return begin()+1; }

    bool empty() const { return s_.get() == NULL; }
    size_t size() const { return empty() ? 0 : 1; }

    void add(const Simplex& s) {
      assert(empty());
      s_ = s;
    }

    private:
    friend class SimplicialComplex;
    Simplex s_;
  };

  class Star {
    Simplex left_;
    Simplex right_;

    friend class SimplicialComplex;

    public:
    Star() : left_(0), right_(0) { }
    void clear() {
      left_.set(0);
      right_.set(0);
    }

    class iterator : public iterator_base<iterator, Simplex, const Simplex&> {
      typedef iterator_base<iterator, Simplex, const Simplex&> super;
      friend class iterator_base<iterator, Simplex, const Simplex&> /*super*/;
      friend class Star;
      const Star * star_;
      iterator(const Star& star, Index index): super(index), star_(&star) { }
      const Simplex& getLeft() const { return star_->left_; }
      const Simplex& getRight() const { return star_->right_; }
    };
    typedef iterator const_iterator;

    /* neigh_iterator returns a "reference" of type Simplex, because it's constructed in-place. */
    class neigh_iterator : public iterator_base<neigh_iterator, Simplex, Simplex> {
      typedef iterator_base<iterator, Simplex, Simplex> super;
      friend class iterator_base<iterator, Simplex, Simplex> /*super*/;
      friend class Star;
      const Star& star_;
      neigh_iterator(const Star& star, Index index): super(index), star_(star) { }
      const Simplex& getLeft() const { return star_.left_->getLeft(); }
      const Simplex& getRight() const { return star_.right_->getRight(); }
    };

    iterator begin() const { return iterator(*this, LEFT); }
    iterator end() const { return iterator(*this, DONE); }

    neigh_iterator begin_neighbours() const { return neigh_iterator(*this, LEFT); }
    neigh_iterator end_neighbours() const { return neigh_iterator(*this, DONE); }

    const Simplex& operator[] (size_t i) {
      switch(i) {
        case 0: return left_;
        case 1: return right_;
        default: assert(0); return left_;
      }
    }

    static size_t size() { return 2; }

    const iterator& erase(const iterator& it) {
      // Not possible in 1-d, but I'd rather not force every user to specialize
      // for 1-d, so we simply leave the function defined and assert if it's called.
      assert(0);
      return it;
    }

    private:
    void computeStar(const Simplex& tosplit, Vertex *v) {
      assert(!left_.get()); assert(!right_.get());
      left_.set(new ISimplex);
      right_.set(new ISimplex);

      left_->setLeft(tosplit->getLeft());
      left_->setRight(right_.get());
      left_->setVertex(tosplit->getLeftV());

      right_->setLeft(left_.get());
      right_->setRight(tosplit->getRightOrDummy());
      right_->setVertex(v);
      assert(left_.get()); assert(right_.get());
    }

    void commit(const Simplex& tosplit) {
      assert(left_.get()); assert(right_.get());
      assert(left_->getLeftV() == tosplit->getLeftV());
      if (left_->getLeft()) {
        left_->getLeft()->setRight(left_.get());
      }
      assert(right_->getRightOrDummy());
      right_->getRightOrDummy()->setLeft(right_.get());
      // left and right already point to each other, and we don't care about
      // the "head" of the doubly-linked list, so we're done.
      assert(left_->getRight() == right_.get());
      assert(right_->getLeft() == left_.get());
      left_->setStatus(IN);
      right_->setStatus(IN);
      tosplit->setStatus(DEAD);
    }
  };

  void computeStar(const Simplex& tosplit, Vertex *apex, Star& star) {
    assert(isMember(tosplit));
    star.computeStar(tosplit, apex);
  }
  void computeStar(const Cavity& cavity, Vertex *apex, Star& star) {
    computeStar(cavity.s_, apex, star);
  }

  void replaceCavity(const Simplex& tosplit, Star& star) {
    assert(isMember(tosplit));
    star.commit(tosplit);
    setHandle(star.left_);
  }
  void replaceCavity(const Cavity& cavity, Star& star) {
    replaceCavity(cavity.s_, star);
  }

  void replaceCavity(const Simplex& tosplit, Vertex *apex) {
    Star star;
    computeStar(tosplit, apex, star);
    replaceCavity(tosplit, star);
  }
  void replaceCavity(const Cavity& cavity, Vertex *apex) {
    replaceCavity(cavity.s_, apex);
  }

  void checkedRemoveSimplex(const Simplex& s) {
    assert(isMember(s));
    assert(getHandle() != s);
    if (s->getLeft()) {
      s->getLeft()->setRight(0);
    }
    ISimplex *right = s->getRightOrDummy();
    assert(right);
    if (right->isDummy()) {
      // delete it: it's otherwise an orphaned dummy
      delete right;
    } else {
      right->setLeft(0);
    }
    s->setLeft(0);
    s->setRight(0);
    s->setStatus(DEAD);
  }

  /***************************************************************************
   ***************************************************************************/
  bool isMember(const Simplex& s) const {
    return s.get() && (s->getStatus() == IN) && !s->isDummy();
  }

  const Simplex& getHandle() const {
    return handle_;
  }

  void setHandle(const Simplex& s) {
    assert(isMember(s));
    handle_ = s;
  }

  /***************************************************************************
   ***************************************************************************/
  Simplex getNeighbour(int i, const Simplex& s) const {
    assert(isMember(s));
    switch (i) {
      case 0: return s->getRight();
      case 1: return s->getLeft();
      default: assert(0); return s->getLeft();
    }
  }

  /***************************************************************************
   ***************************************************************************/
  template <class SearchClosure>
  bool dfsBySimplex(SearchClosure& data, const Simplex& seed) const {
    assert(isMember(seed));
    if (!data.canEnter(seed)) {
      return false;
    } else if (data.choose(seed)) {
      return true;
    }
    // first go left all the way
    ISimplex *next = seed->getLeft();
    while (next && data.canEnter(next)) {
      if (data.choose(next)) { return true; }
      next = next->getLeft();
    }
    // then go right all the way
    next = seed->getRight();
    while (next && data.canEnter(next)) {
      if (data.choose(next)) { return true; }
      next = next->getRight();
    }
    // didn't find it.
    return false;
  }

  template <class SearchClosure>
  bool bfsBySimplex(SearchClosure& data, const Simplex& seed) const {
    assert(isMember(seed));
    if (!data.canEnter(seed)) {
      return false;
    } else if (data.choose(seed)) {
      return true;
    }

    ISimplex *left = seed->getLeft();
    ISimplex *right = seed->getRight();

    while (left || right) {
      if (left) {
        if (!data.canEnter(left)) {
          left = 0;
        } else if (data.choose(left)) {
          return true;
        } else {
          left = left->getLeft();
        }
      }
      if (right) {
        if (!data.canEnter(right)) {
          right = 0;
        } else if (data.choose(right)) {
          return true;
        } else {
          right = right->getRight();
        }
      }
    }
    // never chose anyone.
    return false;
  }

  /***************************************************************************
   * \name Data access
   * We have to be careful with what we return, in order to handle void data.
   * We forward the request on to the complex, and then we pull out the
   * user's part of it.
   ***************************************************************************/
  data_ref getDataRW(const Simplex& s) {
    return s->data_.getRef();
  }

  data_const_ref getData(const Simplex& s) const {
    return s->data_.getCRef();
  }

  private:
  Simplex handle_;
};

#endif

---