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

From: huseyinakcan_at_[hidden]
Date: 2007-08-03 15:06:40

Author: huseyinakcan
Date: 2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
New Revision: 38425
URL: http://svn.boost.org/trac/boost/changeset/38425

Log:
delete_... functions added and tested.
this version of delete_.. functions are similar
to graph erase functions, two overloaded functions
use descriptors or iterators to carry on container's
erase operation. For out case this is sub-optimal
and should be replaced with a more efficient version
later.

Text files modified: 
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp   |    26 +++++++++++++++++++++++                 
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp |    30 +++++++++++++-------------              
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.hpp       |    22 +++++++++++++++++++                     
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.t.cpp     |    34 +++++++++++++++++++++++++++++           
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.hpp    |    45 ++++++++++++++++++++++++++------------- 
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.t.cpp  |    14 ++++++++----                            
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.hpp      |    22 +++++++++++++++++++                     
   sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.t.cpp    |    34 ++++++++++++++++++++++++++++++          
   8 files changed, 191 insertions(+), 36 deletions(-)

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.hpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -382,6 +382,18 @@
     {
         container.erase(it);
     }
+    
+    static void container_remove(descriptor x, type& container)
+        // This utility removes the element with specified descriptor
+        // 'x' from the specified 'container'.
+    {
+        for (iterator it = container.begin(); it!=container.end(); ++it){
+            if (*it == x){
+                container.erase(it);
+                break;
+            }
+        }
+    }
 
     static ValueType& value(descriptor x, type& container)
             // This utility returns the value associated with the specified
@@ -481,6 +493,13 @@
         container.erase(it);
     }
 
+    static void container_remove(descriptor x, type& container)
+        // This utility removes the element with specified descriptor
+        // 'x' from the specified 'container'.
+    {
+        container.erase(container.find(x));
+    }
+
     static const ValueType& value(descriptor x, type& container)
             // This utility returns the value associated with the specified
             // descriptor 'x' of the specified 'container'.
@@ -600,6 +619,13 @@
         return --container_end(container);
     }
     
+    static void container_remove(descriptor x, type& container)
+        // This utility removes the element with specified descriptor
+        // 'x' from the specified 'container'.
+    {
+        container.erase(container.begin()+x);
+    }
+
     static void container_remove(iterator it, type& container)
         // This utility removes the element with specified iterator
         // 'it' from the specified 'container'.

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/container_selectors.t.cpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -161,21 +161,21 @@
     BOOST_CHECK(( ContainerGen::value(*--end, container) == 0 ));
 
     //remove the elements from container
-    //begin = ContainerGen::container_begin(container);
-    //theBegin = *begin;
-    //BOOST_CHECK(( container.size() == 4 ));
-    ////ContainerGen::container_remove(static_cast<iterator>(*&h0), container);
-    //ContainerGen::container_remove(begin, container);
-    //BOOST_CHECK(( container.size() == 3 ));
-    //begin = ContainerGen::container_begin(container);
-    //ContainerGen::container_remove(begin, container);
-    //BOOST_CHECK(( container.size() == 2 ));
-    //begin = ContainerGen::container_begin(container);
-    //ContainerGen::container_remove(begin, container);
-    //BOOST_CHECK(( container.size() == 1 ));
-    //begin = ContainerGen::container_begin(container);
-    //ContainerGen::container_remove(begin, container);
-    //BOOST_CHECK(( container.empty() ));
+    begin = ContainerGen::container_begin(container);
+    theBegin = *begin;
+    BOOST_CHECK(( container.size() == 4 ));
+    //ContainerGen::container_remove(static_cast<iterator>(*&h0), container);
+    ContainerGen::container_remove(begin, container);
+    BOOST_CHECK(( container.size() == 3 ));
+    begin = ContainerGen::container_begin(container);
+    ContainerGen::container_remove(begin, container);
+    BOOST_CHECK(( container.size() == 2 ));
+    begin = ContainerGen::container_begin(container);
+    ContainerGen::container_remove(begin, container);
+    BOOST_CHECK(( container.size() == 1 ));
+    begin = ContainerGen::container_begin(container);
+    ContainerGen::container_remove(begin, container);
+    BOOST_CHECK(( container.empty() ));
 
     return true;
 }

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.hpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -113,6 +113,28 @@
     return *ContainerGen::container_add(facet_f, hds.m_container);
 }
 
+template <typename FacetS, typename HalfedgeDescriptor, typename FacetBase>
+void
+delete_facet(typename facet_gen<FacetS, HalfedgeDescriptor, FacetBase>::facet_descriptor f,
+             facet_gen<FacetS, HalfedgeDescriptor, FacetBase>& hds)
+    // Delete the facet 'f' from the 'hds'.
+{
+    typedef typename facet_gen<FacetS, HalfedgeDescriptor, FacetBase>::ContainerGen ContainerGen;
+    
+    ContainerGen::container_remove(f, hds.m_container);
+}
+
+template <typename FacetS, typename HalfedgeDescriptor, typename FacetBase>
+void
+delete_facet(typename facet_gen<FacetS, HalfedgeDescriptor, FacetBase>::facet_iterator f,
+             facet_gen<FacetS, HalfedgeDescriptor, FacetBase>& hds)
+    // Delete the facet pointed by the iterator 'f' from the 'hds'.
+{
+    typedef typename facet_gen<FacetS, HalfedgeDescriptor, FacetBase>::ContainerGen ContainerGen;
+    
+    ContainerGen::container_remove(f, hds.m_container);
+}
+
 } // namespace hdstl
 } // namespace boost
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.t.cpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.t.cpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/facet_functions.t.cpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -74,8 +74,16 @@
     BOOST_CHECK(( num_facets(facetGen) == 4 ));
     
     facet_descriptor fn = new_facet(facetGen);
