PolyConnectivity.hh

/* ========================================================================= *
 *                                                                           *
 *                               OpenMesh                                    *
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
 *           Department of Computer Graphics and Multimedia                  *
 *                          All rights reserved.                             *
 *                            www.openmesh.org                               *
 *                                                                           *
 *---------------------------------------------------------------------------*
 * This file is part of OpenMesh.                                            *
 *---------------------------------------------------------------------------*
 *                                                                           *
 * Redistribution and use in source and binary forms, with or without        *
 * modification, are permitted provided that the following conditions        *
 * are met:                                                                  *
 *                                                                           *
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
 *                                                                           *
 * 2. Redistributions in binary form must reproduce the above copyright      *
 *    notice, this list of conditions and the following disclaimer in the    *
 *    documentation and/or other materials provided with the distribution.   *
 *                                                                           *
 * 3. Neither the name of the copyright holder nor the names of its          *
 *    contributors may be used to endorse or promote products derived from   *
 *    this software without specific prior written permission.               *
 *                                                                           *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
 *                                                                           *
 * ========================================================================= */



#ifndef OPENMESH_POLYCONNECTIVITY_HH
#define OPENMESH_POLYCONNECTIVITY_HH

#include <OpenMesh/Core/Mesh/ArrayKernel.hh>
#include <OpenMesh/Core/Mesh/SmartRange.hh>

namespace OpenMesh
{

namespace Iterators
{
  template <class Mesh, class ValueHandle, class MemberOwner, bool (MemberOwner::*PrimitiveStatusMember)() const, size_t (MemberOwner::*PrimitiveCountMember)() const>
  class GenericIteratorT;

  template<class Mesh>
  class GenericCirculatorBaseT;

  template<typename Traits>
  class GenericCirculatorT_DEPRECATED;

  template<typename Traits, bool CW>
  class GenericCirculatorT;
}

template <typename RangeTraitT>
class EntityRange;

template<
  typename CONTAINER_T,
  typename ITER_T,
  ITER_T (CONTAINER_T::*begin_fn)() const,
  ITER_T (CONTAINER_T::*end_fn)() const>
struct RangeTraitT
{
  using CONTAINER_TYPE = CONTAINER_T;
  using ITER_TYPE = ITER_T;
  static ITER_TYPE begin(const CONTAINER_TYPE& _container) { return (_container.*begin_fn)(); }
  static ITER_TYPE end(const CONTAINER_TYPE& _container)   { return (_container.*end_fn)(); }
};


template <typename CirculatorRangeTraitT>
class CirculatorRange;

template<
    typename CONTAINER_T,
    typename ITER_T,
    typename CENTER_ENTITY_T,
    typename TO_ENTITY_T,
    ITER_T (CONTAINER_T::*begin_fn)(CENTER_ENTITY_T) const,
    ITER_T (CONTAINER_T::*end_fn)(CENTER_ENTITY_T) const>
struct CirculatorRangeTraitT
{
  using CONTAINER_TYPE = CONTAINER_T;
  using ITER_TYPE = ITER_T;
  using CENTER_ENTITY_TYPE = CENTER_ENTITY_T;
  using TO_ENTITYE_TYPE = TO_ENTITY_T;
  static ITER_TYPE begin(const CONTAINER_TYPE& _container, CENTER_ENTITY_TYPE _ce) { return (_container.*begin_fn)(_ce); }
  static ITER_TYPE end(const CONTAINER_TYPE& _container, CENTER_ENTITY_TYPE _ce)   { return (_container.*end_fn)(_ce); }
};

struct SmartVertexHandle;
struct SmartHalfedgeHandle;
struct SmartEdgeHandle;
struct SmartFaceHandle;

class OPENMESHDLLEXPORT PolyConnectivity : public ArrayKernel
{
public:

  static const VertexHandle                           InvalidVertexHandle;
  static const HalfedgeHandle                         InvalidHalfedgeHandle;
  static const EdgeHandle                             InvalidEdgeHandle;
  static const FaceHandle                             InvalidFaceHandle;

  typedef PolyConnectivity                            This;

  //--- iterators ---

  typedef Iterators::GenericIteratorT<This, This::VertexHandle, ArrayKernel , &ArrayKernel::has_vertex_status, &ArrayKernel::n_vertices> VertexIter;
  typedef Iterators::GenericIteratorT<This, This::HalfedgeHandle, ArrayKernel , &ArrayKernel::has_halfedge_status, &ArrayKernel::n_halfedges> HalfedgeIter;
  typedef Iterators::GenericIteratorT<This, This::EdgeHandle, ArrayKernel , &ArrayKernel::has_edge_status, &ArrayKernel::n_edges> EdgeIter;
  typedef Iterators::GenericIteratorT<This, This::FaceHandle, ArrayKernel , &ArrayKernel::has_face_status, &ArrayKernel::n_faces> FaceIter;

  typedef VertexIter ConstVertexIter;
  typedef HalfedgeIter ConstHalfedgeIter;
  typedef EdgeIter ConstEdgeIter;
  typedef FaceIter ConstFaceIter;

  //--- circulators ---


  /*
   * Vertex-centered circulators
   */

