|
BWAPI
|
00001 // Copyright (c) 1997 Utrecht University (The Netherlands), 00002 // ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany), 00003 // INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg 00004 // (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria), 00005 // and Tel-Aviv University (Israel). All rights reserved. 00006 // 00007 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or 00008 // modify it under the terms of the GNU Lesser General Public License as 00009 // published by the Free Software Foundation; version 2.1 of the License. 00010 // See the file LICENSE.LGPL distributed with CGAL. 00011 // 00012 // Licensees holding a valid commercial license may use this file in 00013 // accordance with the commercial license agreement provided with the software. 00014 // 00015 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00016 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00017 // 00018 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/HalfedgeDS/include/CGAL/HalfedgeDS_vector.h $ 00019 // $Id: HalfedgeDS_vector.h 35751 2007-01-18 13:55:56Z fcacciola $ 00020 // 00021 // 00022 // Author(s) : Lutz Kettner <kettner@mpi-sb.mpg.de> 00023 00024 #ifndef CGAL_HALFEDGEDS_VECTOR_H 00025 #define CGAL_HALFEDGEDS_VECTOR_H 1 00026 00027 // Define this if HalfedgeDS_vector is based on CGAL internal vector. 00028 #define CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR 1 00029 00030 #include <CGAL/basic.h> 00031 #include <CGAL/memory.h> 00032 #include <CGAL/HalfedgeDS_items_decorator.h> 00033 #include <algorithm> 00034 #include <vector> 00035 #include <map> 00036 #include <cstddef> 00037 00038 #ifdef CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR 00039 #include <CGAL/vector.h> 00040 #else 00041 #include <CGAL/HalfedgeDS_iterator_adaptor.h> 00042 #endif 00043 00044 CGAL_BEGIN_NAMESPACE 00045 00046 00047 template < class Traits_, class HalfedgeDSItems, class Alloc> 00048 class HalfedgeDS_vector_types { 00049 public: 00050 typedef HalfedgeDS_vector_types<Traits_,HalfedgeDSItems,Alloc> Self; 00051 typedef Traits_ Traits; 00052 typedef HalfedgeDSItems Items; 00053 typedef Alloc Allocator; 00054 typedef Alloc allocator_type; 00055 00056 typedef typename Items::template Vertex_wrapper<Self,Traits> 00057 Vertex_wrapper; 00058 typedef typename Items::template Halfedge_wrapper<Self,Traits> 00059 Halfedge_wrapper; 00060 typedef typename Items::template Face_wrapper<Self,Traits> 00061 Face_wrapper; 00062 00063 typedef typename Vertex_wrapper::Vertex Vertex; 00064 typedef typename Halfedge_wrapper::Halfedge Halfedge; 00065 typedef typename Face_wrapper::Face Face; 00066 00067 typedef typename Allocator::template rebind< Vertex> Vertex_alloc_rebind; 00068 typedef typename Vertex_alloc_rebind::other Vertex_allocator; 00069 typedef typename Allocator::template rebind< Halfedge> 00070 Halfedge_alloc_rebind; 00071 typedef typename Halfedge_alloc_rebind::other Halfedge_allocator; 00072 typedef typename Allocator::template rebind< Face> Face_alloc_rebind; 00073 typedef typename Face_alloc_rebind::other Face_allocator; 00074 00075 #ifdef CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR 00076 typedef CGALi::vector<Vertex, Vertex_allocator> Vertex_vector; 00077 typedef typename Vertex_vector::iterator Vertex_I; 00078 typedef typename Vertex_vector::const_iterator Vertex_CI; 00079 typedef typename Vertex_vector::iterator Vertex_iterator; 00080 typedef typename Vertex_vector::const_iterator Vertex_const_iterator; 00081 00082 typedef CGALi::vector<Halfedge, Halfedge_allocator> Halfedge_vector; 00083 typedef typename Halfedge_vector::iterator Halfedge_I; 00084 typedef typename Halfedge_vector::const_iterator Halfedge_CI; 00085 typedef typename Halfedge_vector::iterator Halfedge_iterator; 00086 typedef typename Halfedge_vector::const_iterator Halfedge_const_iterator; 00087 00088 typedef CGALi::vector<Face, Face_allocator> Face_vector; 00089 typedef typename Face_vector::iterator Face_I; 00090 typedef typename Face_vector::const_iterator Face_CI; 00091 typedef typename Face_vector::iterator Face_iterator; 00092 typedef typename Face_vector::const_iterator Face_const_iterator; 00093 #else // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR // 00094 typedef std::vector<Vertex, Vertex_allocator> Vertex_vector; 00095 typedef typename Vertex_vector::iterator Vertex_I; 00096 typedef typename Vertex_vector::const_iterator Vertex_CI; 00097 typedef HalfedgeDS_iterator_adaptor<Vertex_I> Vertex_iterator; 00098 typedef HalfedgeDS_iterator_adaptor<Vertex_CI> Vertex_const_iterator; 00099 00100 typedef std::vector<Halfedge, Halfedge_allocator> Halfedge_vector; 00101 typedef typename Halfedge_vector::iterator Halfedge_I; 00102 typedef typename Halfedge_vector::const_iterator Halfedge_CI; 00103 typedef HalfedgeDS_iterator_adaptor<Halfedge_I> Halfedge_iterator; 00104 typedef HalfedgeDS_iterator_adaptor<Halfedge_CI> Halfedge_const_iterator; 00105 00106 typedef std::vector<Face, Face_allocator> Face_vector; 00107 typedef typename Face_vector::iterator Face_I; 00108 typedef typename Face_vector::const_iterator Face_CI; 00109 typedef HalfedgeDS_iterator_adaptor<Face_I> Face_iterator; 00110 typedef HalfedgeDS_iterator_adaptor<Face_CI> Face_const_iterator; 00111 #endif // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR // 00112 00113 typedef Vertex_iterator Vertex_handle; 00114 typedef Vertex_const_iterator Vertex_const_handle; 00115 typedef Halfedge_iterator Halfedge_handle; 00116 typedef Halfedge_const_iterator Halfedge_const_handle; 00117 typedef Face_iterator Face_handle; 00118 typedef Face_const_iterator Face_const_handle; 00119 00120 typedef typename Halfedge_vector::size_type size_type; 00121 typedef typename Halfedge_vector::difference_type difference_type; 00122 typedef std::random_access_iterator_tag iterator_category; 00123 00124 static inline Vertex_handle vertex_handle( Vertex* v) { 00125 return Vertex_handle( Vertex_I(v)); 00126 } 00127 static inline Vertex_const_handle vertex_handle( const Vertex* v) { 00128 return Vertex_const_handle( Vertex_CI(v)); 00129 } 00130 static inline Halfedge_handle halfedge_handle( Halfedge* h) { 00131 return Halfedge_handle( Halfedge_I(h)); 00132 } 00133 static inline Halfedge_const_handle halfedge_handle( const Halfedge* h) { 00134 return Halfedge_const_handle( Halfedge_CI(h)); 00135 } 00136 static inline Face_handle face_handle( Face* f) { 00137 return Face_handle( Face_I(f)); 00138 } 00139 static inline Face_const_handle face_handle( const Face* f) { 00140 return Face_const_handle( Face_CI(f)); 00141 } 00142 }; 00143 00144 00145 #ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM 00146 template < class Traits_, class HalfedgeDSItems, 00147 class Alloc = CGAL_ALLOCATOR(int)> 00148 class HalfedgeDS_vector 00149 : public HalfedgeDS_vector_types<Traits_, HalfedgeDSItems, Alloc> { 00150 public: 00151 typedef HalfedgeDS_vector<Traits_,HalfedgeDSItems,Alloc> Self; 00152 #else 00153 struct HalfedgeDS_vector { 00154 template < class Traits_, class HalfedgeDSItems, 00155 class Alloc = CGAL_ALLOCATOR(int)> 00156 class HDS : public HalfedgeDS_vector_types<Traits_, HalfedgeDSItems, Alloc> { 00157 public: 00158 typedef HDS<Traits_,HalfedgeDSItems,Alloc> Self; 00159 #endif 00160 typedef HalfedgeDS_vector_types<Traits_, HalfedgeDSItems, Alloc> Types; 00161 typedef typename Types::Traits Traits; 00162 typedef typename Types::Items Items; 00163 typedef typename Types::Allocator Allocator; 00164 typedef typename Types::allocator_type allocator_type; 00165 00166 typedef typename Types::Vertex Vertex; 00167 typedef typename Types::Halfedge Halfedge; 00168 typedef typename Types::Face Face; 00169 00170 typedef typename Types::Vertex_vector Vertex_vector; 00171 typedef typename Types::Vertex_handle Vertex_handle; 00172 typedef typename Types::Vertex_const_handle Vertex_const_handle; 00173 typedef typename Types::Vertex_iterator Vertex_iterator; 00174 typedef typename Types::Vertex_const_iterator Vertex_const_iterator; 00175 typedef typename Types::Vertex_I Vertex_I; 00176 typedef typename Types::Vertex_CI Vertex_CI; 00177 00178 typedef typename Types::Halfedge_vector Halfedge_vector; 00179 typedef typename Types::Halfedge_handle Halfedge_handle; 00180 typedef typename Types::Halfedge_const_handle Halfedge_const_handle; 00181 typedef typename Types::Halfedge_iterator Halfedge_iterator; 00182 typedef typename Types::Halfedge_const_iterator Halfedge_const_iterator; 00183 typedef typename Types::Halfedge_I Halfedge_I; 00184 typedef typename Types::Halfedge_CI Halfedge_CI; 00185 00186 typedef typename Types::Face_vector Face_vector; 00187 typedef typename Types::Face_handle Face_handle; 00188 typedef typename Types::Face_const_handle Face_const_handle; 00189 typedef typename Types::Face_iterator Face_iterator; 00190 typedef typename Types::Face_const_iterator Face_const_iterator; 00191 typedef typename Types::Face_I Face_I; 00192 typedef typename Types::Face_CI Face_CI; 00193 00194 typedef typename Types::size_type size_type; 00195 typedef typename Types::difference_type difference_type; 00196 typedef typename Types::iterator_category iterator_category; 00197 00198 typedef Tag_false Supports_removal; 00199 00200 typedef typename Vertex::Supports_vertex_halfedge Supports_vertex_halfedge; 00201 typedef typename Halfedge::Supports_halfedge_prev Supports_halfedge_prev; 00202 typedef typename Halfedge::Supports_halfedge_vertex 00203 Supports_halfedge_vertex; 00204 typedef typename Halfedge::Supports_halfedge_face 00205 Supports_halfedge_face; 00206 typedef typename Face::Supports_face_halfedge Supports_face_halfedge; 00207 00208 protected: 00209 typedef typename Vertex::Base VBase; 00210 typedef typename Halfedge::Base HBase; 00211 typedef typename Halfedge::Base_base HBase_base; 00212 typedef typename Face::Base FBase; 00213 00214 Vertex_vector vertices; 00215 Halfedge_vector halfedges; 00216 Face_vector faces; 00217 00218 size_type nb_border_halfedges; 00219 size_type nb_border_edges; 00220 Halfedge_iterator border_halfedges; 00221 00222 #ifdef CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR 00223 Vertex_I get_v_iter( const Vertex_I& i) const { return i; } 00224 Vertex_CI get_v_iter( const Vertex_CI& i) const { return i; } 00225 Halfedge_I get_h_iter( const Halfedge_I& i) const { return i; } 00226 Halfedge_CI get_h_iter( const Halfedge_CI& i) const { return i; } 00227 Face_I get_f_iter( const Face_I& i) const { return i; } 00228 Face_CI get_f_iter( const Face_CI& i) const { return i; } 00229 #else // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR // 00230 Vertex_I get_v_iter( const Vertex_iterator& i) const { 00231 return i.iterator(); 00232 } 00233 Vertex_CI get_v_iter( const Vertex_const_iterator& i) const { 00234 return i.iterator(); 00235 } 00236 Halfedge_I get_h_iter( const Halfedge_iterator& i) const { 00237 return i.iterator(); 00238 } 00239 Halfedge_CI get_h_iter( const Halfedge_const_iterator& i) const { 00240 return i.iterator(); 00241 } 00242 Face_I get_f_iter( const Face_iterator& i) const { 00243 return i.iterator(); 00244 } 00245 Face_CI get_f_iter( const Face_const_iterator& i) const { 00246 return i.iterator(); 00247 } 00248 #endif // CGAL__HALFEDGEDS_USE_INTERNAL_VECTOR // 00249 00250 // CREATION 00251 00252 private: 00253 #define CGAL__V_UPDATE(v) (((v) == Vertex_handle()) ? (v) : \ 00254 (v_new + ( Vertex_CI (get_v_iter(v)) - v_old))) 00255 #define CGAL__H_UPDATE(h) (((h) == Halfedge_handle()) ? (h) : \ 00256 (h_new + ( Halfedge_CI (get_h_iter(h)) - h_old))) 00257 #define CGAL__F_UPDATE(f) (((f) == Face_handle()) ? (f) : \ 00258 (f_new + ( Face_CI (get_f_iter(f)) - f_old))) 00259 00260 void pointer_update( Vertex_CI v_old, Halfedge_CI h_old, Face_CI f_old) { 00261 // Update own pointers assuming that they lived previously 00262 // in a halfedge data structure with vector starting addresses 00263 // as given as parameters v_old, h_old, f_old. 00264 HalfedgeDS_items_decorator<Self> D; 00265 Vertex_iterator v_new = vertices.begin(); 00266 Halfedge_iterator h_new = halfedges.begin(); 00267 Face_iterator f_new = faces.begin(); 00268 for (Halfedge_iterator h = halfedges_begin();h != halfedges_end();++h){ 00269 h->HBase::set_next( CGAL__H_UPDATE( h->next())); 00270 h->HBase_base::set_opposite( CGAL__H_UPDATE( h->opposite())); 00271 D.set_prev( h, CGAL__H_UPDATE( D.get_prev(h))); 00272 D.set_vertex( h, CGAL__V_UPDATE( D.get_vertex(h))); 00273 D.set_face( h, CGAL__F_UPDATE( D.get_face(h))); 00274 } 00275 border_halfedges = CGAL__H_UPDATE( border_halfedges); 00276 if (check_tag( Supports_vertex_halfedge())) { 00277 for (Vertex_iterator v = vertices_begin();v != vertices_end();++v){ 00278 D.set_vertex_halfedge(v, CGAL__H_UPDATE( 00279 D.get_vertex_halfedge(v))); 00280 } 00281 } 00282 if (check_tag( Supports_face_halfedge())) { 00283 for ( Face_iterator f = faces_begin(); f != faces_end(); ++f) { 00284 D.set_face_halfedge(f,CGAL__H_UPDATE( D.get_face_halfedge(f))); 00285 } 00286 } 00287 } 00288 #undef CGAL__V_UPDATE 00289 #undef CGAL__H_UPDATE 00290 #undef CGAL__F_UPDATE 00291 00292 public: 00293 00294 #ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM 00295 HalfedgeDS_vector() 00296 : nb_border_halfedges(0), nb_border_edges(0) {} 00297 // empty halfedge data structure. 00298 00299 HalfedgeDS_vector( size_type v, size_type h, size_type f) 00300 : nb_border_halfedges(0), nb_border_edges(0) { 00301 // halfedge data structure with storage reserved for v vertices, h 00302 // halfedges, and f faces. The reservation sizes are a hint for 00303 // optimizing storage allocation. They are not used here. 00304 vertices.reserve(v); 00305 halfedges.reserve(h); 00306 faces.reserve(f); 00307 } 00308 00309 HalfedgeDS_vector( const Self& hds) 00310 #else 00311 HDS() : nb_border_halfedges(0), nb_border_edges(0) {} 00312 HDS( size_type v, size_type h, size_type f) 00313 : nb_border_halfedges(0), nb_border_edges(0) { 00314 vertices.reserve(v); 00315 halfedges.reserve(h); 00316 faces.reserve(f); 00317 } 00318 HDS( const Self& hds) 00319 #endif // CGAL_CFG_NO_TMPL_IN_TMPL_PARAM // 00320 : vertices( hds.vertices), 00321 halfedges( hds.halfedges), 00322 faces( hds.faces), 00323 nb_border_halfedges( hds.nb_border_halfedges), 00324 nb_border_edges( hds.nb_border_edges), 00325 border_halfedges( hds.border_halfedges) 00326 { 00327 pointer_update( hds.vertices.begin(), 00328 hds.halfedges.begin(), 00329 hds.faces.begin()); 00330 } 00331 00332 Self& operator=( const Self& hds) { 00333 if ( this != &hds) { 00334 clear(); 00335 vertices = hds.vertices; 00336 halfedges = hds.halfedges; 00337 faces = hds.faces; 00338 nb_border_halfedges = hds.nb_border_halfedges; 00339 nb_border_edges = hds.nb_border_edges; 00340 border_halfedges = hds.border_halfedges; 00341 pointer_update( hds.vertices.begin(), 00342 hds.halfedges.begin(), 00343 hds.faces.begin()); 00344 } 00345 return *this; 00346 } 00347 00348 void reserve( size_type v, size_type h, size_type f) { 00349 // reserve storage for v vertices, h halfedges, and f faces. The 00350 // reservation sizes are a hint for optimizing storage allocation. 00351 // If the `capacity' is already greater than the requested size 00352 // nothing happens. If the `capacity' changes all iterators and 00353 // circulators invalidates. Function is void here. 00354 if ( (check_tag( Supports_halfedge_vertex()) 00355 && v > capacity_of_vertices()) 00356 || h > capacity_of_halfedges() 00357 || (check_tag( Supports_halfedge_face()) 00358 && f > capacity_of_faces())) { 00359 Vertex_CI v_old = vertices.begin(); 00360 Halfedge_CI h_old = halfedges.begin(); 00361 Face_CI f_old = faces.begin(); 00362 if ( check_tag( Supports_halfedge_vertex())) 00363 vertices.reserve(v); 00364 halfedges.reserve(h); 00365 if ( check_tag( Supports_halfedge_face())) 00366 faces.reserve(f); 00367 pointer_update( v_old, h_old, f_old); 00368 } 00369 } 00370 00371 // Access Member Functions 00372 00373 allocator_type get_allocator() const { return allocator_type(); } 00374 00375 size_type size_of_vertices() const { return vertices.size();} 00376 size_type size_of_halfedges() const { return halfedges.size();} 00377 // number of all halfedges (including border halfedges). 00378 size_type size_of_faces() const { return faces.size();} 00379 00380 size_type capacity_of_vertices() const { return vertices.capacity();} 00381 size_type capacity_of_halfedges() const { return halfedges.capacity();} 00382 size_type capacity_of_faces() const { return faces.capacity();} 00383 00384 std::size_t bytes() const { 00385 return sizeof(Self) 00386 + vertices.size() * sizeof( Vertex) 00387 + halfedges.size() * sizeof( Halfedge) 00388 + faces.size() * sizeof( Face); 00389 } 00390 std::size_t bytes_reserved() const { 00391 return sizeof(Self) 00392 + vertices.capacity() * sizeof( Vertex) 00393 + halfedges.capacity() * sizeof( Halfedge) 00394 + faces.capacity() * sizeof( Face); 00395 } 00396 00397 Vertex_iterator vertices_begin() { return vertices.begin();} 00398 Vertex_iterator vertices_end() { return vertices.end();} 00399 Halfedge_iterator halfedges_begin() { return halfedges.begin();} 00400 Halfedge_iterator halfedges_end() { return halfedges.end();} 00401 Face_iterator faces_begin() { return faces.begin();} 00402 Face_iterator faces_end() { return faces.end();} 00403 00404 // The constant iterators and circulators. 00405 00406 Vertex_const_iterator vertices_begin() const{ return vertices.begin();} 00407 Vertex_const_iterator vertices_end() const{ return vertices.end();} 00408 Halfedge_const_iterator halfedges_begin() const{ return halfedges.begin();} 00409 Halfedge_const_iterator halfedges_end() const{ return halfedges.end();} 00410 Face_const_iterator faces_begin() const{ return faces.begin();} 00411 Face_const_iterator faces_end() const{ return faces.end();} 00412 00413 // Insertion 00414 // 00415 // The following operations simply allocate a new element of that type. 00416 // Halfedges are always allocated in pairs of opposite halfedges. The 00417 // opposite pointers are automatically set. 00418 00419 Vertex_handle vertices_push_back( const Vertex& v) { 00420 CGAL_precondition( 1+size_of_vertices() <= capacity_of_vertices()); 00421 vertices.push_back(v); 00422 Vertex_handle vv = vertices.end(); 00423 return --vv; 00424 } 00425 00426 Halfedge_handle edges_push_back( const Halfedge& h, const Halfedge& g) { 00427 // creates a new pair of opposite border halfedges. 00428 CGAL_precondition( 1 + size_of_halfedges() < capacity_of_halfedges()); 00429 halfedges.push_back(h); 00430 Halfedge_handle hh = halfedges.end(); 00431 --hh; 00432 halfedges.push_back(g); 00433 Halfedge_handle gg = halfedges.end(); 00434 --gg; 00435 CGAL_assertion( hh + 1 == gg); 00436 CGAL_assertion( (char*)(&*gg) - (char*)(&*hh) == sizeof( Halfedge)); 00437 hh->HBase_base::set_opposite(gg); 00438 gg->HBase_base::set_opposite(hh); 00439 return hh; 00440 } 00441 00442 Halfedge_handle edges_push_back( const Halfedge& h) { 00443 CGAL_precondition( h.opposite() != Halfedge_const_handle()); 00444 return edges_push_back( h, *(h.opposite())); 00445 } 00446 00447 Face_handle faces_push_back( const Face& f) { 00448 CGAL_precondition( 1+size_of_faces() <= capacity_of_faces()); 00449 faces.push_back(f); 00450 Face_handle ff = faces.end(); 00451 return --ff; 00452 } 00453 00454 00455 // Removal 00456 // 00457 // The following operations erase an element referenced by a handle. 00458 // Halfedges are always deallocated in pairs of opposite halfedges. Erase 00459 // of single elements is optional. The deletion of all is mandatory. 00460 00461 void vertices_pop_back() { vertices.pop_back(); } 00462 void edges_pop_back() { 00463 CGAL_precondition(( halfedges_end()-1)->opposite() == 00464 ( halfedges_end()-2)); 00465 halfedges.pop_back(); 00466 halfedges.pop_back(); 00467 } 00468 void faces_pop_back() { faces.pop_back(); } 00469 00470 void vertices_clear() { vertices.erase( vertices.begin(), vertices.end());} 00471 void edges_clear() { 00472 halfedges.erase( halfedges.begin(), halfedges.end()); 00473 nb_border_halfedges = 0; 00474 nb_border_edges = 0; 00475 border_halfedges = Halfedge_handle(); 00476 } 00477 void faces_clear() { faces.erase( faces.begin(), faces.end()); } 00478 void clear() { 00479 vertices_clear(); 00480 edges_clear(); 00481 faces_clear(); 00482 } 00483 00484 // Special Operations on Polyhedral Surfaces 00485 protected: 00486 // Update operation used in pointer_update(...). 00487 void update_opposite( Halfedge_I h) { 00488 Halfedge_I g = h + 1; 00489 h->HBase_base::set_opposite(g); 00490 g->HBase_base::set_opposite(h); 00491 } 00492 00493 // Operations with Border Halfedges 00494 public: 00495 size_type size_of_border_halfedges() const { return nb_border_halfedges;} 00496 // number of border halfedges. An edge with no incident face 00497 // counts as two border halfedges. Precondition: `normalize_border()' 00498 // has been called and no halfedge insertion or removal and no 00499 // change in border status of the halfedges have occured since 00500 // then. 00501 00502 size_type size_of_border_edges() const { return nb_border_edges;} 00503 // number of border edges. If `size_of_border_edges() == 00504 // size_of_border_halfedges()' all border edges are incident to a 00505 // face on one side and to a hole on the other side. 00506 // Precondition: `normalize_border()' has been called and no 00507 // halfedge insertion or removal and no change in border status of 00508 // the halfedges have occured since then. 00509 00510 Halfedge_iterator border_halfedges_begin() { 00511 // halfedge iterator starting with the border edges. The range [ 00512 // `halfedges_begin(), border_halfedges_begin()') denotes all 00513 // non-border edges. The range [`border_halfedges_begin(), 00514 // halfedges_end()') denotes all border edges. Precondition: 00515 // `normalize_border()' has been called and no halfedge insertion 00516 // or removal and no change in border status of the halfedges have 00517 // occured since then. 00518 return border_halfedges; 00519 } 00520 00521 Halfedge_const_iterator border_halfedges_begin() const { 00522 return border_halfedges; 00523 } 00524 00525 void normalize_border() { 00526 // sorts halfedges such that the non-border edges precedes the 00527 // border edges. For each border edge that is incident to a face 00528 // the halfedge iterator will reference the halfedge incident to 00529 // the face right before the halfedge incident to the hole. 00530 nb_border_halfedges = 0; 00531 nb_border_edges = 0; 00532 border_halfedges = halfedges_end(); 00533 // Lets run one partition step over the array of halfedges. 00534 // First find a pivot -- that means a border edge. 00535 Halfedge_I ll = halfedges.begin(); 00536 while ( ll != halfedges.end() && (! ll->is_border()) && 00537 (! ll->opposite()->is_border() )) 00538 ++ ++ll; 00539 if ( ll == halfedges.end()) // Done. No border edges found. 00540 return; 00541 00542 // An array of pointers to update the changed halfedge pointers. 00543 typedef typename Allocator::template rebind< Halfedge_I> 00544 HI_alloc_rebind; 00545 typedef typename HI_alloc_rebind::other HI_allocator; 00546 00547 typedef std::vector<Halfedge_I, HI_allocator> HVector; 00548 typedef typename HVector::iterator Hiterator; 00549 HVector hvector; 00550 // Initialize it. 00551 hvector.reserve( halfedges.size()); 00552 for ( Halfedge_I i = halfedges.begin(); i != halfedges.end(); ++i) { 00553 hvector.push_back(i); 00554 } 00555 Hiterator llhv = hvector.begin() + (ll-halfedges.begin()); 00556 // Start with the partitioning. 00557 Halfedge_I rr = halfedges.end(); 00558 -- --rr; 00559 Hiterator rrhv = hvector.end(); 00560 -- --rrhv; 00561 // The comments proove the invariant of the partitioning step. 00562 // Note that + 1 or - 1 denotes plus one edge or minus one edge, 00563 // so they mean actually + 2 and - 2. 00564 // Pivot is in *ll 00565 // Elements in [rr+1..end) >= pivot (border) 00566 // Elements in [begin..ll) < pivot (non border) 00567 while (ll < rr) { 00568 // Pivot is in *ll, ll <= rr. 00569 while ( rr > ll && (rr->is_border() 00570 || rr->opposite()->is_border())) { 00571 if ( ! rr->opposite()->is_border()) { 00572 CGAL_assertion( rr + 1 == get_h_iter(rr->opposite())); 00573 std::swap( *rr, *(rr+1)); 00574 update_opposite( rr); 00575 std::swap( *rrhv, *(rrhv+1)); 00576 } 00577 -- --rr; 00578 -- --rrhv; 00579 } 00580 // Elements in [rr+1..end) >= pivot (border) 00581 // *rr <= pivot, ll <= rr. 00582 CGAL_assertion( rr + 1 == get_h_iter( rr->opposite())); 00583 CGAL_assertion( ll + 1 == get_h_iter( ll->opposite())); 00584 std::swap( *(ll+1), *(rr+1)); 00585 std::swap( *ll, *rr); 00586 update_opposite( ll); 00587 update_opposite( rr); 00588 std::swap( *(llhv+1), *(rrhv+1)); 00589 std::swap( *llhv, *rrhv); 00590 // Elements in [begin..ll) < pivot 00591 // Pivot is in *rr, ll <= rr. 00592 while ( !ll->is_border() && ! ll->opposite()->is_border()) { 00593 ++ ++ll; 00594 ++ ++llhv; 00595 } 00596 // Elements in [begin..ll) < pivot 00597 // *ll >= pivot 00598 // ll <= rr (since *rr is pivot.) 00599 CGAL_assertion( ll <= rr); 00600 CGAL_assertion( llhv <= rrhv); 00601 CGAL_assertion( rr + 1 == get_h_iter( rr->opposite())); 00602 CGAL_assertion( ll + 1 == get_h_iter( ll->opposite())); 00603 std::swap( *(ll+1), *(rr+1)); 00604 std::swap( *ll, *rr); 00605 update_opposite( ll); 00606 update_opposite( rr); 00607 std::swap( *(llhv+1), *(rrhv+1)); 00608 std::swap( *llhv, *rrhv); 00609 if ( ! rr->opposite()->is_border()) { 00610 CGAL_assertion( rr + 1 == get_h_iter( rr->opposite())); 00611 std::swap( *rr, *(rr+1)); 00612 update_opposite( rr); 00613 std::swap( *rrhv, *(rrhv+1)); 00614 } 00615 00616 // This guard is needed here because, rr==ll==begin, might be true 00617 // at this point, causing the decrement to result in undefined 00618 // behaviour. 00619 // [Fernando Cacciola] 00620 if ( ll < rr ) 00621 { 00622 -- --rr; 00623 -- --rrhv; 00624 } 00625 // Elements in [rr+1..end) >= pivot 00626 // Pivot is in *ll 00627 } 00628 CGAL_assertion( llhv >= rrhv); 00629 // rr + 1 >= ll >= rr 00630 // Elements in [rr+1..end) >= pivot 00631 // Elemente in [begin..ll) < pivot 00632 // Pivot is in a[ll] 00633 if ( ll == rr) { 00634 // Check for the possibly missed swap. 00635 if ( rr->is_border() && ! rr->opposite()->is_border()) { 00636 CGAL_assertion( rr + 1 == get_h_iter (rr->opposite())); 00637 std::swap( *rr, *(rr+1)); 00638 update_opposite( rr); 00639 std::swap( *rrhv, *(rrhv+1)); 00640 } 00641 } 00642 CGAL_assertion( ll->opposite()->is_border()); 00643 CGAL_assertion( ll == halfedges.begin() || ! (ll-2)->is_border()); 00644 CGAL_assertion( ll == halfedges.begin() || ! (ll-1)->is_border()); 00645 border_halfedges = ll; 00646 nb_border_edges = (halfedges.end() - ll) / 2; 00647 nb_border_halfedges = 0; 00648 00649 HVector inv_vector( halfedges.size()); 00650 // Initialize inverse index. 00651 for ( Hiterator k = hvector.begin(); k != hvector.end(); ++k){ 00652 inv_vector[*k - halfedges.begin()] = 00653 halfedges.begin() + (k - hvector.begin()); 00654 } 00655 // Update halfedge pointers. 00656 HalfedgeDS_items_decorator<Self> D; 00657 for (Halfedge_iterator h = halfedges_begin();h != halfedges_end();++h){ 00658 h->HBase::set_next( inv_vector[ h->next() - halfedges_begin()]); 00659 D.set_vertex_halfedge(h); 00660 if ( D.get_prev( h) == Halfedge_iterator()) 00661 D.set_prev( h, Halfedge_iterator()); 00662 else 00663 D.set_prev( h, inv_vector[ D.get_prev(h) - halfedges_begin()]); 00664 if ( h->is_border()) 00665 nb_border_halfedges++; 00666 else 00667 D.set_face_halfedge(h); 00668 } 00669 } 00670 }; 00671 #ifdef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM 00672 }; 00673 #endif 00674 00675 00676 CGAL_END_NAMESPACE 00677 #endif // CGAL_HALFEDGEDS_VECTOR_H // 00678 // EOF //
1.7.6.1