-    (void) fn;
     BOOST_CHECK(( num_facets(facetGen) == 5 ));
+   
+    // test delete with descriptor
+    delete_facet(fn, facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 4 ));
+    
+    // test delete with iterator
+    delete_facet(facets_begin(facetGen), facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 3 ));
+
     return true;
 }
 
@@ -113,6 +121,13 @@
     (void) fn;
     BOOST_CHECK(( num_facets(facetGen) == 5 ));
     
+    // test delete with descriptor
+    delete_facet(fn, facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 4 ));
+    
+    // test delete with iterator
+    delete_facet(facets_begin(facetGen), facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 3 ));
 
     return true;
 }
@@ -146,6 +161,14 @@
     (void) fn;
     BOOST_CHECK(( num_facets(facetGen) == 5 ));
 
+    // test delete with descriptor
+    delete_facet(fn, facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 4 ));
+    
+    // test delete with iterator
+    delete_facet(facets_begin(facetGen), facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 3 ));
+
     return true;
 }
 
@@ -183,6 +206,15 @@
     facet_descriptor fn = new_facet(facetGen);
     (void) fn;
     BOOST_CHECK(( num_facets(facetGen) == 5 ));
+    
+    // test delete with descriptor
+    delete_facet(fn, facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 4 ));
+    
+    // test delete with iterator
+    delete_facet(facets_begin(facetGen), facetGen);
+    BOOST_CHECK(( num_facets(facetGen) == 3 ));
+
     return true;
 }
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.hpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -47,6 +47,8 @@
 //                     around a given vertex in clockwise order.
 //  -        add_edge: creates two halfedges and adds them to 'hds' as an opposite
 //                     pair
+//  -     delete_edge: removes the given halfedge 'h' and its opposite pair from 
+//                     the 'hds' data structure
 //
 //@SEE_ALSO: {hds_concepts.hpp, container_selectors.hpp, halfedge_selectors.hpp}
 
@@ -963,22 +965,35 @@
     return g;
 }
 
-//template <typename HalfedgeS, typename VertexDescriptor, typename FacetDescriptor, typename Config>
-//void
-//delete_edge(typename halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config>::halfedge_descriptor h,
-//            halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config>& hds)
-//    // Remove the halfedge with descriptor 'h' from 'hds'
-//{
-//    typedef halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config> halfedgeGen;
-//    typedef typename halfedgeGen::halfedge_descriptor halfedge_descriptor;
-//    typedef typename halfedgeGen::halfedge_type halfedge_type;
-//    typedef typename halfedgeGen::ContainerGen ContainerGen;
-//    
-//    typedef typename halfedgeGen::halfedge_selector::container_selector containerS;
-//    
-//    ContainerGen::container_remove(*&h, hds.m_container);
-//}
+template <typename HalfedgeS, typename VertexDescriptor, typename FacetDescriptor, typename Config>
+void
+delete_edge(typename halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config>::halfedge_descriptor h,
+            halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config>& hds)
+    // Remove the halfedge with descriptor 'h' and its opposite from 'hds'
+{
+    typedef halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config> halfedgeGen;
+    typedef typename halfedgeGen::halfedge_descriptor halfedge_descriptor;
+    typedef typename halfedgeGen::ContainerGen ContainerGen;
+    
+    halfedge_descriptor g = static_cast<halfedge_descriptor>(opposite(h, hds));
+    ContainerGen::container_remove(h, hds.m_container); 
+    ContainerGen::container_remove(g, hds.m_container);
+}
 
+template <typename HalfedgeS, typename VertexDescriptor, typename FacetDescriptor, typename Config>
+void
+delete_edge(typename halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config>::halfedge_iterator h,
+            halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config>& hds)
+    // Remove the halfedge pointed by the iterator 'h' and its opposite from 'hds'
+{
+    typedef halfedge_gen<HalfedgeS, VertexDescriptor, FacetDescriptor, Config> halfedgeGen;
+    typedef typename halfedgeGen::halfedge_descriptor halfedge_descriptor;
+    typedef typename halfedgeGen::ContainerGen ContainerGen;
+    
+    halfedge_descriptor g = static_cast<halfedge_descriptor>(opposite(*h, hds));
+    ContainerGen::container_remove(h, hds.m_container); // delete with iterator
+    ContainerGen::container_remove(g, hds.m_container); // delete with descriptor
+}
 
 } // namespace hdstl
 } // namespace boost

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.t.cpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.t.cpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/halfedge_functions.t.cpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -12,7 +12,7 @@
 // Use the set_next_helper_test and set_prev_helper_test functions to
 // test next_.._.. and prev_.._.. functions.
 // Use next_.._.. and prev_.._.. functions to test set functions.
