Class

CGAL::HalfedgeDS_list<Traits,HalfedgeDSItems,Alloc>

Definition

The class HalfedgeDS_list<Traits,HalfedgeDSItems,Alloc> is a model for the HalfedgeDS concept. HalfedgeDS_list<Traits,HalfedgeDSItems,Alloc> is a list-based representation with bidirectional iterators that supports removal.

#include <CGAL/HalfedgeDS_list.h>

Is Model for the Concepts

HalfedgeDS<Traits,Items,Alloc>

Types

typedef bidirectional_iterator_tag
iterator_category;
typedef CGAL::Tag_true Supports_removal;

Operations

Besides operations required from the concept HalfedgeDS<Traits,Items,Alloc>, this class supports additionally:

void
hds.vertices_splice ( Vertex_iterator target,
Self &source,
Vertex_iterator first,
Vertex_iterator last)
inserts elements in the range [first, last) before position target and removes the elements from source. It takes constant time if &source == &hds; otherwise, it takes linear time in the size of the range.
Precondition: [first, last) is a valid range in source. target is not in the range [first, last).

void
hds.halfedges_splice ( Halfedge_iterator target,
Self &source,
Halfedge_iterator first,
Halfedge_iterator last)
inserts elements in the range [first, last) before position target and removes the elements from source. It takes constant time if &source == &hds; otherwise, it takes linear time in the size of the range.
Precondition: [first, last) is a valid range in source. target is not in the range [first, last).

void hds.faces_splice ( Face_iterator target, Self &source, Face_iterator first, Face_iterator last)
inserts elements in the range [first, last) before position target and removes the elements from source. It takes constant time if &source == &hds; otherwise, it takes linear time in the size of the range.
Precondition: [first, last) is a valid range in source. target is not in the range [first, last).

See Also

CGAL::HalfedgeDS_default
CGAL::HalfedgeDS_vector
HalfedgeDSItems
CGAL::Polyhedron_3<Traits>
CGAL::HalfedgeDS_items_decorator<HDS>
CGAL::HalfedgeDS_decorator<HDS>
CGAL::HalfedgeDS_const_decorator<HDS>

Implementation

HalfedgeDS_list<Traits,HalfedgeDSItems,Alloc> uses internally the CGAL::In_place_list container class. The copy constructor and the assignment operator need O(n) time with n the total number of vertices, halfedges, and faces. The former suboptimal implementation with an O(n log n) runtime has been replaced with a faster implementation based on hashing for the pointer lookup.

CGAL_ALLOCATOR(int) is used as default argument for the Alloc template parameter.