Circulators

Circulators are quite similar to iterators that are described in Chapter . 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. A summary of the requirements for circulators is presented here. Thereafter, a couple of adaptors are described that convert between iterators and circulators. For the complete description of the requirements, support to develop own circulators and the adaptors please refer to the CGAL Reference Manual: Part 3: Support Library.

The specialization on circular data structures gives the reason for the slightly different requirements for circulators than for iterators. A circular data structure has no natural past-the-end value. In consequence, a container supporting circulators will not have an end()-member function, only a begin()-member function. The semantic of a range is different for a circulator $c$: The range $[c,\; c)$ 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 requirements. A comparison $c\; ==$ NULL for a circulator $c$ tests whether the data structure is empty or not. An example function demonstrates a typical use of circulators. It counts the number of elements in the range $[c,\; d)$:

template <class Circulator, class Size>
void count( Circulator c, Circulator d, Size& n) {
    n = 0;
    if ( c != NULL) {
        do {
            ++n;
        } while (++c != d);
    }
}

Given a circular data structure $S$, the expression count($S$.begin(), $S$.begin(), counter) counts all elements in $S$ within the counter.

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 $d$ is called reachable from a circulator $c$ if and only if there is a finite sequence of applications of operator++ to $c$ that makes $c\; ==\; d$. If $c$ and $d$ refer to the same non-empty data structure, then $d$ is reachable from $c$, and $c$ is reachable from $d$. In particular, any circulator $c$ referring to a non-empty data structure will return to itself after a finite sequence of applications of operator++ to $c$.

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 $[c,\; c)$ is a full range; in general, a range $[c,\; d)$ refers to the elements in the data structure starting with the one pointed to by $c$ and up to but not including the one pointed to by $d$. Range $[c,\; d)$ 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 to 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 $[c,\; d)$ of circulators used in an interface for iterators will work as expected as long as $c\; !=\; d$. A range $[c,\; c)$ 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 $[c,\; c)$ would be interpreted correctly. For more information how to program functions with this behavior, please refer to the CGAL Reference Manual.

As we said in the introduction, we are a little bit sloppy in the presentation, in order to make it easier to understand. A class is said to be a circulator if it fulfills a set of requirements. In the following sections we do not present the requirements, but we state properties that are true, if the requirements are fulfilled. The difference is best seen by an example: We write that the return value of the test for equality returns a bool. The requirement is only that the return value is convertible to bool.

• Requirements for Circulators.

Adaptor: Container with Iterators from Circulator

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 drawback) to reestablish this generality.

• Class declaration of CGAL_..._container_from_circulator<C>.

Adaptor: Circulator from Iterator

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.

• Class declaration of CGAL_..._circulator_from_iterator<I,T,Size,Dist>.

Adaptor: Circulator from Container

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.

• Class declaration of CGAL_..._circulator_from_container<C>.