\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.6 - Combinatorial Maps
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Combinatorial_map< d, Items, Alloc > Class Template Reference
Classes

#include <CGAL/Combinatorial_map.h>

Definition

The class Combinatorial_map represents a dD combinatorial map.

Darts and non void attributes are stored in memory using Compact_container, using Alloc as allocator.

Is Model Of:
CombinatorialMap
Template Parameters
dis an integer for the dimension of the map.
Itemsmust be a model of the CombinatorialMapItems concept.
Allochas to match the standard allocator requirements. The rebind mechanism Alloc will be used to create appropriate allocators internally with value type Dart.

There are two default template arguments: Combinatorial_map_min_items<d> for Items and CGAL_ALLOCATOR(int) from the <CGAL/memory.h> header file for Alloc.

Complexity

The complexity of sew and unsew is in O( \( |\)S \( |\) \( \times\) \( |\)c \( |\)), S being the set of darts of the orbit \( \langle{}\) \( \beta_1\), \( \ldots\), \( \beta_{i-2}\), \( \beta_{i+2}\), \( \ldots\), \( \beta_d\) \( \rangle{}\) for the considered dart, and c the biggest j-cell merged or split during the sew such that j-attributes are non void. The complexity of is_sewable is in O( \( |\)S \( |\)).

The complexity of set_attribute is in O( \( |\)c \( |\)), c being the i-cell containing the considered dart.

The complexity of is_without_boundary(unsigned int i) is in O( \( |\)D \( |\)), D being the set of darts of the combinatorial map, and the complexity of is_without_boundary() is in O( \( |\)D \( |\) \( \times\)d).

The complexity of unmark_all and free_mark is in O(1) if all the darts of the combinatorial map have the same mark, and in O( \( |\)D \( |\)) otherwise.

The complexity of is_valid is in O( \( |\)D \( |\) \( \times\)d \( ^2\)).

The complexity of clear is in O( \( |\)D \( |\) \( \times\)d).

Other methods have all a constant time complexity.

See Also
CombinatorialMapItems
Dart
Examples:
Combinatorial_map/map_3_dynamic_onmerge.cpp, Combinatorial_map/map_3_marks.cpp, Combinatorial_map/map_3_operations.cpp, Combinatorial_map/map_3_simple_example.cpp, Combinatorial_map/map_3_with_colored_facets.cpp, and Combinatorial_map/map_4_simple_example.cpp.

Types

typedef Combinatorial_map< d,
Items, Alloc > 		Self
 
typedef Items::Dart_wrapper
< Self >::Dart 		Dart