Circulators are quite similar to iterators in the Standard Template Library STL [C++96, MS96, SL95]. Circulators are a generalization of pointers that allow a programmer to work with different circular data structures like a ring list in a uniform manner. Please note that circulators are not part of the STL, but of CGAL.
An introduction to the requirements for circulators is given here.
Thereafter a couple of adaptors are presented that convert between
iterators and circulators. A few useful functions for circulators
follow. Section 
discusses the design
decisions taken and Section presents the
full requirements for circulators which are needed to implement own
circulators. A few base classes and circulator tags (like iterator
tags [SL95]) are provided. An advanced topic is in
Section the support for
algorithms which work for iterators as well as for circulators.
Iterators in the STL were tailored for linear sequences. The
specialization for circular data structures leads to slightly
different requirements which we will call circulators. The main
difference is that a circular data structure has no natural
past-the-end value. In consequence, a container supporting circulators
will not have an end()-member function. The semantic of a
circulator range differs: For a circulator the range denotes the sequence of all elements in the data
structure. For iterators, this range would be empty. A separate test
for an empty sequence has been added to the circulator requirements: A
comparison NULL for a circulator is true for an empty
sequence. The following example demonstrates a typical use of
circulators. It assumes a CGAL polygon given in the variable P
of type Polygon_2 (provided with a typedef) and writes
all edges to cout. Note that the polygon provides iterators over
edges as well as the circulator. The benefit of circulators appears in
more graph-like data structures as discussed in
Section . Examples are triangulations and
polyhedrons.
if ( P.edges_circulator() != NULL) {
Polygon_2::Edge_const_circulator c = P.edges_circulator();
do {
cout << *c;
} while ( ++c != P.edges_circulator());
}
As for iterators, circulators come in different flavors. There are forward, bidirectional and random access circulators. They are either mutable or constant. The past-the-end value is not applicable for circulators.
Reachability: A circulator is called reachable from a circulator if and only if there is a finite sequence of applications of operator++ to that makes . If and refer to the same non-empty data structure, then is reachable from , and is reachable from . In particular, any circulator referring to a non-empty data structure will return to itself after a finite sequence of applications of operator++ to .
Range: Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of circulators that designate the beginning and end of the computation. A range is a full range; in general, a range refers to the elements in the data structure starting with the one pointed to by and up to but not including the one pointed to by . Range is valid if and only if both refer to the same data structure. The result of the application of the algorithms in the library to invalid ranges is undefined.
Warning: Please note that the definition of a range is different from that of iterators. An interface of a data structure must declare whether it works with iterators, circulators, or both. STL algorithms always specify only iterators in their interfaces. A range of circulators used in an interface for iterators will work as expected as long as . A range will be interpreted as the empty range like for iterators, which is different than the full range that it should denote for circulators.
Algorithms could be written to support both, iterators and
circulators, in a single interface. Here, the range would be interpreted correctly. For more information how
to program functions with this behavior, see
Chapter .
Algorithms working on iterators could not be applied to circulators in
full generality, only to subranges (see the warning in
Section ). The following adaptors convert
circulators to iterators (with the unavoidable space and time penalty) to
reestablish this generality.
To obtain circulators, one could use a container class like those in the Standard Template Library (STL) or a pair of begin()-, end()-iterators and one of the following adaptors. Adaptors for iterator pairs are described here, adaptors for container classes are described in the next section.
To obtain circulators, one could use a container class like those in the Standard Template Library (STL) or a pair of begin()-, end()-iterators and one of the provided adaptors here. Adaptors for iterator pairs are described in the previous section, adaptors for container classes are described here.
The size of a circulator is the size of the data structure it refers to. It is zero for a circulator with singular value. The size can be computed in linear time for forward and bidirectional circulators, and in constant time for random access circulators using the minimal circulator. The function CGAL_circulator_size(c) returns the circulator size. It uses the c.min_circulator() function if is a random access circulator.
|
| ||
|
|
| |
The distance of a circulator to a circulator is the number of elements in the range . It is defined to be zero for a singular circulator and it returns the size of the data structure when applied to a range of the form .
|
| ||
|
|
| |
The following function returns the distance between either two iterators or two circulators. The return type is ptrdiff_t for compilers not supporting iterator traits yet.
|
| ||
|
| ||
|
| ||
For circular data structures it is not straightforward to provide a
begin(),end()-pair of STL iterators. There is no natural
past-the-end situation. Additional bookkeeping must be implemented to
provide an end()-iterator or an arbitrary sentinel must be
introduced, which is undesirable since it would break the symmetry of
otherwise symmetric data structure. Examples in CGAL are
triangulations, planar maps and polyhedrons where a natural circular
ordering of incident vertices, edges, and faces around a vertex - or
around a facet - exists. To overcome the performance and space
drawback of the STL iterator requirements, we have introduced circulators, and to obtain STL compliance, we provide adaptors
between circulators and iterators, see
Section up to
Section . Hence, circulators are
designed as the natural light-weight objects to traverse ring-like
data structures, but algorithms working on iterators can also be
applied using the adaptors.
The following example shows a template function that accepts a range of circulators and process each element in this range:
template <class Circulator>
void example( Circulator c, Circulator d) {
if (c != NULL) { /* at least one element in the range */
do {
foo(*c); /* process element */
} while (++c != d);
}
}
If the ring-like data structure is known to contain at least one element, the test if(c != NULL) can be omitted. This test for an empty data structure has been chosen such that it looks similar to a typical ring implementation using pointers to structs. However, other requirements for circulators, like the operator++, will force any implementation of circulators to use classes and operator overloading.
A serious design problem arises due to the fact that the STL template algorithms do not check whether their parameters fulfill the requirements of an iterator or not. Since the circulators are quite similar, they can be used in STL algorithms as iterators, but behave different. A range for a circulator with non singular value denotes the whole sequence, but the iterator algorithm will treat it as an empty sequence. We know four solutions to cope with this problem, neither is fully satisfactory.
One possibility is to choose different signatures for circulators than
for iterators. The operator++ or the operator== are the
only choices since they are the member functions involved in the
semantic of ranges. Both are natural choices and desirable for
circulators as well as for iterators. Specific member functions are
harder to learn and to remember. The second possibility is to change
the semantics of circulators to behave correct in algorithms using
iterators, but than they are full-fledged iterators and the idea about
light-weight objects and efficiency for circulators is superfluous.
The third possibility is to protect the algorithms using iterators
against misuse via circulators which is easy to achieve, see the
CGAL_Assert_iterator() function below in
Section . Nonetheless, this checking has
also to be done in the STL library and this is beyond the scope of
CGAL. For implementations within CGAL it is recommended. The
fourth alternative is to document this design problem and state it as
a feature. In fact it is a feature that each range
of two distinct circulators and (a subsequence within a
circular sequence) is a valid iterator range where one can apply STL algorithms to. The risk that one applies an algorithm to the whole
sequence by accident, where the STL algorithms will see an empty
range, is not too likely, since the normal use of iterators from
container classes like sort( A.begin(), A.end()) will fail for
circulators due to the missing member function end(). We have
chosen this (fourth) solution and documented it in the manual where
appropriate. Following Bjarne Stroustrup: Finally, it has been a
guideline in the design of C++ that when all is said and done the
programmer must be trusted. [Str97]
Similar to STL iterators, we distinguish between forward, bidirectional, and random access circulators. Input circulators are a contradiction, since any circulator is supposed to return once to itself. Output circulators are not supported since they would be indistinguishable from output iterators. Most requirements for circulators are the same as those for iterators. We present the changes, please refer to [MS96, chapter 18] or [C++96, SL95] for the iterator requirements.
Past-the-end value: There is no past-the-end value. On the other hand, a circulator can denote an empty data structure, but not with a past-the-end value.
Singular values: In addition to iterators, a circulator can denote an empty data structure. In this case it has a singular value.
Dereferenceable values: A circulator with a non-singular value is always dereferenceable.
Reachability: In contrast to iterators, dereferenceable circulators can reach itself with a finite and non-empty sequence of applications of operator++.
Ranges: In addition, any range of a circulator is a valid range. If the circulator has a singular value, the range denotes the empty range, otherwise the circulator is dereferenceable and the range denotes the whole sequence of elements in the data structure. Remark: When a circulator is used in a place of an iterator, like with an STL algorithm, it will work as supposed to with the only exception that the range denotes always the empty range. This is not a requirement itself, it is a consequence of the requirements stated here and the fact that the STL requirements for iterators do not include a type safety check for the template parameters used in the related STL algorithms.
Types: Since there is no builtin type that can fulfill the requirements for a circulator we can assume that any circulator is implemented as a class and we can use local type declarations to add the useful type information about the value type and others to the circulators. For a circulator class these are C::value_type, C::reference, C::const_reference, and pointer denoting the element type, references, and pointers to them. C::size_type is an unsigned integral type that can hold the size of a sequence. C::difference_type is a signed integral type that can hold the distance between two circulators of the same sequence (either by counting the elements inbetween or by subtracting two random access circulators).
STL compliance: The functions iterator_category(...), value_type(...), and distance_type(...) are required for STL compliance [SL95]. Beyond the STL requirements is the additionally required function CGAL_query_circulator_or_iterator(...) that distinguishes between circulators and iterators.
For each circulator type C we will assume that a and b denote values of type C, r denotes a value of C& (is assignable), and t denotes a value type T. Let D be the distance type.
| C() | a circulator equal to NULL, i.e. a singular value. |
| a == NULL | Returns true if a has a singular value, false otherwise. For simplicity, |
| NULL == a is not provided. Implementation issues might fail in detecting | |
| comparisons to other values that are not equal to NULL. Here, the beha- | |
| vior is undefined, a runtime assertion is recommended. | |
| a != NULL | Returns !(a == NULL). |
| ++r | Like for forward iterators, but a dereferenceable circulator r will always |
| be dereferenceable after ++r (no past-the-end value). Precondition: r has | |
| no singular value. | |
| r++ | Same as for ++r. |
| C::value_type | T. |
| C::reference | T&. |
| C::const_reference | const T&. |
| C::pointer | T*. |
| C::const_pointer | const T*. |
| C::size_type | unsigned integral type. |
| C::distance_type | signed integral type. |
| C::iterator_category | circulator category CGAL_Forward_circulator_tag. |
| CGAL_query_circulator_or_iterator(a) | returns CGAL_Circulator_tag(). |
| iterator_category(a) | returns C::iterator_category(). |
| value_type(a) | returns (T*)(0). |
| distance_type(a) | returns (D*)(0). |
The same requirements as for the forward circulators hold for bidirectional iterators with the following change:
| C::iterator_category | circulator category CGAL_Bidirectional_circulator_tag. |
The same requirements as for the bidirectional circulators hold for random access iterators with the following changes and extensions.
The idea of a random access extends naturally to circulators using equivalence classes modulus the length of the sequence. With this in mind, the additional requirements for random access iterators hold also for random access circulators. The single exception is that the random access iterator requires a total order on the sequence, which a circulator cannot provide. One might define the ordering by splitting the circle at a fixed point, e.g. the start circulator provided from the data structure. This is what the adaptor to iterators will do. Nonetheless, we do not require this for circulators.
The difference of two circulators is not unique as for iterators. A reasonable requirement demands that the result is in a certain range size, size, where size is the size of the data structure, and that whenever a circulator a is fixed that the differences with all other circulators of the sequence form a consistent ordering.
For the adaptor to iterators there has to be a minimal circulator min for which the difference min to all other circulators is non negative.
| C::iterator_category | circulator category CGAL_Random_access_circulator_tag. |
| b - a | a limited range and a consistent ordering for a fixed |
| circulator a as explained in the paragraph above. | |
| a.min_circulator() | returns the minimal circulator from the range . Its |
| value is singular if a has a singular value. | |
As with iterators we distinguish between circulators and const circulators. The expression *a = t is valid for mutable circulators. It is invalid for const circulators.
For a container x of class X that supports circulators c we would like to recommend the following requirements.
| X::Circulator | the type of the mutable circulator. |
| X::Const_circulator | the type of the const circulator. |
| c = x.begin() | the start point of the data structure. It can be a singular value. It is of |
| type X::Circulator for a mutable container or X::Const_circulator for | |
| a const container. There must not be an end() member function. |
If a container will support iterators and circulators, the member
function circulator_begin() is proposed. However, the support
of iterators and circulators simultaneously is not recommended, since
it would lead to fat interfaces. The natural choice should be
supported, the other technique will be available through the adaptors
in Section up to
Section .
This section demonstrates how to distinguish in algorithms between
different categories of circulators and how to distinguish these from
iterators. We use compile time tags for this purpose. They are
described as iterator tags in [SL95]. Additionally, a
couple of base classes simplify the task of writing own circulators
that conform to the mechanism described here which is also part of the
requirements: A circulator c has to have an appropriately
defined iterator_category(c) function and
CGAL_query_circulator_or_iterator(c) function, see also
Section . All adaptors described in this
chapter use these base classes.
#include <CGAL/circulator.h>
To use the tags or base classes it is sufficient to include:
#include <CGAL/circulator_bases.h>
|
| |
|
any circulator.
| |
|
| |
|
any iterator.
| |
|
| |
|
| |
|
| |
|
| |
|
| |
|
| |
To distinguish between circulator categories the iterator_category() function is sufficient. It is overloaded for the above base classes as follows. (The return values are in fact class derived from the iterator_tag types stated here, see the requirements in the previous section. However, to distinguish circulator categories the iterator_tag types are sufficient, see also the example below.)
|
| ||||
|
| ||||
| ||||
|
| ||||
|
| ||||
| ||||
|
| ||||
|
| ||||
| ||||
The following function distinguishes between circulators and iterators (assuming that the iterators do also conform to the iterator tag description in [SL95] or the iterator traits definition as in [C++96, Mye95]).
|
| ||
|
|
| |
| if I is conforming to the iterator requirements. | ||
|
| ||
|
| ||
|
| ||
| if C is conforming to the circulator requirements. | ||
The value_type and distance_type functions represent a mechanism to derive these dependent types of iterators and circulators [SL95]. They are still provided but superfluous with the new concept of iterator traits [C++96, Mye95].
|
| ||
|
|
| T is the value type of circulator c. |
|
| ||
|
|
| |
| Dist is the difference type of circulator c. | ||
The following assertions check during the compilation if their argument is of the kind as stated in the assertions name, i.e. a circulator, an iterator, or of a particular category, applicable for an iterator or a circulator. Note that no input or output circulator exists.
/* circulator_prog3.C */
/* ------------------------------ */
#include <CGAL/basic.h>
#include <assert.h>
#include <list.h>
#include <CGAL/circulator.h>
template <class C> inline
int foo( C c, forward_iterator_tag) {
CGAL_Assert_circulator( c);
CGAL_Assert_forward_category( c);
return 1;
}
template <class C> inline
int foo( C c, random_access_iterator_tag) {
CGAL_Assert_circulator( c);
CGAL_Assert_random_access_category( c);
return 2;
}
template <class I> inline
int foo( I i, CGAL_Iterator_tag) {
CGAL_Assert_iterator( i);
return 3;
}
template <class C> inline
int foo( C c, CGAL_Circulator_tag) {
CGAL_Assert_circulator( c);
return foo( c, iterator_category(c));
}
template <class IC> inline
int foo( IC ic) {
return foo( ic, CGAL_query_circulator_or_iterator( ic));
}
int main() {
typedef CGAL_Forward_circulator_base<int, ptrdiff_t, size_t> F;
typedef CGAL_Random_access_circulator_base<int, ptrdiff_t, size_t> R;
F f = F();
R r = R();
list<int> l;
assert( foo( f) == 1);
assert( foo( r) == 2);
#ifndef __GNUG__
assert( foo( l.begin()) == 3);
#endif
return 0;
}
Since not all current compilers can eliminate the space needed for the compile time tags even when deriving from them, we implement a variant for each base class that contains a protected void* data member called _ptr. Here, the allocated space in the derived classes can be reused. The discriminating functions are overloaded for these extensions. The variant base classes are:
|
| |
|
| |
|
forward circulator.
| |
|
| |
|
| |
|
bidirectional circulator.
| |
|
| |
|
| |
|
random access circulator.
| |
The 1996 release of the STL that comes with the SGI C++ compiler does not derive their iterators from the base classes as described in [SL95]. The CGAL_query_circulator_or_iterator function needs to be overloaded for several iterators in the STL explicitly. For that, we must know the classes involved in advance. We do not like to include all STL header files that might be necessary (i.e. deque.h, hash table.h, list.h, and tree.h). Instead, we assume that these header files are already included and define the additional functions if necessary. This makes this scheme dependent on the order of header file inclusions, but we consider it as reasonable to assume that standard header files are included before CGAL header files.
SGI has released newer STL implementations on their web server http://www.sgi.com/Technology/STL/. These releases do not longer implement iterators as nested classes which allow us to use forward declarations to stay independent from the actual header file inclusions.
The current scheme is prepared for iterator traits [Mye95, C++96] and will simplify considerably when they are available.
The Gnu g++ 2.7.2 compiler has difficulties with the iterator_category(i) function implementation. The workaround for the Gnu library implements the function within the container classes. Since the CGAL_query_circulator_or_iterator(c) function relies on the same principle, it could not be implemented without patching the Gnu library. The problem will be solved with the next Gnu g++ release. The CGAL_Assert_iterator(i) and CGAL_Assert_circulator_or_iterator(ic) wont work either. The involved container are list and tree. The other container should work.
The previous section describes how we can distinguish between circulators and iterators. Now we encapsulate the difference between both in such a way that it is easy to write algorithms that can be parameterized with an interval according to both requirements. The difference we have to consider is whether a loop will be entered the first time or not. For iterators it is the same test as for the rest of the loop, for circulators it is the comparison with NULL. So, we provide a test that accepts a range of either two circulators or two iterators and decides whether the range is empty or not.
#include <CGAL/circulator.h>
Using this function we can write an example() function that accepts a range of iterators or circulators and process each element in this range:
template <class IC>
void example( IC i, IC j) {
// assures that there is at least one element
if (! CGAL_is_empty_range( i, j)) {
do {
foo(*i); // process element
} while (++i != j);
}
}
Again, a protection against misuse with inappropriate template parameters is possible.
|
| ||
|
|
| |
| results in a compile time error when i is neither a circulator nor an iterator. | ||
A macro CGAL_For_all( i, j) simplifies the writing of such simple loops as the one above. i and j can be either iterators or circulators. The macro loops through the range [i, j). It increments i until it reaches j. The implementation looks like:
CGAL_For_all(i,j) :=
for ( bool CGAL__circ_loop_flag = ! CGAL_is_empty_range(i,j);
CGAL__circ_loop_flag;
CGAL__circ_loop_flag = ((++i) != (j))
)
Note that the macro behaves like a for-loop. It can be used with a single statement or with a statement block. For bidirectional iterators or circulators exist a backwards loop macro CGAL_For_all_backwards( i, j) that decrements j until it reaches i.