From 5e60f2f93d86f98c71380a749c5521df6a0568ae Mon Sep 17 00:00:00 2001 From: wolf Date: Wed, 20 Jul 2005 00:40:10 +0000 Subject: [PATCH] More text. More profound :-) git-svn-id: https://svn.dealii.org/trunk@11182 0785d39b-7218-0410-832d-ea1e28bc413d --- .../doc/doxygen/headers/deal.II/iterators.h | 364 +++++++++++++----- 1 file changed, 263 insertions(+), 101 deletions(-) diff --git a/deal.II/doc/doxygen/headers/deal.II/iterators.h b/deal.II/doc/doxygen/headers/deal.II/iterators.h index ec0e81c15a..07f9967579 100644 --- a/deal.II/doc/doxygen/headers/deal.II/iterators.h +++ b/deal.II/doc/doxygen/headers/deal.II/iterators.h @@ -16,24 +16,130 @@ The template signature of TriaIterator is TriaIterator @endcode -Usually, you will not use this definition directly, but employ one of -the typedefs below. +Usually, you will not use this definition directly, but employ one of the +typedefs below. Before going into this, let us first discuss the concept of +iterators, before delving into what the accessors do. + +As usual in C++, iterators, just as pointers, are incremented to the next +element using operator ++, and decremented to the previous element +using operator --. One can also jump n elements ahead using +the addition operator, it=it+n, and correspondingly to move a number +of elements back. In addition, and keeping with the tradition of the standard +template library, containers provide member functions begin() and +end() that provide the first element of a collection and a +one-past-the-end iterator, respectively. Since there are a number of different +iterators available, there is actually a whole family of such functions, such +as begin_active(), begin_face(), etc. + +In terms of the concepts for iterators defined in the C++ standard, the +deal.II mesh iterators are bi-directional iterators: they can be incremented +and decremented, but an operation like it=it+n takes a computing time +proportional to n, since it is implemented as a sequence of +n individual unit increments. Note that this is in contrast to the +next more specialized iterator concept, random access iterators, for which +access to an arbitrary object requires only constant time, rather than linear. -@section IteratorsDifferences Distinguishing between iterators -The iterators discussed are all of the form +@section IteratorsAndSets Iterators as pointers into sets of objects + +As mentioned above, iterators in deal.II can be considered as iterating over +all the objects that constitute a mesh. (These objects are lines, quads, and +hexes, and are each represented by a different kind of Accessor class; this +accessor is the second template argument in the code example above, and are +discussed in more detail below.) This suggests to view a triangulation as a +collection of cells and other objects that are held together by a certain data +structure that links all these objects, in the same was as a linked list is +the data structure that connects objects in a linear fashion. + +Triangulations in deal.II can indeed be considered in this way. In particular, +they use the computational notion of a forest of regular trees to store their +data. This can be understood as follows: Consider the cells of the coarse mesh +as roots; then, if one of these coarse mesh cells is refined, it will have +2dim children, which in turn can, but do not have to have +2dim children of their own, and so on. This means, that each cell +of the coarse mesh can be considered the root of a binary tree (in qd), a +quadtree (in 2d), or an octree (in 3d). The collection of these trees +emanating from the cells of the coarse mesh then constitutes the forest that +completely describes the triangulation, including all of its active and +inactive cells. In particular, the active cells are those terminal nodes in +the tree that have no decendants, i.e. cells which are not further +refined. Correspondingly, inactive cells correspond to nodes in the tree with +descendents, i.e. cells that are further refined. + +A triangulation contains forests for lines (each of which may have 2 +children), quads (each with possibly four children), and hexes (each with no +or 8 children). Depending on the dimension, these objects are also termed +cells or faces. + +Iterators loop over the elements of such forests. While the usual iterators +loop over all nodes of a forest, active iterators skip iterate over the +elements in the same order, but skip all non-active entries and therefore only +visit terminal nodes (i.e. active cells, faces, etc). There are many ways to +traverse the elements of a forest, for example breadth first or depth +first. Depending on the type of data structure used to store the forest, some +ways are more efficient than others. At present, the way iterators traverse +forests in deal.II is breadth first. I.e., iterators first visit all the +elements (cells, faces, etc) of the coarse mesh before moving on to all the +elements of the immediate level, i.e. the immediate children of the coarse +mesh objects; after this come the grandchildren of the coarse mesh, and so on. +However, it must be noted that programs should not rely on this particular +order of traversing a tree: this is considered an implementation detail that +can change between versions, even if we consider this an unlikely option at +the present time. + + + +@section IteratorsDifferences Different kinds of iterators + +Iterators have two properties: what they point to (i.e. the type of the +Accessor template argument), and the exact definition of the set they iterate +over. In general, iterators are always declared as +@code + KindIterator +@endcode + +Here, Kind determines what property an accessor needs to have to be +reached by this iterator (or omitted, for that matter). For example, +@code + Iterator +@endcode +iterates over all objects of kind Accessor that make up the mesh (for example +all cells, whether they are further refined and have children, or not), whereas @code - LoopIterator + ActiveIterator @endcode +skips all objects that have children, i.e. objects that are not active. +Active iterators therefore operate on a strict subset of the objects +that normal iterators act on, namely those that possess the property that +they are active. Note that this is independent of the kind of object we +are operating on: all valid accessor classes have to provide the iterator +classes a method to find out whether they are active or not. + +(For completeness, let us mention that there is a third kind of iterators: "raw +iterators" also traverse objects that are unused in the triangulation, but +allocated anyway for efficiency reasons. User code should never use raw +iterators, they are only for internal purposes of the library.) + +Whether an object is active can be considered a "predicate": a property that +is either true or false. Filtered iterators can be used to restrict the scope +of existing iterators even more. For instance, you could imagine to iterate +over the subset of those @ref GlossActive "active cells" having their user +flag set or belonging to a certain subdomain (both properties are either true +or false for a given object). + +This is achieved by using an object of type FilteredIterator +<BaseIterator>, where BaseIterator usually is one of the +standard iterators discussed above. + +The FilteredIterator gets an additional Predicate in its constructor and will +skip all objects where this Predicate evaluates to false. A +collection of predicates already implemented can be found in the namespace +IteratorFilters. -Here, Loop determines, which cells are reached (or omitted, -for that matter). This means, independent of the accessor type, this -part of the definition of the iterator determines the meaning of the -increment operator. -@subsection IteratorsLoops The action of the iterator itself +@subsection IteratorsLoops Iterating over objects -All iterators with the same Loop and iterating over the +All iterators of the same kind and iterating over the same kind of geometrical objects traverse the mesh in the same order. Take this code example: @code @@ -41,38 +147,47 @@ order. Take this code example: DoFHandler dof1(tria); DoFHandler dof2(tria); ... - Trianguation::active_cell_iterator ti = tria.begin_active(); - DoFHandler::active_cell_iterator di1 = dof1.begin_active(); - DoFHandler::active_cell_iterator di2 = dof2.begin_active(); + typename Trianguation::cell_iterator ti = tria.active(); + typename DoFHandler::cell_iterator di1 = dof1.active(); + typename DoFHandler::cell_iterator di2 = dof2.active(); ... while (ti != tria.end()) { - do_something_with_iterators(ti, di1, di2); + // do something ++ti; ++di1; ++di2; } @endcode -Here, all iterators will always point to the same mesh cell, even if -the DoFHandlers are handling different finite elements: they all access cells in the same order, the difference is only in the Accessor. - -The standard loops are -
-
TriaIterator
-
Traverse all cells on all levels
- -
TriaActiveIterator
-
Loop over @ref GlossActive "active cells" only
-
+Here, all iterators will always point to the same mesh cell, even though +DoFHandler and Triangulation are very different classes, +and even if the DoFHandlers are handling different finite elements: they +all access cells in the same order, the difference is only in the Accessor. +As mentioned above, the order in which iterators traverse the forest of +objects is actually well-defined, but application programs should not +assume any such order, but rather consider this an implementation detail +of the library. + +Corresponding to above example, the order in which iterators traverse active +objects is the same for all iterators in the following snippet: +@code + typename Trianguation::active_cell_iterator ti = tria.begin_active(); + typename DoFHandler::active_cell_iterator di1 = dof1.begin_active(); + typename DoFHandler::active_cell_iterator di2 = dof2.begin_active(); + ... + while (ti != tria.end()) + { + // do something + ++ti; + ++di1; + ++di2; + } +@endcode -In addition, there are "raw iterators" that also traverse objects that are -unused in the triangulation, but allocated anyway for efficiency reasons. User -code should never use raw iterators, they are only for internal purposes of -the library. -@subsection IteratorsAccessors Accessors +@section IteratorsAccessors Accessors Iterators are like pointers: they can be incremented and decremented, but they are really rather dumb. Their magic only lies in the fact that they point to @@ -80,89 +195,136 @@ some useful object, in this case the Accessor. Accessing data that characterizes a cell is always done through the Accessor, i.e. the expression i-> grants access to all attributes of this Accessor. +Examples of properties you can query from an iterator are +@code + cell->vertex(1); + line->child(0); + hex->face(3); + cell->at_boundary(); + face->boundary_indicator(); +@endcode + +Since dereferencing iterators yields accessor objects, these member functions +are declared in documented in the hierarchy of TriaObjectAccessor, +CellAccessor, DoFObjectAccessor, +DoFCellAccessor, MGDoFObjectAccessor, and +MGDoFCellAccessor classes. -@section IteratorsTypedefs Iterators defined in the containers -The standard iterators are typedefed inside the classes. These are +@section IteratorsTypedefs Iterators defined in the deal.II containers + +Several classes in deal.II typedef iterators inside their class declarations. +The normal iterator types and calls to get them for cells and faces are: - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + + +
cell_iteratorface_iterator
TriangulationTriaIterator<dim, CellAccessor<dim> >TriaIterator<dim, TriaObjectAccessor<dim-1, dim> >
DoFHandlerTriaIterator<dim, DoFCellAccessor<dim> >TriaIterator<dim, DoFObjectAccessor<dim-1, dim> >
Containercell_iterator typefunction call
TriangulationTriaIterator<dim, CellAccessor<dim> >triangulation.begin()
DoFHandlerTriaIterator<dim, DoFCellAccessor<dim> >dof_handler.begin()
MGDoFHandlerTriaIterator<dim, MGDoFCellAccessor<dim> >mg_dof_handler.begin()
-@section IteratorsFiltered Filtered iterators - -Filtered iterators restrict the scope of existing iterators even -more. For instance, you could imagine to iterate over the the subset -of those @ref GlossActive "active cells" having their user flag set or -belonging to a certain subdomain. -This is achieved by using an object of type FilteredIterator -<BaseIterator>, where BaseIterator usually is one of the -standard iterators discussed above. - -The FilteredIterator gets an additional Predicate in its constructor -and will skip all objects where this Predicate evaluates to -false. A collection of already implemented predicates can be -found in the namespace IteratorFilters. + + + + + + + + + + + + + + + + + + + + + + + + +
Containerface_iterator typefunction call
TriangulationTriaIterator<dim, TriaObjectAccessor<dim-1, dim> >triangulation.begin_face()
DoFHandlerTriaIterator<dim, DoFObjectAccessor<dim-1, dim> >dof_handler.begin_face()
MGDoFHandlerTriaIterator<dim, MGDoFObjectAccessor<dim-1, dim> >mg_dof_handler.begin_face()
-@section IteratorsAndSets Iterators as pointers into sets of objects +Likewise, active iterators are as follows: + + + + + + + + + + + + + + + + + + + + + + + + +
Containeractive_cell_iterator typefunction call
TriangulationTriaActiveIterator<dim, TriaCellAccessor<dim> >triangulation.begin_active()
DoFHandlerTriaActiveIterator<dim, DoFCellAccessor<dim> >dof_handler.begin_active()
MGDoFHandlerTriaActiveIterator<dim, MGDoFCellAccessor<dim> >mg_dof_handler.begin_active()
-As mentioned above, iterators in deal.II can be considered as iterating over -all the cells (or faces, lines, etc) that constitute a mesh. This suggests to -view a triangulation as a collection of cells and other objects that are held -together by a certain data structure that links all these objects, in the same -was as a linked list is the data structure that connects objects in a linear -fashion. -Triangulations in deal.II can indeed be considered in this way. In particular, -they use the computational notion of a forrest of regular trees to store their -data. This can be understood as follows: Consider the cells of the coarse mesh -as roots; then, if one of these coarse mesh cells is refined, it will have -2dim children, which in turn can, but do not have to have -2dim children of their own, and so on. This means, that each cell -of the coarse mesh can be considered the root of a binary tree (in qd), a -quadtree (in 2d), or an octree (in 3d). The collection of these trees -emanating from the cells of the coarse mesh then constitutes the forrest that -completely describes the triangulation, including all of its active and -inactive cells. In particular, the active cells are those terminal nodes in -the tree that have no decendants, i.e. cells which are not further -refined. Correspondingly, inactive cells correspond to nodes in the tree with -descendents, i.e. cells that are further refined. + + + + + + + + + + + + + + + + + + + + + + + + +
Containeractive_face_iterator typefunction call
TriangulationTriaActiveIterator<dim, TriaObjectAccessor<dim-1, dim> >triangulation.begin_active_face()
DoFHandlerTriaActiveIterator<dim, DoFObjectAccessor<dim-1, dim> >dof_handler.begin_active_face()
MGDoFHandlerTriaActiveIterator<dim, MGDoFObjectAccessor<dim-1, dim> >mg_dof_handler.begin_active_face()
-A triangulation contains forrests for lines (each of which may have 2 -children), quads (each with possibly four children), and hexes (each with no -or 8 children). Depending on the dimension, these objects are also termed -cells or faces. -Iterators loop over the elements of such forrests. While the usual iterators -loop over all nodes of a forrest, active iterators skip iterate over the -elements in the same order, but skip all non-active entries and therefore only -visit terminal nodes (i.e. active cells, faces, etc). There are many ways to -traverse the elements of a forrest, for example breadth first or depth -first. Depending on the type of data structure used to store the forrest, some -ways are more efficient than others. At present, the way iterators traverse -forrests in deal.II is breadth first. I.e., iterators first visit all the -elements (cells, faces, etc) of the coarse mesh before moving on to all the -elements of the immediate level, i.e. the immediate children of the coarse -mesh objects; after this come the grandchildren of the coarse mesh, and so on. -However, it must be noted that programs should not rely on this particular -order of traversing a tree: this is considered an implementation detail that -can change between versions, even if we consider this an unlikely option at -the present time. */ /** -- 2.39.5