Vertex (Edge, Cell, ...) Grid Range Concept

### Vertex (Edge, Cell, ...) Grid Range Concept

##### Description

A Vertex Grid Range is a sequence of objects of type V which is a model of Grid Vertex.

Virtually the same definitions can be made for the other element types, replacing Vertex with Edge, Cell etc. Therefore, Vertex Grid Range is chosen to stand sui generis for Edge Grid Range, Cell Grid Range and so on.

The Vertex Grid Range concept is seldom useful as such; its primary use is to define further refinements of the basic Grid Range concept: Useful concrete grid types generally will be models of (at least) two different range concepts, such as Vertex Grid Range and Grid Cell Sequence.

##### Notation

R is a type which is a model of Vertex Range
r is an object of type R::grid_type
v is an object of type R::Vertex
vi is an object of type R::VertexIterator

##### Associated types
 Name Expression Description Vertex R::Vertex type of vertex (model of Grid Vertex) handle R::vertex_handle handle type corresponding to R::Vertex model of Grid Vertex Handle (R::Vertex::handle_type is identical to R::vertex_handle) Vertex iterator R::VertexIterator type of the Sequence Iterator corresponding to R::Vertex model of Grid Vertex Iterator (R::Vertex is identical to R::VertexIterator::Vertex)

##### Valid Expressions
 Name Expression Type requirements return type start of sequence vi = r.FirstVertex() VertexIterator end of sequence vi = r.EndVertex() VertexIterator size of sequenceX r.NumOfVertices() size_type handle-to-element conversion v = r.vertex(h) Vertex element-to-handle conversion h = r.handle(v) vertex_handle

##### Expression semantics
 Name Expression Precondition Semantics Postcondition start of sequence v = r.FirstVertex() return iterator pointing to the first vertex of s v is valid, or v == r.EndVertex() end of sequence v = r.EndVertex() v is past-the-end. size of sequence n = r.NumOfVertices() get the number of vertices of s n == distance(r.FirstVertex(), r.EndVertex()) handle-to-element v = r.vertex(h) h is a handle of r.TheGrid() Construct the vertex corresponding to the handle h r.handle(v) == h element-to-handle h = r.handle(v) v is a vertex of r.TheGrid() Construct the vertex corresponding to the handle h r.element(h) == v

##### Complexity guarantees

The r.NumOfVertices() operation has complexity at most O(V), where V is the number of vertices of r X

##### Models

Virtually every concrete grid or grid range:
enumerated_grid_range
Complex2D

##### Notes
1. The reason why a general Vertex Range cannot guarantee O(1) complexity for this operation is the following: Such a sequence might arise from a grid range given by a simple enumeration of its cells (or their handles, see for example enumerated_grid_range). The elements of lower dimension belonging to r are then implicitely defined by the closure (in a topological sense) of the set of cells in the underlying grid. The determination of, for example, the set of vertices can be done in expected time O(V) (using partial grid functions). Requiring to do this determination at time of construction of the range would impose the cost of doing so also to clients not interested in this functionality.
2. This functionality can always be implemented in terms of the element iterators, in which case it is O(n). In some cases, there is no better implementation possible, for example, if edges or facets are implicitely ordered by there vertex sets. Therefore, there is no guarantee for a better complexity here. In these cases, it is not always simple to provide an EndElement() past-the-end iterator, without compromising efficiency of iterator comparison.

Guntram Berti

 Vertex (Edge, Cell, ...) Grid Range Concept