[Boost-commit] svn:boost r38557 - in sandbox/SOC/2007/geometry/libs/hdstl/dev: euler halfedge_ds

From: huseyinakcan_at_[hidden]
Date: 2007-08-09 21:19:02

Author: huseyinakcan
Date: 2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
New Revision: 38557
URL: http://svn.boost.org/trac/boost/changeset/38557

Log:
more Euler operators implemented
base functions corrected and tested

Text files modified: 
   sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp           |   256 ++++++++++++++++++++++++++++++--------- 
   sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp         |   105 ++++------------                        
   sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp          |   216 +++++++++++++++++++++++++++++++--       
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp        |   115 ++++++-----------                       
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp |     5                                         
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp     |     5                                         
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp   |     3                                         
   7 files changed, 475 insertions(+), 230 deletions(-)

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.hpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -28,88 +28,171 @@
 namespace boost {
 namespace hdstl {
 
-// \cond
-namespace detail {
 
-template<typename HalfedgeGen, typename Tag=next_in_facet_tag>
-struct stitch_cycle_helper
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_next_in_facet(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor 
+                , HalfedgeGen& , Tag const& )
 {
-    static void
-    stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    {
-        set_next_in_facet(h,g,hds);
-    }
-};
+    // No-op
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, prev_in_facet_tag>
+template <typename HalfedgeGen>
+void
+stitch_next_in_facet(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+                , HalfedgeGen& hds,  next_in_facet_tag const&)
 {
-    static void
-    stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    {
-        set_prev_in_facet(h,g,hds);
-    }
-};
+    set_next_in_facet(h,g,hds);
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, next_at_source_tag>
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_prev_in_facet(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor 
+                , HalfedgeGen& , Tag const& )
 {
-    static void
-    stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    {
-        set_next_at_source(h,g,hds);
-    }
-};
+    // No-op
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, prev_at_source_tag>
+template <typename HalfedgeGen>
+void
+stitch_prev_in_facet(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+                , HalfedgeGen& hds,  prev_in_facet_tag const&)
 {
-    static void
-    stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    {
-        set_prev_at_source(h,g,hds);
-    }
-};
+    set_prev_in_facet(h,g,hds);
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, next_at_target_tag>
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_next_at_source(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor 
+               , HalfedgeGen& , Tag const& )
 {
-    static void
-    stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    {
-        set_next_at_target(h,g,hds);
-    }
-};
+    // No-op
+}
 
-template<typename HalfedgeGen>
-struct stitch_cycle_helper<HalfedgeGen, prev_at_target_tag>
+template <typename HalfedgeGen>
+void
+stitch_next_at_source(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+                 , HalfedgeGen& hds,  next_at_source_tag const&)
 {
-    static void
-    stitch(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    {
-        set_prev_at_target(h,g,hds);
-    }
-};
+    set_next_at_source(h,g,hds);
+}
 
-} // end namespace detail
-// \endcond
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_prev_at_source(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor 
+               , HalfedgeGen& , Tag const& )
+{
+    // No-op
+}
 
 template <typename HalfedgeGen>
 void
-stitch_next(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    // Sets the appropriate forward accessor relations between h and g, based on the configuration of the 'hds'
+stitch_prev_at_source(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+                 , HalfedgeGen& hds,  prev_at_source_tag const&)
 {
-    typedef typename HalfedgeGen::halfedge_selector::next_tag tag;
-    detail::stitch_cycle_helper<HalfedgeGen, tag>::stitch(h,g,hds);
+    set_prev_at_source(h,g,hds);
+}
+
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_next_at_target(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor 
+               , HalfedgeGen& , Tag const& )
+{
+    // No-op
 }
 
 template <typename HalfedgeGen>
 void
-stitch_prev(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g, HalfedgeGen& hds)
-    // Sets the appropriate backward accessor relations between h and g, based on the configuration of the 'hds'
+stitch_next_at_target(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+                 , HalfedgeGen& hds,  next_at_target_tag const&)
 {
-    typedef typename HalfedgeGen::halfedge_selector::prev_tag tag;
-    detail::stitch_cycle_helper<HalfedgeGen, tag>::stitch(h,g,hds);
+    set_next_at_target(h,g,hds);
+}
+
+template <typename HalfedgeGen, typename Tag>
+void
+stitch_prev_at_target(typename HalfedgeGen::halfedge_descriptor , typename HalfedgeGen::halfedge_descriptor 
+               , HalfedgeGen& , Tag const& )
+{
+    // No-op
+}
+
+template <typename HalfedgeGen>
+void
+stitch_prev_at_target(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+                 , HalfedgeGen& hds,  prev_at_target_tag const&)
+{
+    set_prev_at_target(h,g,hds);
+}
+
+template <typename HalfedgeGen, typename ForwardCategory>
+typename HalfedgeGen::halfedge_descriptor
+get_next_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, ForwardCategory const&)
+{
+    return static_cast<typename HalfedgeGen::halfedge_descriptor>(next_in_facet(h, hds));
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::halfedge_descriptor
+get_next_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, empty_tag const&)
+{
+    // No-op
+}
+
+template <typename HalfedgeGen, typename BackwardCategory>
+typename HalfedgeGen::halfedge_descriptor
+get_prev_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, BackwardCategory const&)
+{
+    return static_cast<typename HalfedgeGen::halfedge_descriptor>(prev_in_facet(h, hds));
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::halfedge_descriptor
+get_prev_in_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, empty_tag const&)
+{
+    // No-op
+}
+
+template <typename HalfedgeGen, typename FacetS>
+typename HalfedgeGen::facet_descriptor
+get_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, FacetS const&)
+{
+    return facet(h, hds);
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::facet_descriptor
+get_facet(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, noFacetS const&)
+{
+    // No-op
+}
+
+template <typename HalfedgeGen, typename Type>
+typename HalfedgeGen::vertex_descriptor
+get_source(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, Type const&)
+{
+    // No-op
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::vertex_descriptor
+get_source(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, sourceS const&)
+{
+    return source(h, hds);
+}
+
+template <typename HalfedgeGen, typename Type>
+typename HalfedgeGen::vertex_descriptor
+get_target(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, Type const&)
+{
+    // No-op
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::vertex_descriptor
+get_target(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds, targetS const&)
+{
+    return target(h, hds);
 }
 
 // \cond
@@ -202,6 +285,59 @@
                                 >::stitch(h,v,hds,vds);
 }
 
+template <typename HalfedgeGen>
+void
+splice(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descritor g
+     , typename HalfedgeGen::halfedge_descriptor i, typename HalfedgeGen::halfedge_descritor j, HalfedgeGen& hds)
+{
+    typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+    typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag; 
+
+    stitch_next_in_facet(h, j, hds, next_tag());                    
+    stitch_prev_in_facet(j, h, hds, prev_tag());
+    
+    stitch_next_in_facet(i, g, hds, next_tag());                    
+    stitch_prev_in_facet(g, i, hds, prev_tag());
+    
+    stitch_next_at_source(opposite(h, hds), j, hds, next_tag()); 
+    stitch_prev_at_source(j, opposite(h, hds), hds, prev_tag());
+    
+    stitch_next_at_source(opposite(i, hds), g, hds, next_tag());    
+    stitch_prev_at_source(g, opposite(i, hds), hds, prev_tag());
+    
+    stitch_next_at_target(h, opposite(j, hds), hds, next_tag());    
+    stitch_prev_at_target(opposite(j, hds), h, hds, prev_tag());
+    
+    stitch_next_at_target(i, opposite(g, hds), hds, next_tag());    
+    stitch_prev_at_target(opposite(g, hds), i, hds, prev_tag());
+}
+
+template <typename HalfedgeGen>
+void
+detach(typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descritor g
+     , typename HalfedgeGen::halfedge_descriptor i, typename HalfedgeGen::halfedge_descritor j, HalfedgeGen& hds)
+{
+    typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+    typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag; 
+
+    stitch_next_in_facet(h, g, hds, next_tag());                    
+    stitch_prev_in_facet(g, h, hds, prev_tag());
+    
+    stitch_next_in_facet(i, j, hds, next_tag());                    
+    stitch_prev_in_facet(j, i, hds, prev_tag());
+    
+    stitch_next_at_source(opposite(h, hds), g, hds, next_tag());    
+    stitch_prev_at_source(g, opposite(h, hds), hds, prev_tag());
+    
+    stitch_next_at_source(opposite(i, hds), j, hds, next_tag());    
+    stitch_prev_at_source(j, opposite(i, hds), hds, prev_tag());
+    
+    stitch_next_at_target(h, opposite(g, hds), hds, next_tag());    
+    stitch_prev_at_target(opposite(g, hds), h, hds, prev_tag());
+    
+    stitch_next_at_target(i, opposite(j, hds), hds, next_tag());    
+    stitch_prev_at_target(opposite(j, hds), i, hds, prev_tag());
+}
 } // end namespace hdstl
 } // end namespace boost
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/base_functions.t.cpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -10,8 +10,7 @@
 #include <boost/hdstl/halfedge_ds/halfedge_selectors.hpp>
 #include <boost/hdstl/halfedge_ds/facet_functions.hpp>
 #include <boost/hdstl/halfedge_ds/vertex_functions.hpp>
