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. The requirements for circulators are presented here. Thereafter a number of adaptors is described that convert between iterators and circulators.

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. The function accepts a range $[c,\; d)$ of circulators and process each element in this range.

template <class Circulator>
void example( Circulator c, Circulator d)
{
    if (c != NULL) { // assures that there is at least one element
        do {
            foo(*c);  // process element
            ++c;
        } while (c != d);
    }
}

Given a circular data structure $S$, this function could be used to process all elements like this: example($S$.begin(),$S$.begin()).

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 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 $[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 your own applications to have this behavior, please refer to the CGAL reference manual.

As we mentioned 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, but 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 a space and time penalty) 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>.