Grid-With-Boundary ConceptGrids and Grid RangesCell-Vertex Input Grid RangeVertex (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.

Refinement of

Grid Range

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


Grid-With-Boundary ConceptGrids and Grid RangesCell-Vertex Input Grid RangeVertex (Edge, Cell, ...) Grid Range Concept