  struct VertexVertexTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::VertexHandle;
    using ValueHandle = This::VertexHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return _mesh->to_vertex_handle(_heh);}
  };


  typedef Iterators::GenericCirculatorT_DEPRECATED<VertexVertexTraits> VertexVertexIter;
  typedef Iterators::GenericCirculatorT<VertexVertexTraits, true> VertexVertexCWIter;

  typedef Iterators::GenericCirculatorT<VertexVertexTraits, false>  VertexVertexCCWIter;


  struct VertexHalfedgeTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::VertexHandle;
    using ValueHandle = This::HalfedgeHandle;
    static ValueHandle toHandle(const Mesh* const /*_mesh*/, This::HalfedgeHandle _heh) { return _heh;}
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<VertexHalfedgeTraits> VertexOHalfedgeIter;
  typedef Iterators::GenericCirculatorT<VertexHalfedgeTraits, true> VertexOHalfedgeCWIter;

  typedef Iterators::GenericCirculatorT<VertexHalfedgeTraits, false> VertexOHalfedgeCCWIter;

  struct VertexOppositeHalfedgeTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::VertexHandle;
    using ValueHandle = This::HalfedgeHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return _mesh->opposite_halfedge_handle(_heh); }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<VertexOppositeHalfedgeTraits> VertexIHalfedgeIter;
  typedef Iterators::GenericCirculatorT<VertexOppositeHalfedgeTraits, true> VertexIHalfedgeCWIter;

  typedef Iterators::GenericCirculatorT<VertexOppositeHalfedgeTraits, false> VertexIHalfedgeCCWIter;


  struct VertexFaceTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::VertexHandle;
    using ValueHandle = This::FaceHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return static_cast<const ArrayKernel*>(_mesh)->face_handle(_heh); }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<VertexFaceTraits> VertexFaceIter;
  typedef Iterators::GenericCirculatorT<VertexFaceTraits, true> VertexFaceCWIter;

  typedef Iterators::GenericCirculatorT<VertexFaceTraits, false> VertexFaceCCWIter;


  struct VertexEdgeTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::VertexHandle;
    using ValueHandle = This::EdgeHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return static_cast<const ArrayKernel*>(_mesh)->edge_handle(_heh); }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<VertexEdgeTraits> VertexEdgeIter;
  typedef Iterators::GenericCirculatorT<VertexEdgeTraits, true> VertexEdgeCWIter;
  typedef Iterators::GenericCirculatorT<VertexEdgeTraits, false> VertexEdgeCCWIter;


  struct FaceHalfedgeTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::FaceHandle;
    using ValueHandle = This::HalfedgeHandle;
    static ValueHandle toHandle(const Mesh* const /*_mesh*/, This::HalfedgeHandle _heh) { return _heh; }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<FaceHalfedgeTraits> HalfedgeLoopIter;
  typedef Iterators::GenericCirculatorT<FaceHalfedgeTraits, false> HalfedgeLoopCWIter;
  typedef Iterators::GenericCirculatorT<FaceHalfedgeTraits, true> HalfedgeLoopCCWIter;

  typedef VertexVertexIter        ConstVertexVertexIter;
  typedef VertexVertexCWIter      ConstVertexVertexCWIter;
  typedef VertexVertexCCWIter     ConstVertexVertexCCWIter;
  typedef VertexOHalfedgeIter     ConstVertexOHalfedgeIter;
  typedef VertexOHalfedgeCWIter   ConstVertexOHalfedgeCWIter;
  typedef VertexOHalfedgeCCWIter  ConstVertexOHalfedgeCCWIter;
  typedef VertexIHalfedgeIter     ConstVertexIHalfedgeIter;
  typedef VertexIHalfedgeCWIter   ConstVertexIHalfedgeCWIter;
  typedef VertexIHalfedgeCCWIter  ConstVertexIHalfedgeCCWIter;
  typedef VertexFaceIter          ConstVertexFaceIter;
  typedef VertexFaceCWIter        ConstVertexFaceCWIter;
  typedef VertexFaceCCWIter       ConstVertexFaceCCWIter;
  typedef VertexEdgeIter          ConstVertexEdgeIter;
  typedef VertexEdgeCWIter        ConstVertexEdgeCWIter;
  typedef VertexEdgeCCWIter       ConstVertexEdgeCCWIter;

  /*
   * Face-centered circulators
   */

  struct FaceVertexTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::FaceHandle;
    using ValueHandle = This::VertexHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return static_cast<const ArrayKernel*>(_mesh)->to_vertex_handle(_heh); }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<FaceVertexTraits> FaceVertexIter;
  typedef Iterators::GenericCirculatorT<FaceVertexTraits, true> FaceVertexCCWIter;

  typedef Iterators::GenericCirculatorT<FaceVertexTraits, false> FaceVertexCWIter;

  typedef Iterators::GenericCirculatorT_DEPRECATED<FaceHalfedgeTraits> FaceHalfedgeIter;
  typedef Iterators::GenericCirculatorT<FaceHalfedgeTraits, true> FaceHalfedgeCCWIter;

  typedef Iterators::GenericCirculatorT<FaceHalfedgeTraits, false> FaceHalfedgeCWIter;


  struct FaceEdgeTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::FaceHandle;
    using ValueHandle = This::EdgeHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return static_cast<const ArrayKernel*>(_mesh)->edge_handle(_heh); }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<FaceEdgeTraits> FaceEdgeIter;
  typedef Iterators::GenericCirculatorT<FaceEdgeTraits, true> FaceEdgeCCWIter;

  typedef Iterators::GenericCirculatorT<FaceEdgeTraits, false> FaceEdgeCWIter;


  struct FaceFaceTraits
  {
    using Mesh = This;
    using CenterEntityHandle = This::FaceHandle;
    using ValueHandle = This::FaceHandle;
    static ValueHandle toHandle(const Mesh* const _mesh, This::HalfedgeHandle _heh) { return static_cast<const ArrayKernel*>(_mesh)->face_handle(_mesh->opposite_halfedge_handle(_heh)); }
  };

  typedef Iterators::GenericCirculatorT_DEPRECATED<FaceFaceTraits> FaceFaceIter;
  typedef Iterators::GenericCirculatorT<FaceFaceTraits, true> FaceFaceCCWIter;

  typedef Iterators::GenericCirculatorT<FaceFaceTraits, false> FaceFaceCWIter;

  typedef FaceVertexIter        ConstFaceVertexIter;
  typedef FaceVertexCWIter      ConstFaceVertexCWIter;
  typedef FaceVertexCCWIter     ConstFaceVertexCCWIter;
  typedef FaceHalfedgeIter      ConstFaceHalfedgeIter;
  typedef FaceHalfedgeCWIter    ConstFaceHalfedgeCWIter;
  typedef FaceHalfedgeCCWIter   ConstFaceHalfedgeCCWIter;
  typedef FaceEdgeIter          ConstFaceEdgeIter;
  typedef FaceEdgeCWIter        ConstFaceEdgeCWIter;
  typedef FaceEdgeCCWIter       ConstFaceEdgeCCWIter;
  typedef FaceFaceIter          ConstFaceFaceIter;
  typedef FaceFaceCWIter        ConstFaceFaceCWIter;
  typedef FaceFaceCCWIter       ConstFaceFaceCCWIter;

  /*
   * Halfedge circulator
   */
  typedef HalfedgeLoopIter      ConstHalfedgeLoopIter;
  typedef HalfedgeLoopCWIter    ConstHalfedgeLoopCWIter;
  typedef HalfedgeLoopCCWIter   ConstHalfedgeLoopCCWIter;


  // --- shortcuts

  typedef VertexHandle    VHandle;
  typedef HalfedgeHandle  HHandle;
  typedef EdgeHandle      EHandle;
  typedef FaceHandle      FHandle;

  typedef VertexIter    VIter;
  typedef HalfedgeIter  HIter;
  typedef EdgeIter      EIter;
  typedef FaceIter      FIter;

  typedef ConstVertexIter    CVIter;
  typedef ConstHalfedgeIter  CHIter;
  typedef ConstEdgeIter      CEIter;
  typedef ConstFaceIter      CFIter;

  typedef VertexVertexIter        VVIter;
  typedef VertexVertexCWIter      VVCWIter;
  typedef VertexVertexCCWIter     VVCCWIter;
  typedef VertexOHalfedgeIter     VOHIter;
  typedef VertexOHalfedgeCWIter   VOHCWIter;
  typedef VertexOHalfedgeCCWIter  VOHCCWIter;
  typedef VertexIHalfedgeIter     VIHIter;
  typedef VertexIHalfedgeCWIter   VIHICWter;
  typedef VertexIHalfedgeCCWIter  VIHICCWter;
  typedef VertexEdgeIter          VEIter;
  typedef VertexEdgeCWIter        VECWIter;
  typedef VertexEdgeCCWIter       VECCWIter;
  typedef VertexFaceIter          VFIter;
  typedef VertexFaceCWIter        VFCWIter;
  typedef VertexFaceCCWIter       VFCCWIter;
  typedef FaceVertexIter          FVIter;
  typedef FaceVertexCWIter        FVCWIter;
  typedef FaceVertexCCWIter       FVCCWIter;
  typedef FaceHalfedgeIter        FHIter;
  typedef FaceHalfedgeCWIter      FHCWIter;
  typedef FaceHalfedgeCCWIter     FHCWWIter;
  typedef FaceEdgeIter            FEIter;
  typedef FaceEdgeCWIter          FECWIter;
  typedef FaceEdgeCCWIter         FECWWIter;
  typedef FaceFaceIter            FFIter;

  typedef ConstVertexVertexIter         CVVIter;
  typedef ConstVertexVertexCWIter       CVVCWIter;
  typedef ConstVertexVertexCCWIter      CVVCCWIter;
  typedef ConstVertexOHalfedgeIter      CVOHIter;
  typedef ConstVertexOHalfedgeCWIter    CVOHCWIter;
  typedef ConstVertexOHalfedgeCCWIter   CVOHCCWIter;
  typedef ConstVertexIHalfedgeIter      CVIHIter;
  typedef ConstVertexIHalfedgeCWIter    CVIHCWIter;
  typedef ConstVertexIHalfedgeCCWIter   CVIHCCWIter;
  typedef ConstVertexEdgeIter           CVEIter;
  typedef ConstVertexEdgeCWIter         CVECWIter;
  typedef ConstVertexEdgeCCWIter        CVECCWIter;
  typedef ConstVertexFaceIter           CVFIter;
  typedef ConstVertexFaceCWIter         CVFCWIter;
  typedef ConstVertexFaceCCWIter        CVFCCWIter;
  typedef ConstFaceVertexIter           CFVIter;
  typedef ConstFaceVertexCWIter         CFVCWIter;
  typedef ConstFaceVertexCCWIter        CFVCCWIter;
  typedef ConstFaceHalfedgeIter         CFHIter;
  typedef ConstFaceHalfedgeCWIter       CFHCWIter;
  typedef ConstFaceHalfedgeCCWIter      CFHCCWIter;
  typedef ConstFaceEdgeIter             CFEIter;
  typedef ConstFaceEdgeCWIter           CFECWIter;
  typedef ConstFaceEdgeCCWIter          CFECCWIter;
  typedef ConstFaceFaceIter             CFFIter;
  typedef ConstFaceFaceCWIter           CFFCWIter;
  typedef ConstFaceFaceCCWIter          CFFCCWIter;