-#include <boost/hdstl/halfedge_ds/meta_functions.hpp>
-#include <boost/pending/ct_if.hpp>
+#include <boost/hdstl/halfedge_ds/halfedge_ds.hpp>
 #include <boost/test/minimal.hpp>
 
 #include <set>
@@ -25,73 +24,6 @@
 //                              CLASS HALFEDGE_GEN
 // ===========================================================================
 
-typedef void* halfedge_ptr;
-
-template <typename HalfedgeS, typename VertexS, typename FacetS>
-struct halfedge_config {
-    // This halfedge_config to identically replace the halfedge_ds_gen::config
-    // and reproduced here for test purposes only. Note that this tests are 
-    // not for the config class, but the halfedge_selectors, so config will
-    // be tested in its own package.
-
-    enum {
-        halfedge_has_opposite_member = !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value,
-        is_forward = HalfedgeS::is_forward,
-        is_backward = HalfedgeS::is_backward,
-        halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
-        is_source = VertexS::is_source,
-        halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
-    };
-    typedef typename boost::ct_if<halfedge_has_opposite_member,
-                  halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
-template <typename HalfedgeS>
-struct halfedge_config<HalfedgeS, noVertexS, noFacetS> {
-    enum {
-        halfedge_has_opposite_member = !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value,
-        is_forward = HalfedgeS::is_forward,
-        is_backward = HalfedgeS::is_backward,
-        halfedge_supports_vertices = false,
-        is_source = false,
-        halfedge_supports_facets = false
-    };
-    typedef typename boost::ct_if<halfedge_has_opposite_member,
-                  halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
-template <typename HalfedgeS, typename FacetS>
-struct halfedge_config<HalfedgeS, noVertexS, FacetS> {
-    enum {
-        halfedge_has_opposite_member = !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value,
-        is_forward = HalfedgeS::is_forward,
-        is_backward = HalfedgeS::is_backward,
-        halfedge_supports_vertices = false,
-        is_source = false,
-        halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
-    };
-    typedef typename boost::ct_if<halfedge_has_opposite_member,
-                  halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
-template <typename HalfedgeS, typename VertexS>
-struct halfedge_config<HalfedgeS, VertexS, noFacetS> {
-    enum {
-        halfedge_has_opposite_member = !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value,
-        is_forward = HalfedgeS::is_forward,
-        is_backward = HalfedgeS::is_backward,
-        halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
-        is_source = VertexS::is_source,
-        halfedge_supports_facets = false
-    };
-    typedef typename boost::ct_if<halfedge_has_opposite_member,
-                  halfedge_ptr, std::size_t>::type halfedge_descriptor;
-};
-
 template <typename HalfedgeGen>
 void create_hds(HalfedgeGen& halfedgeGen){
     // Types must exist.
@@ -128,9 +60,13 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
-    stitch_next(ha, hb, halfedgeGen);
+    stitch_next_in_facet(ha, hb, halfedgeGen, next_in_facet_tag());
+    stitch_next_at_source(ha, hb, halfedgeGen, next_in_facet_tag());
+    stitch_next_at_target(ha, hb, halfedgeGen, next_in_facet_tag());
     
     BOOST_CHECK(( next_in_facet(ha, halfedgeGen) == hb )); 
+    BOOST_CHECK(( get_next_in_facet(ha, halfedgeGen, next_in_facet_tag()) == hb )); 
+
     return true;
 }
 
@@ -148,7 +84,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
-    stitch_next(ha, hb, halfedgeGen);
+    stitch_next_in_facet(ha, hb, halfedgeGen, next_at_source_tag());
+    stitch_next_at_source(ha, hb, halfedgeGen, next_at_source_tag());
+    stitch_next_at_target(ha, hb, halfedgeGen, next_at_source_tag());
     
     BOOST_CHECK(( next_at_source(ha, halfedgeGen) == hb )); 
 
@@ -169,7 +107,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
-    stitch_next(ha, hb, halfedgeGen);
+    stitch_next_in_facet(ha, hb, halfedgeGen, next_at_target_tag());
+    stitch_next_at_source(ha, hb, halfedgeGen, next_at_target_tag());
+    stitch_next_at_target(ha, hb, halfedgeGen, next_at_target_tag());
     
     BOOST_CHECK(( next_at_target(ha, halfedgeGen) == hb )); 
 
@@ -190,9 +130,12 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
-    stitch_prev(ha, hb, halfedgeGen);
+    stitch_prev_in_facet(ha, hb, halfedgeGen, prev_in_facet_tag());
+    stitch_prev_at_source(ha, hb, halfedgeGen, prev_in_facet_tag());
+    stitch_prev_at_target(ha, hb, halfedgeGen, prev_in_facet_tag());
     
     BOOST_CHECK(( prev_in_facet(ha, halfedgeGen) == hb )); 
+    BOOST_CHECK(( get_prev_in_facet(ha, halfedgeGen, prev_in_facet_tag()) == hb )); 
 
     return true;
 }
@@ -211,7 +154,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
-    stitch_prev(ha, hb, halfedgeGen);
+    stitch_prev_in_facet(ha, hb, halfedgeGen, prev_at_source_tag());
+    stitch_prev_at_source(ha, hb, halfedgeGen, prev_at_source_tag());
+    stitch_prev_at_target(ha, hb, halfedgeGen, prev_at_source_tag());
     
     BOOST_CHECK(( prev_at_source(ha, halfedgeGen) == hb )); 
 
@@ -232,7 +177,9 @@
     halfedge_descriptor ha = *begin;
     halfedge_descriptor hb = *(++begin);
 
-    stitch_prev(ha, hb, halfedgeGen);
+    stitch_prev_in_facet(ha, hb, halfedgeGen, prev_at_target_tag());
+    stitch_prev_at_source(ha, hb, halfedgeGen, prev_at_target_tag());
+    stitch_prev_at_target(ha, hb, halfedgeGen, prev_at_target_tag());
     
     BOOST_CHECK(( prev_at_target(ha, halfedgeGen) == hb )); 
 
@@ -253,9 +200,9 @@
                     halfedge_gen<
                       halfedgeS<ContainerS, TraversalS>, 
                       int, int, 
-                      halfedge_config<
+                      typename halfedge_ds_gen<
                         halfedgeS<ContainerS, TraversalS>, 
-                        VertexS, FacetS> > 
+                        VertexS, FacetS>::config> 
                   >(next_tag()) ));
    return true;
 }
