Reference Manual: CGAL_Halfedge_data_structure_using

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

A Halfedge Data Structure Using Lists

Definition

CGAL_Halfedge_data_structure_using_list<V,H,F> is a model of the Halfedge_data_structure concept. It is parameterized with a model

V

of the Vertex_base concept, a model

H

of the Halfedge_base concept, and a model

F

of the Facet_base concept, whose requirements can be found in Section

. Predefined models can be found in Section

CGAL_Halfedge_data_structure_using_list<V,H,F> uses doubly-linked lists to store the items. This implies bidirectional iterators to access the elements and support for random insertions and deletions. It adds internally two additional pointers to each element. The capacity is not influenced by calls to reserve() and calling reserve() do not invalidate any iterator or circulator.

#include <CGAL/Halfedge_data_structure_using_list.h>

Types

It supports all types required for the Halfedge_data_structure concept, specifically the following two types are fixed.

typedef CGAL_Tag_true
Supports_removal;

typedef bidirectional_iterator_tag
iterator_category;

Operations

CGAL_Halfedge_data_structure_using_list<V,H,F> complies to the requirements stated for the concept Halfedge_data_structure in Section

Implementation

It uses CGAL_In_place_list to implement the internal list storage, see the CGAL support library manual. The copy constructor and the assignment operator must update all internal pointers, which is currently done using the STL map, thus resulting in a runtime of

O( |V| log |V| + |H| log |H| + |F| log |F|)

instead of optimal linear time.

Next: Class declaration of CGAL_Halfedge_data_structure_using_vector<V,H,F>

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

The CGAL Project. 22 January, 1999.

typedef CGAL_Tag_true
	Supports_removal;
typedef bidirectional_iterator_tag
	iterator_category;