HalfedgeDS.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__HalfedgeDS_h__)
#define __HalfedgeDS_h__

#include "../defs.h"

#include "circulator.h"

#include <vector>

#include <cassert>

BEGIN_NAMESPACE_ADS
  
template < template<class> class Vertex, 
           template<class> class Halfedge, 
           template<class> class Face >
class HalfedgeDS
{
  //
  // Types
  //

private:

  typedef HalfedgeDS<Vertex, Halfedge, Face> HDS;

public:

  typedef Vertex<HDS> Vertex_type;
  typedef Halfedge<HDS> Halfedge_type;
  typedef Face<HDS> Face_type;

private:

  typedef std::vector<Vertex_type> Vertex_container;
  typedef std::vector<Halfedge_type> Halfedge_container;
  typedef std::vector<Face_type> Face_container;
    
public:

  typedef typename Vertex_container::iterator Vertex_iterator;
  typedef typename Halfedge_container::iterator Halfedge_iterator;
  typedef typename Face_container::iterator Face_iterator;

  typedef typename Vertex_container::const_iterator Vertex_const_iterator;
  typedef typename Halfedge_container::const_iterator 
  Halfedge_const_iterator;
  typedef typename Face_container::const_iterator Face_const_iterator;

  typedef typename Vertex_container::iterator Vertex_handle;
  typedef typename Halfedge_container::iterator Halfedge_handle;
  typedef typename Face_container::iterator Face_handle;

  typedef typename Vertex_container::const_iterator Vertex_const_handle;
  typedef typename Halfedge_container::const_iterator Halfedge_const_handle;
  typedef typename Face_container::const_iterator Face_const_handle;

  typedef typename Vertex_container::size_type size_type;
  typedef typename Vertex_container::difference_type difference_type;

  typedef Face_Halfedge_circ<Halfedge_handle> Face_Halfedge_circulator;
  typedef Face_Halfedge_circ<Halfedge_const_handle> 
  Face_Halfedge_const_circulator;

private:
      
  //
  // Data
  //
    
  // Containers.
  Vertex_container   _vertices;
  Halfedge_container _halfedges;
  Face_container     _faces;

  // Null handles.
  Vertex_handle   _null_vertex_handle;
  Halfedge_handle _null_halfedge_handle;
  Face_handle     _null_face_handle;

public:

  //
  // Constructors and Destructor
  //

  HalfedgeDS() :
    _vertices(),
    _halfedges(),
    _faces(),
    _null_vertex_handle( 0 ),
    _null_halfedge_handle( 0 ),
    _null_face_handle( 0 )
  {}


  HalfedgeDS( size_type v, size_type h, size_type f ) :
    _vertices(),
    _halfedges(),
    _faces(),
    _null_vertex_handle( 0 ),
    _null_halfedge_handle( 0 ),
    _null_face_handle( 0 )
  {
    _vertices.reserve( v );
    _halfedges.reserve( h );
    _faces.reserve( f );
  }

  HalfedgeDS( const HalfedgeDS& x );

  ~HalfedgeDS()
  {}

  HalfedgeDS& 
  operator=( const HalfedgeDS& x );

  //  
  // Accessors
  //

  Vertex_const_iterator
  vertices_begin() const
  {
    return _vertices.begin();
  }

  Vertex_const_iterator
  vertices_end() const
  {
    return _vertices.end();
  }

  Halfedge_const_iterator
  halfedges_begin() const
  {
    return _halfedges.begin();
  }

  Halfedge_const_iterator
  halfedges_end() const
  {
    return _halfedges.end();
  }

  Face_const_iterator
  faces_begin() const
  {
    return _faces.begin();
  }

  Face_const_iterator
  faces_end() const
  {
    return _faces.end();
  }

  size_type
  vertices_size() const
  {
    return _vertices.size();
  }
    
  size_type
  halfedges_size() const
  {
    return _halfedges.size();
  }
    
  size_type
  faces_size() const
  {
    return _faces.size();
  }

  //  
  // Manipulators
  //

  Vertex_iterator
  vertices_begin()
  {
    return _vertices.begin();
  }

  Vertex_iterator
  vertices_end()
  {
    return _vertices.end();
  }

  Halfedge_iterator
  halfedges_begin()
  {
    return _halfedges.begin();
  }

  Halfedge_iterator
  halfedges_end()
  {
    return _halfedges.end();
  }

  Face_iterator
  faces_begin()
  {
    return _faces.begin();
  }

  Face_iterator
  faces_end()
  {
    return _faces.end();
  }

  //
  // Utility
  //


