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.