Prev Up Next
Go backward to Cell-Vertex Input Grid Range
Go up to Grids and Grid Ranges
Go forward to Grid-With-Boundary 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

Prev Up Next