  bool
  is_valid() const
  {
    // Check the vertices.
    for ( Vertex_const_iterator i = vertices_begin(); 
          i != vertices_end(); ++i ) {
      if ( ! is_valid( i->halfedge() ) ) {
        return false;
      }
    }
    // Check the halfedges.
    for ( Halfedge_const_iterator i = halfedges_begin(); 
          i != halfedges_end(); ++i ) {
      if ( ! ( is_valid( i->opposite() ) && 
               is_valid( i->prev() ) && 
               is_valid( i->next() ) && 
               is_valid( i->vertex() ) && 
               is_valid( i->face() ) ) ) {
        return false;
      }
    }
    // Check the faces.
    for ( Face_const_iterator i = faces_begin(); 
          i != faces_end(); ++i ) {
      if ( ! is_valid( i->halfedge() ) ) {
        return false;
      }
    }
    return true;
  }
    
  bool
  is_valid( Vertex_const_handle h ) const
  {
    if ( is_null( h ) || ( vertices_begin() <= h && h < vertices_end() ) ) {
      return true;
    }
    return false;
  }
    
  bool
  is_valid( Halfedge_const_handle h ) const
  {
    if ( is_null( h ) || ( halfedges_begin() <= h && h < halfedges_end() ) ){
      return true;
    }
    return false;
  }
    
  bool
  is_valid( Face_const_handle h ) const
  {
    if ( is_null( h ) || ( faces_begin() <= h && h < faces_end() ) ){
      return true;
    }
    return false;
  }
    
  difference_type
  index( Vertex_const_handle h ) const
  {
    if ( h == _null_vertex_handle ) {
      return std::distance( vertices_begin(), vertices_end() );
    }
    return std::distance( vertices_begin(), h );
  }
    
  difference_type
  index( Halfedge_const_handle h ) const
  {
    if ( h == _null_halfedge_handle ) {
      return std::distance( halfedges_begin(), halfedges_end() );
    }
    return std::distance( halfedges_begin(), h );
  }
    
  difference_type
  index( Face_const_handle h ) const
  {
    if ( h == _null_face_handle ) {
      return std::distance( faces_begin(), faces_end() );
    }
    return std::distance( faces_begin(), h );
  }

  bool
  is_null( Vertex_const_handle h ) const
  {
    return ( h == _null_vertex_handle );
  }
    
  bool
  is_null( Halfedge_const_handle h ) const
  {
    return ( h == _null_halfedge_handle );
  }
    
  bool
  is_null( Face_const_handle h ) const
  {
    return ( h == _null_face_handle );
  }
    
  //
  // Insert items
  //

  void
  reserve( size_type v, size_type h, size_type f );

  void
  clear();
    
  Vertex_handle
  insert_vertex();
    
  Vertex_handle
  insert_vertex( const Vertex_type& x );
    

  Halfedge_handle
  insert_halfedge();
    
  Halfedge_handle
  insert_halfedge( const Halfedge_type& x );
    
  Halfedge_handle
  insert_halfedge( const Halfedge_type& x, const Halfedge_type& y );
    
  Face_handle
  insert_face();
    
  Face_handle
  insert_face( const Face_type& x );

  //
  // I/O
  //

  void
  put( std::ostream& out ) const;

  void
  get( std::istream& in );

private:

  //
  // private member functions
  //

  void
  increase_vertex_capacity();

  void
  increase_halfedge_capacity();

  void
  increase_face_capacity();

  void 
  shift_vertex_handles( difference_type d );

  void 
  shift_halfedge_handles( difference_type d );

  void 
  shift_face_handles( difference_type d );
};

//
// Equality.
//

template < template<class> class Vertex, 
           template<class> class Halfedge, 
           template<class> class Face >
inline
bool
operator==( const HalfedgeDS<Vertex,Halfedge,Face>& a,
            const HalfedgeDS<Vertex,Halfedge,Face>& b );

template < template<class> class Vertex, 
           template<class> class Halfedge, 
           template<class> class Face >
inline
bool
operator!=( const HalfedgeDS<Vertex,Halfedge,Face>& a,
            const HalfedgeDS<Vertex,Halfedge,Face>& b )
{
  return !(a == b );
}

//
// I/O
//

template < template<class> class Vertex, 
           template<class> class Halfedge, 
           template<class> class Face >
inline
std::ostream&
operator<<( std::ostream& out, const HalfedgeDS<Vertex,Halfedge,Face>& x )
{
  x.put( out );
  return out;
}
  
template < template<class> class Vertex, 
           template<class> class Halfedge, 
           template<class> class Face >
inline
std::istream&
operator>>( std::istream& in, HalfedgeDS<Vertex,Halfedge,Face>& x )
{
  x.get( in );
  return in;
}
  
END_NAMESPACE_ADS

#define __HalfedgeDS_ipp__
#include "HalfedgeDS.ipp"
#undef __HalfedgeDS_ipp__

#endif

---