@@ -270,9 +217,9 @@
                     halfedge_gen<
                       halfedgeS<ContainerS, TraversalS>, 
                       int, int, 
-                      halfedge_config<
+                      typename halfedge_ds_gen<
                         halfedgeS<ContainerS, TraversalS>, 
-                        VertexS, FacetS> > 
+                        VertexS, FacetS>::config> 
                   >(prev_tag()) ));
     return true;
 }

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/euler/euler_operators.hpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -4,9 +4,9 @@
 //
 //@CLASSES:
 //   'create_lens':  
-//   'destroy_lens':
+//   'delete_lens':
 //  'create_torus':  
-//   'destroy_torus'
+//   'delete_torus'
 //   'split_facet':
 //   'join_facets':
 //   'split_vertex':
@@ -14,8 +14,47 @@
 //  
 //@SEE_ALSO: {hds_concepts.hpp, halfedge_ds.hpp}
 //
-//@DESCRIPTION: //
+//@DESCRIPTION:
 //
+//  - 'create_lens': Create_lens is an Euler operator whose purpose is to create a topological ball. It makes a new lens
+//                   (i.e. a vertex, two halfedges, and two faces) and connects them in the HDS.
+//  - 'delete_lens': Delete_lens takes a halfedge which is adjacent to a lens, and reclaims the vertex, the halfedge and
+//                   its opposite, and the two adjacent facets. The behaviour is undefined if the halfedge is not 
+//                   adjacent to a lens.
+//  - 'create_torus': Create_torus is an Euler operator whose purpose is to create a topological torus. The smallest
+//                    torus representable in our HDS is a torus split along a major and a minor circle (one vertex, two
+//                    edges, one facet with one loop, one shell). This torus can be obtained by gluing
+//                    a square along opposite sides (h2 and h4 in figure, top, then the two cycles h1 and h3). Note that
+//                    the torus is completely symmetric in h1, h2, h3 or h4. This functions makes such a new toric HDS,
+//                    and returns the handle to h1.
+//  - 'delete_torus': Delete_torus takes a halfedge which is adjacent to a torus, and reclaims the vertex, the four
+//                    halfedges, and the adjacent facet. The behaviour is undefined if the halfedge is not adjacent to a
+//                    torus.
+//  - 'split_facet':  Split_facet is an Euler operator whose purpose is to insert an edge inside an existing facet,
+//                    attach both its endpoints at two (not necessarily distinct) vertices in the boundary, and split
+//                    the existing facet into two (one which is a copy of the previous one, and a new one which is
+//                    created). If holes are supported, the attach vertices must be both on the outer boundary or on the
+//                    same hole boundary; care must be taken to assign the holes of the split facet to either of the new
+//                    two facets. In this case, our default behavior is to not assign any hole to the new facet that is
+//                    created.  Specifically, h1 and h2 must be consecutive in the facet boundary, same with g1 and g2,
+//                    and all four must be adjacent to the same facet f, and on the same outer or inner boundary if
+//                    holes are supported. Two halfedges k1 and k2 are created, k1 is stitched as the successor of h1
+//                    and predecessor of g2, and k2 becomes the successor of g1 and predecessor of h2; k1 and k2 are
+//                    also stitched in the cycles around the two anchor vertices. A new facet f2 is created and made
+//                    adjacent to k2 and to all its successors and predecessors.  If holes are supported, all the holes
+//                    of f remain assigned to f and none to f2. The halfedge k2 whose incident facet is the new facet f2
+//                    is returned. 
+//
+//  - 'join_facet':   Join_facets is an Euler operator whose purpose is to remove an edge incident to two existing
+//                    facet, and delete one of the two facets while extending the boundary of the other to include both
+//                    boundary cycles (minus the removed edge). If holes are supported, the two facets must be distinct.
+//                    In that case, the new facet contains the holes of both.  Specifically, let f1 be the facet
+//                    incident to k1, k2 its opposite and f2 be the facet incident to k2. The boundary cycle of f2 is
+//                    traversed starting from k2, and the incident facet is set to f1 for all halfedges in this cycle.
+//                    Then, the predecessor h1 of k1 is stitched (in cycle and in facet) with the successor h2 of k2,
+//                    and so are the successor g2 of k1, and the predecessor g1 of k2. Finally k1 and k2 are deleted.
+//                    This operation is strictly the reverse of split_facet and takes the same running time.
+
 ///Usage Example
 //--------------
 // Suppose we want to build a square shaped halfedge data structure from scratch. First 