public:

  PolyConnectivity()  {}
  virtual ~PolyConnectivity() {}

  inline static bool is_triangles()
  { return false; }

  inline void assign_connectivity(const PolyConnectivity& _other)
  { ArrayKernel::assign_connectivity(_other); }
  

  inline SmartVertexHandle add_vertex();

  SmartFaceHandle add_face(const std::vector<VertexHandle>& _vhandles);

  SmartFaceHandle add_face(const std::vector<SmartVertexHandle>& _vhandles);
 
   
  SmartFaceHandle add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2);

  SmartFaceHandle add_face(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2, VertexHandle _vh3);
 
  SmartFaceHandle add_face(const VertexHandle* _vhandles, size_t _vhs_size);




  bool is_collapse_ok(HalfedgeHandle _he);
    
    
  void delete_vertex(VertexHandle _vh, bool _delete_isolated_vertices = true);

  void delete_edge(EdgeHandle _eh, bool _delete_isolated_vertices=true);

  void delete_face(FaceHandle _fh, bool _delete_isolated_vertices=true);




  using ArrayKernel::next_halfedge_handle;
  using ArrayKernel::prev_halfedge_handle;
  using ArrayKernel::opposite_halfedge_handle;
  using ArrayKernel::ccw_rotated_halfedge_handle;
  using ArrayKernel::cw_rotated_halfedge_handle;

  inline SmartHalfedgeHandle next_halfedge_handle       (SmartHalfedgeHandle _heh) const;
  inline SmartHalfedgeHandle prev_halfedge_handle       (SmartHalfedgeHandle _heh) const;
  inline SmartHalfedgeHandle opposite_halfedge_handle   (SmartHalfedgeHandle _heh) const;
  inline SmartHalfedgeHandle ccw_rotated_halfedge_handle(SmartHalfedgeHandle _heh) const;
  inline SmartHalfedgeHandle cw_rotated_halfedge_handle (SmartHalfedgeHandle _heh) const;

  using ArrayKernel::s_halfedge_handle;
  using ArrayKernel::s_edge_handle;

  static SmartHalfedgeHandle s_halfedge_handle(SmartEdgeHandle _eh, unsigned int _i);
  static SmartEdgeHandle s_edge_handle(SmartHalfedgeHandle _heh);

  using ArrayKernel::halfedge_handle;
  using ArrayKernel::edge_handle;
  using ArrayKernel::face_handle;

  inline SmartHalfedgeHandle halfedge_handle(SmartEdgeHandle _eh, unsigned int _i) const;
  inline SmartHalfedgeHandle halfedge_handle(SmartFaceHandle _fh) const;
  inline SmartHalfedgeHandle halfedge_handle(SmartVertexHandle _vh) const;
  inline SmartEdgeHandle edge_handle(SmartHalfedgeHandle _heh) const;
  inline SmartFaceHandle face_handle(SmartHalfedgeHandle _heh) const;


  

  VertexIter vertices_begin();
  ConstVertexIter vertices_begin() const;
  VertexIter vertices_end();
  ConstVertexIter vertices_end() const;

  HalfedgeIter halfedges_begin();
  ConstHalfedgeIter halfedges_begin() const;
  HalfedgeIter halfedges_end();
  ConstHalfedgeIter halfedges_end() const;

  EdgeIter edges_begin();
  ConstEdgeIter edges_begin() const;
  EdgeIter edges_end();
  ConstEdgeIter edges_end() const;

  FaceIter faces_begin();
  ConstFaceIter faces_begin() const;
  FaceIter faces_end();
  ConstFaceIter faces_end() const;



  VertexIter vertices_sbegin();
  ConstVertexIter vertices_sbegin() const;

  HalfedgeIter halfedges_sbegin();
  ConstHalfedgeIter halfedges_sbegin() const;

  EdgeIter edges_sbegin();
  ConstEdgeIter edges_sbegin() const;

  FaceIter faces_sbegin();
  ConstFaceIter faces_sbegin() const;


  //--- circulators ---


  VertexVertexIter vv_iter(VertexHandle _vh);
  VertexVertexCWIter vv_cwiter(VertexHandle _vh);
  VertexVertexCCWIter vv_ccwiter(VertexHandle _vh);
  VertexIHalfedgeIter vih_iter(VertexHandle _vh);
  VertexIHalfedgeCWIter vih_cwiter(VertexHandle _vh);
  VertexIHalfedgeCCWIter vih_ccwiter(VertexHandle _vh);
  VertexOHalfedgeIter voh_iter(VertexHandle _vh);
  VertexOHalfedgeCWIter voh_cwiter(VertexHandle _vh);
  VertexOHalfedgeCCWIter voh_ccwiter(VertexHandle _vh);
  VertexEdgeIter ve_iter(VertexHandle _vh);
  VertexEdgeCWIter ve_cwiter(VertexHandle _vh);
  VertexEdgeCCWIter ve_ccwiter(VertexHandle _vh);
  VertexFaceIter vf_iter(VertexHandle _vh);
  VertexFaceCWIter vf_cwiter(VertexHandle _vh);
  VertexFaceCCWIter vf_ccwiter(VertexHandle _vh);

  ConstVertexVertexIter cvv_iter(VertexHandle _vh) const;
  ConstVertexVertexCWIter cvv_cwiter(VertexHandle _vh) const;
  ConstVertexVertexCCWIter cvv_ccwiter(VertexHandle _vh) const;
  ConstVertexIHalfedgeIter cvih_iter(VertexHandle _vh) const;
  ConstVertexIHalfedgeCWIter cvih_cwiter(VertexHandle _vh) const;
  ConstVertexIHalfedgeCCWIter cvih_ccwiter(VertexHandle _vh) const;
  ConstVertexOHalfedgeIter cvoh_iter(VertexHandle _vh) const;
  ConstVertexOHalfedgeCWIter cvoh_cwiter(VertexHandle _vh) const;
  ConstVertexOHalfedgeCCWIter cvoh_ccwiter(VertexHandle _vh) const;
  ConstVertexEdgeIter cve_iter(VertexHandle _vh) const;
  ConstVertexEdgeCWIter cve_cwiter(VertexHandle _vh) const;
  ConstVertexEdgeCCWIter cve_ccwiter(VertexHandle _vh) const;
  ConstVertexFaceIter cvf_iter(VertexHandle _vh) const;
  ConstVertexFaceCWIter cvf_cwiter(VertexHandle _vh) const;
  ConstVertexFaceCCWIter cvf_ccwiter(VertexHandle _vh) const;

  FaceVertexIter fv_iter(FaceHandle _fh);
  FaceVertexCWIter fv_cwiter(FaceHandle _fh);
  FaceVertexCCWIter fv_ccwiter(FaceHandle _fh);
  FaceHalfedgeIter fh_iter(FaceHandle _fh);
  FaceHalfedgeCWIter fh_cwiter(FaceHandle _fh);
  FaceHalfedgeCCWIter fh_ccwiter(FaceHandle _fh);
  FaceEdgeIter fe_iter(FaceHandle _fh);
  FaceEdgeCWIter fe_cwiter(FaceHandle _fh);
  FaceEdgeCCWIter fe_ccwiter(FaceHandle _fh);
  FaceFaceIter ff_iter(FaceHandle _fh);
  FaceFaceCWIter ff_cwiter(FaceHandle _fh);
  FaceFaceCCWIter ff_ccwiter(FaceHandle _fh);

  ConstFaceVertexIter cfv_iter(FaceHandle _fh) const;
  ConstFaceVertexCWIter cfv_cwiter(FaceHandle _fh) const;
  ConstFaceVertexCCWIter cfv_ccwiter(FaceHandle _fh) const;
  ConstFaceHalfedgeIter cfh_iter(FaceHandle _fh) const;
  ConstFaceHalfedgeCWIter cfh_cwiter(FaceHandle _fh) const;
  ConstFaceHalfedgeCCWIter cfh_ccwiter(FaceHandle _fh) const;
  ConstFaceEdgeIter cfe_iter(FaceHandle _fh) const;
  ConstFaceEdgeCWIter cfe_cwiter(FaceHandle _fh) const;
  ConstFaceEdgeCCWIter cfe_ccwiter(FaceHandle _fh) const;
  ConstFaceFaceIter cff_iter(FaceHandle _fh) const;
  ConstFaceFaceCWIter cff_cwiter(FaceHandle _fh) const;
  ConstFaceFaceCCWIter cff_ccwiter(FaceHandle _fh) const;
  
  // 'begin' circulators
  
  VertexVertexIter vv_begin(VertexHandle _vh);
  VertexVertexCWIter vv_cwbegin(VertexHandle _vh);
  VertexVertexCCWIter vv_ccwbegin(VertexHandle _vh);
  VertexIHalfedgeIter vih_begin(VertexHandle _vh);
  VertexIHalfedgeCWIter vih_cwbegin(VertexHandle _vh);
  VertexIHalfedgeCCWIter vih_ccwbegin(VertexHandle _vh);
  VertexOHalfedgeIter voh_begin(VertexHandle _vh);
  VertexOHalfedgeCWIter voh_cwbegin(VertexHandle _vh);
  VertexOHalfedgeCCWIter voh_ccwbegin(VertexHandle _vh);
  VertexEdgeIter ve_begin(VertexHandle _vh);
  VertexEdgeCWIter ve_cwbegin(VertexHandle _vh);
  VertexEdgeCCWIter ve_ccwbegin(VertexHandle _vh);
  VertexFaceIter vf_begin(VertexHandle _vh);
  VertexFaceCWIter vf_cwbegin(VertexHandle _vh);
  VertexFaceCCWIter vf_ccwbegin(VertexHandle _vh);


  ConstVertexVertexIter cvv_begin(VertexHandle _vh) const;
  ConstVertexVertexCWIter cvv_cwbegin(VertexHandle _vh) const;
  ConstVertexVertexCCWIter cvv_ccwbegin(VertexHandle _vh) const;
  ConstVertexIHalfedgeIter cvih_begin(VertexHandle _vh) const;
  ConstVertexIHalfedgeCWIter cvih_cwbegin(VertexHandle _vh) const;
  ConstVertexIHalfedgeCCWIter cvih_ccwbegin(VertexHandle _vh) const;
  ConstVertexOHalfedgeIter cvoh_begin(VertexHandle _vh) const;
  ConstVertexOHalfedgeCWIter cvoh_cwbegin(VertexHandle _vh) const;
  ConstVertexOHalfedgeCCWIter cvoh_ccwbegin(VertexHandle _vh) const;
  ConstVertexEdgeIter cve_begin(VertexHandle _vh) const;
  ConstVertexEdgeCWIter cve_cwbegin(VertexHandle _vh) const;
  ConstVertexEdgeCCWIter cve_ccwbegin(VertexHandle _vh) const;
  ConstVertexFaceIter cvf_begin(VertexHandle _vh) const;
  ConstVertexFaceCWIter cvf_cwbegin(VertexHandle _vh) const;
  ConstVertexFaceCCWIter cvf_ccwbegin(VertexHandle _vh) const;

  FaceVertexIter fv_begin(FaceHandle _fh);
  FaceVertexCWIter fv_cwbegin(FaceHandle _fh);
  FaceVertexCCWIter fv_ccwbegin(FaceHandle _fh);
  FaceHalfedgeIter fh_begin(FaceHandle _fh);
  FaceHalfedgeCWIter fh_cwbegin(FaceHandle _fh);
  FaceHalfedgeCCWIter fh_ccwbegin(FaceHandle _fh);
  FaceEdgeIter fe_begin(FaceHandle _fh);
  FaceEdgeCWIter fe_cwbegin(FaceHandle _fh);
  FaceEdgeCCWIter fe_ccwbegin(FaceHandle _fh);
  FaceFaceIter ff_begin(FaceHandle _fh);
  FaceFaceCWIter ff_cwbegin(FaceHandle _fh);
  FaceFaceCCWIter ff_ccwbegin(FaceHandle _fh);
  HalfedgeLoopIter hl_begin(HalfedgeHandle _heh);
  HalfedgeLoopCWIter hl_cwbegin(HalfedgeHandle _heh);
  HalfedgeLoopCCWIter hl_ccwbegin(HalfedgeHandle _heh);

  ConstFaceVertexIter cfv_begin(FaceHandle _fh) const;
  ConstFaceVertexCWIter cfv_cwbegin(FaceHandle _fh) const;
  ConstFaceVertexCCWIter cfv_ccwbegin(FaceHandle _fh) const;
  ConstFaceHalfedgeIter cfh_begin(FaceHandle _fh) const;
  ConstFaceHalfedgeCWIter cfh_cwbegin(FaceHandle _fh) const;
  ConstFaceHalfedgeCCWIter cfh_ccwbegin(FaceHandle _fh) const;
  ConstFaceEdgeIter cfe_begin(FaceHandle _fh) const;
  ConstFaceEdgeCWIter cfe_cwbegin(FaceHandle _fh) const;
  ConstFaceEdgeCCWIter cfe_ccwbegin(FaceHandle _fh) const;
  ConstFaceFaceIter cff_begin(FaceHandle _fh) const;
  ConstFaceFaceCWIter cff_cwbegin(FaceHandle _fh) const;
  ConstFaceFaceCCWIter cff_ccwbegin(FaceHandle _fh) const;
  ConstHalfedgeLoopIter chl_begin(HalfedgeHandle _heh) const;
  ConstHalfedgeLoopCWIter chl_cwbegin(HalfedgeHandle _heh) const;
  ConstHalfedgeLoopCCWIter chl_ccwbegin(HalfedgeHandle _heh) const;
  
  // 'end' circulators
  
  VertexVertexIter vv_end(VertexHandle _vh);
  VertexVertexCWIter vv_cwend(VertexHandle _vh);
  VertexVertexCCWIter vv_ccwend(VertexHandle _vh);
  VertexIHalfedgeIter vih_end(VertexHandle _vh);
  VertexIHalfedgeCWIter vih_cwend(VertexHandle _vh);
  VertexIHalfedgeCCWIter vih_ccwend(VertexHandle _vh);
  VertexOHalfedgeIter voh_end(VertexHandle _vh);
  VertexOHalfedgeCWIter voh_cwend(VertexHandle _vh);
  VertexOHalfedgeCCWIter voh_ccwend(VertexHandle _vh);
  VertexEdgeIter ve_end(VertexHandle _vh);
  VertexEdgeCWIter ve_cwend(VertexHandle _vh);
  VertexEdgeCCWIter ve_ccwend(VertexHandle _vh);
  VertexFaceIter vf_end(VertexHandle _vh);
  VertexFaceCWIter vf_cwend(VertexHandle _vh);
  VertexFaceCCWIter vf_ccwend(VertexHandle _vh);

  ConstVertexVertexIter cvv_end(VertexHandle _vh) const;
  ConstVertexVertexCWIter cvv_cwend(VertexHandle _vh) const;
  ConstVertexVertexCCWIter cvv_ccwend(VertexHandle _vh) const;
  ConstVertexIHalfedgeIter cvih_end(VertexHandle _vh) const;
  ConstVertexIHalfedgeCWIter cvih_cwend(VertexHandle _vh) const;
  ConstVertexIHalfedgeCCWIter cvih_ccwend(VertexHandle _vh) const;
  ConstVertexOHalfedgeIter cvoh_end(VertexHandle _vh) const;
  ConstVertexOHalfedgeCWIter cvoh_cwend(VertexHandle _vh) const;
  ConstVertexOHalfedgeCCWIter cvoh_ccwend(VertexHandle _vh) const;
  ConstVertexEdgeIter cve_end(VertexHandle _vh) const;
  ConstVertexEdgeCWIter cve_cwend(VertexHandle _vh) const;
  ConstVertexEdgeCCWIter cve_ccwend(VertexHandle _vh) const;
  ConstVertexFaceIter cvf_end(VertexHandle _vh) const;
  ConstVertexFaceCWIter cvf_cwend(VertexHandle _vh) const;
  ConstVertexFaceCCWIter cvf_ccwend(VertexHandle _vh) const;

  FaceVertexIter fv_end(FaceHandle _fh);
  FaceVertexCWIter fv_cwend(FaceHandle _fh);
  FaceVertexCCWIter fv_ccwend(FaceHandle _fh);
  FaceHalfedgeIter fh_end(FaceHandle _fh);
  FaceHalfedgeCWIter fh_cwend(FaceHandle _fh);
  FaceHalfedgeCCWIter fh_ccwend(FaceHandle _fh);
  FaceEdgeIter fe_end(FaceHandle _fh);
  FaceEdgeCWIter fe_cwend(FaceHandle _fh);
  FaceEdgeCCWIter fe_ccwend(FaceHandle _fh);
  FaceFaceIter ff_end(FaceHandle _fh);
  FaceFaceCWIter ff_cwend(FaceHandle _fh);
  FaceFaceCCWIter ff_ccwend(FaceHandle _fh);
  HalfedgeLoopIter hl_end(HalfedgeHandle _heh);
  HalfedgeLoopCWIter hl_cwend(HalfedgeHandle _heh);
  HalfedgeLoopCCWIter hl_ccwend(HalfedgeHandle _heh);

  ConstFaceVertexIter cfv_end(FaceHandle _fh) const;
  ConstFaceVertexCWIter cfv_cwend(FaceHandle _fh) const;
  ConstFaceVertexCCWIter cfv_ccwend(FaceHandle _fh) const;
  ConstFaceHalfedgeIter cfh_end(FaceHandle _fh) const;
  ConstFaceHalfedgeCWIter cfh_cwend(FaceHandle _fh) const;
  ConstFaceHalfedgeCCWIter cfh_ccwend(FaceHandle _fh) const;
  ConstFaceEdgeIter cfe_end(FaceHandle _fh) const;
  ConstFaceEdgeCWIter cfe_cwend(FaceHandle _fh) const;
  ConstFaceEdgeCCWIter cfe_ccwend(FaceHandle _fh) const;
  ConstFaceFaceIter cff_end(FaceHandle _fh) const;
  ConstFaceFaceCWIter cff_cwend(FaceHandle _fh) const;
  ConstFaceFaceCCWIter cff_ccwend(FaceHandle _fh) const;
  ConstHalfedgeLoopIter chl_end(HalfedgeHandle _heh) const;
  ConstHalfedgeLoopCWIter chl_cwend(HalfedgeHandle _heh) const;
  ConstHalfedgeLoopCCWIter chl_ccwend(HalfedgeHandle _heh) const;


  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstVertexIter,
          &PolyConnectivity::vertices_begin,
          &PolyConnectivity::vertices_end>> ConstVertexRange;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstVertexIter,
          &PolyConnectivity::vertices_sbegin,
          &PolyConnectivity::vertices_end>> ConstVertexRangeSkipping;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstHalfedgeIter,
          &PolyConnectivity::halfedges_begin,
          &PolyConnectivity::halfedges_end>> ConstHalfedgeRange;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstHalfedgeIter,
          &PolyConnectivity::halfedges_sbegin,
          &PolyConnectivity::halfedges_end>> ConstHalfedgeRangeSkipping;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstEdgeIter,
          &PolyConnectivity::edges_begin,
          &PolyConnectivity::edges_end>> ConstEdgeRange;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstEdgeIter,
          &PolyConnectivity::edges_sbegin,
          &PolyConnectivity::edges_end>> ConstEdgeRangeSkipping;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstFaceIter,
          &PolyConnectivity::faces_begin,
          &PolyConnectivity::faces_end>> ConstFaceRange;
  typedef EntityRange<RangeTraitT<
          const PolyConnectivity,
          PolyConnectivity::ConstFaceIter,
          &PolyConnectivity::faces_sbegin,
          &PolyConnectivity::faces_end>> ConstFaceRangeSkipping;


  template <typename HandleType>
  struct ElementRange;

  ConstVertexRangeSkipping vertices() const;

  ConstVertexRange all_vertices() const;

  ConstHalfedgeRangeSkipping halfedges() const;

  ConstHalfedgeRange all_halfedges() const;

  ConstEdgeRangeSkipping edges() const;

  ConstEdgeRange all_edges() const;

  ConstFaceRangeSkipping faces() const;

  ConstFaceRange all_faces() const;

  template <typename HandleType>
  typename ElementRange<HandleType>::RangeSkipping elements() const;

  template <typename HandleType>
  typename ElementRange<HandleType>::Range all_elements() const;


  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstVertexVertexCWIter,
          VertexHandle,
          VertexHandle,
          &PolyConnectivity::cvv_cwbegin,
          &PolyConnectivity::cvv_cwend>> ConstVertexVertexRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstVertexIHalfedgeIter,
          VertexHandle,
          HalfedgeHandle,
          &PolyConnectivity::cvih_begin,
          &PolyConnectivity::cvih_end>> ConstVertexIHalfedgeRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstVertexOHalfedgeIter,
          VertexHandle,
          HalfedgeHandle,
          &PolyConnectivity::cvoh_begin,
          &PolyConnectivity::cvoh_end>> ConstVertexOHalfedgeRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstVertexEdgeIter,
          VertexHandle,
          EdgeHandle,
          &PolyConnectivity::cve_begin,
          &PolyConnectivity::cve_end>> ConstVertexEdgeRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstVertexFaceIter,
          VertexHandle,
          FaceHandle,
          &PolyConnectivity::cvf_begin,
          &PolyConnectivity::cvf_end>> ConstVertexFaceRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstFaceVertexIter,
          FaceHandle,
          VertexHandle,
          &PolyConnectivity::cfv_begin,
          &PolyConnectivity::cfv_end>> ConstFaceVertexRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstFaceHalfedgeIter,
          FaceHandle,
          HalfedgeHandle,
          &PolyConnectivity::cfh_begin,
          &PolyConnectivity::cfh_end>> ConstFaceHalfedgeRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstFaceEdgeIter,
          FaceHandle,
          EdgeHandle,
          &PolyConnectivity::cfe_begin,
          &PolyConnectivity::cfe_end>> ConstFaceEdgeRange;
  typedef CirculatorRange<CirculatorRangeTraitT<
          PolyConnectivity,
          ConstFaceFaceIter,
          FaceHandle,
          FaceHandle,
          &PolyConnectivity::cff_begin,
          &PolyConnectivity::cff_end>> ConstFaceFaceRange;

  ConstVertexVertexRange vv_range(VertexHandle _vh) const;

  ConstVertexIHalfedgeRange vih_range(VertexHandle _vh) const;

  ConstVertexOHalfedgeRange voh_range(VertexHandle _vh) const;

  ConstVertexEdgeRange ve_range(VertexHandle _vh) const ;

  ConstVertexFaceRange vf_range(VertexHandle _vh) const;

  ConstFaceVertexRange fv_range(FaceHandle _fh) const;

  ConstFaceHalfedgeRange fh_range(FaceHandle _fh) const;

  ConstFaceEdgeRange fe_range(FaceHandle _fh) const;

  ConstFaceFaceRange ff_range(FaceHandle _fh) const;


  //===========================================================================
  //===========================================================================

  bool is_boundary(HalfedgeHandle _heh) const
  { return ArrayKernel::is_boundary(_heh); }

  bool is_boundary(EdgeHandle _eh) const
  {
    return (is_boundary(halfedge_handle(_eh, 0)) ||
            is_boundary(halfedge_handle(_eh, 1)));
  }

  bool is_boundary(VertexHandle _vh) const
  {
    HalfedgeHandle heh(halfedge_handle(_vh));
    return (!(heh.is_valid() && face_handle(heh).is_valid()));
  }

  bool is_boundary(FaceHandle _fh, bool _check_vertex=false) const;

  bool is_manifold(VertexHandle _vh) const;

  // --- shortcuts ---
  
  inline FaceHandle opposite_face_handle(HalfedgeHandle _heh) const
  { return face_handle(opposite_halfedge_handle(_heh)); }
    
  // --- misc ---

  void adjust_outgoing_halfedge(VertexHandle _vh);

  HalfedgeHandle find_halfedge(VertexHandle _start_vh, VertexHandle _end_vh) const;
  uint valence(VertexHandle _vh) const;
  uint valence(FaceHandle _fh) const;
  
  // --- connectivity operattions 
    
  void collapse(HalfedgeHandle _heh);
  bool is_simple_link(EdgeHandle _eh) const;
  bool is_simply_connected(FaceHandle _fh) const;
  FaceHandle remove_edge(EdgeHandle _eh);
  void reinsert_edge(EdgeHandle _eh);
  HalfedgeHandle insert_edge(HalfedgeHandle _prev_heh, HalfedgeHandle _next_heh);
    
  void split(FaceHandle _fh, VertexHandle _vh);

  void split_copy(FaceHandle _fh, VertexHandle _vh);
  
  void triangulate(FaceHandle _fh);

  void triangulate();
  
  void split_edge(EdgeHandle _eh, VertexHandle _vh);

  void split_edge_copy(EdgeHandle _eh, VertexHandle _vh);


  const Vertex&    deref(VertexHandle _h)   const { return vertex(_h); }
  Vertex&          deref(VertexHandle _h)         { return vertex(_h); }
  const Halfedge&  deref(HalfedgeHandle _h) const { return halfedge(_h); }
  Halfedge&        deref(HalfedgeHandle _h)       { return halfedge(_h); }
  const Edge&      deref(EdgeHandle _h)     const { return edge(_h); }
  Edge&            deref(EdgeHandle _h)           { return edge(_h); }
  const Face&      deref(FaceHandle _h)     const { return face(_h); }
  Face&            deref(FaceHandle _h)           { return face(_h); }

