Combinatorial_map<d,Items,Alloc>

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL::Combinatorial_map<d,Items,Alloc>

#include <CGAL/Combinatorial_map.h>

Definition

The class Combinatorial_map<d,Items,Alloc> represents a dD combinatorial map.

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

Is Model for the Concepts

CombinatorialMap

Parameters

d an integer for the dimension of the map.
Items must be a model of the CombinatorialMapItems concept.
Alloc has to match the standard allocator requirements. The rebind mechanism from 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.

Types

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

Complexity

The complexity of sew and unsew is in O(|S|×|c|), S being the set of darts of the orbit ⟨β₁,…,β_i-2,β_i+2,…,β_d⟩ 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|×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|×d²).

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