@@ -68,12 +107,33 @@
           , typename HalfedgeGen::vertex_descriptor v1, typename HalfedgeGen::vertex_descriptor v2
           , typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
 {
-    set_next(h, opposite(h, hds), hds);
-    set_next(opposite(h, hds), h, hds);
-    set_vertex(h, v1, hds);
-    set_vertex(opposite(h), v2, hds);
-    set_facet(h, f1, hds);
-    set_facet(opposite(h), v2, hds);
+    typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+    typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag; 
+    typedef typename HalfedgeGen::facet_selector facet_tag;
+    typedef typename HalfedgeGen::vertex_selector vertex_tag;
+
+    stitch_next_in_facet(h, h, hds, next_tag());
+    stitch_prev_in_facet(h, h, hds, prev_tag());
+    
+    stitch_next_in_facet(opposite(h, hds), opposite(h, hds), hds, next_tag());
+    stitch_prev_in_facet(opposite(h, hds), opposite(h, hds), hds, prev_tag());
+
+    stitch_next_at_source(h, opposite(h,hds), hds, next_tag());
+    stitch_prev_at_source(opposite(h,hds), h, hds, prev_tag());
+    
+    stitch_next_at_source(opposite(h,hds), h, hds, next_tag());
+    stitch_prev_at_source(h, opposite(h,hds), hds, prev_tag());
+
+    stitch_next_at_target(h, opposite(h,hds), hds, next_tag());
+    stitch_prev_at_target(opposite(h,hds), h, hds, prev_tag());
+    
+    stitch_next_at_target(opposite(h,hds), h, hds, next_tag());
+    stitch_prev_at_target(h, opposite(h,hds), hds, prev_tag());
+
+    stitch_set_facet(h, f1, hds, facet_tag());
+    stitch_set_facet(opposite(h), f2, hds, facet_tag());
+    stitch_set_vertex(h, v1, hds, vertex_tag());
+    stitch_set_vertex(opposite(h), v2, hds, vertex_tag());
 }
 
 template <typename HalfedgeGen>