protected:  
  void collapse_edge(HalfedgeHandle _hh);
  void collapse_loop(HalfedgeHandle _hh);



private: // Working storage for add_face()
       struct AddFaceEdgeInfo
       {
               HalfedgeHandle halfedge_handle;
               bool is_new;
               bool needs_adjust;
       };
       std::vector<AddFaceEdgeInfo> edgeData_; //
       std::vector<std::pair<HalfedgeHandle, HalfedgeHandle> > next_cache_; // cache for set_next_halfedge and vertex' set_halfedge

};

template <>
struct PolyConnectivity::ElementRange<VertexHandle>
{
  using Range         = ConstVertexRange;
  using RangeSkipping = ConstVertexRangeSkipping;
};

template <>
struct PolyConnectivity::ElementRange<HalfedgeHandle>
{
  using Range         = ConstHalfedgeRange;
  using RangeSkipping = ConstHalfedgeRangeSkipping;
};

template <>
struct PolyConnectivity::ElementRange<EdgeHandle>
{
  using Range         = ConstEdgeRange;
  using RangeSkipping = ConstEdgeRangeSkipping;
};

template <>
struct PolyConnectivity::ElementRange<FaceHandle>
{
  using Range         = ConstFaceRange;
  using RangeSkipping = ConstFaceRangeSkipping;
};

}//namespace OpenMesh

#include <OpenMesh/Core/Mesh/PolyConnectivity_inline_impl.hh>

#endif//OPENMESH_POLYCONNECTIVITY_HH