-// Test add_edge function.
+// Test add_remove_edge function.
 // Perform the above mentioned tests for each combination of template selectors.
 //
 // The set functions and the set helper functions set up the halfedges as follows 
@@ -803,7 +803,7 @@
 }
 
 template <typename HalfedgeGen>
-bool halfedge_add_edge_test() {
+bool halfedge_add_remove_edge_test() {
     
     // Types must exist.
     typedef typename HalfedgeGen::halfedge_selector      halfedge_selector;
@@ -834,7 +834,11 @@
     BOOST_CHECK(( opposite(hi, halfedgeGen) == hj));
     BOOST_CHECK(( opposite(hj, halfedgeGen) == hi));
 
-    //delete_edge(hi, halfedgeGen);    
+    delete_edge(hi, halfedgeGen);    
+    BOOST_CHECK(( num_halfedges(halfedgeGen) == 2));
+    delete_edge(halfedges_begin(halfedgeGen), halfedgeGen);
+    BOOST_CHECK(( num_halfedges(halfedgeGen) == 0));
+
 
     return true;
 }
@@ -934,8 +938,8 @@
 bool test_edge_functions()
 {
     
-    // add_edge test
-    BOOST_CHECK(( halfedge_add_edge_test<
+    // add_remove_edge test
+    BOOST_CHECK(( halfedge_add_remove_edge_test<
                     halfedge_gen<
                       halfedgeS<ContainerS, TraversalS>, 
                       int, int, 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.hpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.hpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.hpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -150,6 +150,28 @@
     return *ContainerGen::container_add(vertex_f, hds.m_container);
 }
 
+template <typename VertexS, typename HalfedgeDescriptor, typename VertexBase>
+void
+delete_vertex(typename vertex_gen<VertexS, HalfedgeDescriptor, VertexBase>::vertex_descriptor v,
+              vertex_gen<VertexS, HalfedgeDescriptor, VertexBase>& hds)
+    // Delete the vertex 'v' from the 'hds'.
+{
+    typedef typename vertex_gen<VertexS, HalfedgeDescriptor, VertexBase>::ContainerGen ContainerGen;
+    
+    ContainerGen::container_remove(v, hds.m_container);
+}
+
+template <typename VertexS, typename HalfedgeDescriptor, typename VertexBase>
+void
+delete_vertex(typename vertex_gen<VertexS, HalfedgeDescriptor, VertexBase>::vertex_iterator v,
+              vertex_gen<VertexS, HalfedgeDescriptor, VertexBase>& hds)
+    // Delete the vertex pointed by the iterator 'v' from the 'hds'.
+{
+    typedef typename vertex_gen<VertexS, HalfedgeDescriptor, VertexBase>::ContainerGen ContainerGen;
+    
+    ContainerGen::container_remove(v, hds.m_container);
+}
+
 } // namespace hdstl
 } // namespace boost
 

Modified: sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.t.cpp
==============================================================================
--- sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.t.cpp	(original)
+++ sandbox/SOC/2007/geometry/libs/hdstl/dev/halfedge_ds/vertex_functions.t.cpp	2007-08-03 15:06:28 EDT (Fri, 03 Aug 2007)
@@ -85,6 +85,15 @@
     vertex_descriptor vn = new_vertex(vertexGen);
     (void) vn;
     BOOST_CHECK(( num_vertices(vertexGen) == 5 ));
+    
+    // test delete with descriptor
+    delete_vertex(vn, vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 4 ));
+    
+    // test delete with iterator
+    delete_vertex(vertices_begin(vertexGen), vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 3 ));
+
     return true;
 }
 
@@ -122,6 +131,14 @@
     (void) vn;
     BOOST_CHECK(( num_vertices(vertexGen) == 5 ));
     
+    // test delete with descriptor
+    delete_vertex(vn, vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 4 ));
+    
+    // test delete with iterator
+    delete_vertex(vertices_begin(vertexGen), vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 3 ));
+
     return true;
 }
 
@@ -156,6 +173,14 @@
     (void) vn;
     BOOST_CHECK(( num_vertices(vertexGen) == 5 ));
 
+    // test delete with descriptor
+    delete_vertex(vn, vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 4 ));
+    
+    // test delete with iterator
+    delete_vertex(vertices_begin(vertexGen), vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 3 ));
+
     return true;
 }
 
@@ -194,6 +219,15 @@
     vertex_descriptor vn = new_vertex(vertexGen);
     (void) vn;
     BOOST_CHECK(( num_vertices(vertexGen) == 5 ));
+    
+    // test delete with descriptor
+    delete_vertex(vn, vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 4 ));
+    
+    // test delete with iterator
+    delete_vertex(vertices_begin(vertexGen), vertexGen);
+    BOOST_CHECK(( num_vertices(vertexGen) == 3 ));
+
     return true;
 }