@@ -81,10 +141,30 @@
 create_lens(typename HalfedgeGen::vertex_descriptor v1, typename HalfedgeGen::vertex_descriptor v2
           , typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
 {
-    set_next(h, opposite(h, hds), hds);
-    set_next(opposite(h, hds), h, hds);
-    set_vertex(h, v1, hds);
-    set_vertex(opposite(h), v2, hds);
+    typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+    typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag; 
+    typedef typename HalfedgeGen::vertex_selector vertex_tag;
+
+    stitch_next_in_facet(h, h, hds, next_tag());
+    stitch_prev_in_facet(h, h, hds, prev_tag());
+    
+    stitch_next_in_facet(opposite(h, hds), opposite(h, hds), hds, next_tag());
+    stitch_prev_in_facet(opposite(h, hds), opposite(h, hds), hds, prev_tag());
+
+    stitch_next_at_source(h, opposite(h,hds), hds, next_tag());
+    stitch_prev_at_source(opposite(h,hds), h, hds, prev_tag());
+    
+    stitch_next_at_source(opposite(h,hds), h, hds, next_tag());
+    stitch_prev_at_source(h, opposite(h,hds), hds, prev_tag());
+
+    stitch_next_at_target(h, opposite(h,hds), hds, next_tag());
+    stitch_prev_at_target(opposite(h,hds), h, hds, prev_tag());
+    
+    stitch_next_at_target(opposite(h,hds), h, hds, next_tag());
+    stitch_prev_at_target(h, opposite(h,hds), hds, prev_tag());
+    
+    stitch_set_vertex(h, v1, hds, vertex_tag());
+    stitch_set_vertex(opposite(h), v2, hds, vertex_tag());
 }
 
 template <typename HalfedgeGen>
@@ -92,17 +172,119 @@
 create_lens(typename HalfedgeGen::facet_descriptor f1, typename HalfedgeGen::facet_descriptor f2
           , typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
 {
-    set_next(h, opposite(h, hds), hds);
-    set_next(opposite(h, hds), h, hds);
-    set_facet(h, f1, hds);
-    set_facet(opposite(h), v2, hds);
+    typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+    typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag; 
+    typedef typename HalfedgeGen::facet_selector facet_tag;
+
+    stitch_next_in_facet(h, h, hds, next_tag());
+    stitch_prev_in_facet(h, h, hds, prev_tag());
+    
+    stitch_next_in_facet(opposite(h, hds), opposite(h, hds), hds, next_tag());
+    stitch_prev_in_facet(opposite(h, hds), opposite(h, hds), hds, prev_tag());
+
+    stitch_next_at_source(h, opposite(h,hds), hds, next_tag());
+    stitch_prev_at_source(opposite(h,hds), h, hds, prev_tag());
+    
+    stitch_next_at_source(opposite(h,hds), h, hds, next_tag());
+    stitch_prev_at_source(h, opposite(h,hds), hds, prev_tag());
+
+    stitch_next_at_target(h, opposite(h,hds), hds, next_tag());
+    stitch_prev_at_target(opposite(h,hds), h, hds, prev_tag());
+    
+    stitch_next_at_target(opposite(h,hds), h, hds, next_tag());
+    stitch_prev_at_target(h, opposite(h,hds), hds, prev_tag());
+    
+    stitch_set_facet(h, f1, hds, facet_tag());
+    stitch_set_facet(opposite(h), f2, hds, facet_tag());
 }
 
 template <typename HalfedgeGen>
 typename HalfedgeGen::halfedge_descriptor
 create_lens(HalfedgeGen& hds)
 {
+    // in order to use this method with no parameters except hds, we have to use specialized helpers
+    // to create the lens based on the many configuration options such as has vertex, has facet etc...
+}
+
+template <typename HalfedgeGen>
+void
+delete_lens(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
+{
+    delete_vertex(source(h, hds), hds);
+    delete_facet(facet(h, hds), hds);
+    delete_edge(h, hds);
+}
+
+template <typename HalfedgeGen>
+typename HalfedgeGen::halfedge_descriptor
+create_torus(typename HalfedgeGen::facet_descriptor f, typename HalfedgeGen::vertex_descriptor v 
+           , typename HalfedgeGen::halfedge_descriptor h, typename HalfedgeGen::halfedge_descriptor g
+           , HalfedgeGen& hds)
+{
+    typedef typename HalfedgeGen::halfedge_selector::next_tag next_tag;
+    typedef typename HalfedgeGen::halfedge_selector::prev_tag prev_tag; 
+    typedef typename HalfedgeGen::facet_selector facet_tag;
+    typedef typename HalfedgeGen::vertex_selector vertex_tag;
+
+    stitch_next_in_facet(h, g, hds, next_tag());
+    stitch_prev_in_facet(g, h, hds, prev_tag());
+
+    stitch_next_in_facet(g, opposite(h, hds) , hds, next_tag());
+    stitch_prev_in_facet(opposite(h, hds), g , hds, prev_tag());
+
+    stitch_next_in_facet(opposite(h, hds), opposite(g, hds), hds, next_tag());
+    stitch_prev_in_facet(opposite(g, hds), opposite(h, hds), hds, prev_tag());
+
+    stitch_next_in_facet(opposite(g, hds), h, hds, next_tag());
+    stitch_prev_in_facet(h, opposite(g, hds), hds, prev_tag());
+
+    stitch_next_at_source(h, opposite(g,hds), hds, next_tag());
+    stitch_prev_at_source(opposite(g,hds), h, hds, prev_tag());
+
+    stitch_next_at_source(opposite(g,hds), opposite(h,hds), hds, next_tag());
+    stitch_prev_at_source(opposite(h,hds), opposite(g,hds), hds, prev_tag());
+
+    stitch_next_at_source(opposite(h,hds), g, hds, next_tag());
+    stitch_prev_at_source(opposite(g,hds), h, hds, prev_tag());
+
+    stitch_next_at_source(g, h, hds, next_tag());
+    stitch_prev_at_source(h, g, hds, prev_tag());
+
+    stitch_next_at_target(h, opposite(g,hds), hds, next_tag());
+    stitch_prev_at_target(opposite(g,hds), h, hds, prev_tag());
+
+    stitch_next_at_target(opposite(g,hds), opposite(h,hds), hds, next_tag());
+    stitch_prev_at_target(opposite(h,hds), opposite(g,hds), hds, prev_tag());
+
+    stitch_next_at_target(opposite(h,hds), g, hds, next_tag());
+    stitch_prev_at_target(g, opposite(h,hds), hds, prev_tag());
+
+    stitch_next_at_target(g, h, hds, next_tag());
+    stitch_prev_at_target(h, g, hds, prev_tag());
+
+    stitch_set_vertex(h, v, hds, vertex_tag());
+    stitch_set_vertex(opposite(h, hds), v, hds, vertex_tag());
+    stitch_set_vertex(g, v, hds, vertex_tag());
+    stitch_set_vertex(opposite(g, hds), v, hds, vertex_tag());
+    stitch_set_facet(h, f, hds, facet_tag());
+    stitch_set_facet(opposite(h, hds), f, hds, facet_tag());
+    stitch_set_facet(g, f, hds, facet_tag());
+    stitch_set_facet(opposite(g, hds), f, hds, facet_tag());
+}
+
+template <typename HalfedgeGen>
+void
+delete_torus(typename HalfedgeGen::halfedge_descriptor h, HalfedgeGen& hds)
+{
+    typedef typename HalfedgeGen::halfedge_selector halfedge_selector;
+    typename HalfedgeGen::halfedge_descriptor op_h = opposite(h, hds);
+    typename HalfedgeGen::halfedge_descriptor g = get_next_in_facet(h, hds, halfedge_selector::is_forward);
+    g = get_prev_in_facet(h, hds, halfedge_selector::is_backward);
+    typename HalfedgeGen::halfedge_descriptor op_g = opposite(g, hds);
 
+    delete_vertex(source(h, hds), hds);
+    delete_facet(facet(h, hds), hds);
+    delete_edge(h, hds);
 }
 
 } // end namespace hdstl

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_ds.hpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -34,109 +34,78 @@
 #include <boost/hdstl/halfedge_ds/halfedge_selectors.hpp>
 #include <boost/hdstl/halfedge_ds/vertex_selectors.hpp>
 #include <boost/hdstl/halfedge_ds/facet_selectors.hpp>
+#include <boost/pending/ct_if.hpp>
 
 namespace boost {
 namespace hdstl {
 
+typedef void* halfedge_ptr;
 
 template <typename HalfedgeS, typename VertexS, typename FacetS>
 struct halfedge_ds_gen {
     struct config {
-        
-        enum { halfedge_has_opposite_member =  !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value };
-        enum { is_forward = HalfedgeS::is_forward };
-        enum { is_backward = HalfedgeS::is_backward };
-        typedef typename HalfedgeS::tag traversal_tag;
-            // halfedge config
-
-        enum { halfedge_supports_vertices = !meta_is_same<
-                                                 VertexS,noVertexS>::value }; 
-        enum { is_source = VertexS::is_source };
-        enum { is_target = VertexS::is_target };
-        enum { has_vertex_link = VertexS::has_vertex_link };
-            // vertex config
-        
-        enum { halfedge_supports_facets= !meta_is_same<FacetS,noFacetS>::value}; 
-            // facet config
-
+        enum {
+            halfedge_has_opposite_member = !meta_is_same<
+                typename HalfedgeS::container_selector, vecS>::value,
+            is_forward = HalfedgeS::is_forward,
+            is_backward = HalfedgeS::is_backward,
+            halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
+            is_source = VertexS::is_source,
+            halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
+        };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
-              halfedge_ptr, std::size_t>::type halfedge_descriptor;
+                halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 
 template <typename HalfedgeS>
 struct halfedge_ds_gen<HalfedgeS, noVertexS, noFacetS> {
     struct config {
-        
-        enum { halfedge_has_opposite_member =  !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value };
-        enum { is_forward = HalfedgeS::is_forward };
-        enum { is_backward = HalfedgeS::is_backward };
-        typedef typename HalfedgeS::tag traversal_tag;
-            // halfedge config
-        
-        enum { halfedge_supports_vertices = false };
-        enum { is_source = false }; // has no meaning here, 
-                                    // but vertex_helper in stored_halfedge 
-                                    // requires it defined even for noVertexS.
-        enum { is_target = false }; // has no meaning here 
-        
-        enum { halfedge_supports_facets = false };
-        
+        enum {
+            halfedge_has_opposite_member = !meta_is_same<
+                typename HalfedgeS::container_selector, vecS>::value,
+            is_forward = HalfedgeS::is_forward,
+            is_backward = HalfedgeS::is_backward,
+            halfedge_supports_vertices = false,
+            is_source = false,
+            halfedge_supports_facets = false
+        };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
-              halfedge_ptr, std::size_t>::type halfedge_descriptor;
+                halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 
 template <typename HalfedgeS, typename FacetS>
 struct halfedge_ds_gen<HalfedgeS, noVertexS, FacetS> {
     struct config {
-        
-        enum { halfedge_has_opposite_member =  !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value };
-        enum { is_forward = HalfedgeS::is_forward };
-        enum { is_backward = HalfedgeS::is_backward };
-        typedef typename HalfedgeS::tag traversal_tag;
-            // halfedge config
-
-        enum { halfedge_supports_vertices = false };
-        enum { is_source = false }; // has no meaning here, 
-                                    // but vertex_helper in stored_halfedge 
-                                    // requires it defined even for noVertexS.
-        enum { is_target = false }; // has no meaning here 
-        
-        enum { halfedge_supports_facets= !meta_is_same<FacetS,noFacetS>::value}; 
-            // facet config
-        
+        enum {
+            halfedge_has_opposite_member = !meta_is_same<
+                typename HalfedgeS::container_selector, vecS>::value,
+            is_forward = HalfedgeS::is_forward,
+            is_backward = HalfedgeS::is_backward,
+            halfedge_supports_vertices = false,
+            is_source = false,
+            halfedge_supports_facets = !meta_is_same<FacetS,noFacetS>::value
+        };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
-              halfedge_ptr, std::size_t>::type halfedge_descriptor;
+                halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 
 template <typename HalfedgeS, typename VertexS>
 struct halfedge_ds_gen<HalfedgeS, VertexS, noFacetS> {
     struct config {
-        
-        enum { halfedge_has_opposite_member =  !meta_is_same<
-                        typename HalfedgeS::container_selector, vecS>::value };
-        enum { is_forward = HalfedgeS::is_forward };
-        enum { is_backward = HalfedgeS::is_backward };
-        typedef typename HalfedgeS::tag traversal_tag;
-            // halfedge config
-
-        enum { halfedge_supports_vertices = !meta_is_same<
-                                                 VertexS,noVertexS>::value }; 
-        enum { is_source = VertexS::is_source };
-        enum { is_target = VertexS::is_target };
-        enum { has_vertex_link = VertexS::has_vertex_link };
-            // vertex config
-        
-        enum { halfedge_supports_facets= false }; 
-            // facet config
-        
+        enum {
+            halfedge_has_opposite_member = !meta_is_same<
+                typename HalfedgeS::container_selector, vecS>::value,
+            is_forward = HalfedgeS::is_forward,
+            is_backward = HalfedgeS::is_backward,
+            halfedge_supports_vertices = !meta_is_same<VertexS,noVertexS>::value,
+            is_source = VertexS::is_source,
+            halfedge_supports_facets = false
+        };
         typedef typename boost::ct_if<halfedge_has_opposite_member,
-              halfedge_ptr, std::size_t>::type halfedge_descriptor;
+                halfedge_ptr, std::size_t>::type halfedge_descriptor;
     };
 };
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_selectors.hpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -37,12 +37,14 @@
 
                    // =========================
                    // halfedge selector classes
-                   // =========================
+                  // =========================
+struct empty_tag {};
 
 template <typename ForwardCategory>
 struct forwardS {
     typedef forward_traversal_tag tag;
     typedef ForwardCategory next_tag;
+    typedef empty_tag prev_tag;
     enum { is_forward = true };
     enum { is_backward = false };
 };
@@ -51,6 +53,7 @@
 struct backwardS {
     typedef backward_traversal_tag tag;
     typedef BackwardCategory prev_tag;
+    typedef empty_tag next_tag;
     enum { is_forward = false };
     enum { is_backward = true };
 };

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/meta_functions.hpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -1,3 +1,7 @@
+
+#ifndef BOOST_HDSTL_META_FUNCTIONS_HPP
+#define BOOST_HDSTL_META_FUNCTIONS_HPP 1
+
 struct true_type {};
 struct false_type{};
 
@@ -13,3 +17,4 @@
     typedef true_type type;
 };
 
+#endif

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_selectors.hpp	2007-08-09 21:19:01 EDT (Thu, 09 Aug 2007)
@@ -191,6 +191,7 @@
 template <typename VertexType>
 struct base_vertexS {
     // A selector that specializes whether source or target vertices are stored.
+    typedef noVertexS t_type;
 };
 
 template<>
@@ -202,6 +203,7 @@
     enum { type = true };
     enum { is_source = true };
     enum { is_target = !is_source };
+    typedef sourceS t_type;
 };
 
 template<>
@@ -213,6 +215,7 @@
     enum { type = false };
     enum { is_target = true };
     enum { is_source = !is_target };
+    typedef targetS t_target;
 };
 
 template <typename ContainerS, bool HasVertexLink=false,